Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control
Open Access
- 1 September 2021
- journal article
- research article
- Published by IOP Publishing in Journal of Statistical Mechanics: Theory and Experiment
- Vol. 2021 (9) , 093401
Abstract
We consider a reconstruction problem of sparse signals from a smaller number of measurements than the dimension formulated as a minimization problem of nonconvex sparse penalties: smoothly clipped absolute deviations and minimax concave penalties. The nonconvexity of these penalties is controlled by nonconvexity parameters, and the ℓ 1 penalty is contained as a limit with respect to these parameters. The analytically-derived reconstruction limit overcomes that of the ℓ 1 limit and is also expected to overcome the algorithmic limit of the Bayes-optimal setting when the nonconvexity parameters have suitable values. However, for small nonconvexity parameters, where the reconstruction of the relatively dense signals is theoretically expected, the algorithm known as approximate message passing (AMP), which is closely related to the analysis, cannot achieve perfect reconstruction leading to a gap from the analysis. Using the theory of state evolution, it is clarified that this gap can be understood on the basis of the shrinkage in the basin of attraction to the perfect reconstruction and also the divergent behavior of AMP in some regions. A part of the gap is mitigated by controlling the shapes of nonconvex penalties to guide the AMP trajectory to the basin of the attraction.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matricesJournal of Statistical Mechanics: Theory and Experiment, 2012
- Nearly unbiased variable selection under minimax concave penaltyThe Annals of Statistics, 2010
- A typical reconstruction limit for compressed sensing based on Lp-norm minimizationJournal of Statistical Mechanics: Theory and Experiment, 2009
- Restricted isometry properties and nonconvex compressive sensingInverse Problems, 2008
- The restricted isometry property and its implications for compressed sensingComptes Rendus Mathématique, 2008
- High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to DimensionDiscrete & Computational Geometry, 2005
- Sparse representations in unions of basesIEEE Transactions on Information Theory, 2003
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle PropertiesJournal of the American Statistical Association, 2001
- Atomic Decomposition by Basis PursuitSIAM Review, 2001
- Stability of the Sherrington-Kirkpatrick solution of a spin glass modelJournal of Physics A: General Physics, 1978