The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
Abstract
The minimum lscr1-norm solution to an underdetermined system of linear equationsy=Axis often, remarkably, also the sparsest solution to that system. This sparsity-seeking property is of interest in signal processing and information transmission. However, general-purpose optimizers are much too slow for lscr1minimization in many large-scale applications.In this paper, the Homotopy method, originally proposed by Osborne et al. and Efron et al., is applied to the underdetermined lscr1-minimization problem min parxpar1subject toy=Ax. Homotopy is shown to run much more rapidly than general-purpose LP solvers when sufficient sparsity is present. Indeed, the method often has the followingk-step solution property: if the underlying solution has onlyknonzeros, the Homotopy method reaches that solution in onlykiterative steps. Thisk-step solution property is demonstrated for several ensembles of matrices, including incoherent matrices, uniform spherical matrices, and partial orthogonal matrices. These results imply that Homotopy may be used to rapidly decode error-correcting codes in a stylized communication system with a computational budget constraint. The approach also sheds light on the evident parallelism in results on lscr1minimization and orthogonal matching pursuit (OMP), and aids in explaining the inherent relations between Homotopy, least angle regression (LARS), OMP, and polytope faces pursuit.
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
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Self-citationDonoho, D. L. (2004) · Cited by 16,703
Self-citationCandes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
Tropp, J. A., & Gilbert, A. C. (2007) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.909108 · Cited by 9,653
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004) · The Annals of Statistics · doi:10.1214/009053604000000067 · Cited by 9,357
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
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Self-citation
Cited by
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Robust Face Recognition via Sparse Representation
Wright, J., Yang, A. Y., Ganesh, A., Sastry, S. S., & Ma, Y. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.79 · Cited by 9,388
Figueiredo, M. A. T., Nowak, R. D., & Wright, S. J. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910281 · Cited by 3,524
Subspace Pursuit for Compressive Sensing Signal Reconstruction
Dai, W., & Milenkovic, O. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2016006 · Cited by 2,388
An Interior-Point Method for Large-Scale -Regularized Least Squares
Kim, S.-J., Koh, K., Lustig, M., Boyd, S., & Gorinevsky, D. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910971 · Cited by 2,083
Probing the Pareto Frontier for Basis Pursuit Solutions
van den Berg, E., & Friedlander, M. P. (2009) · SIAM Journal on Scientific Computing · doi:10.1137/080714488 · Cited by 1,939
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
Sparse Representation for Computer Vision and Pattern Recognition
Wright, J., Ma, Y., Mairal, J., Sapiro, G., Huang, T. S., & Yan, S. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2044470 · Cited by 1,847
ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression
Luo, J.-H., Wu, J., & Lin, W. (2017) · 2017 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.541 · Cited by 1,832
Iteratively reweighted least squares minimization for sparse recovery
Daubechies, I., DeVore, R., Fornasier, M., & Güntürk, C. S. (2010) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20303 · Cited by 1,295
A Survey of Sparse Representation: Algorithms and Applications
Zhang, Z., Xu, Y., Yang, J., Li, X., & Zhang, D. (2015) · IEEE Access · doi:10.1109/access.2015.2430359 · Cited by 1,092
Visual Place Recognition: A Survey
Lowry, S., Sünderhauf, N., Newman, P., Leonard, J. J., Cox, D., Corke, P., & Milford, M. J. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2015.2496823 · Cited by 1,079
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
Computational Methods for Sparse Solution of Linear Inverse Problems
Tropp, J. A., & Wright, S. J. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2044010 · Cited by 1,046
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
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
Becker, S., Bobin, J., & Candès, E. J. (2011) · SIAM Journal on Imaging Sciences · doi:10.1137/090756855 · Cited by 848
Sparsity preserving projections with applications to face recognition
Qiao, L., Chen, S., & Tan, X. (2010) · Pattern Recognition · doi:10.1016/j.patcog.2009.05.005 · Cited by 807
Comparing Measures of Sparsity
Hurley, N., & Rickard, S. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2027527 · Cited by 757
A review of unsupervised feature selection methods
Solorio-Fernández, S., Carrasco-Ochoa, J. A., & Martínez-Trinidad, J. F. (2020) · Artificial Intelligence Review · doi:10.1007/s10462-019-09682-y · Cited by 648
Templates for convex cone problems with applications to sparse signal recovery
Becker, S. R., Candès, E. J., & Grant, M. C. (2011) · Mathematical Programming Computation · doi:10.1007/s12532-011-0029-5 · Cited by 608
Extended SRC: Undersampled Face Recognition via Intraclass Variant Dictionary
Deng, W., Hu, J., & Guo, J. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.30 · Cited by 557
Zhang, Q., Liu, Y., Blum, R. S., Han, J., & Tao, D. (2018) · Information Fusion · doi:10.1016/j.inffus.2017.05.006 · Cited by 499
L1-L2 Optimization in Signal and Image Processing
Zibulevsky, M., & Elad, M. (2010) · IEEE Signal Processing Magazine · doi:10.1109/msp.2010.936023 · Cited by 426
Fast ℓ1-minimization algorithms and an application in robust face recognition: A review
Yang, A. Y., Sastry, S. S., Ganesh, A., & Ma, Y. (2010) · 2010 IEEE International Conference on Image Processing · doi:10.1109/icip.2010.5651522 · Cited by 414
Half-Quadratic-Based Iterative Minimization for Robust Sparse Representation
He, R., Zheng, W.-S., Tan, T., & Sun, Z. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.102 · Cited by 342
Fast $\ell_{1}$-Minimization Algorithms for Robust Face Recognition
Yang, A. Y., Zhou, Z., Balasubramanian, A. G., Sastry, S. S., & Ma, Y. (2013) · IEEE Transactions on Image Processing · doi:10.1109/tip.2013.2262292 · Cited by 341
Multiscale Change Point Inference
Frick, K., Munk, A., & Sieling, H. (2014) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/rssb.12047 · Cited by 320
Morphological Component Analysis: An Adaptive Thresholding Strategy
Bobin, J., Starck, J.-L., Fadili, J. M., Moudden, Y., & Donoho, D. L. (2007) · IEEE Transactions on Image Processing · doi:10.1109/tip.2007.907073 · Cited by 314
Self-citationPartial Face Recognition: Alignment-Free Approach
Liao, S., Jain, A. K., & Li, S. Z. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.191 · Cited by 313
Hyperspectral Anomaly Detection: A survey
Su, H., Wu, Z., Zhang, H., & Du, Q. (2022) · IEEE Geoscience and Remote Sensing Magazine · doi:10.1109/mgrs.2021.3105440 · Cited by 310
Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm
Lu, C., Tang, J., Yan, S., & Lin, Z. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2511584 · Cited by 307
Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing
Maleki, A., & Donoho, D. L. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2009.2039176 · Cited by 289
Self-citationHyperspectral Anomaly Detection by the Use of Background Joint Sparse Representation
Li, J., Zhang, H., Zhang, L., & Ma, L. (2015) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2015.2437073 · Cited by 289
A Review of Sparse Recovery Algorithms
Crespo Marques, E., Maciel, N., Naviner, L., Cai, H., & Yang, J. (2019) · IEEE Access · doi:10.1109/access.2018.2886471 · Cited by 268
Compressed Sensing in Astronomy
Bobin, J., Starck, J.-L., & Ottensamer, R. (2008) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2008.2005337 · Cited by 268
Recent Advances of Large-Scale Linear Classification
Yuan, G.-X., Ho, C.-H., & Lin, C.-J. (2012) · Proceedings of the IEEE · doi:10.1109/jproc.2012.2188013 · Cited by 266
Taubock, G., Hlawatsch, F., Eiwen, D., & Rauhut, H. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042410 · Cited by 260
Gao, Y., Ma, J., & Yuille, A. L. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2675341 · Cited by 254
Sparse Signal Reconstruction via Iterative Support Detection
Wang, Y., & Yin, W. (2010) · SIAM Journal on Imaging Sciences · doi:10.1137/090772447 · Cited by 253
Metadata
- Authors
- Donoho, D. L., & Tsaig, Y.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2008-11
- Volume
- 54
- Issue
- 11
- Pages
- 4789-4812
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2098012923
- Cited by
- 829
- References
- 42
- FWCI
- 53.91
- Type
- journal article
- Language
- en
- Open access
- closed
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.