2012/07/20 by Bubacarr Bah, Jared Tanner, Bah, Bubacarr +1
Computer Science · Earth and Planetary Sciences · Engineering · #15B52 #60F10 #94A20 (Primary) 94A12 (Secondary) #Blind Source Separation Techniques #FOS: Computer and information sciences #FOS: Mathematics #Geophysical and Geoelectrical Methods #Information Theory (cs.IT) #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1207.4883
openalex publication_date 2012/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Restricted Isometry Constants (RICs) provide a measure of how far from an\nisometry a matrix can be when acting on sparse vectors. This, and related\nquantities, provide a mechanism by which standard eigen-analysis can be applied\nto topics relying on sparsity. RIC bounds have been presented for a variety of\nrandom matrices and matrix dimension and sparsity ranges. We provide explicitly\nformulae for RIC bounds, of n by N Gaussian matrices with sparsity k, in three\nsettings: a) n/N fixed and k/n approaching zero, b) k/n fixed and n/N\napproaching zero, and c) n/N approaching zero with k/n decaying inverse\nlogrithmically in N/n; in these three settings the RICs a) decay to zero, b)\nbecome unbounded (or approach inherent bounds), and c) approach a non-zero\nconstant. Implications of these results for RIC based analysis of compressed\nsensing algorithms are presented.\n