On U-Statistics and Compressed Sensing II: Non-Asymptotic Worst-Case Analysis
arXiv:1210.8117 · doi:10.1109/TSP.2013.2255041
Abstract
In another related work, U-statistics were used for non-asymptotic "average-case" analysis of random compressed sensing matrices. In this companion paper the same analytical tool is adopted differently - here we perform non-asymptotic "worst-case" analysis. Simple union bounds are a natural choice for "worst-case" analyses, however their tightness is an issue (and questioned in previous works). Here we focus on a theoretical U-statistical result, which potentially allows us to prove that these union bounds are tight. To our knowledge, this kind of (powerful) result is completely new in the context of CS. This general result applies to a wide variety of parameters, and is related to (Stein-Chen) Poisson approximation. In this paper, we consider i) restricted isometries, and ii) mutual coherence. For the bounded case, we show that k-th order restricted isometry constants have tight union bounds, when the measurements m = \mathcal{O}(k (1 + \log(n/k))). Here we require the restricted isometries to grow linearly in k, however we conjecture that this result can be improved to allow them to be fixed. Also, we show that mutual coherence (with the standard estimate \sqrt{(4\log n)/m}) have very tight union bounds. For coherence, the normalization complicates general discussion, and we consider only Gaussian and Bernoulli cases here.
arXiv comment12 pages. Submitted to IEEE Transactions on Signal Processing
References in corpus (5)
- User-friendly tail bounds for sums of random matrices
- Near-ideal model selection by minimization
- Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property
- On U-Statistics and Compressed Sensing I: Non-Asymptotic Average-Case Analysis
- On U-Statistics and Compressed Sensing II: Non-Asymptotic Worst-Case Analysis