When is a matrix unitary or Hermitian plus low rank?
Del Corso G. M., Poloni F., Robol L., Vandebril R.
Unitary plus low rank Rank-structured matrices Mathematics - Numerical Analysis 65FXX Algebra and Number Theory 15B10 FOS: Mathematics Hermitian plus low rank 15B57 Applied Mathematics Numerical Analysis (math.NA)
Hermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low-rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low-rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low-rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew-Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low-rank perturbation. Numerical tests prove that this straightforward algorithm is effective.
Source: Numerical linear algebra with applications 26 (2019). doi:10.1002/nla.2266
Publisher: Wiley., Chichester, West Sussex, Regno Unito
[9] D. A. Bini, P. Boito, Y. Eidelman, L. Gemignani, and I. Gohberg. A fast implicit QR eigenvalue algorithm for companion matrices. Linear Algebra and its Applications, 432(8):2006- 2031, 2010.
[10] D. A. Bini, Y. Eidelman, L. Gemignani, and I. Gohberg. Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices. SIAM Journal on Matrix Analysis and Applications, 29(2):566-585, 2007.
[11] D. A. Bini and L. Robol. On a class of matrix pencils and ℓ-ifications equivalent to a given matrix polynomial. Linear Algebra and its Applications, 502:275-298, 2016.
[12] D. A. Bini and L. Robol. Quasiseparable Hessenberg reduction of real diagonal plus low rank matrices and applications. Linear Algebra and its Applications, 502:186-213, 2016.
[13] P. Boito, Y. Eidelman, and L. Gemignani. Implicit QR for rank-structured matrix pencils. BIT, 54:85-111, 2013.
[14] P. Boito, Y. Eidelman, L. Gemignani, and I. Gohberg. Implicit QR with compression. Indagationes Mathematicae, 23(4):733-761, 2012.
[15] A. Bunse-Gerstner and L. Elsner. Schur parameter pencils for the solution of the unitary eigenproblem. Linear Algebra and its Applications, 154-156:741-778, 1991.
[16] M. J. Cantero, L. Moral, and L. Vel´azquez. Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle. Linear Algebra and its Applications, 362:29-56, 2003.
[17] T. F. Chan. Rank revealing QR factorizations. Linear Algebra and its Applications, 88/89:67-82, 1987.
[18] S. Chandrasekaran and M. Gu. Fast and stable eigendecomposition of symmetric banded plus semi-separable matrices. Linear Algebra and its Applications, 313:107-114, 2000.
[19] S. Chandrasekaran, M. Gu, J. Xia, and J. Zhu. A fast QR algorithm for companion matrices. Operator Theory: Advances and Applications, 179:111-143, 2007.
[20] F. De Ter´an, F. M. Dopico, and J. P´erez. Condition numbers for inversion of fiedler companion matrices. Linear Algebra Appl., 439(4):944-981, 2013.
[21] G. M. Del Corso, F. Poloni, L. Robol, and R. Vandebril. Factoring block Fiedler Companion Matrices. In Proceedings of the Structured Matrices in Numerical Linear Algebra: Analysis, Algorithms and Applications conference in Cortono, Italy, 2017. Springer, to appear.
[22] S. Delvaux. Rank Structured Matrices. PhD thesis, Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3000 Leuven (Heverlee), Belgium, June 2007.
[23] J. W. Demmel, O. A. Marques, B. N. Parlett, and C. Vo¨mel. Performance and accuracy of LAPACK's symmetric tridiagonal eigensolvers. SIAM Journal on Scientific Computing, 30(3):1508-1526, 2008.
[24] I. S. Dhillon, B. N. Parlett, and C. Vo¨mel. The design and implementation of the MRRR algorithm. ACM Transactions on Mathematical Software, 32(4):533-560, Dec. 2006.
[25] Y. Eidelman, L. Gemignani, and I. C. Gohberg. Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbation. Numerical Algorithms, 47(3):253-273, March 2008.
[26] L. Elsner and K. D. Ikramov. Normal matrices: An update. Linear Algebra and its Applications, 285:291-303, 1998.
[27] J. N. Franklin. Matrix Theory. Dover publications inc., Mineola, New York, USA, 2012.
[28] L. Gemignani. A unitary Hessenberg QR-based algorithm via semiseparable matrices. Journal of Computational and Applied Mathematics, 184:505-517, 2005.
[29] L. Gemignani and L. Robol. Fast Hessenberg reduction of some rank structured matrices. SIAM Journal on Matrix Analysis and Applications, 38(2):574-598, 2017.
[30] W. B. Gragg. The QR algorithm for unitary Hessenberg matrices. Journal of Computational and Applied Mathematics, 16:1-8, 1986.
[31] W. B. Gragg and L. Reichel. A divide and conquer method for unitary and orthogonal eigenproblems. Numerische Mathematik, 57:695-718, 1990.
[32] R. Grone, C. R. Johnson, E. M. Sa, and H. Wolkowicz. Normal matrices. Linear Algebra and its Applications, 87:213-225, 1987.
[33] N. Halko, P. G. Martinsson, and J. A. Tropp. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217-288, 2011.
[34] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, second edition, 2013.
[35] B. N. Parlett. The Symmetric Eigenvalue Problem, volume 20 of Classics in Applied Mathematics. SIAM, Philadelphia, Pennsylvania, USA, 1998.
[36] L. Robol. Exploiting rank structures for the numerical treatment of matrix polynomials. PhD thesis, Scuola Normale Superiore di Pisa, 2015.
[37] L. Robol and R. Vandebril. Efficient Ehrlich-Aberth iteration for finding intersections of interpolating polynomials and rational functions. Linear Algebra and its Applications, 542:282-309, 2018.
[38] L. Robol, R. Vandebril, and P. V. Dooren. A framework for structured linearizations of matrix polynomials in various bases. SIAM Journal on Matrix Analysis and Applications, 38(1):188-216, 2017.
[39] R. C. Thompson. Principal submatrices. IX. Interlacing inequalities for singular values of submatrices. Linear Algebra and its Applications, 5:1-12, 1972.
[40] M. Van Barel, R. Vandebril, P. Van Dooren, and K. Frederix. Implicit double shift QRalgorithm for companion matrices. Numerische Mathematik, 116(2):177-212, 2010.
[41] R. Vandebril and G. M. Del Corso. An implicit multishift QR-algorithm for Hermitian plus low rank matrices. SIAM Journal on Scientific Computing, 32(4):2190-2212, 2010.
[42] R. Vandebril, M. Van Barel, and N. Mastronardi. Matrix Computations and Semiseparable Matrices: Linear Systems, volume 1. JHU Press, 2007.
[43] J. von Neumann. Allgemeine Eigenwerttheorie Hermitescher Funktionaloperatoren. Mathematische Annalen, 102:49-131, 1930.
[44] D. S. Watkins. The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. SIAM, Philadelphia, USA, 2007.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:424802,
title = {When is a matrix unitary or Hermitian plus low rank?},
author = {Del Corso G. M. and Poloni F. and Robol L. and Vandebril R.},
publisher = {Wiley., Chichester, West Sussex, Regno Unito},
doi = {10.1002/nla.2266 and 10.48550/arxiv.1811.05854},
journal = {Numerical linear algebra with applications},
volume = {26},
year = {2019}
}
0000-0002-6545-1748ISTI Repository
DOI
10.1002/nla.2266
10.48550/arxiv.1811.05854
arXiv.org e-Print Archive
Numerical Linear Algebra with Applications
Lirias
onlinelibrary.wiley.com