Minimization of transformed penalty: theory, difference of convex function algorithm, and robust application in compressed sensing

• 成果类型: Article
• 署名作者: Zhang, Shuai; Xin, Jack
• 署名单位: University of California System; University of California Irvine
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1236-x
• 发表日期: 2018
• 页码: 307-336
• 关键词: iterative thresholding algorithms; least-squares; l-1/2 regularization; variable selection; l(1) minimization; signal recovery; REPRESENTATION; approximation; Dictionaries

摘要

We study the minimization problem of a non-convex sparsity promoting penalty function, the transformed (TL1), and its application in compressed sensing (CS). The TL1 penalty interpolates and norms through a nonnegative parameter , similar to with , and is known to satisfy unbiasedness, sparsity and Lipschitz continuity properties. We first consider the constrained minimization problem, and discuss the exact recovery of norm minimal solution based on the null space property (NSP). We then prove the stable recovery of norm minimal solution if the sensing matrix A satisfies a restricted isometry property (RIP). We formulated a normalized problem to overcome the lack of scaling property of the TL1 penalty function. For a general sensing matrix A, we show that the support set of a local minimizer corresponds to linearly independent columns of A. Next, we present difference of convex algorithms for TL1 (DCATL1) in computing TL1-regularized constrained and unconstrained problems in CS. The DCATL1 algorithm involves outer and inner loops of iterations, one time matrix inversion, repeated shrinkage operations and matrix-vector multiplications. The inner loop concerns an minimization problem on which we employ the Alternating Direction Method of Multipliers. For the unconstrained problem, we prove convergence of DCATL1 to a stationary point satisfying the first order optimality condition. In numerical experiments, we identify the optimal value , and compare DCATL1 with other CS algorithms on two classes of sensing matrices: Gaussian random matrices and over-sampled discrete cosine transform matrices (DCT). Among existing algorithms, the iterated reweighted least squares method based on norm is the best in sparse recovery for Gaussian matrices, and the DCA algorithm based on minus penalty is the best for over-sampled DCT matrices. We find that for both classes of sensing matrices, the performance of DCATL1 algorithm (initiated with minimization) always ranks near the top (if not the top), and is the most robust choice insensitive to the conditioning of the sensing matrix A. DCATL1 is also competitive in comparison with DCA on other non-convex penalty functions commonly used in statistics with two hyperparameters.