PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Shuai Zhang, Jack Xin

arXiv:1411.5735v4cs.ITmath.IT

TL;DR

Compressed sensing seeks sparse recovery from limited measurements, but non-convex penalties have differing performance across sensing-matrix regimes. This paper analyzes TL1 and develops difference-of-convex algorithms; experiments report robust performance across matrices with varying coherence.

  • Problem

    Non-convex penalties have different recovery strengths near RIP and in highly coherent settings, motivating a penalty that performs consistently across both regimes.

    Source: §1 · p. 2

  • Method

    The paper analyzes TL1 recovery under generalized null space and RIP conditions and develops difference-of-convex algorithms for constrained and unconstrained TL1 optimization.

    Source: §1 · p. 3, §2.1 · pp. 5, 7, §3.4 · p. 14

  • Results

    DCATL1 was most robust across varying-coherence matrices in both models, on par with reweighted l1/2 for incoherent Gaussian matrices and DCA l1−l2 for highly coherent DCT matrices.

    Source: §6 · p. 21

  • Takeaways & Limitations

    Robust recovery is valuable when sensing hardware cannot be modified or upgraded; the paper gives super-resolution from low-frequency measurements as an example.

    Source: §4.3.2 · p. 19

    The RIP condition in the stable-recovery analysis is more stringent for smaller a, reflecting TL1’s lack of scaling property and the analysis’s sub-optimal treatment.

    Source: §2.1 · p. 8

Abstract

from arXiv · show

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.

1. Introduction

Compressed sensing seeks sparse signals from far fewer linear measurements than the ambient dimension, but l0 minimization is computationally hard and nonconvex alternatives have coherence-dependent tradeoffs. This paper studies TL1 and difference-of-convex algorithms, with theory on exact and stable recovery and experiments reporting robust performance across sensing matrices.

1. Introduction

  • Compressed sensing aims to recover a sparse signal from far fewer linear measurements than its ambient dimension, while direct l0 minimization is NP-hard.The introduction also identifies constrained and regularized unconstrained l0 formulations as direct approaches.Source: §1 · pp. 1–2
  • The paper targets a non-convex penalty that performs consistently across sensing matrices, since existing alternatives have different strengths in RIP and highly coherent regimes.The introduction notes that l1/2 can outperform l1 near RIP but may fare worse far from RIP, while l1−l2 performs well in highly coherent settings.Source: §1 · p. 2
  • TL1 is a one-parameter family of Lipschitz-continuous penalties with unbiasedness and sparsity-promoting properties.The introduction contrasts these properties with the bias toward large peaks associated with lp penalties.Source: §1 · p. 2
  • DCATL1 applies a difference-of-convex algorithm to TL1 and is presented as robust to the conditioning of the sensing matrix.The paper notes that verifying conditions such as RIP or the null space property for a specific matrix is NP-hard.Source: §1 · p. 2
  • The paper outlines exact recovery analysis using a generalized null space property, stable recovery analysis using RIP, and DC algorithms and comparisons across Gaussian and over-sampled DCT matrices.It also reports comparisons with DCA using other non-convex penalties.Source: §1 · p. 3

2. Transformed l1 (TL1) and its regularization models

TL1 varies with parameter a between l0-like and l1-like behavior, but lacks absolute scalability. The section establishes recovery conditions for constrained TL1 minimization and structural properties of its local minimizers.

2. Transformed l1 (TL1) and its regularization models

  • As a varies, TL1 interpolates between l0-like and l1-like behavior, while its penalty lacks absolute scalability.For large a, its level lines resemble l1; for small a, they tend toward the axis.Source: §2 · pp. 3, 5

2.1. Exact and Stable Sparse Recovery for Constrained Model

  • For separable, concave, symmetric penalties, gNSP is necessary and sufficient for exact recovery and is no more restrictive than NSP; SCAD and capped l1 offer no exact-recovery gain over l1.For TL1 and other concave penalties, the set of matrices satisfying gNSP can be larger than the set satisfying NSP.Source: §2.1 · pp. 5–7
  • A constructed example shows TL1 can recover the sparsest solution exactly when l1 recovery fails, and concave penalties recover exactly for Gaussian matrices with i.i.d. entries with overwhelming probability.The example’s null-space vector satisfies gNSP for TL1 although NSP fails; the Gaussian conclusion is stated for matrices satisfying the stated conditions.Source: §2.1 · pp. 6–7
  • After normalizing the constraint because TL1 lacks scaling, the paper proves exact and stable recovery under an RIP condition, but that condition is suboptimal and understates TL1’s numerical advantage.The RIP condition becomes the cited Gaussian-matrix condition as a approaches infinity and is more stringent for smaller a.Source: §2.1 · pp. 7–8

2.2. Sparsity of Local Minimizer

  • Every local minimizer has linearly independent active columns, so its sparsity is at most rank(A); the paper also states that each model has finitely many local minimizers.The active-column result is stated for both constrained and unconstrained TL1 models and does not require NSP.Source: §2.2 · p. 9

3. DC Algorithm for Transformed l1 Penalty

The paper casts TL1 minimization as a difference-of-convex problem and develops DCA schemes for constrained and unconstrained compressed-sensing models. The unconstrained method uses ADMM for its inner subproblem and has a stationary-point convergence guarantee; the constrained scheme has finite-convergence properties when its inner problem is solved exactly.

3.1. DC Form of TL1

  • The TL1 penalty is expressed as a difference of two convex functions, with a continuously differentiable second term.Its derivative is described using the subdifferential of the l1 norm.Source: §3.1 · p. 10

3.2. Algorithm for Unconstrained Model — DCATL1

  • Each unconstrained DCA iteration solves a strongly convex l1-regularized subproblem, using ADMM with an auxiliary variable and three alternating updates.The first two updates have closed-form solutions, and the third updates the Lagrange multiplier.Source: §3.2 · p. 11

3.3. Convergence Theory for Unconstrained DCATL1

  • DCATL1’s objective values decrease and converge, and under a condition on λ its iterates are bounded with every subsequential limit satisfying first-order optimality.The paper identifies such a limit as a stationary point of the unconstrained model.Source: §3.3 · p. 12

3.4. Algorithm for Constrained Model

  • For the constrained TL1 model, the DCA sequence has finite subsequential limit points if its inner subproblem is solved exactly.The paper also states that a similar convergence theorem can be proved for this polyhedral DC program.Source: §3.4 · p. 14

4. Numerical Results

The experiments compare DCATL1 with other sparse-recovery algorithms on Gaussian and over-sampled DCT sensing matrices. DCATL1 performs robustly across coherence levels, and the tests select a = 1 for subsequent experiments.

4. Numerical Results

  • The experiments compare unconstrained and constrained solvers on Gaussian and over-sampled DCT random sensing matrices.Source: §4 · p. 15
  • The tests used no prior knowledge of true sparsity and initialized algorithms at zero; random DCATL1 starts often became trapped at local minima, especially for ill-conditioned matrices.Source: §4 · p. 15

4.1. Choice of Parameter: ‘a’

  • Among tested values, a = 1 gave the best DCATL1 success rate and was used in subsequent tests.The comparison tested a values 0.1, 0.3, 1, 2, and 10 over 100 trials.Source: §4.1 · pp. 15–16, Figure 4.1 · p. 16

4.2.1. Gaussian matrix

  • For every tested Gaussian coherence level, DCATL1 and reweighted l1/2 performed almost equally and substantially better than the other two algorithms, while CEL0 had the lowest success rate.Source: §4.2.1 · pp. 16–17, Figure 4.2 · p. 17

