Toeplitz Low-Rank Approximation with Sublinear Query Complexity

Michael Kapralov, Hannah Lawrence, Mikhail Makarov +2

We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix $T\in {\mathbb{R}}^{d\times d}$. In particu…