Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms
Open accessThe DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Abstract
This paper treats the problem of minimizing a general continuously differentiable function subject to sparsity constraints. We present and analyze several different optimality criteria which are based on the notions of stationarity and coordinatewise optimality. These conditions are then used to derive three numerical algorithms aimed at finding points satisfying the resulting optimality criteria: the iterative hard thresholding method and the greedy and partial sparse-simplex methods. The first algorithm is essentially a gradient projection method, while the remaining two algorithms are of a coordinate descent type. The theoretical convergence of these techniques and their relations to the derived optimality conditions are studied. The algorithms and results are illustrated by several numerical examples.
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
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,591
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
De-noising by soft-thresholding
Donoho, D. L. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.382009 · Cited by 9,619
Matching pursuits with time-frequency dictionaries
Mallat, S. G., & Zhang, Z. (1993) · IEEE Transactions on Signal Processing · doi:10.1109/78.258082 · Cited by 9,112
Emergence of simple-cell receptive field properties by learning a sparse code for natural images
Olshausen, B. A., & Field, D. J. (1996) · Nature · doi:10.1038/381607a0 · Cited by 5,694
Phase retrieval algorithms: a comparison
Fienup, J. R. (1982) · Applied Optics · doi:10.1364/ao.21.002758 · Cited by 5,596
A practical algorithm for the determination of phase from image and diffraction plane pictures
Gerchberg, R. W. (1972) · Optik · Cited by 4,519
Greed is Good: Algorithmic Results for Sparse Approximation
Tropp, J. A. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834793 · Cited by 3,635
Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
Donoho, D. L., & Elad, M. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0437847100 · Cited by 2,898
A Wavelet Tour of Signal Processing : The Sparse Way
Mallat, S., & Gabriel Peyré, A. (2008) · Cited by 2,734
Introduction to the non-asymptotic analysis of random matrices
Vershynin, R. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.006 · Cited by 2,150
Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm
Gorodnitsky, I. F., & Rao, B. D. (1997) · IEEE Transactions on Signal Processing · doi:10.1109/78.558475 · Cited by 1,834
Iterative Thresholding for Sparse Approximations
Blumensath, T., & Davies, M. E. (2008) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-008-9035-z · Cited by 1,248
Adaptive greedy approximations
Davis, G., Mallat, S., & Avellaneda, M. (1997) · Constructive Approximation · doi:10.1007/bf02678430 · Cited by 1,166
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
DeVore, R. A. (1998) · Acta Numerica · doi:10.1017/s0962492900002816 · Cited by 877
Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance
Blumensath, T., & Davies, M. E. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042411 · Cited by 485
Introduction to compressed sensing
Davenport, M. A., Duarte, M. F., Eldar, Y. C., & Kutyniok, G. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.002 · Cited by 484
Self-citationGradient-based algorithms with applications to signal-recovery problems
Beck, A., & Teboulle, M. (2009) · Convex Optimization in Signal Processing and Communications · doi:10.1017/cbo9780511804458.003 · Cited by 333
Self-citationSparse Optimization with Least-Squares Constraints
van den Berg, E., & Friedlander, M. P. (2011) · SIAM Journal on Optimization · doi:10.1137/100785028 · Cited by 226
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-citationGreedy Sparsity-Constrained OptimizationPreprint
Bahmani, S., Raj, B., & Boufounos, P. T. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1203.5483 · Cited by 162
Cited by
Phase Retrieval with Application to Optical Imaging: A contemporary overview
Shechtman, Y., Eldar, Y. C., Cohen, O., Chapman, H. N., Miao, J., & Segev, M. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2352673 · Cited by 1,131
Self-citationHandbook of Mathematical Methods in Imaging
(2011) · Springer eBooks · doi:10.1007/978-0-387-92920-0 · Cited by 334
Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
Oymak, S., Jalali, A., Fazel, M., Eldar, Y. C., & Hassibi, B. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2401574 · Cited by 252
Self-citation
Metadata
- Authors
- Beck, A., & Eldar, Y. C.
- Venue
- SIAM Journal on Optimization
- Published
- 2013-01
- Volume
- 23
- Issue
- 3
- Pages
- 1480-1509
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2083346837
- Cited by
- 331
- References
- 25
- FWCI
- 28.44
- 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.