The Convex Geometry of Linear Inverse Problems

By Venkat Chandrasekaran, B. Recht, Pablo A. Parrilo, Alan S. Willsky. 2010

1,386 citations recorded by the source corpus.

In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees of freedom relative to their ambient dimension. This paper provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined inverse problems. The class of simple models considered includes those formed as the sum of a few atoms from some (possibly infinite) elementary atomic set; examples include well-studied cases from many technical fields such as sparse vectors (signal processing, statistics) and low-rank matrices (control, statistics), as well as several others including sums of a few permutation matrices (ranked elections, multiobject tracking), low-rank tensors (computer vision, neuroscience), orthogonal matrices (machine learning), and atomic measures (system identification). The convex programming formulation is based on minimizing the norm induced by the convex hull of the atomic set; this norm is referred to as the atomic norm. The facial structure of the atomic norm ball carries a number of favorable properties that are useful for recovering simple models, and an analysis of the underlying convex geometry provides sharp estimates of the number of generic measurements required for exact and robust recovery of models from partial information. These estimates are based on computing the Gaussian widths of tangent cones to the atomic norm ball. When the atomic set has algebraic structure the resulting optimization problems can be solved or approximated via semidefinite programming. The quality of these approximations affects the number of measurements required for recovery, and this tradeoff is characterized via some examples. Thus this work extends the catalog of simple models (beyond sparse vectors and low-rank matrices) that can be recovered from limited linear information via tractable convex programming.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Certified Adversarial Robustness via Randomized Smoothing (2019, background): “For comparison, ImageNet has dimension d = 224× 224× 3, so the expected norm of a draw from N (0, σ2Id) is √ 2Γ(d+12 )/Γ( d 2 )σ ≈ 97 (Chandrasekaran et al., 2012), which is many times larger than the radii at which g is provably robust at high accuracy.”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “More general atomic decompositions have found uses in a variety of situations, including solving linear inverse problems [48].”
Optimization with Sparsity-Inducing Penalties (2011, background): “Moreover, this norm can also be interpreted as a particular case of the family of atomic norms, which were recently introduced by [35].”
Generalized Dantzig Selector: Application to the k-support norm (2014, background): “For any set Ω ⊆ R, we would measure the size of this set using its Gaussian width [17, 6], which is defined as ω(Ω) = Eg [supz∈Ω〈g, z〉] , where g is a vector of i.”
Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems (2016, neutral): “If we ignore the structure in x and choose f as the 0 or 1 norms, then the mean widths are ωK = O(k log(d/k)) [56] and ωC 2(k log(d/k)) [54] respectively.”
Sparse Methods for Direction-of-Arrival Estimation (2016, methodology): “In fact, initially this has been a major obstacle in applying the atomic norm technique [141,143].”
Sparse Regularization via Convex Analysis (2017, background): “For example, the idea may admit extension to more general convex regularizers such as total variation [48], nuclear norm [10], mixed norms [34], composite regularizers [1], [2], co-sparse regularization [40], and more generally, atomic norms [14], and partly smooth regularizers [61].”
Optimal rates of statistical seriation (2016, neutral): “, [17]) of Θ defined by IE[supθ∈Θ〈θ, z〉], whose connection to the statistical dimension was studied in [1].”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, background): “Alternatively, the logarithm of the determinant is a nonconvex, but smooth, proxy for rank when X is positive semideﬁnite (and can be applied to general matrices by embedding them in a PSD matrix).”
Sparse Representation for 3D Shape Estimation: A Convex Relaxation Approach (2015, background): “Interestingly, the conditions for exact recovery using such a convex program has been theoretically analyzed in [45].”
Collaborative Filtering with Graph Information: Consistency and Scalable Methods (2015, background): “In [2], it is shown that any local minimizer of (5) is a global minimizer of (5) if k is larger than the true rank of the underlying matrix.3 From [25], the alternating minimization procedure is guaranteed to globally converge to a block coordinate-wise minimum4 of (5).”