Sublinear Time Low-Rank Approximation of Toeplitz Matrices

We present a sublinear time algorithm for computing a near optimal low-rank approximation to any positive semidefinite (PSD) Toeplitz matrix T∈ Rd× d, given noisy access to its entries. In particular, given entrywise query access to $T+E$ for an arbitrary noise matrix E∈ Rd× d, integer rank k≤ d, and error parameter δ>0, our algorithm runs in time poly(k,log(d/δ)) and outputs (in factored form) a Toeplitz matrix T ∈ Rd × d with rank poly(k,log(d/δ)) satisfying, for some fixed constant C, {equation*} \|T-{T}\|_F ≤ C · max\{\|E\|_F,\|T-T_k\|_F\} + δ · \|T\|_F. {equation*} Here \|· \|F is the Frobenius norm and Tₖ is the best (not necessarily Toeplitz) rank-k approximation to T in the Frobenius norm, given by projecting T onto its top k eigenvectors. Our result has the following applications. When $E = 0$, we obtain the first sublinear time near-relative-error low-rank approximation algorithm for PSD Toeplitz matrices, resolving the main open problem of Kapralov et al. SODA `23, whose algorithm had sublinear query complexity but exponential runtime. Our algorithm can also be applied to approximate the unknown Toeplitz covariance matrix of a multivariate Gaussian distribution, given sample access to this distribution, resolving an open question of Eldar et al. SODA `20. Our algorithm applies sparse Fourier transform techniques to recover a low-rank Toeplitz matrix using its Fourier structure. Our key technical contribution is the first polynomial time algorithm for discrete time off-grid sparse Fourier recovery, which may be of independent interest.