Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix

Abstract

This note demonstrates that we can stably recover all symmetric Toeplitz matrices $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).

16 pages; typos corrected