Sample Complexity of Total Variation Minimization

Abstract

This work considers the use of Total variation (TV) minimization in the recovery of a given gradient sparse vector from Gaussian linear measurements. It has been shown in recent studies that there exist a sharp phase transition behavior in TV minimization in asymptotic regimes. The phase transition curve specifies the boundary of success and failure of TV minimization for large number of measurements. It is a challenging task to obtain a theoretical bound that reflects this curve. In this work, we present a novel upper-bound that suitably approximates this curve and is asymptotically sharp. Numerical results show that our bound is closer to the empirical TV phase transition curve than the previously known bound obtained by Kabanava.

Cited by in corpus (7)

• Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
• Blind Goal-Oriented Massive Access for Future Wireless Networks
• Living near the edge: A lower-bound on the phase transition of total variation minimization
• 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
• Improved Recovery of Analysis Sparse Vectors in Presence of Prior Information