Abstract
Matrices with displacement structure such as Pick, Vandermonde, and Hankel matrices appear in a diverse range of applications. In this paper, we use an extremal problem involving rational functions to derive explicit bounds on the singular values of such matrices. For example, we show that the $k$th singular value of a real $n\times n$ positive definite Hankel matrix, $H_n$, is bounded by $C\rho^{-k/\log n}\|H_n\|_2$ with explicitly given constants $C>0$ and $\rho>1$, where $\|H_n\|_2$ is the spectral norm. This means that a real $n\times n$ positive definite Hankel matrix can be approximated, up to an accuracy of $\epsilon\|H_n\|_2$ with $0<\epsilon<1$, by a rank $\mathcal{O}(\log n\log(1/\epsilon) )$ matrix. Analogous results are obtained for Pick, Cauchy, real Vandermonde, Löwner, and certain Krylov matrices.
Introduction
In computational mathematics, many structured matrices are technically full rank but "numerically low rank." This means their singular values decay so rapidly that the matrix can be approximated by a much smaller one without losing significant precision. This property is the "secret sauce" behind fast algorithms for particle simulations, model reduction, and solving differential equations.
While practitioners have long exploited this decay, providing explicit and tight theoretical bounds has been challenging. This paper bridges the gap by focusing on matrices with displacement structure, defined by their relationship to a Sylvester matrix equation: $AX - XB = MN^*$. The goal is to explain exactly how fast the singular values $\sigma_k$ drop off based on the properties of $A$ and $B$.
Methods
The authors employ a beautiful intersection of linear algebra and complex approximation theory. Their primary tool is the Zolotarev number $Z_k(E, F)$, which measures how well two disjoint sets in the complex plane ($E$ and $F$) can be separated by a rational function of degree $k$.
The key steps include:
- The Displacement Link: Proving a fundamental theorem (Theorem 2.1) that bounds the $(j + \nu k)$-th singular value of a matrix $X$ by the $j$-th singular value multiplied by a Zolotarev number, where $\nu$ is the displacement rank.
- Spectral Mapping: Using Möbius transformations to map the eigenvalues (spectra) of the matrices $A$ and $B$ onto real intervals or complex sets where Zolotarev numbers are well-understood.
- Formula Correction: The authors identify and correct a long-standing typo in an infinite product formula for Zolotarev numbers originally published by Lebedev in 1977.
Key Results
The paper provides a comprehensive "cheat sheet" of bounds for various matrix classes, linking the decay rate of singular values directly to the separation of the spectra of $A$ and $B$. If the eigenvalues of $A$ and $B$ are far apart in the complex plane, the singular values of $X$ plummet instantly.
Notable insights include:
- Logarithmic Rank Growth: For many common matrices (like positive definite Hankel matrices), the "$\epsilon$-rank" (the rank needed to approximate the matrix within error $\epsilon$) only grows as $O(\log n \log(1/\epsilon))$. This explains why low-rank methods remain efficient even as the matrix size $n$ becomes very large.
- Numerical Tightness: The derived bounds are shown to be remarkably tight, especially for the largest singular values, which are most critical for low-rank approximation.
- Fiedler Factorization: To handle Hankel matrices, the authors use a Fiedler factorization to relate them to Krylov matrices, allowing the same displacement-based bounds to apply.
Limitations and Future Work
While the current analysis captures geometric decay, the authors note that for some matrices (like Krylov matrices), the actual decay is "supergeometric" (faster than any geometric rate). Future work may involve using "discrete" Zolotarev numbers (based on specific finite sets of eigenvalues) to yield even tighter bounds, though they are much harder to compute. Additionally, extending these results to non-normal matrices using $K$-spectral sets involves constants that might be difficult to estimate in some cases.
Summary updated