Abstract
This paper introduces the first algorithm capable of computing a low-rank approximation of a positive semidefinite (PSD) Hankel matrix in sublinear time—specifically, in time proportional to $\text{polylog}(n, 1/\epsilon)$. By exploiting the unique Vandermonde structure of Hankel matrices and deriving new universal bounds for ridge leverage scores, the authors demonstrate that a high-quality, structure-preserving approximation can be found via a robust, sampling-based approach. This work bridges operator theory and randomized linear algebra, providing significant theoretical and practical speedups for signal processing and computational mathematics.
Introduction
Hankel matrices—defined by constant values along each anti-diagonal—are fundamental to signal processing, control theory, and the study of orthogonal polynomials. A well-established property of PSD Hankel matrices is that they are "approximately low-rank." Research by Beckermann and Townsend (2017) demonstrated that their eigenvalues decay exponentially, implying that an $n \times n$ matrix can be effectively approximated by a rank-$k$ matrix where $k$ is only logarithmic in $n$.
Despite this inherent compressibility, existing algorithms to compute these approximations typically require at least $O(n \log n)$ time (utilizing Fast Fourier Transforms) or $O(n^2)$ time. As dataset sizes continue to scale, even near-linear time complexity becomes a computational bottleneck. This paper addresses a fundamental challenge: finding a near-optimal low-rank approximation without inspecting the majority of the matrix entries.
Methodology
The authors achieve sublinear runtime through a synthesis of structural matrix theory and randomized linear algebra techniques:
1. Fiedler Factorization and Structure Preservation
The algorithm represents the PSD Hankel matrix $H$ using its Fiedler factorization: $H = V_X D_X V_X^T$, where $V_X$ is a Vandermonde matrix and $D_X$ is a diagonal matrix of weights. A key theoretical contribution is the proof of a finite-dimensional version of the "AAK Theorem," which shows that a rank-$k$ approximation exists that is itself a Hankel matrix, matching the error bounds of the best unconstrained low-rank approximation.
2. Log-scale Bucketing
To address the inherent ill-conditioning of Vandermonde matrices, the authors partition the "nodes" of the matrix into buckets based on their decay rates. Each bucket is then approximated using a small set of "exponentiated Chebyshev nodes," allowing for a more stable and efficient representation.
3. Universal Ridge Leverage Scores
The primary algorithmic innovation is the discovery of universal bounds for the ridge leverage scores of Vandermonde matrices. These bounds are "universal" because the sampling pattern depends solely on $n$ and $\epsilon$, rather than the specific entries of the matrix. This allows the algorithm to sample a tiny fraction of the matrix rows and columns to solve a sketched regression problem, identifying the optimal weights for the approximation in polylogarithmic time.
Key Results
Computational Complexity
The proposed algorithm runs in $\text{polylog}(n, 1/\epsilon)$ time, representing a massive improvement over the previous $O(n \log n)$ state-of-the-art. For a PSD Hankel matrix $H$, the algorithm returns a rank-$O(\log n \log(1/\epsilon))$ Hankel matrix $\widehat{H}$ such that: $$\|H - \widehat{H}\|_F \leq \epsilon \|H\|_F$$
Applications and Robustness
The authors demonstrate the versatility of their approach through several applications:
- Fast Polynomial Basis Transform: By plugging the algorithm into transforms used to convert between bases (e.g., Chebyshev to Legendre), the total runtime is improved from $O(n \log^4 n)$ to $O(n \log^3 n)$.
- Covariance Estimation: The results enable sample-efficient covariance estimation of Gaussian distributions with Hankel structure, requiring only $\text{poly}(\log n, 1/\epsilon)$ samples.
- Robustness to Noise: The algorithm is robust to non-Hankel noise; if a Hankel matrix $H$ is corrupted by an arbitrary noise matrix $E$, the algorithm still identifies a high-quality approximation of $H$.
Discussion and Limitations
While this work establishes a new frontier for sublinear matrix algorithms, several open questions remain. The current existence results and algorithms specifically target positive semidefinite (PSD) matrices; extending these guarantees to general, non-PSD Hankel matrices is a significant open challenge. Additionally, while the existence result holds for the spectral norm, the sublinear algorithm currently provides tight guarantees only for the Frobenius norm. Finally, there remains a small gap between the $O(\log n \log(1/\epsilon))$ upper bound and the $\Omega(\log n + \log(1/\epsilon))$ lower bound for the rank required to achieve a specific error $\epsilon$, suggesting further refinements in rank optimality are possible.
Summary updated