Accelerated Schemes for the $L_1/L_2$ Minimization

Chao Wang, Ming Yan, Yaghoub Rahimi, Yifei Lou

This paper, published in 2020, tackles a classic problem in signal processing: how to find a "sparse" signal (one with mostly zeros) from a limited set of measurements. While the $L_1$ norm is the industry standard for this, it often fails when the measurement matrix is "coherent" (meaning its columns are highly correlated).

The authors propose using the $L_1/L_2$ ratio as a better, parameter-free proxy for sparsity and introduce "adaptive" algorithms that make solving this difficult non-convex problem much faster.

TL;DR

The authors develop accelerated, parameter-free algorithms for sparse signal recovery by minimizing the ratio of $L_1$ and $L_2$ norms. Their "adaptive" schemes significantly outperform previous methods in speed and are uniquely effective at recovering signals with a high dynamic range.

What Problem Does This Paper Address?

In compressed sensing, we try to solve $Ax = b$ for the sparsest possible $x$. The "gold standard" for sparsity is the $L_0$ norm (which simply counts non-zero entries), but minimizing it is computationally impossible (NP-hard).

Researchers usually use the $L_1$ norm as a convex substitute. However, $L_1$ struggles when the matrix $A$ is highly coherent. Non-convex alternatives like $L_1 - \alpha L_2$ work better but require the user to manually tune the parameter $\alpha$. The $L_1/L_2$ ratio is an attractive alternative because it is scale-invariant and parameter-free, but it is mathematically "messy" to optimize efficiently. This paper aims to bridge that efficiency gap.

Methods

The authors propose three numerical schemes to solve the $L_1/L_2$ minimization problem:

  1. $L_1/L_2$-BS (Bisection Search): A baseline method that treats the ratio as a root-finding problem. It is theoretically sound but slow because it requires solving a full optimization problem at every step.
  2. $L_1/L_2$-A1 (Adaptive Selection 1): An accelerated scheme that updates the ratio estimate ($\alpha$) on the fly during the iterations. It transforms the sub-problem into a Linear Programming (LP) task.
  3. $L_1/L_2$-A2 (Adaptive Selection 2): Similar to A1, but it adds a "proximal" quadratic term to improve stability and robustness. This version is solved using the Alternating Direction Method of Multipliers (ADMM).

The "Adaptive" part is the key innovation: instead of the slow nested loops used in Bisection Search, these algorithms update the signal and the ratio parameter simultaneously in a single loop.

Datasets

The paper evaluates the algorithms using simulated signals and oversampled Discrete Cosine Transform (DCT) matrices.

  • Coherence: They use a parameter $F$ to control how correlated the columns of the matrix are. High $F$ values (e.g., $F=20$) represent extremely difficult recovery scenarios where standard $L_1$ methods typically fail.
  • Dynamic Range: They simulate signals where the non-zero entries have a "High Dynamic Range" (HDR), meaning the largest values are orders of magnitude larger than the smallest ones (e.g., $10^3$ to $10^5$ times larger).

Key Insights and Ideas

  • The HDR Advantage: One of the most striking findings is that $L_1/L_2$ minimization is exceptionally good at recovering signals with a high dynamic range. Most other models struggle when signal magnitudes vary wildly.
  • Parameter-Free Performance: Unlike the $TL_1$ (Transformed $L_1$) model, which is very sensitive to its internal parameter $a$, the $L_1/L_2$ ratio achieves similar or better results without needing any prior knowledge of the signal's structure.
  • Counter-Intuitive $L_1$ Behavior: The authors observed that for the standard $L_1$ model, a higher dynamic range actually makes the signal easier to recover in coherent settings. This is a surprising empirical result that contradicts common intuition in the field.
  • Mathematical Connections: The authors prove that their adaptive schemes are essentially non-linear versions of the "inverse power method" used in linear algebra to find eigenvalues.

Key Results

  • Speedup: The adaptive schemes (A1 and A2) are significantly faster than the Bisection Search and the authors' own previous ADMM-based approach, often reducing computation time by several fold while maintaining accuracy.
  • Success Rates: In high-coherence tests ($F=20$), the $L_1/L_2$ models consistently outperformed standard $L_1$ and were the second-best overall, trailing only the $TL_1$ model (and $TL_1$ only wins if you already know the perfect parameter to give it).
  • Convergence: The authors provide formal proofs (Theorems 1 and 2) showing that their adaptive algorithms are guaranteed to converge to a "critical point" of the cost function.

Limitations and Future Work

  • Local Minima: Because the $L_1/L_2$ ratio is non-convex, the algorithms are only guaranteed to find a local minimum (a "critical point"), not necessarily the absolute best global solution.
  • Theoretical Justification: While the authors documented that high dynamic range helps $L_1$ recovery, they note that this "calls for theoretical justification in the future."
  • Real-World Application: The current work is focused on 1D signal recovery. The authors suggest that applying these ratio models to 2D image processing tasks, such as blind deconvolution (sharpening blurry images without knowing the blur kernel), is a promising next step.

Summary updated

Abstract

In this paper, we consider the L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> /L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> minimization for sparse recovery and study its relationship with the L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -αL <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> model. Based on this relationship, we propose three numerical algorithms to minimize this ratio model, two of which work as adaptive schemes and greatly reduce the computation time. Focusing on the two adaptive schemes, we discuss their connection to existing approaches and analyze their convergence. The experimental results demonstrate that the proposed algorithms are comparable to state-of-the-art methods in sparse recovery and work particularly well when the ground-truth signal has a high dynamic range. Lastly, we reveal some empirical evidence on the exact L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> recovery under various combinations of sparsity, coherence, and dynamic ranges, which calls for theoretical justification in the future.
BibTeX
@article{wang2020accelerated,
  author = {Chao Wang and Ming Yan and Yaghoub Rahimi and Yifei Lou},
  title = {{Accelerated Schemes for the $L\_1/L\_2$ Minimization}},
  journal = {IEEE Transactions on Signal Processing},
  year = {2020},
  doi = {10.1109/tsp.2020.2985298},
}
Figure