Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis

Abstract

We analyse a linear regression problem with nonconvex regularization called smoothly clipped absolute deviation (SCAD) under an overcomplete Gaussian basis for Gaussian random data. We propose an approximate message passing (AMP) algorithm considering nonconvex regularization, namely SCAD-AMP, and analytically show that the stability condition corresponds to the de Almeida--Thouless condition in spin glass literature. Through asymptotic analysis, we show the correspondence between the density evolution of SCAD-AMP and the replica symmetric solution. Numerical experiments confirm that for a sufficiently large system size, SCAD-AMP achieves the optimal performance predicted by the replica method. Through replica analysis, a phase transition between replica symmetric (RS) and replica symmetry breaking (RSB) region is found in the parameter space of SCAD. The appearance of the RS region for a nonconvex penalty is a significant advantage that indicates the region of smooth landscape of the optimization problem. Furthermore, we analytically show that the statistical representation performance of the SCAD penalty is better than that of L1-based methods, and the minimum representation error under RS assumption is obtained at the edge of the RS/RSB phase. The correspondence between the convergence of the existing coordinate descent algorithm and RS/RSB transition is also indicated.

References in corpus (8)

• Nearly unbiased variable selection under minimax concave penalty
• On the "degrees of freedom" of the lasso
• Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• The Mutual Information in Random Linear Estimation
• Sparse approximation based on a random overcomplete basis
• Evaluation of Generalized Degrees of Freedom for Sparse Estimation by Replica Method

Cited by in corpus (5)

• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Prediction Errors for Penalized Regressions based on Generalized Approximate Message Passing
• Cross validation in sparse linear regression with piecewise continuous nonconvex penalties and its acceleration
• Estimator of Prediction Error Based on Approximate Message Passing for Penalized Linear Regression
• Phase transition in binary compressed sensing based on $L_1$-norm minimization