Precise phase transition of total variation minimization

Bingwen Zhang, Weiyu Xu, Jian-Feng Cai, Lifeng Lai

TL;DR

This paper solves a long-standing open problem in signal processing: precisely determining the "phase transition" for Total Variation (TV) minimization. The authors rigorously prove that the minimum number of measurements required to recover a piece-wise constant signal matches the minimax Mean Square Error (MSE) of a related denoising problem, effectively bridging the gap between convex geometry and iterative algorithm conjectures.

What Problem Does This Paper Address?

In the world of compressed sensing, we want to recover a signal from as few measurements as possible. For signals that are "sparse" (mostly zeros), we use $\ell_1$ minimization. For signals that are "piece-wise constant" (the gradient is sparse), we use Total Variation (TV) minimization.

Researchers have long observed a phase transition phenomenon: if you have more than a certain number of measurements ($m$), recovery succeeds with high probability; if you have fewer, it fails. While these thresholds were well-understood for $\ell_1$ and nuclear norm minimization, TV minimization remained a mystery. The difficulty stems from the fact that the TV "norm" is non-separable—the value at one point depends on its neighbors—making the standard geometric tools (like calculating the "Gaussian width" of descent cones) incredibly difficult to apply.

Methods

The authors take a two-pronged approach to crack this problem:

  1. Convex Geometry: They utilize the framework of "Gaussian width." Recent theory suggests that the phase transition occurs at the Gaussian width of the "descent cone" of the penalty function.
  2. Weak Decomposability: To handle the non-separable nature of TV, the authors prove that the TV regularizer satisfies a technical condition called "weak decomposability." This allows them to use a specific proposition (from Foygel and Mackey) to bound the Gaussian width.
  3. Linking Denoising to Recovery: They connect the geometric recovery threshold to the minimax MSE of a TV-denoising problem. This is significant because the minimax MSE was already conjectured by Donoho, Johnstone, and Montanari to be the threshold for the Approximate Message Passing (AMP) algorithm.

By proving that TV satisfies weak decomposability, the authors show that the geometric threshold and the denoising MSE are essentially the same (within a negligible constant).

Datasets

As a theoretical paper in mathematical signal processing, this work does not use standard empirical datasets (like ImageNet). Instead, it focuses on:

  • Synthetic Sparse-Gradient Signals: One-dimensional vectors $x^* \in \mathbb{R}^n$ where the finite difference $Bx^*$ is sparse.
  • Gaussian Observation Matrices: The analysis assumes the measurement matrix $A$ consists of i.i.d. standard Gaussian random variables, which is the standard benchmark for characterizing phase transitions in this field.

Key Insights and Ideas

  • The Missing Link: The "aha moment" is the proof that the TV regularizer satisfies the weak decomposability assumption. This was the technical hurdle preventing researchers from applying general geometric recovery theorems to TV.
  • Validation of Conjectures: The paper provides a rigorous proof for a threshold that was previously only conjectured based on the behavior of the TV-AMP algorithm. It confirms that the "empirical" success seen in simulations matches a deep geometric truth.
  • Separability isn't Required: Most early successes in phase transition theory relied on "separable" functions (where the function is a sum of terms acting on individual coordinates). This paper demonstrates a path forward for more complex, structured regularizers.

Key Results

  • The Formula: The authors prove that the phase transition for TV minimization is given by $\min_{\lambda \ge 0} D(\lambda \partial f(x))$, where $D$ is the mean square distance to the scaled subdifferential of the TV functional.
  • Precision: They show that the difference between the minimax MSE and the Gaussian width is at most a constant (6), which becomes negligible as the signal dimension $n$ grows toward infinity.
  • Unified Theory: The result successfully unifies three different perspectives: the performance of the TV-AMP algorithm, the minimax error of TV denoising, and the high-dimensional geometry of the TV descent cone.

Limitations and Future Work

  • 1D Focus: The proof specifically addresses one-dimensional signals. While TV is most famous for 2D image processing, the 2D finite difference matrix has a much more complex structure that isn't covered here.
  • Gaussian Assumption: The results rely on the measurement matrix being Gaussian. While this is standard for theoretical characterization, real-world sensing matrices (like those in MRI or Radar) often have different structures.
  • Future Directions: A natural next step is extending this rigorous characterization to 2D and 3D Total Variation, as well as other non-separable regularizers like the "fused lasso" or group-sparse penalties.

Summary updated

Abstract

Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. In this paper, we fully characterize the phase transition curve of the TV minimization. Our proof builds on Donoho, Johnstone and Montanari's conjectured phase transition curve for the TV approximate message passing algorithm (AMP), together with the linkage between the minmax Mean Square Error (MSE) of a denoising problem and the high-dimensional convex geometry for TV minimization.
BibTeX
@inproceedings{zhang2016precise,
  author = {Bingwen Zhang and Weiyu Xu and Jian-Feng Cai and Lifeng Lai},
  title = {{Precise phase transition of total variation minimization}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2016},
  url = {https://openreview.net/forum?id=R28oxGFXbFo},
}

Loading related content...

Figure