Minimization of Transformed $L_1$ Penalty: Closed Form Representation and Iterative Thresholding Algorithms

c 2017 International Press C OMMUN. M ATH. S CI. Vol. 15, No. 2, pp. 511–537 MINIMIZATION OF TRANSFORMED L 1 PENALTY: CLOSED FORM REPRESENTATION AND ITERATIVE THRESHOLDING ALGORITHMS ∗ SHUAI ZHANG † AND JACK XIN ‡ Abstract. The transformed l 1 penalty (TL1) functions are a one parameter family of bilinear transformations composed with the absolute value function. When acting on vectors, the TL1 penalty interpolates l 0 and l 1 similar to l p norm, where p is in (0,1). In our companion paper, we showed that TL1 is a robust sparsity promoting penalty in compressed sensing (CS) problems for a broad range of incoherent and coherent sensing matrices. Here we develop an explicit ﬁxed point representation for the TL1 regularized minimization problem. The TL1 thresholding functions are in closed form for all parameter values. In contrast, the l p thresholding functions (p is in [0,1]) are in closed form only for p = 0,1,1/2,2/3, known as hard, soft, half, and 2/3 thresholding respectively. The TL1 threshold values diﬀer in subcritical (supercritical) parameter regime where the TL1 threshold functions are continuous (discontinuous) similar to soft-thresholding (half-thresholding) functions. We propose TL1 iterative thresholding algorithms and compare them with hard and half thresholding algorithms in CS test problems. For both incoherent and coherent sensing matrices, a proposed TL1 iterative thresholding algorithm with adaptive subcritical and supercritical thresholds (TL1IT-s1 for short), consistently performs the best in sparse signal recovery with and without measurement noise. Keywords. Transformed l 1 penalty, closed form thresholding functions, iterative thresholding algorithms, compressed sensing, robust recovery. AMS subject classiﬁcations. 94A12, 94A15. 1. Introduction Iterative thresholding (IT) algorithms merit our attention in high dimensional set- tings due to their simplicity, speed, and low computational costs. In compressed sensing (CS) problems [4, 10] under l p sparsity penalty (p ∈ [0,1]), the corresponding thresh- olding functions are in closed form when p = 0, 12 , 23 ,1. The l 1 algorithm is known as soft-thresholding [8, 9], and the l 0 algorithm hard-thresholding [1, 2]. IT algorithms only involve scalar thresholding and matrix multiplication. We note that the linearized Bregman algorithm [21, 22] is similar for solving the constrained l 1 minimization (ba- sis pursuit) problem. Recently, half and 23 -thesholding algorithms have been actively studied [7, 18] as non-convex alternatives to improve on l 1 (convex relaxation) and l 0 algorithms. However, the non-convex l p penalties (p ∈ (0,1)) are non-Lipschitz. There are also some Lipschitz continuous non-convex sparse penalties, including the diﬀerence of l 1 and l 2 norms (DL12) [11, 14, 20], and the transformed l 1 (TL1) [25]. When applied to CS problems, the diﬀerence of convex function algorithms (DCA) of DL12 are found to perform the best for highly coherent sensing matrices. In contrast, the DCAs of TL1 are the most robust (consistently ranked in the top among existing algorithms) for coherent and incoherent sensing matrices alike. In this paper, as companion of [25], we develop robust and eﬀective IT algorithms for TL1 regularized minimization with evaluation on CS test problems. The TL1 penalty is a one parameter family of bilinear transformations composed with the absolute value ∗ Received: September 25, 2015; accepted (in revised form): July 12, 2016. Communicated by Wotao Yin. The work was partially supported by NSF grants DMS-0928427, DMS-1222507 and DMS-1522383. † Department of Mathematics, University of California, Irvine, CA, 92697, USA (szhang3@uci.edu); Phone: (949)-824-5309. Fax: (949)-824-7993. ‡ Department of Mathematics, University of California, Irvine, CA, 92697, USA (jxin@math.uci.edu).