{"ID":2836432,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.21418","arxiv_id":"2511.21418","title":"Sublinear Time Low-Rank Approximation of Hankel Matrices","abstract":"Hankel matrices are an important class of highly-structured matrices, arising across computational mathematics, engineering, and theoretical computer science. It is well-known that positive semidefinite (PSD) Hankel matrices are always approximately low-rank. In particular, a celebrated result of Beckermann and Townsend shows that, for any PSD Hankel matrix $H \\in \\mathbb{R}^{n \\times n}$ and any $ε\u003e 0$, letting $H_k$ be the best rank-$k$ approximation of $H$, $\\|H-H_k\\|_F \\leq ε\\|H\\|_F$ for $k = O(\\log n \\log(1/ε))$. As such, PSD Hankel matrices are natural targets for low-rank approximation algorithms. We give the first such algorithm that runs in \\emph{sublinear time}. In particular, we show how to compute, in $\\polylog(n, 1/ε)$ time, a factored representation of a rank-$O(\\log n \\log(1/ε))$ Hankel matrix $\\widehat{H}$ matching the error guarantee of Beckermann and Townsend up to constant factors. We further show that our algorithm is \\emph{robust} -- given input $H+E$ where $E \\in \\mathbb{R}^{n \\times n}$ is an arbitrary non-Hankel noise matrix, we obtain error $\\|H - \\widehat{H}\\|_F \\leq O(\\|E\\|_F) + ε\\|H\\|_F$. Towards this algorithmic result, our first contribution is a \\emph{structure-preserving} existence result - we show that there exists a rank-$k$ \\emph{Hankel} approximation to $H$ matching the error bound of Beckermann and Townsend. Our result can be interpreted as a finite-dimensional analog of the widely applicable AAK theorem, which shows that the optimal low-rank approximation of an infinite Hankel operator is itself Hankel. Armed with our existence result, and leveraging the well-known Vandermonde structure of Hankel matrices, we achieve our sublinear time algorithm using a sampling-based approach that relies on universal ridge leverage score bounds for Vandermonde matrices.","short_abstract":"Hankel matrices are an important class of highly-structured matrices, arising across computational mathematics, engineering, and theoretical computer science. It is well-known that positive semidefinite (PSD) Hankel matrices are always approximately low-rank. In particular, a celebrated result of Beckermann and Townsen...","url_abs":"https://arxiv.org/abs/2511.21418","url_pdf":"https://arxiv.org/pdf/2511.21418v1","authors":"[\"Michael Kapralov\",\"Cameron Musco\",\"Kshiteej Sheth\"]","published":"2025-11-26T14:09:28Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.NA\"]","methods":"[]","has_code":false}