The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Iterative Reweighted $\ell_1$ and $\ell_2$ Methods for Finding Sparse Solutions
Abstract
A variety of practical methods have recently been introduced for finding maximally sparse representations from overcomplete dictionaries, a central computational task in compressive sensing applications as well as numerous others. Many of the underlying algorithms rely on iterative reweighting schemes that produce more focal estimates as optimization progresses. Two such variants are iterative reweighted l1and l2minimization; however, some properties related to convergence and sparse estimation, as well as possible generalizations, are still not clearly understood or fully exploited. In this paper, we make the distinction betweenseparableandnon-separableiterative reweighting algorithms. The vast majority of existing methods are separable, meaning the weighting of a given coefficient at each iteration is only a function of that individual coefficient from the previous iteration (as opposed to dependency on all coefficients). We examine two such separable reweighting schemes: an l2method from Chartrand and Yin (2008) and an l1approach from Cande's (2008), elaborating on convergence results and explicit connections between them. We then explore an interesting non-separable alternative that can be implemented via either l2or l1reweighting and maintains several desirable properties relevant to sparse recovery despite a highly non-convex underlying cost function. For example, in the context of canonical sparse estimation problems, we prove uniform superiority of this method over the minimum l1solution in that, 1) it can never do worse when implemented with reweighted l1, and 2) for any dictionary and sparsity profile, there will always exist cases where it does better. These results challenge the prevailing reliance on strictly convex (and separable) penalty functions for finding sparse solutions. We then derive a new non-separable variant with similar properties that exhibits further performance improvements in empirical tests. Finally, we address natural extensions to group sparsity problems and non-negative sparse coding.
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
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
Enhancing Sparsity by Reweighted ℓ 1 Minimization
Candès, E. J., Wakin, M. B., & Boyd, S. P. (2008) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-008-9045-x · Cited by 4,863
Linear and nonlinear programming.
(1986) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(86)90092-3 · Cited by 4,805
Bayesian Learning for Neural Networks
Neal, R. M. (1996) · Lecture Notes in Statistics · doi:10.1007/978-1-4612-0745-0 · Cited by 4,276
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
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
(2000) · CrossRef Listing of Deleted DOIs · doi:10.1162/15324430152748236 · Cited by 1,819
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
Iteratively reweighted algorithms for compressive sensing
Chartrand, R., & Yin, W. (2008) · 2008 IEEE International Conference on Acoustics, Speech and Signal Processing · doi:10.1109/icassp.2008.4518498 · Cited by 1,248
Nonlinear Programming: A Unified Approach.
Beale, E. M. L., & Zangwill, W. (1970) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2343701 · Cited by 1,057
Nonlinear Programming: A Unified Approach
Peterson, D. W., & Zangwill, W. I. (1972) · Econometrica · doi:10.2307/1909424 · Cited by 1,005
Sparse representations in unions of bases
Gribonval, R., & Nielsen, M. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.820031 · Cited by 960
Linear and nonlinear programming
Sydsæter, K., Strøm, A., & Berck, P. (1999) · Economists’ Mathematical Manual · doi:10.1007/978-3-662-03995-3_15 · Cited by 864
Algorithms for simultaneous sparse approximation. Part II: Convex relaxation
Tropp, J. A. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.031 · Cited by 691
Fazel, M., Hindi, H., & Boyd, S. P. (2004) · Proceedings of the 2003 American Control Conference, 2003. · doi:10.1109/acc.2003.1243393 · Cited by 574
On Sparse Representations in Arbitrary Redundant Bases
Fuchs, J.-J. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.828141 · Cited by 563
Majorization–Minimization Algorithms for Wavelet-Based Image Restoration
Figueiredo, M. A. T., Bioucas-Dias, J. M., & Nowak, R. D. (2007) · IEEE Transactions on Image Processing · doi:10.1109/tip.2007.909318 · Cited by 548
Adaptive sparseness for supervised learning
Figueiredo, M. A. T. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1227989 · Cited by 536
An affine scaling methodology for best basis selection
Rao, B. D., & Kreutz-Delgado, K. (1999) · IEEE Transactions on Signal Processing · doi:10.1109/78.738251 · Cited by 526
ALGORITHMS FOR SIMULTANEOUS SPARSE APPROXIMATIONPreprint
Tropp, J. A. (2006) · Cited by 350
Subset selection in noise based on diversity measure minimization
Rao, B. D., Engan, K., Cotter, S. F., Palmer, J., & Kreutz-Delgado, K. (2003) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2002.808076 · Cited by 324
A new view of automatic relevance determination
Wipf, D., & Nagarajan, S. S. (2008) · Cited by 310
Self-citationLatent Variable Bayesian Models for Promoting Sparsity
Wipf, D. P., Rao, B. D., & Nagarajan, S. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2162174 · Cited by 305
Self-citationOn the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
Bruckstein, A. M., Elad, M., & Zibulevsky, M. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.929920 · Cited by 285
Wipf, D. P., Owen, J. P., Attias, H. T., Sekihara, K., & Nagarajan, S. S. (2010) · NeuroImage · doi:10.1016/j.neuroimage.2009.06.083 · Cited by 214
Self-citationVariational EM algorithms for non-Gaussian latent variable models
Palmer, J. A., Kreutz-Delgado, K., Wipf, D. R., & Rao, B. D. (2006) · Cited by 212
Self-citationRecovery of Jointly Sparse Signals from Few Random Projections
Wakin, M. B., Duarte, M. F., Sarvotham, S., Baron, D., & Baraniuk, R. G. (2005) · neural information processing systems · Cited by 76
Optimal sparse representations in general overcomplete bases
Malioutov, D., Çetin, M., & Willsky, A. S. (2004) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2004.1326377 · Cited by 71
Selecting Landmark Points for Sparse Manifold Learning
Silva, J. S., Marques, J. S., & Lemos, J. M. (2005) · Cited by 51
Basis selection in the presence of noise
Rao, B. D., & Kreutz-Delgado, K. (2002) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.1998.750962 · Cited by 20
Cited by
Image Super-Resolution Via Sparse Representation
Yang, J., Wright, J., Huang, T. S., & Ma, Y. (2010) · IEEE Transactions on Image Processing · doi:10.1109/tip.2010.2050625 · Cited by 5,217
Sparse Signal Recovery With Temporally Correlated Source Vectors Using Sparse Bayesian Learning
Zhang, Z., & Rao, B. D. (2011) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2011.2159773 · Cited by 868
Extension of SBL Algorithms for the Recovery of Block Sparse Signals With Intra-Block Correlation
Zhang, Z., & Rao, B. D. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2241055 · Cited by 558
Channel Estimation for Reconfigurable Intelligent Surface Aided Multi-User mmWave MIMO Systems
Chen, J., Liang, Y.-C., Cheng, H. V., & Yu, W. (2023) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2023.3246264 · Cited by 410
Robust Joint Graph Sparse Coding for Unsupervised Spectral Feature Selection
Zhu, X., Li, X., Zhang, S., Ju, C., & Wu, X. (2017) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2016.2521602 · Cited by 339
Metadata
- Authors
- Wipf, D., & Nagarajan, S.
- Venue
- IEEE Journal of Selected Topics in Signal Processing
- Published
- 2010-04
- Volume
- 4
- Issue
- 2
- Pages
- 317-329
- ISSN
- 1932-4553 (ISSN-L)
- 1941-0484
- OpenAlex
- W2161765392
- Cited by
- 448
- References
- 32
- FWCI
- 22.74
- 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.