The DOI matches its Crossref record; 55 of the 55 references it cites were found in a registry or an index.
Recovering Sparse Signals With a Certain Family of Nonconvex Penalties and DC Programming
Abstract
This paper considers the problem of recovering a sparse signal representation according to a signal dictionary. This problem could be formalized as a penalized least-squares problem in which sparsity is usually induced by a lscr1-norm penalty on the coefficients. Such an approach known as the Lasso or Basis Pursuit Denoising has been shown to perform reasonably well in some situations. However, it was also proved that nonconvex penalties like the pseudo lscrq-norm with q < 1 or smoothly clipped absolute deviation (SCAD) penalty are able to recover sparsity in a more efficient way than the Lasso. Several algorithms have been proposed for solving the resulting nonconvex least-squares problem. This paper proposes a generic algorithm to address such a sparsity recovery problem for some class of nonconvex penalties. Our main contribution is that the proposed methodology is based on an iterative algorithm which solves at each iteration a convex weighted Lasso problem. It relies on the family of nonconvex penalties which can be decomposed as a difference of convex functions (DC). This allows us to apply DC programming which is a generic and principled way for solving nonsmooth and nonconvex optimization problem. We also show that several algorithms in the literature dealing with nonconvex penalties are particular instances of our algorithm. Experimental results demonstrate the effectiveness of the proposed generic framework compared to existing algorithms, including iterative reweighted least-squares methods.
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
Advances in Neural Information Processing Systems 19
(2007) · The MIT Press eBooks · doi:10.52202/085713 · Cited by 15,539
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004) · The Annals of Statistics · doi:10.1214/009053604000000067 · Cited by 9,357
Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
Fan, J., & Li, R. (2001) · Journal of the American Statistical Association · doi:10.1198/016214501753382273 · Cited by 8,900
The adaptive lasso and its oracle properties
Zou, H. (2006) · Journal of the American Statistical Association · doi:10.1198/016214506000000735 · Cited by 7,470
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
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (2001) · SIAM Review · doi:10.1137/s003614450037906x · Cited by 5,085
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
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
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
High dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · Cited by 2,539
High-dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · The Annals of Statistics · doi:10.1214/009053606000000281 · Cited by 2,521 · cited 1×
“Furthermore, some theoretical arguments support the Lasso and state that under certain conditions variable selection with the Lasso can be consistent [49], [31], [44].”
A Statistical View of Some Chemometrics Regression Tools
Frank, L. E., & Friedman, J. H. (1993) · Technometrics · doi:10.1080/00401706.1993.10485033 · Cited by 2,213
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
Sparsity and incoherence in compressive sampling
Candès, E., & Romberg, J. (2007) · Inverse Problems · doi:10.1088/0266-5611/23/3/008 · Cited by 2,075
Uncertainty principles and ideal atomic decomposition
Donoho, D. L., & Huo, X. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.959265 · Cited by 1,949
Pathwise coordinate optimization
Friedman, J., Hastie, T., Höfling, H., & Tibshirani, R. (2007) · The Annals of Applied Statistics · doi:10.1214/07-aoas131 · Cited by 1,895
(2000) · CrossRef Listing of Deleted DOIs · doi:10.1162/15324430152748236 · Cited by 1,819
The Dantzig selector: Statistical estimation when p is much larger than n
Candes, E., & Tao, T. (2007) · The Annals of Statistics · doi:10.1214/009053606000001523 · Cited by 1,747
Just relax: convex programming methods for identifying sparse signals in noise
Tropp, J. A. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.864420 · Cited by 1,407
Exact Reconstruction of Sparse Signals via Nonconvex Minimization
Chartrand, R. (2007) · IEEE Signal Processing Letters · doi:10.1109/lsp.2007.898300 · Cited by 1,277
Asymptotics for lasso-type estimators
Fu, W., & Knight, K. (2000) · The Annals of Statistics · doi:10.1214/aos/1015957397 · Cited by 1,276
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
Wainwright, M. J. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2016018 · Cited by 1,198
Yuille, A. L., & Rangarajan, A. (2003) · Neural Computation · doi:10.1162/08997660360581958 · Cited by 1,151
The Tradeoffs of Large-Scale Learning
Bottou, L., & Bousquet, O. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0015 · Cited by 1,128
Penalized Regressions: The Bridge versus the Lasso
Fu, W. J. (1998) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.1998.10474784 · Cited by 1,092
On Model Selection Consistency of Lasso
ZhaoPeng, & Yubin, Y. (2006) · Journal of Machine Learning Research · doi:10.5555/1248547.1248637 · Cited by 996
Extensions of compressed sensing
Tsaig, Y., & Donoho, D. L. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.029 · Cited by 947
One-step sparse estimates in nonconcave penalized likelihood modelsPreprint
Zou, H., & Li, R. (2008) · Cited by 919
A new approach to variable selection in least squares problems
Osborne, M. (2000) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/20.3.389 · Cited by 859
Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0<q⩽1
Foucart, S., & Lai, M.-J. (2009) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2008.09.001 · Cited by 715
Osborne, M. R., Presnell, B., & Turlach, B. A. (2000) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2000.10474883 · Cited by 696
Use of the zero norm with linear models and kernel methods
Weston, J., Elisseeff, A., Schölkopf, B., & Tipping, M. (2003) · MPG.PuRe (Max Planck Society) · doi:10.5555/944919.944982 · Cited by 688
One-step sparse estimates in nonconcave penalized likelihood models
Zou, H., & Li, R. (2008) · The Annals of Statistics · doi:10.1214/009053607000000802 · Cited by 683
Horst, R., & Thoai, N. V. (1999) · Journal of Optimization Theory and Applications · doi:10.1023/a:1021765131316 · Cited by 672
Restricted isometry properties and nonconvex compressive sensing
Chartrand, R., & Staneva, V. (2008) · Inverse Problems · doi:10.1088/0266-5611/24/3/035020 · Cited by 597
A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
Dinh, T. P., & Thi, H. A. L. (1998) · SIAM Journal on Optimization · doi:10.1137/s1052623494274313 · Cited by 569
Regularization of Wavelet Approximations
Antoniadis, A., & Fan, J. (2001) · Journal of the American Statistical Association · doi:10.1198/016214501753208942 · Cited by 498
Asymptotic properties of bridge estimators in sparse high-dimensional regression models
Huang, J., Horowitz, J. L., & Ma, S. (2008) · The Annals of Statistics · doi:10.1214/009053607000000875 · Cited by 482
A simple and efficient algorithm for gene selection using sparse logistic regression
Shevade, S. K., & Keerthi, S. S. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg308 · Cited by 401
Simultaneous Variable Selection
Turlach, B. A., Venables, W. N., & Wright, S. J. (2005) · Technometrics · doi:10.1198/004017005000000139 · Cited by 386
Local Strong Homogeneity of a Regularized Estimator
Nikolova, M. (2000) · SIAM Journal on Applied Mathematics · doi:10.1137/s0036139997327794 · Cited by 291
Breakdown of equivalence between the minimalℓ1-norm solution and the sparsest solution
Tsaig, Y., & Donoho, D. L. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.028 · Cited by 241
Some sharp performance bounds for least squares regression with L1 regularizationPreprint
Zhang, T. (2009) · Cited by 209
Highly sparse representations from dictionaries are unique and independent of the sparseness measure
Gribonval, R., & Nielsen, M. (2007) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2006.09.003 · Cited by 185
Stable sparse approximations via nonconvex optimization
Saab, R., Chartrand, R., & Yilmaz, O. (2008) · 2008 IEEE International Conference on Acoustics, Speech and Signal Processing · doi:10.1109/icassp.2008.4518502 · Cited by 180
On the design of maximally sparse beamforming arrays
Leahy, R. M., & Jeffs, B. D. (1991) · IEEE Transactions on Antennas and Propagation · doi:10.1109/8.97353 · Cited by 164
Honest variable selection in linear and logistic regression models via ℓ1 and ℓ1+ℓ2 penalization
Bunea, F. (2008) · Electronic Journal of Statistics · doi:10.1214/08-ejs287 · Cited by 156
Honest variable selection in linear and logistic regression models via ℓ1 and ℓ1 + ℓ2 penalizationPreprint
Bunea, F. (2008) · Cited by 136
Multicategory ψ-Learning and Support Vector Machine: Computational Tools
Liu, Y., Shen, X., & Doss, H. (2005) · Journal of Computational and Graphical Statistics · doi:10.1198/106186005x37238 · Cited by 111
Discussion: One-step sparse estimates in nonconcave penalized likelihood models
Bühlmann, P., & Meier, L. (2008) · The Annals of Statistics · doi:10.1214/07-aos0316a · Cited by 64
Algorithms for Sparse Linear Classifiers in the Massive Data Setting
Balakrishnan, S., Madigan, D., & Bartlett, P. (2008) · doi:10.7916/d8z0368x · Cited by 54
Surrogate maximization/minimization algorithms and extensions
Zhang, Z., Kwok, J. T.-Y., & Yeung, D. (2007) · Machine Learning · doi:10.1007/s10994-007-5022-x · Cited by 40
A continuous approach for the concave cost supply problem via DC programming and DCA
Thi, H. A. L., & Dinh, T. P. (2007) · Discrete Applied Mathematics · doi:10.1016/j.dam.2007.03.024 · Cited by 27
Cited by
Optimization with Sparsity-Inducing Penalties
Bach, F. (2011) · now publishers, Inc. eBooks · doi:10.1561/9781601985118 · Cited by 608
Sparse Regularization via Convex Analysis
Selesnick, I. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2711501 · Cited by 429
A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding
Zuo, W., Meng, D., Zhang, L., Feng, X., & Zhang, D. (2013) · 2013 IEEE International Conference on Computer Vision · doi:10.1109/iccv.2013.34 · Cited by 396
DC programming and DCA: thirty years of developments
Le Thi, H. A., & Pham Dinh, T. (2018) · Mathematical Programming · doi:10.1007/s10107-018-1235-y · Cited by 348
Sparse Modeling for Image and Vision Processing
Mairal, J. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781680830095 · Cited by 322
Metadata
- Authors
- Gasso, G., Rakotomamonjy, A., & Canu, S.
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2009-12
- Volume
- 57
- Issue
- 12
- Pages
- 4686-4698
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W2103215959
- Cited by
- 304
- References
- 55
- FWCI
- 9.44
- 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.