Toeplitz Low-Rank Approximation with Sublinear Query Complexity

We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix T ∈ ℝd×d. In particular, for any integer rank k ≤ d and ε, δ > 0, our algorithm makes Õ (k2 · log(1/δ) · poly(1/ε)) queries to the entries of T and outputs a rank Õ (k · log(1/δ)/ε) matrix d×d such that ||T – ||F ≤ (1 + ε) · ||T - Tk ||F + δ||Τ||F. Here, || · ||F is the Frobenius norm and Tk is the optimal rank-k approximation to T, given by projection onto its top k eigenvectors. Õ(·) hides polylog(d) factors. Our algorithm is structure-preserving, in that the approximation is also Toeplitz. A key technical contribution is a proof that any positive semidefinite Toeplitz matrix in fact has a near-optimal low-rank approximation which is itself Toeplitz. Surprisingly, this basic existence result was not previously known. Building on this result, along with the well-established off-grid Fourier structure of Toeplitz matrices [Cybenko'82], we show that Toeplitz with near optimal error can be recovered with a small number of random queries via a leverage-score-based off-grid sparse Fourier sampling scheme.