The Convex Geometry of Linear Inverse Problems. Seizes Simplicity of data to solve underdetermined problem. Provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined in-verse problems. Convex optimization, Linear inverse problem

"many interesting signals or models in practice contain few degrees of freedom relative to their ambient dimension". We describe a model (or object) as simple if it can be written as a nonnegative linear combination of a few elements from an atomic set (for instance, a specified set of functions, vectors, matrices,...). As they explain, examples of simple objects are sparse vectors, and low-rank matrices. These have been shown to be recoverable from very incomplete information:

• Robust Uncertainty Principles: Exact Signal Reconstruction From Highly Incomplete Frequency Information
• Exact Matrix Completion via Convex Optimization
• For Most Large Underdetermined Systems of Equations, the Minimal l1-norm Near-Solution Approximates the Sparsest Near-Solution
• Compressed Sensing

Method: Under suitable conditions the convex hull $conv(A)$ defines the unit ball of a norm, which is called the atomic norm induced by the atomic set $A$. We can then minimize the atomic norm subject to measurement constraints, which results in a convex programming heuristic for recovering simple models given linear measurements.

There is a tradeoff between the complexity of the recovery algorithm and the number of measurements required for recovery

Examples

See Linear inverse problem for application to the Matrix completion problem