  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 l1-minimization and LASSO
essentially require on the order of k \cdot [\log((n-k)/u) + \sqrt{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 l0/l1-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.
