Toeplitz Low-Rank Approximation with Sublinear Query Complexity

DOI10.1137/1.9781611977554.CH159MaRDI QIDQ6417941zbMATH OpenOpenAlexFDO

Authors Michael Kapralov, Hannah Lawrence, M. M. Makarov, Cameron Musco, Kshiteej Sheth

Publication date 21 November 2022

Full work available at URL https://doi.org/10.1137/1.9781611977554.ch159

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix $Tinmathbb{R}^{dimesd}$. In particular, for any integer rank $kleqd$ and $epsilon,delta>0$, our algorithm makes $ildeOleft(k^{2}cdotlog(1/delta)cdotextpoly(1/epsilon)ight)$ queries to the entries of $T$ and outputs a rank $ildeOleft(kcdotlog(1/delta)/epsilonight)$ matrix $ildeTinmathbb{R}^{dimesd}$ such that $|T-ildeT{|}_{F}leq(1+epsilon)cdot|T-T_k{|}_F+delta|T{|}_F$. Here, $|cdot{|}_F$ is the Frobenius norm and $T_k$ is the optimal rank-$k$ approximation to $T$, given by projection onto its top $k$ eigenvectors. $ildeO(cdot)$ hides $extpolylog(d)$ factors. Our algorithm is emph{structure-preserving}, in that the approximation $ildeT$ 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 $ildeT$ 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.

Cited in

(1)

• Quasi-optimal hierarchically semi-separable matrix approximation

This page was built for publication: Toeplitz Low-Rank Approximation with Sublinear Query Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6417941)