Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.03175 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917508262395904 |
|---|---|
| author | Huang, Gao Li, Song |
| author_facet | Huang, Gao Li, Song |
| contents | This note demonstrates that we can stably recover all symmetric Toeplitz matrices $\pmb{X}_0\in\mathbb{R}^{n\times n}$ of rank at most $r$ from a number of rank-one subgaussian measurements on the order of $r\log^{2} n$ with an exponentially decreasing failure probability by employing a nuclear norm minimization program. Our approach utilizes descent cone analysis through Mendelson's small ball method with the Toeplitz constraint. The key ingredient is to determine the spectral norm of a random matrix with Toeplitz structure, which may be of independent interest. This improves upon earlier analyses and resolves the conjecture in Chen et al. (IEEE Transactions on Information Theory, 61(7):4034--4059, 2015). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_03175 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix Huang, Gao Li, Song Information Theory This note demonstrates that we can stably recover all symmetric Toeplitz matrices $\pmb{X}_0\in\mathbb{R}^{n\times n}$ of rank at most $r$ from a number of rank-one subgaussian measurements on the order of $r\log^{2} n$ with an exponentially decreasing failure probability by employing a nuclear norm minimization program. Our approach utilizes descent cone analysis through Mendelson's small ball method with the Toeplitz constraint. The key ingredient is to determine the spectral norm of a random matrix with Toeplitz structure, which may be of independent interest. This improves upon earlier analyses and resolves the conjecture in Chen et al. (IEEE Transactions on Information Theory, 61(7):4034--4059, 2015). |
| title | Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix |
| topic | Information Theory |
| url | https://arxiv.org/abs/2407.03175 |