Source-linked AI summary
On the singular values of matrices with displacement structure
Bernhard Beckermann, Alex Townsend
TL;DR
Explaining why displacement-structured matrices often support effective low-rank methods is theoretically challenging. The paper uses extremal rational functions to derive explicit singular-value bounds, extending Zolotarev-number techniques beyond condition numbers. The bounds support rapid decay for structured matrix classes, with spectral separation determining an important scope condition.
Problem
Low-rank techniques are used on matrices with rapidly decaying singular values, but fully explaining their effectiveness theoretically is challenging.
Source: §1 · p. 1Method
The paper uses an extremal rational-function problem to derive explicit singular-value bounds for matrices with displacement structure.
Source: §1 · p. 1Results
The bounds extend Zolotarev-number applications from condition numbers to singular values and establish rapid decay for many displacement-structured matrices.
Source: §1 · pp. 2–3Takeaways & Limitations
Real positive definite Hankel matrices have ϵ-rank at most O(log n log(1/ϵ)), supporting low-rank techniques for these matrices.
Source: §5.2 · p. 18Low-rank behavior is not guaranteed by displacement structure alone; for normal defining matrices, the eigenvalues should be well-separated.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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\|_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\"{o}wner, and certain Krylov matrices.
1. Introduction.
The paper derives explicit singular-value bounds for matrices with displacement structure using extremal rational functions, extending Zolotarev-number techniques beyond condition-number estimates. These bounds explain when such matrices admit low-rank approximations, while the spectral properties of the defining matrices determine whether rapid decay should be expected.
1. Introduction.
- Displacement structure includes Toeplitz, Hankel, Cauchy, Krylov, Vandermonde, Pick, Sylvester, and Lowner matrices, with fast algorithms derived by exploiting their Sylvester equation.The equation represents X through low-rank factors M and N.Source: §1 · p. 1
- Displacement structure alone does not ensure numerical low rank: normal defining matrices call for separated eigenvalues, while non-normal ones call for separated spectral sets.The paper notes full-rank identity and exchange matrices as counterexamples.Source: §1 · p. 2
- For real positive definite Hankel matrices, the ϵ-rank is O(log n log(1/ϵ)); other classes have bounds in log γ or log n, with mild separation conditions for Cauchy and Lowner matrices.Table 1.2 summarizes these upper-bound forms.Source: §1 · p. 2, Table 1.2 · p. 3
- Explicit Zolotarev-number bounds extend prior condition-number work to singular values and justify low-rank approximation for many matrices with displacement structure.The bounds are particularly tight for σ_j when j is small relative to n.Source: §1 · pp. 1–3
- Zolotarev numbers arise from extremal rational approximation and decay rapidly for disjoint, well-separated sets, making careful selection of the sets central to explicit bounds.The paper uses complex analysis and Möbius transformations to make the resulting bounds explicit.Source: §1 · pp. 3–4
2. The singular values of matrices with displacement structure and Zolotarev numbers.
For matrices satisfying a Sylvester displacement equation, the paper bounds singular-value decay using Zolotarev numbers on sets containing the defining matrices' spectra. The bounds extend from normal matrices to certain non-normal matrices and connect to rational-function choices in the ADI method.
2. The singular values of matrices with displacement structure and Zolotarev numbers.
- An extremal rational function yields a rank-νk component in the proof, which combines with a best rank-(j−1) approximation to bound the next singular values.The polynomial expression p(A)Xq(B) − q(A)Xp(B) has rank at most νk.Source: §2 · p. 5
- With normal A and B, singular values decay at least as fast as Z_k(σ(A), σ(B)); disjoint, well-separated spectra make this bound decay rapidly.The theorem applies when the matrix satisfies the stated displacement equation and the spectra lie in E and F.Source: §2 · pp. 4–5
- The same rational-function zeros and poles can serve as ADI shifts: after k steps, the method constructs a rank-νk approximation with error bounded by Z_k(E,F)σ_1(X).The paper gives this as an analogous interpretation of the proof.Source: §2 · pp. 5–6
- For non-normal A and B with K-spectral sets E and F, the bound becomes σ_(j+νk)(X) ≤ K^2 Z_k(E,F) σ_j(X).The extension assumes a fixed K > 0 for both spectral sets.Source: §2 · p. 6
3. Zolotarev numbers.
Section 3 derives explicit bounds for Z_k on separated symmetric intervals and constructs extremal rational functions with specified symmetry properties. It also corrects an earlier infinite-product formula and explains why sharp Z_k bounds do not guarantee sharp singular-value bounds.
3. Zolotarev numbers.
- Theorem 3.1 gives a corrected infinite-product formula for Z_k after correcting typos in Lebedev’s formula, which had been copied elsewhere.The paper notes that erroneous related bounds had also been repeated in other works.Source: §3 · pp. 6–7
- The proof derives the product formula using a product representation for the inverse of μ and classical theta-function identities.It also uses Gauss’ and Landen’s transformations.Source: §3 · p. 7
- Z_k ≤ 4ρ^-2k is asymptotically sharp for all k, and improves the earlier upper-bound constant from 16 to 4.The sharpness applies to the geometric decay rate and the constant when the bound is required to hold for all k.Source: §3 · pp. 7–8
- Although the Z_k upper bound is asymptotically sharp, the resulting singular-value inequalities are usually not; sharper bounds may require discrete Zolotarev numbers.The paper identifies these as Z_k(σ(A), σ(B)).Source: §3 · p. 8
- An extremal R in R_k,k can be derived from best rational approximation of the sign function and satisfies R(−z) = 1/R(z) and |R(iz)| = 1 for real z.The approximation is on [−b, −a] ∪ [a, b].Source: §3 · p. 8
- A weaker bound omitting the Grötzsch ring function is used later for explicit singular-value estimates on Pick, Cauchy, and L"owner matrices.The paper also uses it in Section 5.Source: §3 · pp. 6, 8, 10
4. The decay of the singular values of Pick, Cauchy, and L¨owner ma-
This section applies singular-value bounds based on displacement structure to Pick, Cauchy, and L¨owner matrices. The bounds yield low-rank approximation results under class-specific separation conditions.
4. The decay of the singular values of Pick, Cauchy, and L¨owner ma-
- The section constructs displacement equations with low-rank right-hand sides and seeks separated real spectral intervals to apply the singular-value bounds.This approach works under mild separation conditions for Pick, Cauchy, and L¨owner matrices.Source: §4 · p. 10
4.1. Pick matrices.
- For Pick matrices, the bounds imply ǫ-rank O(log(b/a) log(1/ǫ)); they are usually ill-conditioned unless b/a is large and/or n is small.The plotted bound has a stepping behavior because the j = 1 inequality bounds only odd-indexed singular values; the tested matrices also show stepping, for which the authors offer little explanation.Source: §4.1 · pp. 10–11
4.2. Cauchy matrices.
- For Cauchy matrices with disjoint intervals, singular-value decay depends on the absolute cross-ratio of the interval endpoints, not their separation distance.The Hilbert matrix is a special case with exponentially decaying singular values and ǫ-rank at most ⌈log(8n−4) log(4/ǫ)/π2⌉.Source: §4.2 · pp. 12–13
4.3. L¨owner matrices.
- For L¨owner matrices, disjoint intervals permit singular-value bounds in terms of the endpoint cross-ratio; many have ǫ-rank O(log γ log(1/ǫ)) and are exponentially ill-conditioned.The separation condition is an additional assumption for applying the section’s methodology.Source: §4.3 · p. 14
5. The singular values of Krylov, Vandermonde, and Hankel matrices.
Section 5 develops singular-value bounds for Krylov matrices with Hermitian arguments and applies them to real Vandermonde matrices and real positive definite Hankel matrices. The Hankel bounds imply logarithmic-scale approximate rank, while the Krylov analysis yields a geometric bound with a stated limitation for larger singular-value indices.
5. The singular values of Krylov, Vandermonde, and Hankel matrices.
- The section addresses the more challenging singular-value bounds for Krylov matrices with Hermitian arguments, real Vandermonde matrices, and real positive definite Hankel matrices.For the Krylov analysis, the spectra of A and Q are disjoint when n is even; odd n is handled using the preceding relation for the matrix with its last column removed.Source: §5 · p. 14, §5.1 · pp. 14–15
5.1. Krylov and real Vandermonde matrices.
- For Krylov matrices with Hermitian arguments, (5.5) bounds singular values with a log n dependence; the analysis realizes geometric decay even though decay can be supergeometric.The bound is only reasonable for σ_j when j is small relative to n; improved bounds may be possible for j/n→c in (0,1) using discrete Zolotarev numbers.Source: §5.1 · pp. 16–17
- The Krylov bound also applies to Vandermonde matrices with real abscissas, which therefore have rapidly decaying singular values and are exponentially ill-conditioned.The section identifies real-abscissa Vandermonde matrices as Krylov matrices with Hermitian arguments.Source: §5.1 · p. 17
5.2. Real positive definite Hankel matrices.
- Real positive definite Hankel matrices have ǫ-rank O(log n log(1/ǫ)), and the results extend to real positive semidefinite Hankel matrices by approximation.The argument uses a Fiedler factorization: Hankel singular values are squares of those of an associated Krylov matrix with Hermitian argument.Source: §5.2 · pp. 18–19
Appendix A. Typos in an infinite product formula.
Appendix A revisits erroneous infinite product formulas associated with the Zolotarev problem and derives a corrected formula for the related sign-approximation problem. It gives corrected bounds and notes that further estimates can be obtained by retaining more product terms.
Appendix A. Typos in an infinite product formula.
- For 0 < η < 1, an infinite product formula for E_k([η, 1]) correcting [27, (1.11)] is obtained by taking square roots and setting a/b = η in Theorem 3.1.Source: Appendix A · p. 21
- Taking more terms from the infinite product yields more refined estimates than the stated bounds.Source: Appendix A · pp. 21–22
- Earlier lower and upper bounds for E_2k,2k and E_2k+1,2k+1 were claimed using erroneous infinite product formulas.The cited claims are [24, (4.1)] and [30, (3.8)], respectively.Source: Appendix A · p. 21