A Caltech Library Service

The Convex Geometry of Linear Inverse Problems

Chandrasekaran, Venkat and Recht, Benjamin and Parrilo, Pablo A. and Willsky, Alan S. (2012) The Convex Geometry of Linear Inverse Problems. Foundations of Computational Mathematics, 12 (6). pp. 805-849. ISSN 1615-3375. doi:10.1007/s10208-012-9135-7.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Parrilo, Pablo A.0000-0003-1132-8477
Additional Information:© 2012 SFoCM. Received: 02 December 2010; Revised: 25 February 2012; Accepted: 03 July 2012; First Online: 16 October 2012. This work was supported in part by AFOSR grant FA9550-08-1-0180, in part by a MURI through ARO grant W911NF-06-1-0076, in part by a MURI through AFOSR grant FA9550-06-1-0303, in part by NSF FRG 0757207, in part through ONR award N00014-11-1-0723, and NSF award CCF-1139953. We gratefully acknowledge Holger Rauhut for several suggestions on how to improve the presentation in Sect. 3, and Amin Jalali for pointing out an error in a previous draft. We thank Santosh Vempala, Joel Tropp, Bill Helton, Martin Jaggi, and Jonathan Kelner for helpful discussions. Finally, we acknowledge the suggestions of the associate editor Emmanuel Candès as well as the comments and pointers to references made by the reviewers, all of which improved our paper.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-08-1-0180
Army Research Office (ARO)W911NF-06-1-0076
Air Force Office of Scientific Research (AFOSR)FA9550-06-1-0303
Office of Naval Research (ONR)N00014-11-1-0723
Subject Keywords:Convex optimization; Semidefinite programming; Atomic norms; Real algebraic geometry; Gaussian width; Symmetry
Issue or Number:6
Classification Code:Mathematics Subject Classification: 52A41; 90C25; 90C22; 60D05; 41A45
Record Number:CaltechAUTHORS:20121004-152325296
Persistent URL:
Official Citation:Chandrasekaran, V., Recht, B., Parrilo, P.A. et al. Found Comput Math (2012) 12: 805. doi:10.1007/s10208-012-9135-7
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34687
Deposited By: Tony Diaz
Deposited On:04 Oct 2012 22:43
Last Modified:09 Nov 2021 23:10

Repository Staff Only: item control page