Sublinear Time Low-Rank Approximation of Toeplitz Matrices

Cameron Musco, Kshiteej Sheth

We present a sublinear time algorithm for computing a near optimal low-rank approximation to any positive semidefinite (PSD) Toeplitz matrix $T\in {\mathbb{R}}^{d\times d}$, given no…