On the singular values of matrices with displacement structure

DOI10.1137/16M1096426MaRDI QIDQ4588942zbMATH OpenOpenAlexFDO

Authors Alex Townsend, Bernhard Beckermann

Publication date 6 November 2017

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.09494

zbMATH Keywords

displacement structurerationalsingular valueszolotarev

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Real rational functions (26C15)

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 $nimesn$ positive definite Hankel matrix, $H_n$, is bounded by $Ch{o}^{-k/logn}|H{|}_2$ with explicitly given constants $C>0$ and $ho>1$, where $|H_n{|}_2$ is the spectral norm. This means that a real $nimesn$ positive definite Hankel matrix can be approximated, up to an accuracy of $epsilon|H_n{|}_2$ with $0<epsilon<1$, by a rank $mathcalO(lognlog(1/epsilon))$ matrix. Analogous results are obtained for Pick, Cauchy, real Vandermonde, L"{o}wner, and certain Krylov matrices.

Recommendations

• Bounds on the singular values of matrices with displacement structure
• On singular values of Hankel operators of finite rank
• On the singular values of matrices with high displacement rank
• Displacement structure for Hankel, Vandermonde, and related (derived) matrices
• Publication:3497210

Cites work

• A fast algorithm for particle simulations
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• Algebraic methods for Toeplitz-like matrices and operators
• Alternating Direction Implicit Methods
• An error analysis for rational Galerkin projection applied to the Sylvester equation
• Analysis of the solution of the Sylvester equation using low-rank ADI with exact shifts
• Approximation of 1/x by exponential sums in [1, ∞)
• Bounds for analytical functions of matrices
• Bounds on the trace of a solution to the Lyapunov equation with a general stable matrix
• Computational Methods for Linear Matrix Equations
• Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions
• Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case
• Error Estimates and Evaluation of Matrix Functions via the Faber Transform
• Exact matrix completion via convex optimization
• Existence of a low rank or ℋ︁‐matrix approximant to the solution of a Sylvester equation
• Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method
• Fast polynomial transforms based on Toeplitz and Hankel matrices
• Fast singular value decay for Lyapunov solutions with nonnormal coefficients
• How bad are Hankel matrices?
• How bad are symmetric Pick matrices?
• How bad are Vandermonde matrices?
• scientific article; zbMATH DE number 4071579 (Why is no real title available?)
• scientific article; zbMATH DE number 4109935 (Why is no real title available?)
• scientific article; zbMATH DE number 46496 (Why is no real title available?)
• scientific article; zbMATH DE number 1875877 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 2204499 (Why is no real title available?)
• scientific article; zbMATH DE number 3317936 (Why is no real title available?)
• Lower bounds for separable approximations of the Hilbert kernel
• Lower bounds for the condition number of Vandermonde matrices
• NIST handbook of mathematical functions
• On a Zolotarev problem in the method of alternating directions
• On the decay of the off-diagonal singular values in cyclic reduction
• On the decay rate of Hankel singular values and related issues
• Principal submatrices. IX: Interlacing inequalities for singular values of submatrices
• Rational approximation of Stieltjes functions by the Carathéodory-Fejér method
• The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
• The numerical range is a \((1+\sqrt{2})\)-spectral set
• ZOLOTAREV PROBLEMS CONNECTED WITH RATIONAL FUNCTIONS
• Zolotarev quadrature rules and load balancing for the FEAST eigensolver

Cited in

(54)

• On the singular values of matrices with high displacement rank
• Combined error estimates for local fluctuations of SPDEs
• Computation of adaptive Fourier series by sparse approximation of exponential sums
• Approximating the \(p\)th root by composite rational functions
• Numerical computation and new output bounds for time-limited balanced truncation of discrete-time systems
• New applications of matrix methods
• Sampling the flow of a bandlimited function
• Decay of singular values for infinite-dimensional systems with Gevrey regularity
• Low-rank updates and divide-and-conquer methods for quadratic matrix equations
• Inexact methods for the low rank solution to large scale Lyapunov equations
• Galerkin trial spaces and Davison-Maki methods for the numerical solution of differential Riccati equations
• Application of a complete radiation boundary condition for the Helmholtz equation in locally perturbed waveguides
• Balanced truncation for discrete time-delay systems via the interpretation of system energy
• Low-rank parareal: a low-rank parallel-in-time integrator
• 6 The Loewner framework for system identification and reduction
• Asymptotic relationships between singular values of structured matrices similarly generated by different formal expansions of a rational function
• Displacement structure approach to singular root distribution problems: the unit circle case
• Solving rank-structured Sylvester and Lyapunov equations
• Rational minimax approximation via adaptive barycentric representations
• Fast matrix multiplication and its algebraic neighbourhood
• Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
• Fast polynomial transforms based on Toeplitz and Hankel matrices
• Displacement structure approach to singular root distribution problems: the imaginary axis case
• Rational Spectral Filters with Optimal Convergence Rate
• On the feasibility of extrapolation of the complex electromagnetic permittivity function using Kramers-Kronig relations
• How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?
• Why Are Big Data Matrices Approximately Low Rank?
• Pseudospectra of Loewner matrix pencils
• scientific article; zbMATH DE number 7625195 (Why is no real title available?)
• Reconstructing Stieltjes functions from their approximate values: a search for a needle in a haystack
• On the singular values of the Hankel matrix with application in singular spectrum analysis
• A low-rank technique for computing the quasi-stationary distribution of subcritical Galton-Watson processes
• Approximate residual-minimizing shift parameters for the low-rank ADI iteration
• Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices
• Zolotarev iterations for the Matrix square Root
• Bounds on the singular values of matrices with displacement structure
• Computing with functions in spherical and polar geometries. II: The disk
• Fast computation of spectral projectors of banded matrices
• On the Compressibility of Tensors
• Data Recovery from Cauchy Measurements in Transient Heat Transfer
• Low-rank tensor structure preservation in fractional operators by means of exponential sums
• Fast randomized numerical rank estimation for numerically low-rank matrices
• An Efficient Block Rational Krylov Solver for Sylvester Equations with Adaptive Pole Selection
• On the emergence of numerical instabilities in next generation reservoir computing
• \(S^{\top}S\)-SVD via sketching and the nearest \(S^{\top}S\)-orthogonal matrix
• Non-asymptotic error analysis of subspace identification for deterministic systems
• An optimal complexity spectral solver for the Poisson equation
• Superfast direct inversion of the nonuniform discrete Fourier transform via hierarchically semiseparable least squares
• A nested divide-and-conquer method for tensor Sylvester equations with positive definite hierarchically semiseparable coefficients
• Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
• Conditioning of solutions to the Sylvester equation
• Minimal residual rational Krylov subspace method for sequences of shifted linear systems
• Newtonian potentials of Legendre polynomials on rectangles have displacement structure
• Finite sample analysis of subspace identification for autonomous stochastic systems

Describes a project that uses

Uses Software

• FEAST
• RKToolbox
• DLMF

This page was built for publication: On the singular values of matrices with displacement structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4588942)