Bounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matrices
Restricted isometry constants (RICs) provide a measure of how far from an isometry a matrix can be when acting on sparse vectors. This, and related quantities, provide a mechanism by which standard eigen-analysis can be applied to topics relying on sparsity. RIC bounds have been presented for a vari...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
2014
|
| _version_ | 1826271728568893440 |
|---|---|
| author | Bah, B Tanner, J |
| author_facet | Bah, B Tanner, J |
| author_sort | Bah, B |
| collection | OXFORD |
| description | Restricted isometry constants (RICs) provide a measure of how far from an isometry a matrix can be when acting on sparse vectors. This, and related quantities, provide a mechanism by which standard eigen-analysis can be applied to topics relying on sparsity. RIC bounds have been presented for a variety of random matrices and matrix dimension and sparsity ranges. We provide explicitly formulae for RIC bounds, of n × N Gaussian matrices with sparsity k, in three settings: (a) n/N fixed and k/n approaching zero, (b) k/n fixed and n/N approaching zero, and (c) n/N approaching zero with k/n decaying inverse logarithmically in N/n; in these three settings the RICs (a) decay to zero, (b) become unbounded (or approach inherent bounds), and (c) approach a non-zero constant. Implications of these results for RIC based analysis of compressed sensing algorithms are presented. © 2012 Elsevier Inc. All rights reserved. |
| first_indexed | 2024-03-06T22:01:16Z |
| format | Journal article |
| id | oxford-uuid:4eab5102-fda6-4991-9361-195e5574f061 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:01:16Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | oxford-uuid:4eab5102-fda6-4991-9361-195e5574f0612022-03-26T16:02:33ZBounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matricesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:4eab5102-fda6-4991-9361-195e5574f061Symplectic Elements at Oxford2014Bah, BTanner, JRestricted isometry constants (RICs) provide a measure of how far from an isometry a matrix can be when acting on sparse vectors. This, and related quantities, provide a mechanism by which standard eigen-analysis can be applied to topics relying on sparsity. RIC bounds have been presented for a variety of random matrices and matrix dimension and sparsity ranges. We provide explicitly formulae for RIC bounds, of n × N Gaussian matrices with sparsity k, in three settings: (a) n/N fixed and k/n approaching zero, (b) k/n fixed and n/N approaching zero, and (c) n/N approaching zero with k/n decaying inverse logarithmically in N/n; in these three settings the RICs (a) decay to zero, (b) become unbounded (or approach inherent bounds), and (c) approach a non-zero constant. Implications of these results for RIC based analysis of compressed sensing algorithms are presented. © 2012 Elsevier Inc. All rights reserved. |
| spellingShingle | Bah, B Tanner, J Bounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matrices |
| title | Bounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matrices |
| title_full | Bounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matrices |
| title_fullStr | Bounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matrices |
| title_full_unstemmed | Bounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matrices |
| title_short | Bounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matrices |
| title_sort | bounds of restricted isometry constants in extreme asymptotics formulae for gaussian matrices |
| work_keys_str_mv | AT bahb boundsofrestrictedisometryconstantsinextremeasymptoticsformulaeforgaussianmatrices AT tannerj boundsofrestrictedisometryconstantsinextremeasymptoticsformulaeforgaussianmatrices |