Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |