PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast L1-L2 minimization via a proximal operator

Yifei Lou, Ming Yan

arXiv:1609.09530v4math.OCcs.ITmath.NA

TL;DR

Compressive sensing needs sparse recovery from few measurements, yet L1 can perform poorly for highly coherent matrices and L1-L2 is computationally expensive. This paper derives an analytical proximal operator for L1-αL2 and incorporates it into FBS and ADMM, which are shown to be much more efficient than DCA while retaining convergence under stated conditions.

  • Problem

    Sparse recovery is difficult because L1 may perform poorly for highly coherent sensing matrices, while L1-L2 alternatives are computationally expensive.

  • Method

    The paper derives an analytical proximal operator for L1-αL2 and uses it within forward-backward splitting and alternating direction method of multipliers.

  • Results

    FBS and ADMM with the proximal operator are shown numerically to be much more efficient than the DCA approach.

  • Takeaways & Limitations

    The proximal mapping makes fast L1 solvers applicable to L1-αL2 minimization, with convergence analyses for both algorithms.

  • Takeaways & Limitations

    FBS and ADMM may converge to stationary points that are not local minimizers, and DCA gives better recovery results than ADMM for coherent matrices.

Abstract

from arXiv · show

This paper aims to develop new and fast algorithms for recovering a sparse vector from a small number of measurements, which is a fundamental problem in the field of compressive sensing (CS). Currently, CS favors incoherent systems, in which any two measurements are as little correlated as possible. In reality, however, many problems are coherent, and conventional methods such as $L_1$ minimization do not work well. Recently, the difference of the $L_1$ and $L_2$ norms, denoted as $L_1$-$L_2$, is shown to have superior performance over the classic $L_1$ method, but it is computationally expensive. We derive an analytical solution for the proximal operator of the $L_1$-$L_2$ metric, and it makes some fast $L_1$ solvers such as forward-backward splitting (FBS) and alternating direction method of multipliers (ADMM) applicable for $L_1$-$L_2$. We describe in details how to incorporate the proximal operator into FBS and ADMM and show that the resulting algorithms are convergent under mild conditions. Both algorithms are shown to be much more efficient than the original implementation of $L_1$-$L_2$ based on a difference-of-convex approach in the numerical experiments.

1 Introduction

Compressive sensing seeks sparse recovery from underdetermined measurements, but L1 methods can struggle with highly coherent sensing matrices. The paper addresses the computational cost of L1-L2 minimization by developing proximal-operator-based FBS and ADMM approaches.

  • Problem setting: Compressive sensing recovers a sparse x from underdetermined measurements b = Ax, where M < N.The decoding problem is posed after linear encoding with a measurement matrix A.
  • Problem setting: L0 minimization directly seeks the sparsest solution but is NP-hard, motivating the use of L1 as a tractable heuristic.L1 often gives satisfactory sparse solutions, although it is a relaxation of the sparsity-counting objective.
  • Limitations of L1: When the sensing matrix is highly coherent, the sufficient L1 recovery condition can restrict signals to at most one nonzero element.High coherence corresponds to µ approximately 1 in the stated condition.
  • Proposed direction: L1-L2 is introduced as a nonconvex alternative, while the paper generalizes it to the L1 − αL2 metric for α ≥ 0.The related-work discussion presents L1-L2 as an alternative for sparse recovery, and the paper extends the formalism with parameter α.
  • Proposed direction: DCA minimizes L1-L2 through iterative L1 subproblems, making it slower than L1 minimization and motivating faster approaches.The paper considers an unconstrained formulation to allow noise in the data.
  • Contributions: The proposed methods use an analytical proximal mapping with FBS and ADMM, aiming for approximately L1 computational complexity and convergence under mild conditions.The paper derives the proximal mapping, develops both algorithms, and compares them numerically with DCA.

2 Proximal operator

The paper derives a closed-form proximal operator for L1-αL2, extending the soft-shrinkage role of the L1 proximal operator. Its case-based solution supports efficient FBS and ADMM implementations and their convergence analysis.

  • Definition: The proximal operator minimizes ∥x∥1 − α∥x∥2 plus a quadratic distance term from y.It is defined as prox_λr_α(y) = arg min_x ∥x∥1 − α∥x∥2 + (1/(2λ))∥x − y∥2^2.
  • Algorithmic role: Replacing soft shrinkage with this proximal mapping makes fast L1 solvers such as FBS and ADMM applicable to L1-αL2.Lemma 2 supplies an inequality used to prove convergence of the resulting algorithms.
  • Closed-form cases: When ∥y∥∞ > λ, the optimal solution is obtained by scaling the soft-shrunk vector z = S1(y, λ).The stated solution is x* = z(∥z∥2 + αλ)/∥z∥2.
  • Closed-form cases: When ∥y∥∞ = λ, optimal solutions satisfy support and norm conditions, and multiple maximal components can produce infinitely many solutions.The solution has zero components where |y_i| < λ, norm αλ, and matching signs.
  • Closed-form cases: When (1 − α)λ < ∥y∥∞ < λ, an optimal solution is 1-sparse; when ∥y∥∞ ≤ (1 − α)λ, the solution is zero.The zero-solution threshold is stated explicitly in Lemma 1.
  • Definition: For α = 0, the operator reduces to the L1 proximal operator, namely soft shrinkage.Soft shrinkage is the thresholding map used by efficient L1 algorithms.

3 Forward-Backward Splitting

Forward-backward splitting alternates gradient descent on l(x) with the proximal operator for the L1-αL2 regularizer. Under Lipschitz-gradient and coercivity assumptions with λ < 1/L, its objective decreases and its limit points are stationary; its fixed-point structure favors sparse solutions.

  • Algorithm: Each FBS iteration applies gradient descent to l(x), followed by the proximal operator for the regularizer.The paper also considers an accelerated proximal-gradient variant.
  • Convergence: Under Assumptions 1–2 and λ < 1/L, FBS decreases the objective and has a subsequence converging to a stationary point.Every limit point is a stationary point of E(x).
  • Fixed points: Global minimizers are fixed points of the FBS operator for all positive λ < 1/L.The paper derives necessary conditions for global minimizers, including restrictions on their sparsity when their L2 norm is small.
  • Fixed points: FBS tends to select sparser fixed points than other stationary points, excluding non-1-sparse stationary points with sufficiently small L2 norms from global solutions.The stated example uses the condition ∥x∗∥2 < 1/L = 1/3 for such stationary points.
  • Convergence: The accelerated FBS algorithm converges to a critical point when λ < 1/L.When α = 0, the method becomes ISTA; for α > 0, a larger stepsize may be possible when a lower bound on ∥xk∥2 is known.

4 Alternating Direction Method of Multipliers

The paper applies ADMM to the nonconvex problem using an auxiliary variable and establishes convergence under stated smoothness, coercivity, and parameter conditions. The analysis also notes that convergence can lead to stationary points that are not local minimizers.

  • Algorithm: ADMM reformulates the unconstrained problem with an auxiliary variable and applies alternating updates to the resulting constrained minimization.The method is developed for a general coercive regularization r(x), which includes the paper’s specific regularizer as a special case.
  • Convergence: Under Assumptions 1 and 2 and a sufficient penalty parameter δ, the ADMM sequence is bounded and has at least one limit point.The theorem states the required condition on δ, with an additional condition when l(x) is convex.
  • Convergence: Every limit point is stationary for the augmented Lagrangian, and its x-component is stationary for r(x)+l(x).At a limit point, the analysis obtains x*=y* and the stationarity condition 0 ∈ ∂r(x*) + ∇l(x*).
  • Limitations: Both FBS and ADMM may converge to a stationary point that is not a local minimizer.The paper gives an example with global minimizers and another stationary point, showing that stationarity alone does not ensure local optimality.

5 Numerical Experiments

The experiments compare FBS, ADMM, DCA, and a weighted continuation model across incoherent and coherent sensing matrices, with additional noisy-recovery tests. FBS and ADMM improve computational efficiency, while the weighted model improves recovery for highly coherent matrices.

  • Experimental setup: The experiments use random Gaussian, partial DCT, and over-sampled DCT matrices, with larger F indicating greater coherence.The over-sampled DCT matrices have size 100 × 1500 with F = 5 and F = 20; Gaussian and partial DCT matrices have size 64 × 256.
  • 5.1 Constructed Stationary Points: FBS and ADMM find constructed stationary points much faster than DCA on incoherent matrices.The comparison uses sparsity 10, λ = 1 for FBS, and δ = 0.1 for ADMM; trials where POCS failed to converge were discarded.
  • 5.2 Noise-free case: For incoherent matrices, ADMM often matches DCA, whereas the weighted model performs best for highly coherent over-sampled DCT matrices.The weighted model uses a continuation strategy for α, with a rapid linear update for incoherent matrices and a sigmoid transition for coherent matrices.
  • 5.2 Noise-free case: DCA is almost one order of magnitude slower than ADMM and the weighted model, while L1-L2 via ADMM and the weighted model are comparable in efficiency to L1.The weighted model achieves the best recovery results in terms of both success rates and computational time.
  • 5.3 Noisy Data: In noisy recovery, L1-L2 outperforms L1/2 when M is small, but L1/2 performs better when M is large.The experiment uses N = 512, 130 non-zero elements, Gaussian noise with σ = 0.1, and averages MSE over 100 realizations.

6 Conclusions

The paper derives a proximal operator for L1-αL2 and uses it to extend FBS and ADMM to this nonconvex objective. Numerical results show greater efficiency than DCA, while a continuation strategy addresses weaker ADMM recovery on coherent matrices.

  • 6 Conclusions: The derived proximal operator for L1-αL2 makes fast L1 solvers such as FBS and ADMM applicable.The paper presents convergence analyses for both algorithms.
  • 6 Conclusions: FBS and ADMM with the proximal operator are much more efficient than the DCA approach.DCA gives better recovery results than ADMM for coherent matrices, motivating continuation in α.
Loading 1609.09530v4…