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 $ε> 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.

翻译：汉克尔矩阵是一类重要的高度结构化矩阵，广泛出现于计算数学、工程学和理论计算机科学领域。众所周知，半正定汉克尔矩阵总是近似低秩的。特别地，Beckermann和Townsend的一个著名结果表明：对于任意半正定汉克尔矩阵$H \\in \\mathbb{R}^{n \\times n}$和任意$ε> 0$，令$H_k$为$H$的最佳秩$k$逼近，则当$k = O(\\log n \\log(1/ε))$时，有$\\|H-H_k\\|_F \\leq ε\\|H\\|_F$。因此，半正定汉克尔矩阵自然成为低秩逼近算法的目标。我们提出了首个在亚线性时间内运行的此类算法。具体而言，我们展示了如何在$\\polylog(n, 1/ε)$时间内，计算一个秩为$O(\\log n \\log(1/ε))$的汉克尔矩阵$\\widehat{H}$的分解表示，其误差保证与Beckermann和Townsend的结果在常数因子内匹配。我们进一步证明该算法具有鲁棒性——给定输入$H+E$，其中$E \\in \\mathbb{R}^{n \\times n}$为任意非汉克尔噪声矩阵，我们获得的误差满足$\\|H - \\widehat{H}\\|_F \\leq O(\\|E\\|_F) + ε\\|H\\|_F$。为实现这一算法结果，我们的首要贡献是一个结构保持的存在性结果——我们证明存在一个秩$k$的汉克尔逼近矩阵，其误差界与Beckermann和Townsend的结果匹配。我们的结果可视为广泛适用的AAK定理的有限维类比，该定理表明无限维汉克尔算子的最优低秩逼近本身也是汉克尔型的。基于我们的存在性结果，并利用汉克尔矩阵著名的范德蒙结构，我们通过采用依赖范德蒙矩阵通用岭杠杆得分界的抽样方法，实现了亚线性时间算法。