The Convergence Guarantees of a Non-Convex Approach for Sparse Recovery
The Convergence Guarantees of a Non-Convex Approach for Sparse Recovery
复制标题
稀疏恢复非凸方法的收敛保证
DOI：
10.1109/tsp.2014.2330349
复制
发表时间：
2014-08-01
影响因子：
5.4
通讯作者：
Gu, Yuantao
中科院分区：
文献类型：
--
作者：
Chen, Laming;Gu, Yuantao
在稀疏恢复领域，大量研究表明非凸惩罚可能比凸惩罚带来更好的稀疏性，但到目前为止，相应的非凸算法缺乏从初始解到全局最优的收敛保证。本文旨在为稀疏恢复的非凸方法提供性能保证。具体来说，弱凸性的概念被纳入一类稀疏性诱导惩罚中，以表征非凸性。借鉴投影次梯度法的思想，提出一种求解非凸优化问题的算法。此外，在投影步骤中采用统一的近似投影，使得该算法在计算上易于处理大规模问题。在噪声场景下提供收敛分析。结果表明，如果惩罚的非凸性低于阈值（与初始解和稀疏信号之间的距离成反比），则恢复的解在步长和噪声项上都具有线性恢复误差。实施数值模拟来测试所提出方法的性能并验证理论分析。
In the area of sparse recovery, numerous researches hint that non-convex penalties might induce better sparsity than convex ones, but up until now those corresponding non-convex algorithms lack convergence guarantees from the initial solution to the global optimum. This paper aims to provide performance guarantees of a non-convex approach for sparse recovery. Specifically, the concept of weak convexity is incorporated into a class of sparsity-inducing penalties to characterize the non-convexity. Borrowing the idea of the projected subgradient method, an algorithm is proposed to solve the non-convex optimization problem. In addition, a uniform approximate projection is adopted in the projection step to make this algorithm computationally tractable for large scale problems. The convergence analysis is provided in the noisy scenario. It is shown that if the non-convexity of the penalty is below a threshold (which is in inverse proportion to the distance between the initial solution and the sparse signal), the recovered solution has recovery error linear in both the step size and the noise term. Numerical simulations are implemented to test the performance of the proposed approach and verify the theoretical analysis.