Foundations and Trends® in Optimization > Vol 3 > Issue 4

Atomic Decomposition via Polar Alignment: The Geometry of Structured Optimization

By Zhenan Fan, University of British Columbia, Canada, zhenanf@cs.ubc.ca | Halyun Jeong, University of British Columbia, Canada, clatar1@gmail.com | Yifan Sun, Stony Brook University, USA, yifan.sun@stonybrook.edu | Michael P. Friedlander, University of British Columbia, Canada, michael.friedlander@ubc.ca

 
Suggested Citation
Zhenan Fan, Halyun Jeong, Yifan Sun and Michael P. Friedlander (2020), "Atomic Decomposition via Polar Alignment: The Geometry of Structured Optimization", Foundations and TrendsĀ® in Optimization: Vol. 3: No. 4, pp 280-366. http://dx.doi.org/10.1561/2400000028

Publication Date: 24 Nov 2020
© 2020 Zhenan Fan, Halyun Jeong, Yifan Sun and Michael P. Friedlander
 
Subjects
Optimization,  Operations research,  Information theory and statistics,  Information theory and computer science,  Pattern recognition and learning,  Modeling and analysis,  Mathematical modelling
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Atomic Decomposition
3. Alignment with Respect to General Convex Sets
4. Alignment with Respect to Atomic Sets
5. Alignment as Optimality
6. Alignment in Optimization Methods
7. Alignment in Convolution of Atomic Sets
8. Conclusions
Acknowledgments
References

Abstract

Structured optimization uses a prescribed set of atoms to assemble a solution that fits a model to data. Polarity, which extends the familiar notion of orthogonality from linear sets to general convex sets, plays a special role in a simple and geometric form of convex duality. This duality correspondence yields a general notion of alignment that leads to an intuitive and complete description of how atoms participate in the final decomposition of the solution. The resulting geometric perspective leads to variations of existing algorithms effective for large-scale problems. We illustrate these ideas with many examples, including applications in matrix completion and morphological component analysis for the separation of mixtures of signals.

DOI:10.1561/2400000028
ISBN: 978-1-68083-742-1
100 pp. $75.00
Buy book (pb)
 
ISBN: 978-1-68083-743-8
100 pp. $140.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Atomic Decomposition
3. Alignment with Respect to General Convex Sets
4. Alignment with Respect to Atomic Sets
5. Alignment as Optimality
6. Alignment in Optimization Methods
7. Alignment in Convolution of Atomic Sets
8. Conclusions
Acknowledgments
References

Atomic Decomposition via Polar Alignment: The Geometry of Structured Optimization

The use of convex optimization in the fields of data science and engineering is becoming ubiquitous. But is has been recognized in the research community for more than a decade that significant efficiencies can be gained by acknowledging the latent structure in the solution itself, coupled with the overarching structure provided by convexity. Structured optimization proceeds along these lines by using a prescribed set of points, called atoms, from which to assemble an optimal solution. In effect, the atoms selected to participate in forming a solution decompose the model into simpler parts, which offers opportunities for algorithmic efficiency in solving the optimization problem. An atomic decomposition provides a description of the most informative features of a solution or a kind of generalized principal component analysis.

In this monograph, the authors describe the rich convex geometry that underlies atomic decomposition and demonstrate its use in practical examples. They expose the basic elements of this theory and its many connections to sparse and structured optimization. The authors have adopted a self-contained treatment and make a few modest assumptions that greatly simplify the derivations to make it accessible researchers who are not specialists in convex analysis.

Atomic Decomposition via Polar Alignment provides an introduction for all researchers and practitioners to a powerful optimization technique with many future applications throughout engineering and computer science.

 
OPT-028