Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix
Provides a theoretical guarantee for low-rank Toeplitz matrix recovery, relevant to signal processing and system identification communities.
The paper proves that symmetric Toeplitz matrices of rank r can be stably recovered from O(r log^2 n) rank-one subgaussian measurements via nuclear norm minimization, improving on prior work and resolving a conjecture.
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).