×

Bounds on the singular values of matrices with displacement structure. (English) Zbl 1441.15005

Authors’ 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<\varepsilon <1,\) by a rank \(O(\log n\log (1/\varepsilon))\) matrix. Analogous results are obtained for Pick, Cauchy, real Vandermonde, Löwner, and certain Krylov matrices.

MSC:

15A18 Eigenvalues, singular values, and eigenvectors
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
15B48 Positive matrices and their generalizations; cones of matrices
26C15 Real rational functions

Software:

FEAST; DLMF; RKToolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. I. Akhieser, Elements of the Theory of Elliptic Functions, Transl. Math. Monogr. 79, AMS, Providence RI, 1990. · Zbl 0694.33001
[2] A. C. Antoulas, D. C. Sorensen, and Y. Zhou, On the decay rate of Hankel singular values and related issues, Systems Control Lett., 46 (2002), pp. 323-342. · Zbl 1003.93024
[3] C. Badea and B. Beckermann, Spectral sets, in Handbook of Linear Algebra, 2nd ed., L. Hogben, ed., Chapman and Hall/CRC, Boca Raton, FL, 2013, Chapter 37.
[4] J. Baker, M. Embree, and J. Sabino, Fast singular value decay for Lyapunov solutions with nonnormal coefficients, SIAM J. Matrix. Anal. Appl., 36 (2015), pp. 656-668, https://doi.org/10.1137/140993867. · Zbl 1320.15011
[5] B. Beckermann, On the Numerical Condition of Polynomial Bases: Estimates for the Condition Number of Vandermonde, Krylov and Hankel Matrices, Habilitationsschrift, Universität Hannover, Hannover, Germany, 1996.
[6] B. Beckermann, The condition number of real Vandermonde, Krylov and positive definite Hankel matrices, Numer. Math., 85 (2000), pp. 553-577. · Zbl 0965.15003
[7] B. Beckermann, Singular Value Estimates for Matrices with Small Displacement Rank, Presentation at Structured Matrices, Cortona, 2004.
[8] B. Beckermann, An error analysis for rational Galerkin projection applied to the Sylvester equation, SIAM J. Numer. Anal., 49 (2011), pp. 2430-2450, https://doi.org/10.1137/110824590. · Zbl 1244.65057
[9] B. Beckermann and A. Gryson, Extremal rational functions on symmetric discrete sets and superlinear convergence of the ADI method, Constr. Approx., 32 (2010), pp. 393-428. · Zbl 1208.30036
[10] B. Beckermann and L. Reichel, Error estimates and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal., 47 (2009), pp. 3849-3883, https://doi.org/10.1137/080741744. · Zbl 1204.65041
[11] B. Beckermann and A. Townsend, On the singular values of matrices with displacement structure, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1227-1248, https://doi.org/10.1137/16M1096426. · Zbl 1386.15024
[12] P. Benner, R.-C. Li, and N. Truhar, On the ADI method for Sylvester equations, J. Comput. Appl. Math., 233 (2009), pp. 1035-1045. · Zbl 1176.65050
[13] M. Berljafa and S. Güttel, A Rational Krylov Toolbox for MATLAB, MIMS EPrint 2014.56, The University of Manchester, Manchester, UK, 2014.
[14] D. A. Bini, S. Massei, and L. Robol, On the decay of the off-diagonal singular values in cyclic reduction, Linear Algebra Appl., 519 (2017), pp. 27-53. · Zbl 1360.65118
[15] G. Birkhoff, R. S. Varga, and D. Young, Alternating direction implicit methods, Adv. Comput., 3 (1962), pp. 189-273. · Zbl 0111.31402
[16] D. Braess, Nonlinear Approximation Theory, Springer-Verlag, Berlin, Heidelberg, New York, 1986. · Zbl 0656.41001
[17] D. Braess, Rational approximation of Stieltjes functions by the Carathéodory-Fejér method, Constr. Approx., 3 (1987), pp. 43-50. · Zbl 0626.41007
[18] D. Braess and W. Hackbusch, Approximation of \(1/x\) by exponential sums in \([1,\infty)\), IMA J. Numer. Anal., 25 (2005), pp. 685-697. · Zbl 1082.65025
[19] D. Braess and W. Hackbusch, On the efficient computation of high-dimensional integrals and the approximation by exponential sums, in Multiscale, Nonlinear and Adaptive Approximation, Springer, 2009, pp. 39-74. · Zbl 1190.65036
[20] E. J. Candés and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), pp. 717-772. · Zbl 1219.90124
[21] M. Crouzeix, Bounds for analytic functions of matrices, Integral Equations Operator Theory, 48 (2004), pp. 461-477. · Zbl 1069.47004
[22] M. Crouzeix and C. Palencia, The numerical range is a \((1+\sqrt{2} )\)-spectral set, SIAM J. Matrix. Anal. Appl., 38 (2017), pp. 649-655, https://doi.org/10.1137/17M1116672. · Zbl 1368.47006
[23] A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, II, Appl. Comput. Harmon. Anal., 2 (1995), pp. 85-100. · Zbl 0822.65130
[24] D. Fasino and V. Olshevsky, How bad are symmetric Pick matrices?, in Structured Matrices in Mathematics, Computer Science, and Engineering I, Contemp. Math. 280, AMS, Providence, RI, 2001, pp. 301-312. · Zbl 0993.15004
[25] M. Fiedler, Special Matrices and Their Applications in Numerical Mathematics, Martinus Nijhoff, Leiden, The Netherlands, 1986. · Zbl 0677.65019
[26] D. Fortunato and A. Townsend, Fast Poisson Solvers for Spectral Methods, preprint, https://arxiv.org/abs/1710.11259, 2017.
[27] T. Ganelius, Rational functions, capacities and approximation, in Aspects of Contemporary Complex Analysis (Proc. NATO Adv. Study Inst., Univ. Durham, Durham, 1979), Academic Press, London, 1980, pp. 409-414. · Zbl 0495.30029
[28] W. Gautschi and G. Inglese, Lower bounds for the condition number of Vandermonde matrices, Numer. Math., 52 (1988), pp. 241-250. · Zbl 0646.15003
[29] E. S. Gawlik, Zolotarev Iterations for the Matrix Square Root, preprint, https://arxiv.org/abs/1804.11000, 2018.
[30] G. Golub and C. Van Loan, Matrix Computations, 4th ed., The Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[31] A. A. Gončar, Zolotarev problems connected with rational functions, Sb. Math., 7 (1969), pp. 623-635. · Zbl 0203.07302
[32] L. Grasedyck, Existence of a low rank or \(\mathcal{H}\) matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra. Appl., 11 (2004), pp. 371-389. · Zbl 1164.65381
[33] L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys., 73 (1987), pp. 325-348. · Zbl 0629.65005
[34] S. Güttel, E. Polizzi, P. T. P. Tang, and G. Viaud, Zolotarev quadrature rules and load balancing for the FEAST eigensolver, SIAM J. Sci. Comput., 37 (2015), A2100-A2122, https://doi.org/10.1137/140980090. · Zbl 1321.65055
[35] W. Hackbusch, A sparse matrix arithmetic based on \(\mathcal{H} \)-matrices. Part I: Introduction to \(\mathcal{H} \)-matrices, Computing, 62 (1999), pp. 89-108. · Zbl 0927.65063
[36] G. Heinig and K. Rost, Algebraic Methods for Toeplitz-Like Matrices and Operators, Oper. Theory Adv. Appl. 13, Birkhäuser Verlag, Basel, 1984. · Zbl 0549.15013
[37] D. Kressner, S. Massei, and L. Robol, Low-Rank Updates and a Divide-and-Conquer Method for Linear Matrix Equations, preprint, https://arxiv.org/abs/1712.04349, 2017. · Zbl 1448.65034
[38] V. I. Lebedev, On a Zolotarev problem in the method of alternating directions, USSR Comput. Math. Math. Phys., 17 (1977), pp. 58-76. · Zbl 0379.65032
[39] S. Massei, D. Palitta, and L. Robol, Solving rank-structured Sylvester and Lyapunov equations, SIAM J. Matrix. Anal. Appl., 39 (2018), pp. 1564-1590, https://doi.org/10.1137/17M1157155. · Zbl 1404.65036
[40] A. A. Medovikov and V. I. Lebedev, Variable time steps optimization of \(L_\omega \)-stable Crank-Nicolson method, Russian J. Numer. Anal. Math. Model., 20 (2005), pp. 283-303. · Zbl 1080.65077
[41] A. Moitra, Super-resolution, extremal functions and the condition number of Vandermonde matrices, in Proceedings of the 47th Annual ACM Symposium on Theory of Computing, ACM, 2015, pp. 821-830. · Zbl 1321.68421
[42] M. Morf, Fast Algorithms for Multivariable Systems, Ph.D. thesis, Stanford University, Stanford, CA, 1974.
[43] Y. Nakatsukasa and R. W. Freund, Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of Zolotarev’s functions, SIAM Rev., 58 (2016), pp. 461-493, https://doi.org/10.1137/140990334. · Zbl 1383.15012
[44] F. W. J. Olver, D. W. Lozier, R. F. Boisvert, and C. W. Clark, NIST Handbook of Mathematical Functions, Cambridge University Press, Cambridge, UK, 2010. · Zbl 1198.00002
[45] I. V. Oseledets, Lower bounds for separable approximations of the Hilbert kernel, Sb. Math., 198 (2007), pp. 425-432. · Zbl 1151.41016
[46] V. Y. Pan, How bad are Vandermonde matrices?, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 676-694, https://doi.org/10.1137/15M1030170. · Zbl 1382.15008
[47] V. Peller, Hankel Operators and Their Applications, Springer, New York, 2012.
[48] T. Penzl, Eigenvalue decay bounds for solutions of Lyapunov equations: The symmetric case, Systems Control Lett., 40 (2000), pp. 130-144. · Zbl 0977.93034
[49] J. Sabino, Solution of Large-Scale Lyapunov Equations via the Block Modified Smith Method, Ph.D. thesis, Rice University, Houston, TX, 2006.
[50] E. B. Saff and V. Totik, Logarithmic Potentials with External Fields, Grundlehren Math. Wiss. 316, Springer, Heidelberg, 1997. · Zbl 0881.31001
[51] T. Shi and A. Townsend, On the Numerical Ranks of Tensors, preprint, https://arxiv.org/abs/1812.09576, 2018.
[52] V. Simoncini, Computational methods for linear matrix equations, SIAM Rev., 58 (2016), pp. 377-441, https://doi.org/10.1137/130912839. · Zbl 1386.65124
[53] G. Starke, Near-circularity for the rational Zolotarev problem in the complex plane, J. Approx. Theory, 70 (1992), pp. 115-130. · Zbl 0758.41019
[54] R. C. Thompson, Principal submatrices IX: Interlacing inequalities for singular values of submatrices, Linear Algebra Appl., 5 (1972), pp. 1-12. · Zbl 0252.15009
[55] A. Townsend, Computing with Functions in Two dimensions, D.Phil. thesis, University of Oxford, Oxford, UK, 2014.
[56] A. Townsend, M. Webb, and S. Olver, Fast polynomial transforms based on Toeplitz and Hankel matrices., Math. Comp., 87 (2018), pp. 1913-1934. · Zbl 1478.65147
[57] A. Townsend and H. Wilber, On the singular values of matrices with high displacement rank, Linear Algebra Appl., 548 (2018), pp. 19-41. · Zbl 1446.65022
[58] N. Truhar, Z. Tomljanović, and R.-C. Li, Analysis of the solution of the Sylvester equation using low-rank ADI with exact shifts, Systems Control Lett., 59 (2010), pp. 248-257. · Zbl 1193.65045
[59] N. Truhar and K. Veselić, Bounds on the trace of a solution to the Lyapunov equation with a general stable matrix, Systems Control Lett., 56 (2007), pp. 493-503. · Zbl 1117.93066
[60] E. E. Tyrtyshnikov, Mosaic-skeleton approximations, Calcolo, 33 (1996), pp. 47-57. · Zbl 0906.65048
[61] E. E. Tyrtyshnikov, More on Hankel Matrices, manuscript, 1998.
[62] E. E. Tyrtyshnikov, How bad are Hankel matrices?, Numer. Math., 67 (1994), pp. 261-269. · Zbl 0797.65039
[63] E. L. Wachspress, Trail to a Lyapunov equation solver, Comput. Math. Appl., 55 (2008), pp. 1653-1659. · Zbl 1139.65033
[64] H. Wilber, A. Townsend, and G. B. Wright, Computing with functions in spherical and polar geometries II. The disk, SIAM J. Sci. Comput., 39 (2017), C238-C262, https://doi.org/10.1137/16M1070207. · Zbl 1368.65026
[65] H. S. Wilf, Finite Sections of Some Classical Inequalities, Springer, Heidelberg, 1970. · Zbl 0199.38301
[66] E. I. Zolotarev, Application of elliptic functions to questions of functions deviating least and most from zero, Zap. Imp. Akad. Nauk. St. Petersburg, 30 (1877), pp. 1-59. · JFM 09.0343.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.