Computational approaches to non-convex, sparsity-inducing multi-penalty\n regularization

Željko Kereta, Johannes Maly, Valeriya Naumova

TL;DR

This paper introduces a computationally efficient way to recover sparse signals from data corrupted by noise both before and after measurement (a phenomenon called "noise folding"). By reformulating a complex multi-penalty optimization problem into a single-penalty version using infimal convolution, the authors achieve linear convergence rates while avoiding the massive computational bottlenecks that plague existing methods in large-scale applications.

What Problem Does This Paper Address?

In standard compressed sensing, we assume noise happens at the sensor (post-measurement). However, in many real-world scenarios, the signal is already "dirty" before it even hits the measurement device. This "pre-measurement" noise gets amplified by the measurement process itself—a headache known as noise folding.

To fight this, researchers use multi-penalty regularization, which applies different "punishments" to the signal (to keep it sparse) and the noise (to keep it small). While effective, solving these problems is hard. Traditional "alternating minimization" (switching back and forth between solving for signal and noise) is notoriously slow. Recent "augmented" methods simplify the math but require heavy matrix operations (like square roots and inversions) that become impossible to compute as the problem size grows.

Methods

The authors focus on the non-convex case ($L_q$ regularization where $0 < q \le 1$), which is better at promoting sparsity than standard convex methods but much harder to analyze. They compare two main strategies:

  1. The Augmented Formulation: This extends an existing technique to the non-convex setting. It transforms the multi-penalty problem into a single-penalty one by "fattening" the measurement matrix.
  2. The Infimal Convolution Formulation (The Novel Approach): To avoid the $O(m^3)$ computational cost of the augmented approach, the authors use the mathematical concept of infimal convolution (related to Moreau envelopes). This allows them to decouple the signal and noise components more efficiently.

Both methods are solved using Iterative Thresholding (a type of proximal gradient descent). The authors provide a rigorous theoretical analysis, proving that both algorithms converge at a linear rate—meaning the error drops exponentially over time—provided the measurement matrix satisfies the Restricted Isometry Property (RIP).

Datasets

The paper relies on synthetic benchmarks to validate the theory:

  • Measurement Matrices: Random Gaussian matrices $A \in \mathbb{R}^{m \times n}$.
  • Signals: $s$-sparse vectors (e.g., 20 non-zero entries in a 600-dimensional vector).
  • Noise: Gaussian pre-measurement noise ($v$) and post-measurement noise ($\xi$).
  • Scaling Tests: They tested the algorithms on problems ranging from 600 to 5,000 dimensions to demonstrate how the computational cost scales with the number of measurements ($m$).

Key Insights and Ideas

  • The "Aha" Moment on Efficiency: The augmented approach is mathematically elegant but computationally "heavy" because it requires pre-processing the entire measurement matrix. The infimal convolution approach achieves the same goal but keeps the matrix operations "light," making it the clear winner for high-dimensional data.
  • Linear Convergence in Non-Convexity: Proving linear convergence for non-convex problems ($q < 1$) is difficult. The authors show that once the algorithm correctly identifies the "support" (which entries are non-zero), it behaves predictably and closes in on the solution rapidly.
  • Support Stability: A key finding is that these algorithms are "stable"—once they find the right non-zero entries in the signal, they don't easily lose them in subsequent iterations.

Key Results

  • Computational Speedup: In tests with 5,000-dimensional signals, the running time for the augmented approach exploded as the number of measurements increased, while the infimal convolution approach remained nearly flat (see Figure 2b).
  • Superiority over Alternating Minimization: The proposed methods reached high accuracy in a fraction of the iterations required by standard alternating minimization techniques.
  • Theoretical Validation: Numerical experiments perfectly matched the predicted linear convergence rates, confirming that the "design parameters" (like the regularization weights $\alpha$ and $\beta$) directly control the speed of recovery.

Limitations and Future Work

  • Parameter Tuning: The speed of convergence depends heavily on choosing the right regularization parameters ($\alpha, \beta$) and step size ($\mu$). If these are poorly chosen, the "linear" speedup might not materialize.
  • Initialization: As with most non-convex problems, the algorithm needs a decent starting point to guarantee it finds the global optimum rather than a local "trap."
  • Future Directions: The authors suggest extending this framework to infinite-dimensional spaces (Hilbert spaces) and exploring other non-convex penalties like the Smoothly Clipped Absolute Deviation (SCAD) or the Minimax Concave Penalty (MCP).

Summary updated

Abstract

In this work we consider numerical efficiency and convergence rates for\nsolvers of non-convex multi-penalty formulations when reconstructing sparse\nsignals from noisy linear measurements. We extend an existing approach, based\non reduction to an augmented single-penalty formulation, to the non-convex\nsetting and discuss its computational intractability in large-scale\napplications. To circumvent this limitation, we propose an alternative\nsingle-penalty reduction based on infimal convolution that shares the benefits\nof the augmented approach but is computationally less dependent on the problem\nsize. We provide linear convergence rates for both approaches, and their\ndependence on design parameters. Numerical experiments substantiate our\ntheoretical findings.\n
BibTeX
@misc{kereta2019computational,
  author = {Željko Kereta and Johannes Maly and Valeriya Naumova},
  title = {{Computational approaches to non-convex, sparsity-inducing multi-penalty\textbackslash\{\}n regularization}},
  year = {2019},
  eprint = {1908.02503},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.02503},
}
Figure