On U-Statistics and Compressed Sensing I: Non-Asymptotic Average-Case Analysis

Hoeffding\´s U-statistics model combinatorial-type matrix parameters (appearing in CS theory) in a natural way. This paper proposes using these statistics for analyzing random compressed sensing matrices, in the non-asymptotic regime (relevant to practice). The aim is to address certain pessimisms of "worst-case" restricted isometry analyses, as observed by both Blanchard & Dossal, et. al. We show how U-statistics can obtain "average-case" analyses, by relating to statistical restricted isometry property (StRIP) type recovery guarantees. However unlike standard StRIP, random signal models are not required; the analysis here holds in the almost sure (probabilistic) sense. For Gaussian/bounded entry matrices, we show that both ℓ₁-minimization and LASSO essentially require on the order of k · [log((n-k)/u) + √(2(k/n) log(n/k))] measurements to respectively recover at least 1-5u fraction, and 1-4u fraction, of the signals. Noisy conditions are considered. Empirical evidence suggests our analysis to compare well to Donoho & Tanner\´s recent large deviation bounds for ℓ₀/ℓ₁-equivalence, in the regime of block lengths 1000~3000 with high undersampling (50-150 measurements); similar system sizes are found in recent CS implementation. In this work, it is assumed throughout that matrix columns are independently sampled.