Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917871345467392 |
|---|---|
| author | Rao, Shravas |
| author_facet | Rao, Shravas |
| contents | A matrix $Φ\in \mathbb{R}^{Q \times N}$ satisfies the restricted isometry property if $\|Φx\|_2^2$ is approximately equal to $\|x\|_2^2$ for all $k$-sparse vectors $x$. We give a construction of RIP matrices with the optimal $Q = O(k \log(N/k))$ rows using $O(k\log(N/k)\log(k))$ bits of randomness. The main technical ingredient is an extension of the Hanson-Wright inequality to $ε$-biased distributions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_07889 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness Rao, Shravas Information Theory Data Structures and Algorithms A matrix $Φ\in \mathbb{R}^{Q \times N}$ satisfies the restricted isometry property if $\|Φx\|_2^2$ is approximately equal to $\|x\|_2^2$ for all $k$-sparse vectors $x$. We give a construction of RIP matrices with the optimal $Q = O(k \log(N/k))$ rows using $O(k\log(N/k)\log(k))$ bits of randomness. The main technical ingredient is an extension of the Hanson-Wright inequality to $ε$-biased distributions. |
| title | Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness |
| topic | Information Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.07889 |