4.2.2. Over-sampled DCT

  • For over-sampled DCT recovery, spikes need at least 2RL separation empirically; above the minimum separation, sparsity relative to M matters more for success.The Rayleigh length RL equals factor F for these matrices.Source: §4.2.2 · pp. 17–18
  • For sensing matrices of size 100 × 1500 as F ranges from 2 to 20, DCATL1 remains robust and near the top, sometimes best, with stable, high performance even at F = 20.Source: §4.2.2 · p. 18, §4.3.2 · p. 19

5. Comparison of DCA on Different Non-convex Penalties

The section compares DCA using TL1 with DCA using PiE, MCP, and SCAD. TL1 achieves nearly MCP-level success rates across the experiments while requiring only one hyperparameter.

5. Comparison of DCA on Different Non-convex Penalties

  • The comparison applies DCA-ADMM to unconstrained problems and subproblems, selecting penalty parameters using 64 × 256 Gaussian random matrices.Source: §5 · p. 19
  • Across the experiments, DCA-TL1 achieved almost the same success rates as DCA-MCP; SCAD lagged in incoherent settings but performed well for highly coherent DCT matrices at F = 20.Source: §5 · pp. 20–21
  • DCA-TL1 has one hyperparameter, whereas MCP and SCAD have two, trading a smaller tuning burden for fewer parameters to optimize.Source: §5 · p. 21

6. Concluding Remarks

The paper develops TL1 recovery theory and DC algorithms for constrained and unconstrained compressed sensing. Experiments find DCATL1 robust across sensing-matrix coherence and competitive with other methods.

6. Concluding Remarks

  • The work establishes exact and stable TL1 recovery results using NSP and RIP, and presents two DC algorithms with convergence theory.The study covers constrained and unconstrained models with random sensing matrices spanning a broad range of coherence.Source: §6 · p. 21
  • Across varying matrix coherence, DCATL1 is the most robust method for both constrained and unconstrained models, while remaining competitive with the best methods on Gaussian and oversampled DCT matrices.It is also competitive with DCA using other non-convex penalties, including PiE, SCAD, and MCP.Source: §6 · p. 21
  • The authors identify image processing and machine learning as planned application areas for future TL1 algorithms.Source: §6 · p. 22

Appendix A. Proof of Exact TL1 Sparse Recovery (Theorem 2.1).

The proof establishes uniqueness of the constrained TL1 solution by showing it equals the l0-minimal solution. It adapts prior proof arguments using properties of the TL1 penalty.

Appendix A. Proof of Exact TL1 Sparse Recovery (Theorem 2.1).

  • The proof follows arguments in and, using special properties of ρa.Source: Appendix A · p. 22
  • It sets e=β−β0 and partitions off-support coordinates by decreasing |e| into blocks of R elements, except possibly the final block.Source: Appendix A · pp. 22–23
  • For i outside T, the proof uses ρa(|βi|)=a+|βi| and the monotonicity of ρa on nonnegative inputs.Source: Appendix A · p. 23
  • The proof concludes that βC=β0C and that βC is the unique solution to the constrained problem.Source: Appendix A · p. 24

Appendix B. Proof of Stable TL1 Sparse Recovery (Theorem 2.2).

The proof establishes a chain connecting constrained TL1 solutions to the l0-minimal solution. It follows the exact-recovery proof strategy and uses an observation-noise assumption and RIP-based bounds.

Appendix B. Proof of Stable TL1 Sparse Recovery (Theorem 2.2).

  • The proof links βC as an optimal solution of constrained problem (2.14) to optimality for (2.12), then to β0C as an optimal solution of the l0 problem (2.11).Source: Appendix B · p. 24
  • Following Theorem 2.2's proof, the argument invokes the assumed bound on observation noise and feasibility of βC for problem (2.14).Source: Appendix B · p. 24
  • An ensuing bound uses a positive constant D depending only on δR and δR+|T|, with an inequality justified by the RIP definition.Source: Appendix B · p. 25
Loading 1411.5735v4…