The DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.
The Convex Geometry of Linear Inverse Problems
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Tensor Decompositions and Applications
Kolda, T. G., & Bader, B. W. (2009) · SIAM Review · doi:10.1137/07070111x · Cited by 10,301
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Robust principal component analysis?
Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011) · Journal of the ACM · doi:10.1145/1970392.1970395 · Cited by 6,921
A Singular Value Thresholding Algorithm for Matrix Completion
Cai, J.-F., Candès, E. J., & Shen, Z. (2010) · SIAM Journal on Optimization · doi:10.1137/080738970 · Cited by 5,809
An iterative thresholding algorithm for linear inverse problems with a sparsity constraint.
Daubechies, I., Defrise, M., & De Mol, C. (2004) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20042 · Cited by 4,958
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
Self-citationGoemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · cited 2×
“These decompositions are useful, for instance, in actually computing the rank-one binary vectors optimized in semidefinite relaxations of combinatorial algorithms [2, 37, 55], or in the computation of tensor decompositions from incomplete data [47].”
BackgroundGuaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
Self-citationUniversal approximation bounds for superpositions of a sigmoidal function
Barron, A. R. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.256500 · Cited by 2,804
Introductory Lectures on Convex Optimization
Nesterov, Y. (2004) · Applied Optimization · doi:10.1007/978-1-4419-8853-9 · Cited by 2,698
Signal Recovery by Proximal Forward-Backward Splitting
Combettes, P. L., & Wajs, V. R. (2005) · Multiscale Modeling & Simulation · doi:10.1137/050626090 · Cited by 2,678
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
Simultaneous analysis of Lasso and Dantzig selector
Bickel, P. J., Ritov, Y., & Tsybakov, A. B. (2009) · The Annals of Statistics · doi:10.1214/08-aos620 · Cited by 2,396
Sparse Reconstruction by Separable Approximation
Wright, S. J., Nowak, R. D., & Figueiredo, M. A. T. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016892 · Cited by 1,854
Bochnak, J., Coste, M., & Roy, M.-F. (1998) · Springer · doi:10.1007/978-3-662-03718-8 · Cited by 1,538
Semidefinite programming relaxations for semialgebraic problems
Parrilo, P. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0387-5 · Cited by 1,527
Self-citationBregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
Yin, W., Osher, S., Goldfarb, D., & Darbon, J. (2008) · SIAM Journal on Imaging Sciences · doi:10.1137/070703983 · Cited by 1,414
An EM algorithm for wavelet-based image restoration
Figueiredo, M. A. T., & Nowak, R. D. (2003) · IEEE Transactions on Image Processing · doi:10.1109/tip.2003.814255 · Cited by 1,219
Ledoux, M., & Talagrand, M. (1991) · doi:10.1007/978-3-642-20212-4 · Cited by 1,160
Fixed point and Bregman iterative methods for matrix rank minimization
Ma, S., Goldfarb, D., & Chen, L. (2011) · Mathematical Programming · doi:10.1007/s10107-009-0306-5 · Cited by 1,048
Deza, M. M., & Laurent, M. (1997) · Algorithms and combinatorics · doi:10.1007/978-3-642-04295-9 · Cited by 1,014
Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
de Silva, V., & Lim, L.-H. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/06066518x · Cited by 927
Polak, E. (1997) · Applied Mathematical Sciences · doi:10.1007/978-1-4612-0663-7 · Cited by 914
Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
Hale, E. T., Yin, W., & Zhang, Y. (2008) · SIAM Journal on Optimization · doi:10.1137/070698920 · Cited by 909
Tensorial extensions of independent component analysis for multisubject FMRI analysis
Beckmann, C. F., & Smith, S. M. (2005) · NeuroImage · doi:10.1016/j.neuroimage.2004.10.043 · Cited by 761
A random polynomial-time algorithm for approximating the volume of convex bodies
Dyer, M., Frieze, A., & Kannan, R. (1991) · Journal of the ACM · doi:10.1145/102782.102783 · Cited by 693
Rank-Sparsity Incoherence for Matrix Decomposition
Chandrasekaran, V., Sanghavi, S., Parrilo, P. A., & Willsky, A. S. (2011) · SIAM Journal on Optimization · doi:10.1137/090761793 · Cited by 686
Self-citationOn the conditions used to prove oracle results for the Lasso
van de Geer, S. A., & Bühlmann, P. (2009) · Electronic Journal of Statistics · doi:10.1214/09-ejs506 · Cited by 684
Barvinok, A. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/054 · Cited by 660
Some remarks on greedy algorithms
DeVore, R., & Temlyakov, V. N. (1996) · Advances in Computational Mathematics · doi:10.1007/bf02124742 · Cited by 646
Sparse nonnegative solution of underdetermined linear equations by linear programming
Donoho, D. L., & Tanner, J. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0502269102 · Cited by 577
Candès, E. J., & Plan, Y. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2111771 · Cited by 569
Jones, L. K. (1992) · The Annals of Statistics · doi:10.1214/aos/1176348546 · Cited by 474
Local Operator Theory, Random Matrices and Banach Spaces
(2001) · Handbook of the Geometry of Banach Spaces · doi:10.1016/s1874-5849(01)80010-3 · Cited by 432
Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation
Haupt, J., Bajwa, W. U., Raz, G., & Nowak, R. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2070191 · Cited by 424
The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
Dudley, R. M. (1967) · Journal of Functional Analysis · doi:10.1016/0022-1236(67)90017-1 · Cited by 423
Orthogonal Tensor Decompositions
Kolda, T. G. (2001) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479800368354 · Cited by 376
High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension
Donoho, D. L. (2006) · Discrete & Computational Geometry · doi:10.1007/s00454-005-1220-0 · Cited by 370
On Milman's inequality and random subspaces which escape through a mesh in ℝ n
Gordon, Y. (1988) · Lecture Notes in Mathematics · doi:10.1007/bfb0081737 · Cited by 282
Approximating the Cut-Norm via Grothendieck's Inequality
Alon, N., & Naor, A. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704441629 · Cited by 222
Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications
Donoho, D. L., & Tanner, J. (2010) · Discrete & Computational Geometry · doi:10.1007/s00454-009-9221-z · Cited by 183
A generalized proximal point algorithm for certain non-convex minimization problems
FUKUSHIMA, M., & MINE, H. (1981) · International Journal of Systems Science · doi:10.1080/00207728108963798 · Cited by 166
Theta Bodies for Polynomial Ideals
Gouveia, J., Parrilo, P. A., & Thomas, R. R. (2010) · SIAM Journal on Optimization · doi:10.1137/090746525 · Cited by 103
Self-citationInferring Rankings Using Constrained Sensing
Jagabathula, S., & Shah, D. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2165827 · Cited by 30
Cited by
High-Dimensional Statistics: A Non-Asymptotic Viewpoint
Wainwright, M. J. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108627771 · Cited by 882
Kernel methods in system identification, machine learning and function estimation: A survey
Pillonetto, G., Dinuzzo, F., Chen, T., De Nicolao, G., & Ljung, L. (2014) · Automatica · doi:10.1016/j.automatica.2014.01.001 · Cited by 741
Atomic Norm Denoising With Applications to Line Spectral Estimation
Bhaskar, B. N., Tang, G., & Recht, B. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2273443 · Cited by 579
Self-citationPhase recovery, MaxCut and complex semidefinite programming
Waldspurger, I., d’Aspremont, A., & Mallat, S. (2015) · Mathematical Programming · doi:10.1007/s10107-013-0738-9 · Cited by 573
An Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439
Metadata
- Authors
- Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S.
- Venue
- Foundations of Computational Mathematics
- Published
- 2012-10-16
- Volume
- 12
- Issue
- 6
- Pages
- 805-849
- ISSN
- 1615-3375 (ISSN-L)
- 1615-3383
- OpenAlex
- W2167077875
- Cited by
- 886
- References
- 47
- FWCI
- 47.34
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.