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 ∈ R d×d , given noisy access to its entries. In particular, given entrywise query access to T + E for an arbitrary noise matrix E ∈ R d×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 ∈ R d×d with rank poly(k, log(d/δ)) satisfying, for some fixed constant C,

Here • F is the Frobenius norm and T k 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 robust low-rank approximation primitive can be applied in several settings. 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, which gave an algorithm with 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. By doing so, we resolve an open question of Eldar et al. SODA '20, improving the state-of-the-art error bounds and achieving a polynomial rather than exponential (in the sample size) runtime.

Our algorithm is based on applying sparse Fourier transform techniques to recover a lowrank 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. We also contribute a structural heavy-light decomposition result for PSD Toeplitz matrices, which allows us to apply this primitive to low-rank Toeplitz matrix recovery.