The DOI matches its Crossref record; 63 of the 63 references it cites were found in a registry or an index.
Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
Open accessAbstract
Recovering structured models (e.g., sparse or group-sparse vectors, low-rank matrices) given a few linear observations have been well-studied recently. In various applications in signal processing and machine learning, the model of interest is structured in several ways, for example, a matrix that is simultaneously sparse and low rank. Often norms that promote the individual structures are known, and allow for recovery using an order-wise optimal number of measurements (e.g., 11 norm for sparsity, nuclear norm for matrix rank). Hence, it is reasonable to minimize a combination of such norms. We show that, surprisingly, using multiobjective optimization with these norms can do no better, orderwise, than exploiting only one of the structures, thus revealing a fundamental limitation in sample complexity. This result suggests that to fully exploit the multiple structures, we need an entirely new convex relaxation. Further, specializing our results to the case of sparse and low-rank matrices, we show that a nonconvex formulation recovers the model from very few measurements (on the order of the degrees of freedom), whereas the convex problem combining the 11 and nuclear norms requires many more measurements, illustrating a gap between the performance of the convex and nonconvex recovery problems. Our framework applies to arbitrary structure-inducing norms as well as to a wide range of measurement ensembles. This allows us to give sample complexity bounds for problems such as sparse phase retrieval and low-rank tensor completion.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Donoho, D. L. (2004) · Cited by 16,703
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Sturm, J. F. (1999) · Optimization Methods and Software · doi:10.1080/10556789908805766 · Cited by 7,377
Model Selection and Estimation in Regression with Grouped Variables
Yuan, M., & Lin, Y. (2006) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2005.00532.x · Cited by 7,261
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
Stable signal recovery from incomplete and inaccurate measurements
Candès, E. J., Romberg, J. K., & Tao, T. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20124 · Cited by 7,036
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
Phase retrieval algorithms: a comparison
Fienup, J. R. (1982) · Applied Optics · doi:10.1364/ao.21.002758 · Cited by 5,596
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
A practical algorithm for the determination of phase from image and diffraction plane pictures
Gerchberg, R. W. (1972) · Optik · Cited by 4,519
Rockafellar, R. T., & Wets, R. J. B. (1998) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-642-02431-3 · Cited by 4,086
Some Mathematical Notes on Three-Mode Factor Analysis
Tucker, L. R. (1966) · Psychometrika · doi:10.1007/bf02289464 · Cited by 3,492
Guaranteed 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-citationSparse Principal Component Analysis
Zou, H., Hastie, T., & Tibshirani, R. (2006) · Journal of Computational and Graphical Statistics · doi:10.1198/106186006x113430 · Cited by 3,152
Sparsity and Smoothness Via the Fused Lasso
Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., & Knight, K. (2005) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2005.00490.x · Cited by 2,724
Introduction to the non-asymptotic analysis of random matrices
Vershynin, R. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.006 · Cited by 2,150
Convex Analysis and Optimization
Bertsekas, D. P., Nedić, A., & Ozdaglar, A. (2003) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 2,148
Tensor Completion for Estimating Missing Values in Visual Data
Liu, J., Musialski, P., Wonka, P., & Ye, J. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.39 · Cited by 2,063
Compressed sensing : theory and applications
Eldar, Y. C., & Gitta Kutyniok, B. (2012) · Cited by 2,027
Self-citationCompressed Sensing: Theory and Applications
(2012) · Cambridge University Press eBooks · doi:10.1017/cbo9780511794308 · Cited by 1,660
PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
Candès, E. J., Strohmer, T., & Voroninski, V. (2013) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21432 · Cited by 1,197
Robust Recovery of Signals From a Structured Union of Subspaces
Eldar, Y. C., & Mishali, M. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2030471 · Cited by 1,044
Self-citationThe Convex Geometry of Linear Inverse Problems
Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S. (2010) · Cited by 921
The Convex Geometry of Linear Inverse Problems
Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S. (2012) · Foundations of Computational Mathematics · doi:10.1007/s10208-012-9135-7 · Cited by 886
Tensor completion and low-n-rank tensor recovery via convex optimization
Gandy, S., Recht, B., & Yamada, I. (2011) · Inverse Problems · doi:10.1088/0266-5611/27/2/025010 · Cited by 738
Phase retrieval by iterated projections
Elser, V. (2003) · Journal of the Optical Society of America A · doi:10.1364/josaa.20.000040 · Cited by 737
Phase retrieval in crystallography and optics
Millane, R. P. (1990) · Journal of the Optical Society of America A · doi:10.1364/josaa.7.000394 · Cited by 720
Compressed Sensing: List of contributors
Eldar, Y. C., & Kutyniok, G. (2012) · Cited by 600
Self-citationA Probabilistic and RIPless Theory of Compressed Sensing
Candes, E. J., & Plan, Y. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2161794 · Cited by 598
A literature survey of low‐rank tensor approximation techniques
Grasedyck, L., Kressner, D., & Tobler, C. (2013) · GAMM-Mitteilungen · doi:10.1002/gamm.201310004 · Cited by 577
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
Phase Retrieval via Matrix Completion
Candès, E. J., Eldar, Y. C., Strohmer, T., & Voroninski, V. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/110848074 · Cited by 565
Self-citationLimit of the Smallest Eigenvalue of a Large Dimensional Sample Covariance Matrix
Bai, Z. D., & Yin, Y. Q. (1993) · The Annals of Probability · doi:10.1214/aop/1176989118 · Cited by 519
Phase Retrieval via Matrix Completion
Candès, E. J., Eldar, Y. C., Strohmer, T., & Voroninski, V. (2015) · SIAM Review · doi:10.1137/151005099 · Cited by 481
Self-citationGeneralized power method for sparse principal component analysis
Journée, M., Nesterov, Y. E., Richtárik, P., & Sepulchre, R. J. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0811.4724 · Cited by 473
Living on the edge: phase transitions in convex programs with random data
Amelunxen, D., Lotz, M., McCoy, M. B., & Tropp, J. A. (2014) · Information and Inference · doi:10.1093/imaiai/iau005 · Cited by 413
Tensor-Based Formulation and Nuclear Norm Regularization for Multienergy Computed Tomography
Semerci, O., Hao, N., Kilmer, M. E., & Miller, E. L. (2014) · IEEE Transactions on Image Processing · doi:10.1109/tip.2014.2305840 · Cited by 389
Latent variable graphical model selection via convex optimization
Chandrasekaran, V., Parrilo, P. A., & Willsky, A. S. (2012) · The Annals of Statistics · doi:10.1214/11-aos949 · Cited by 377
Characterization of the subdifferential of some matrix norms
Watson, G. A. (1992) · Linear Algebra and its Applications · doi:10.1016/0024-3795(92)90407-2 · Cited by 364
Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms
Beck, A., & Eldar, Y. C. (2013) · SIAM Journal on Optimization · doi:10.1137/120869778 · Cited by 331
Self-citationSolving Quadratic Equations via PhaseLift When There Are About as Many Equations as Unknowns
Candès, E. J., & Li, X. (2014) · Foundations of Computational Mathematics · doi:10.1007/s10208-013-9162-z · Cited by 292
A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers
Negahban, S. N., Ravikumar, P., Wainwright, M. J., & Yu, B. (2012) · Statistical Science · doi:10.1214/12-sts400 · Cited by 287
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
Stable Image Reconstruction Using Total Variation Minimization
Needell, D., & Ward, R. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/120868281 · Cited by 259
Optimal Solutions for Sparse Principal Component Analysis
d’Aspremont, A., Bach, F., & Ghaoui, L. E. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0707.0705 · Cited by 250
Sparse Signal Recovery from Quadratic Measurements via Convex Programming
Li, X., & Voroninski, V. (2013) · SIAM Journal on Mathematical Analysis · doi:10.1137/120893707 · Cited by 217
Sparsity-based single-shot subwavelength coherent diffractive imaging
Szameit, A., Shechtman, Y., Osherovich, E., Bullkich, E., Sidorenko, P., Dana, H., Steiner, S., Kley, E. B., Gazit, S., Cohen-Hyams, T., et al. (2012) · Nature Materials · doi:10.1038/nmat3289 · Cited by 213
Self-citationOn the conditioning of random subdictionaries
Tropp, J. A. (2008) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2007.09.001 · Cited by 212
Phase Retrieval: Stability and Recovery GuaranteesPreprint
(n.d.) · Cited by 207
Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
Mu, C., Huang, B., Wright, J. N., & Goldfarb, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.5870 · Cited by 203
Generalized Power Method for Sparse Principal Component Analysis
JournéeMichel, NesterovYurii, RichtárikPeter, & SepulchreRodolphe (2010) · Journal of Machine Learning Research · doi:10.5555/1756006.1756021 · Cited by 200
C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework
Sprechmann, P., Ramirez, I., Sapiro, G., & Eldar, Y. C. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2157912 · Cited by 184
Self-citationLatent variable graphical model selection via convex optimization
Chandrasekaran, V., Parrilo, P. A., & Willsky, A. S. (2010) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2010.5707106 · Cited by 167
Hyperspectral image compressed sensing via low-rank and joint-sparse matrix recovery
Golbabaee, M., & Vandergheynst, P. (2012) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2012.6288484 · Cited by 159
Compressive Phase Retrieval From Squared Output Measurements Via Semidefinite Programming
Ohlsson, H., Yang, A. Y., Dong, R., & Sastry, S. (2012) · IFAC Proceedings Volumes · doi:10.3182/20120711-3-be-2027.00415 · Cited by 137
Phase Retrieval with Polarization
Alexeev, B., Bandeira, A. S., Fickus, M. C., & Mixon, D. G. (2014) · SIAM Journal on Imaging Sciences · doi:10.1137/12089939x · Cited by 135
Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
Needell, D. M., & Ward, R. (2013) · IEEE Transactions on Image Processing · doi:10.1109/tip.2013.2264681 · Cited by 121
The squared-error of generalized LASSO: A precise analysis
Oymak, S., Thrampoulidis, C., & Hassibi, B. (2013) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2013.6736635 · Cited by 113
Self-citationNear-optimal Compressed Sensing Guarantees for Total Variation Minimization
Needell, D., & Ward, R. (2013) · Scholarship - Claremont (Claremont Colleges) · Cited by 111
Tight convex relaxations for sparse matrix factorizationPreprint
Richard, É., Obozinski, G., & Vert, J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.5158 · Cited by 35
Cited by
Phase Retrieval Using Alternating Minimization
Netrapalli, P., Jain, P., & Sanghavi, S. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2448516 · Cited by 535
Phase retrieval from coded diffraction patterns
Candès, E. J., Li, X., & Soltanolkotabi, M. (2015) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2014.09.004 · Cited by 387
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
Metadata
- Authors
- Oymak, S., Jalali, A., Fazel, M., Eldar, Y. C., & Hassibi, B.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2015-05
- Volume
- 61
- Issue
- 5
- Pages
- 2886-2908
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2110355775
- Cited by
- 252
- References
- 63
- FWCI
- 34.43
- 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.