3 years ago

Minimization of Transformed $L_1$ Penalty: Theory, Difference of Convex Function Algorithm, and Robust Application in Compressed Sensing.

Shuai Zhang, Jack Xin

We study the minimization problem of a non-convex sparsity promoting penalty function, the transformed $l_1$ (TL1), and its application in compressed sensing (CS). The TL1 penalty interpolates $l_0$ and $l_1$ norms through a nonnegative parameter $a \in (0,+\infty)$, similar to $l_p$ with $p \in (0,1]$, and is known to satisfy unbiasedness, sparsity and Lipschitz continuity properties. We first consider the constrained minimization problem and discuss the exact recovery of $l_0$ norm minimal solution based on the null space property (NSP). We then prove the stable recovery of $l_0$ norm minimal solution if the sensing matrix $A$ satisfies a restricted isometry property (RIP). Next, we present difference of convex algorithms for TL1 (DCATL1) in computing TL1-regularized constrained and unconstrained problems in CS. The inner loop concerns an $l_1$ minimization problem on which we employ the Alternating Direction Method of Multipliers (ADMM). 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 $a=1$, and compare DCATL1 with other CS algorithms on two classes of sensing matrices: Gaussian random matrices and over-sampled discrete cosine transform matrices (DCT). We find that for both classes of sensing matrices, the performance of DCATL1 algorithm (initiated with $l_1$ 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.

Publisher URL: http://arxiv.org/abs/1411.5735

DOI: arXiv:1411.5735v4

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.