Non-Asymptotic Analysis of Compressed Sensing Random Matrices: An U-Statistics Approach
The authors apply Heoffding's U-statistics to obtain non-asymptotic analysis for Compressed Sensing (CS) random matrices. These powerful (U-statistics) tools appear to apply naturally to CS theory, in particular here they focus on one particular large deviation result. They chose two applications to outline how Ustatistics may apply to various CS recovery guarantees. Pros, cons, and further directions of the approach, are discussed. Restricted isometries of random matricies have well-regarded importance in CS. U-statistics related to Fuchs' conditions for L1-minimization support recovery, are derived. This leads to bounds on the fraction of recoverable k-supports.