On the Error in Phase Transition Computations for Compressed Sensing

Abstract

Evaluating the statistical dimension is a common tool to determine the asymptotic phase transition in compressed sensing problems with Gaussian ensemble. Unfortunately, the exact evaluation of the statistical dimension is very difficult and it has become standard to replace it with an upper-bound. To ensure that this technique is suitable, [1] has introduced an upper-bound on the gap between the statistical dimension and its approximation. In this work, we first show that the error bound in [1] in some low-dimensional models such as total variation and ${\ell }_1$ analysis minimization becomes poorly large. Next, we develop a new error bound which significantly improves the estimation gap compared to [1]. In particular, unlike the bound in [1] that is not applicable to settings with overcomplete dictionaries, our bound exhibits a decaying behavior in such cases.

Cited by in corpus (6)

• Blind Goal-Oriented Massive Access for Future Wireless Networks
• Living near the edge: A lower-bound on the phase transition of total variation minimization
• 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