Sublinear Time Low-Rank Approximation of Hankel Matrices

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 $\epsilon \gt 0$, letting $H_k$ be the best rank-$k$ approximation of $H$ (obtained via truncated singular value decomposition), $\|H - H_k\|_F \le \epsilon \|H\|_F$ for $k = O(\log n \log (1/\epsilon))$. I.e., the optimal low-rank approximation error decays exponentially in the rank-$k$. As such, PSD Hankel matrices are natural targets for low-rank approximation algorithms. We give the first such algorithm that runs in sublinear time. In particular, we show how to compute, in $\operatorname{polylog}(n, 1/\epsilon)$ time, a factored representation of a rank-$O(\log n \log(1/\epsilon))$ Hankel matrix $\widehat{H}$ matching the error guarantee of Beckermann and Townsend up to constant factors. We further show that our algorithm is 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 \le O(\|E\|_F) + \epsilon \|H\|_F$. Towards this algorithmic result, our first contribution is a structure-preserving existence result – we show that there exists a rank-$k$ 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.