Low rank update of singular values

Chu, Delin; Chu, Moody

doi:10.1090/S0025-5718-06-01825-4

Low rank update of singular values
HTML articles powered by AMS MathViewer

by Delin Chu and Moody Chu PDF

Math. Comp. 75 (2006), 1351-1366 Request permission

Abstract:

The notion of a low rank update arises in many important applications. This paper deals with the inverse problem of updating a rectangular matrix by additive low rank matrices so as to reposition the associated singular values. The setting is analogous to the classical pole assignment problem where eigenvalues of a square matrix are relocated. Precise and easy-to-check necessary and sufficient conditions under which the problem is solvable are completely characterized, generalizing some traditional Weyl inequalities for singular values. The constructive proof makes it possible to compute such a solution numerically. A pseudo algorithm is outlined.

References

Ali R. Amir-Moéz, Extreme properties of eigenvalues of a hermitian transformation and singular values of the sum and product of linear transformations, Duke Math. J. 23 (1956), 463–476. MR 79564
Daniel Boley and Gene H. Golub, A survey of matrix inverse eigenvalue problems, Inverse Problems 3 (1987), no. 4, 595–622. MR 928047
C. I. Byrnes, Pole assignment by output feedback, Three decades of mathematical system theory, Lect. Notes Control Inf. Sci., vol. 135, Springer, Berlin, 1989, pp. 31–78. MR 1025786, DOI 10.1007/BFb0008458
Moody T. Chu, Numerical methods for inverse singular value problems, SIAM J. Numer. Anal. 29 (1992), no. 3, 885–903. MR 1163362, DOI 10.1137/0729054
Moody T. Chu, On constructing matrices with prescribed singular values and diagonal elements, Linear Algebra Appl. 288 (1999), no. 1-3, 11–22. MR 1670590, DOI 10.1016/S0024-3795(98)10124-6
Moody T. Chu, A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values, SIAM J. Numer. Anal. 37 (2000), no. 3, 1004–1020. MR 1749246, DOI 10.1137/S0036142998339301
Moody T. Chu and Gene H. Golub, Structured inverse eigenvalue problems, Acta Numer. 11 (2002), 1–71. MR 2008966, DOI 10.1017/S0962492902000016
Moody T. Chu, Robert E. Funderlic, and Robert J. Plemmons, Structured low rank approximation, Linear Algebra Appl. 366 (2003), 157–172. Special issue on structured matrices: analysis, algorithms and applications (Cortona, 2000). MR 1987719, DOI 10.1016/S0024-3795(02)00505-0
C. de Boor and G. H. Golub, The numerically stable reconstruction of a Jacobi matrix from spectral data, Linear Algebra Appl. 21 (1978), no. 3, 245–260. MR 504044, DOI 10.1016/0024-3795(78)90086-1
Graciano N. de Oliveira, Matrices with prescribed principal elements and singular values, Canad. Math. Bull. 14 (1971), 247–249. MR 311686, DOI 10.4153/CMB-1971-043-4
Israel Gohberg, Marinus A. Kaashoek, and Frederik van Schagen, Partially specified matrices and operators: classification, completion, applications, Operator Theory: Advances and Applications, vol. 79, Birkhäuser Verlag, Basel, 1995. MR 1409814, DOI 10.1007/978-3-0348-9100-4
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
William B. Gragg and William J. Harrod, The numerically stable reconstruction of Jacobi matrices from spectral data, Numer. Math. 44 (1984), no. 3, 317–335. MR 757489, DOI 10.1007/BF01405565
Per Christian Hansen, Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank, SIAM J. Sci. Statist. Comput. 11 (1990), no. 3, 503–518. MR 1047208, DOI 10.1137/0911028
Alfred Horn, On the eigenvalues of a matrix with prescribed singular values, Proc. Amer. Math. Soc. 5 (1954), 4–7. MR 61573, DOI 10.1090/S0002-9939-1954-0061573-6
Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge, 1991. MR 1091716, DOI 10.1017/CBO9780511840371
A. Frieze, R. Kannaa and S. Vempala, Fast Monte-Carlo algorithm for finding low rank approximations, Proceedings of the Foundations of Computer Science, 1998. 378-390, available at http://www.cs.yale.edu/~kannan.
J. Kautsky, N. K. Nichols, and P. Van Dooren, Robust pole assignment in linear state feedback, Internat. J. Control 41 (1985), no. 5, 1129–1155. MR 792933, DOI 10.1080/0020718508961188
Albert W. Marshall and Ingram Olkin, Inequalities: theory of majorization and its applications, Mathematics in Science and Engineering, vol. 143, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 552278
Horst D. Simon and Hongyuan Zha, Low-rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM J. Sci. Comput. 21 (2000), no. 6, 2257–2274. MR 1762041, DOI 10.1137/S1064827597327309
Fuk Yum Sing, Some results on matrices with prescribed diagonal elements and singular values, Canad. Math. Bull. 19 (1976), no. 1, 89–92. MR 424850, DOI 10.4153/CMB-1976-012-5
Ji-Guang Sun, Perturbation analysis of the pole assignment problem, SIAM J. Matrix Anal. Appl. 17 (1996), no. 2, 313–331. MR 1384510, DOI 10.1137/S0895479894276771
G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
R. C. Thompson, Singular values, diagonal elements, and convexity, SIAM J. Appl. Math. 32 (1977), no. 1, 39–63. MR 424847, DOI 10.1137/0132003
Hermann Weyl, Inequalities between the two kinds of eigenvalues of a linear transformation, Proc. Nat. Acad. Sci. U.S.A. 35 (1949), 408–411. MR 30693, DOI 10.1073/pnas.35.7.408
W. Murray Wonham, Linear multivariable control, 3rd ed., Applications of Mathematics (New York), vol. 10, Springer-Verlag, New York, 1985. A geometric approach. MR 770574, DOI 10.1007/978-1-4612-1082-5