Precise Phase Transition of Total Variation Minimization

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

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 $\ell_1$ 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 of a denoising problem and the high-dimensional convex geometry for TV minimization.

Introduction

In the field of compressed sensing, the primary objective is to recover a signal from as few measurements as possible. For signals that are "sparse" (containing mostly zeros), researchers typically employ $\ell_1$ minimization. However, for signals that are "piece-wise constant"—where the gradient is sparse—Total Variation (TV) minimization is the standard approach.

Researchers have long observed a phase transition phenomenon in these problems: if the number of measurements ($m$) exceeds a specific threshold, recovery succeeds with high probability; otherwise, it fails. While these thresholds were well-understood for $\ell_1$ and nuclear norm minimization, the precise phase transition for TV minimization remained a long-standing open problem. The difficulty stems from the fact that the TV "norm" is non-separable—the value at one point depends on its neighbors—making standard geometric tools, such as calculating the "Gaussian width" of descent cones, extremely difficult to apply.

Methodology

This paper solves this problem by bridging the gap between convex geometry and iterative algorithm conjectures. The authors utilize a three-pronged approach:

  1. Convex Geometry: They leverage the framework of "Gaussian width," where recent theory suggests 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 specific mathematical propositions to bound the Gaussian width.
  3. Linking Denoising to Recovery: They connect the geometric recovery threshold to the minimax Mean Square Error (MSE) of a TV-denoising problem. This is significant because the minimax MSE was already conjectured to be the threshold for the TV-based Approximate Message Passing (AMP) algorithm.

As a theoretical work, the analysis focuses on synthetic 1D sparse-gradient signals where the finite difference is sparse, using Gaussian observation matrices as the standard benchmark for characterizing these transitions.

Key Insights and Results

The "aha moment" of this research is the proof that the TV regularizer satisfies the weak decomposability assumption. This was the technical hurdle that previously prevented researchers from applying general geometric recovery theorems to TV minimization.

The authors prove that the phase transition for TV minimization is given by the formula: $$\min_{\lambda \ge 0} D(\lambda \partial f(x))$$ where $D$ is the mean square distance to the scaled subdifferential of the TV functional. They demonstrate that the difference between the minimax MSE and the Gaussian width is at most a small constant (6), which becomes negligible as the signal dimension $n$ grows toward infinity.

Ultimately, this 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.

Discussion and Future Work

While this work provides a rigorous characterization for one-dimensional signals, it opens several doors for future research. The current proof addresses 1D TV, but 2D image processing involves a much more complex finite difference structure that remains to be fully characterized. Additionally, while Gaussian measurement matrices are the theoretical gold standard, real-world sensing matrices (such as those in MRI) often have different structures. Extending this rigorous framework to 2D/3D TV and other non-separable regularizers like the "fused lasso" or group-sparse penalties represents the next frontier in this field.

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 $\ell_1$ 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 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},
}
Figure