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 Õ ( k 2 · 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 - T k || F + δ|| Τ || F. Here, || · || F is the Frobenius norm and T k 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.

Authors

• Michael Kapralov
• Hannah Lawrence
• Mikhail Makarov
• Cameron Musco
• Kshiteej Sheth

Keywords

No keywords are indexed for this paper.