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.