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

Understand

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).