Living near the edge: A lower-bound on the phase transition of total variation minimization

Abstract

This work is about the total variation (TV) minimization which is used for recovering gradient-sparse signals from compressed measurements. Recent studies indicate that TV minimization exhibits a phase transition behavior from failure to success as the number of measurements increases. In fact, in large dimensions, TV minimization succeeds in recovering the gradient-sparse signal with high probability when the number of measurements exceeds a certain threshold; otherwise, it fails almost certainly. Obtaining a closed-form expression that approximates this threshold is a major challenge in this field and has not been appropriately addressed yet. In this work, we derive a tight lower-bound on this threshold in case of any random measurement matrix whose null space is distributed uniformly with respect to the Haar measure. In contrast to the conventional TV phase transition results that depend on the simple gradient-sparsity level, our bound is highly affected by generalized notions of gradient-sparsity. Our proposed bound is very close to the true phase transition of TV minimization confirmed by simulation results.

References in corpus (7)

• The Convex Geometry of Linear Inverse Problems
• The Cosparse Analysis Model and Algorithms
• Near-optimal compressed sensing guarantees for total variation minimization
• Corrupted Sensing: Novel Guarantees for Separating Structured Signals
• Robust analysis ${\ell }_1$-recovery from Gaussian measurements and total variation minimization
• Sample Complexity of Total Variation Minimization
• On the Error in Phase Transition Computations for Compressed Sensing

Cited by in corpus (5)

• Blind Goal-Oriented Massive Access for Future Wireless Networks
• Multi-weight Nuclear Norm Minimization for Low-rank Matrix Recovery in Presence of Subspace Prior Information
• Demixing Sines and Spikes Using Multiple Measurement Vectors
• Timely and Painless Breakups: Off-the-grid Blind Message Recovery and Users' Demixing
• Off-the-grid Recovery of Time and Frequency Shifts with Multiple Measurement Vectors