Analysis of The Ratio of $\ell_1$ and $\ell_2$ Norms in Compressed Sensing

Yiming Xu, Akil Narayan, Hoang Tran, Clayton G. WebsterarXiv 2020 · arXiv

Introduction

Compressed sensing (CS) has revolutionized signal processing by demonstrating that sparse signals can be reconstructed from far fewer measurements than the Nyquist-Shannon sampling theorem traditionally suggests. The core challenge in CS is solving the underdetermined linear system $y = Ax$, where $x$ is a sparse signal. While the ideal approach involves minimizing the $\ell_0$ "norm" (the count of non-zero entries), this is an NP-hard problem. Consequently, researchers typically rely on the $\ell_1$ norm as a convex proxy. However, $\ell_1$ minimization often requires more measurements than theoretically necessary to achieve perfect recovery.

Recent empirical work has pointed toward the ratio of $\ell_1$ and $\ell_2$ norms ($\ell_1/\ell_2$) as a powerful non-convex alternative. This ratio is particularly advantageous because it is scale-invariant—the objective value does not change if the signal is scaled by a constant. Despite its empirical success, $\ell_1/\ell_2$ is mathematically challenging due to its non-convexity, non-smoothness, and lack of global continuity. This paper provides the first rigorous theoretical foundation for this objective, establishing conditions for recovery and introducing algorithmic improvements.

Theoretical Contributions

Geometric Null Space Analysis

Rather than using the standard Restricted Isometry Property (RIP), which can be difficult to verify for many measurement matrices, the authors employ a high-dimensional geometric approach. They characterize the null space (kernel) of the measurement matrix $A$ using Gaussian complexity and width. This analysis yields the first uniform recovery condition for the $\ell_1/\ell_2$ ratio, proving that for a large class of random sub-gaussian matrices, the objective successfully recovers sparse signals with high probability, provided the number of measurements $m$ scales appropriately with sparsity $s$ and signal length $n$.

Local Optimality and Dynamic Range

The paper introduces a criterion for local optimality based on the "dynamic range" of the signal—defined as the ratio between the smallest and largest non-zero entries. The authors demonstrate that signals with a higher dynamic range are more easily "trapped" as local minimizers by the $\ell_1/\ell_2$ objective. This insight is crucial for understanding why certain sparse signals are more recoverable than others and highlights the specific strengths of the ratio-based approach over difference-based methods like $\ell_1 - \ell_2$.

The Support Selection (SS) Initialization

A significant hurdle for non-convex optimization is the tendency of solvers to become stuck in local minima. The authors argue that the perceived failures of $\ell_1/\ell_2$ are often not due to the objective function itself, but rather poor initialization.

To mitigate this, they propose the Support Selection (SS) initialization technique. Instead of a single starting point (like the $\ell_1$ solution), the SS method identifies the support of the initial $\ell_1$ estimate and tests $s$ different initializations based on the individual components of that support. This multi-start strategy effectively "un-sticks" the numerical solver, significantly increasing the likelihood of reaching the global minimum. While this adds a computational cost, the sub-problems are embarrassingly parallel, making it feasible for modern multi-core processors.

Experimental Validation

The authors validated their theoretical findings using synthetic benchmarks. They utilized $50 \times 250$ Gaussian random matrices and tested sparse signals with $s$ ranging from 6 to 24. To test the impact of dynamic range, non-zero components were drawn from two distributions: a standard Uniform([-10, 10]) and a high-dynamic range Uniform([-10, -5] ∪ [5, 10]).

Key Results:

  • Performance: The $\ell_1/\ell_2 + SS$ approach consistently outperformed standard $\ell_1$ minimization and other popular non-convex solvers, including IRLS, CoSaMP, and OMP.
  • Robustness: The method proved stable against noise. When measurements were corrupted, the recovery error remained bounded relative to the noise level, satisfying a key requirement for real-world applications.
  • Scale Invariance: Unlike methods that require parameter tuning based on signal magnitude, the $\ell_1/\ell_2$ ratio remains effective regardless of signal strength, offering a distinct practical advantage.

Conclusion and Future Directions

This research bridges the gap between the empirical performance and theoretical understanding of the $\ell_1/\ell_2$ ratio in compressed sensing. By providing rigorous recovery guarantees and a robust initialization strategy, the authors have established $\ell_1/\ell_2$ as a viable and often superior alternative to convex relaxation.

Future work remains to tighten the theoretical bounds, as a gap still exists between the number of measurements required by the current theory and those observed in practice. Additionally, the authors suggest exploring whether other norm ratios, such as $\ell_p/\ell_q$, could further enhance recovery for highly compressible signals that are not strictly sparse.

Summary updated

Abstract

We first propose a novel criterion that guarantees that an $s$-sparse signal is the local minimizer of the $\ell_1/\ell_2$ objective; our criterion is interpretable and useful in practice. We also give the first uniform recovery condition using a geometric characterization of the null space of the measurement matrix, and show that this condition is easily satisfied for a class of random matrices. We also present analysis on the robustness of the procedure when noise pollutes data. Numerical experiments are provided that compare $\ell_1/\ell_2$ with some other popular non-convex methods in compressed sensing. Finally, we propose a novel initialization approach to accelerate the numerical optimization procedure. We call this initialization approach \emph{support selection}, and we demonstrate that it empirically improves the performance of existing $\ell_1/\ell_2$ algorithms.
BibTeX
@misc{xu2020analysis,
  author = {Yiming Xu and Akil Narayan and Hoang Tran and Clayton G. Webster},
  title = {{Analysis of The Ratio of $\textbackslash\{\}ell\_1$ and $\textbackslash\{\}ell\_2$ Norms in Compressed Sensing}},
  year = {2020},
  eprint = {2004.05873},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.05873},
}
Figure