2025/11/26 by Michael Kapralov, Cameron Musco, Kapralov, Michael +3
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Statistical and numerical algorithms #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2511.21418
openalex publication_date 2025/11/26 · openalex created_date 2025/11/28 · openalex updated_date 2026/07/28
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 ∈ ℝn × n and any ε> 0, letting Hk be the best rank-k approximation of H, ‖H-Hk‖F ≤ ε‖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 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 \widehatH 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 ∈ ℝn × n is an arbitrary non-Hankel noise matrix, we obtain error ‖H - \widehatH‖F ≤ O(‖E‖F) + ε‖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.