Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control

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.