Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
复制标题
DOI：
10.1088/1742-5468/aab051
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
A. Sakata;Y. Xu
中科院分区：
文献类型：
--
作者：
A. Sakata;Y. Xu
我们分析了一个线性回归问题与非凸正则化称为光滑剪切绝对偏差（SCAD）下的高斯随机数据的过完备高斯基。我们提出了一个考虑非凸正则化的近似消息传递（AMP）算法，即SCAD-AMP，并解析地证明了该算法的稳定性条件与自旋玻璃文献中的de Almeida-numerless条件相对应.通过渐近分析，我们发现了SCAD-AMP的密度演化与副本对称（RS）解之间的对应关系。数值实验证实，对于一个足够大的系统大小，SCAD-AMP达到最佳的性能预测的副本方法。通过复型分析，在SCAD的参数空间中发现了复型对称区和复型对称破缺区之间的相变。非凸罚函数的RS区域的出现是一个显著的优点，它表明了优化问题的光滑区域。此外，我们分析表明，SCAD惩罚的统计表示性能优于基于RST 1的方法，并且在RS/RSB相位的边缘处获得RS假设下的最小表示误差。文中还指出了现有坐标下降算法的收敛性与RS/RSB变换之间的对应关系。
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 (RS) 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 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 ℓ1-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.