×

Gradient flow methods for matrix completion with prescribed eigenvalues. (English) Zbl 1055.15026

Matrix completion with prescribed eigenvalues is a special type of inverse eigenvalue problem which is a challenging problem both theoretically and computationally. In the present paper, the completion problem is recast as one of minimizing the distance between the isospectral matrices with prescribed eigenvalues and the affined matrices with prescribed entries.
In the first part, the authors have chronicled some major developments on this subject in the literature.
In the second part, they have proposed a dynamical system of which the trajectory allows one to complete the construction of a matrix numerically even under the situation when no existence theory is available at all.
In the third part, numerical experiments seem to suggest that the idea of gradient flow approach can serve as a reasonable means to tackle the most general inverse eigenvalue problems with prescribed entries where the prescribed entries are at arbitrary locations with arbitrary cardinalities.

MSC:

15A29 Inverse problems in linear algebra
15A18 Eigenvalues, singular values, and eigenvectors
65F18 Numerical solutions to inverse eigenvalue problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boley, D.; Golub, G. H., A survey of matrix inverse eigenvalue problems, Inverse Problems, 3, 4, 595-622 (1987) · Zbl 0633.65036
[2] Chu, M. T., Constructing a Hermitian matrix from its diagonal entries and eigenvalues, SIAM J. Matrix Anal. Appl., 16, 207-217 (1995) · Zbl 0815.65052
[3] Chu, M. T., Inverse eigenvalue problems, SIAM Rev., 40, 1, 1-39 (1998), electronic · Zbl 0915.15008
[4] Chu, M. T., On constructing matrices with prescribed singular values and diagonal elements, Linear Algebra Appl., 288, 1-3, 11-22 (1999) · Zbl 0933.65043
[5] Chu, M. T.; Golub, G., Structured inverse eigenvalue problems, Acta Numer., 11, 1-71 (2002) · Zbl 1105.65326
[6] de Oliveira, G. N., Note on an inverse characteristic value problem, Numer. Math., 15, 345-347 (1970) · Zbl 0202.03504
[7] de Oliveira, G. N., Matrices with prescribed entries and eigenvalues, I, Proc. Amer. Math. Soc., 37, 2, 380-386 (1973) · Zbl 0231.15013
[8] de Oliveira, G. N., Matrices with prescribed entries and eigenvalues, II, SIAM J. Appl. Math., 24, 414-417 (1973) · Zbl 0235.15005
[9] de Oliveira, G. N., Matrices with prescribed entries and eigenvalues, III, Arch. Math. (Basel), 26, 57-59 (1975) · Zbl 0302.15013
[10] Friedland, S., Matrices with prescribed off-diagonal elements, Israel J. Math., 11, 184-189 (1972) · Zbl 0252.15004
[11] Friedland, S., Inverse eigenvalue problems, Linear Algebra Appl., 17, 1, 15-51 (1977) · Zbl 0358.15007
[12] Friedland, S.; Nocedal, J.; Overton, M. L., Four quadratically convergent methods for solving inverse eigenvalue problems, (in: Numerical Analysis (Dundee, 1985) (1986), Longman Sci. Tech: Longman Sci. Tech Harlow), 47-65 · Zbl 0642.65025
[13] Hadeler, K. P., Ein inverse eigenwertproblem, Linear Algebra Appl., 1, 83-101 (1968) · Zbl 0159.03602
[14] D. Hershkowitz, Existence of matrices satisfying prescribed conditions, Master’s thesis, Technion, Haifa, 1978; D. Hershkowitz, Existence of matrices satisfying prescribed conditions, Master’s thesis, Technion, Haifa, 1978
[15] Hershkowitz, D., Existence of matrices with prescribed eigenvalues and entries, Linear and Multilinear Algebra, 14, 315-342 (1983) · Zbl 0529.15005
[16] Horn, A., Doubly stochastic matrices and the diagonal of a rotation matrix, Amer. J. Math., 76, 620-630 (1954) · Zbl 0055.24601
[17] Horn, R. A.; Johnson, C. R., Matrix Analysis (1991), Cambridge University Press: Cambridge University Press New York · Zbl 0729.15001
[18] Ikramov, K. D.; Chugunov, V. N., Inverse matrix eigenvalue problems, J. Math. Sci. (New York), 98, 1, 51-136 (2000) · Zbl 0954.65032
[19] London, D.; Mine, H., Eigenvalues of matrices with prescribed entries, Proc. Amer. Math. Soc., 34, 8-14 (1972) · Zbl 0215.08603
[20] Marshall, A. W.; Olkin, I., Inequalities: Theory of Majorization and Its Applications (1979), Academic Press: Academic Press New York · Zbl 0437.26007
[21] Mirsky, L., Matrices with prescribed characteristic roots and diagonal elements, J. London Math. Soc., 33, 14-21 (1958) · Zbl 0101.25303
[22] Peluso, R.; Sgura, I., Newton method for symmetric inverse! eigenvalue problems, (Trigiante, D., ACTP Series, vol. 3 (2000), Nova Sci), 289-298 · Zbl 1019.65025
[23] Shampine, L. F.; Reichelt, M. W., The MATLAB ODE suite, SIAM J. Sci. Comput., 18, 1, 1-22 (1997) · Zbl 0868.65040
[24] Shapiro, A., On the unsolvability of inverse eigenvalues problems almost everywhere, Linear Algebra Appl., 49, 27-31 (1983) · Zbl 0507.15005
[25] Sing, F. Y., Some results on matrices with prescribed diagonal elements and singular values, Canad. Math. Bull., 19, 1, 89-92 (1976) · Zbl 0341.15007
[26] Sun, J. G.; Qiang, Y., The unsolvability of inverse algebraic eigenvalue problems almost everywhere, J. Comput. Math., 4, 3, 212-226 (1986) · Zbl 0595.15007
[27] Thompson, R. C., Singular values, diagonal elements, and convexity, SIAM J. Appl. Math., 32, 1, 39-63 (1977) · Zbl 0361.15009
[28] Xu, S. F., An Introduction to Inverse Algebraic Eigenvalue Problems (1998), Peking University Press, Friedr, Vieweg & Sohn Verlagsgesellschaft mbH: Peking University Press, Friedr, Vieweg & Sohn Verlagsgesellschaft mbH Braunschweig/Wiesbden, Beijing · Zbl 0927.65057
[29] Zha, H.; Zhang, Z., A note on constructing a symmetric matrix with specified diagonal entries and eigenvalues, BIT, 35, 448-452 (1995) · Zbl 0841.65028
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.