Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Low rank update of singular values


Authors: Delin Chu and Moody Chu
Journal: Math. Comp. 75 (2006), 1351-1366
MSC (2000): Primary 68F18, 93B55, 15A18
DOI: https://doi.org/10.1090/S0025-5718-06-01825-4
Published electronically: February 27, 2006
MathSciNet review: 2219032
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. A. R. Amir-Moez, Extreme properties of eigenvalues of a hermitian transformation and singular values of the sum and product of linear transformations, Duke Math. J., 23(1955), 463-476. MR 0079564 (18,105j)
  • 2. D. Boley and G. H. Golub, A survey of matrix inverse eigenvalue problem, Inverse Problems, 3(1987), 595-622. MR 0928047 (89m:65036)
  • 3. C. I. Byrnes, Pole placement by output feedback, in Three Decades of Mathematical Systems Theory, Lecture Notes in Control and Information Sciences, Springer-Verlag, 135(1989), 31-78. MR 1025786 (90k:93001)
  • 4. M. T. Chu, Numerical methods for inverse singular value problems, SIAM J. Numer. Anal., 29(1992), 885-903. MR 1163362 (93a:65048)
  • 5. M. T. Chu, On constructing matrices with prescribed singular values and diagonal elements, Linear Alg. Appl., 288(1999), 11-22. MR 1670590 (2000a:15010)
  • 6. M. T. Chu, A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values, SIAM J. Numer. Anal., 37(2000), 1004-1020.MR 1749246 (2001d:65044)
  • 7. M. T. Chu and G. H. Golub, Structured inverse eigenvalue problems, Acta Numerica, 12(2002), 1-71.MR 2008966 (2005b:65040)
  • 8. M. T. Chu, R. E. Funderlic, and R. J. Plemmons, Structured low-rank approximation, Linear Alg. Appl., 366(2003), 157-172. MR 1987719 (2004e:15001)
  • 9. C. de Boor and G. H. Golub, The numerically stable reconstruction of a Jacobi matrix from spectral data, Linear Alg. Appl., 21(1978), 245-260.MR 0504044 (80i:15007)
  • 10. G. N. de Oliveira, Matrices with prescribed principal elements and singular values, Canada Math. Bull., 14(1971), 247-249. MR 0311686 (47:248)
  • 11. I. Gohberg, M. Kaashoek, and F. van Schagen, Partially specified matrices and operators: classification, completion, applications, Operator Theory: Advances and Applications Series, vol. 79, Birkhäuser Verlag, Basel, 1995. MR 1409814 (97i:47002)
  • 12. G. H. Golub and C. F. Van Loan. Matrix Computations, The Johns Hopkins University Press, Baltimore, Maryland, 3rd edition, 1996. MR 1417720 (97g:65006)
  • 13. W. B. Gragg and W. J. Harrod, The numerically stable reconstruction of Jacobi matrices from spectral data, Numer. Math., 44(1984), 317-335. MR 0757489 (85i:65052)
  • 14. P. C. Hansen, Truncated SVD solution to discrete ill-posed problems with ill-determined numerical rank, SIAM J. Sci. Stat. Computing, 11(1991), 503-518. MR 1047208 (91e:65058)
  • 15. A. Horn, On the eigenvalues of a matrix with prescribed singular values, Proc. Amer. J. Math., 76(1954), 4-7. MR 0061573 (15:847d)
  • 16. R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, New York, 1991. MR 1091716 (92e:15003)
  • 17. 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.
  • 18. J. Kautsky, N. K. Nichols and P. Van Dooren, Robust pole assignment in linear state feedback, Internat. J. Control, 41(1985), 1129-1155. MR 0792933 (86g:93038)
  • 19. A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Applications, Academic Press, New York, 1979. MR 0552278 (81b:00002)
  • 20. H. S. Simon and H. Zha, Low rank matrix approximation using the Lanczos bidiagonalization process, SIAM J. Sci. Comput., 21(2000), 2257-2274.MR 1762041 (2001e:65065)
  • 21. F. Y. Sing, Some results on matrices with prescribed diagonal elements and singular values, Canad. Math., 19(1976), 89-92. MR 0424850 (54:12808)
  • 22. J.-G. Sun, Perturbation analysis of the pole assignment problem, SIAM J. Matrix Anal. Appl., 17(1996), 313-331. MR 1384510 (97c:93052)
  • 23. G. W. Stewrat and J.-G. Sun, Matrix Perturbation Theory, Academic Press, Boston, 1990.MR 1061154 (92a:65017)
  • 24. R. C. Thompson, Singular values, diagonal elements, and convexity, SIAM, J. Appl. Math., 32(1977), 39-63. MR 0424847 (54:12805)
  • 25. H. Weyl, Inequalities between two kinds of eigenvalues of a linear transformation, Proc. Nat. Acad. Sci. U.S.A., 35(1949), 408-411.MR 0030693 (11:37d)
  • 26. W. W. Wonham, Linear Multivariable Control: A Geometric Control, Third edition. Springer-Verlag, New York, 1985. MR 0770574 (86e:93034)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68F18, 93B55, 15A18

Retrieve articles in all journals with MSC (2000): 68F18, 93B55, 15A18


Additional Information

Delin Chu
Affiliation: Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543
Email: matchudl@math.nus.edu.sg

Moody Chu
Affiliation: Department of Mathematics, North Carolina State University, Raleigh, North Carolina 27695-8205
Email: chu@math.ncsu.edu

DOI: https://doi.org/10.1090/S0025-5718-06-01825-4
Keywords: Singular values, low rank update, interlacing properties, pole assignment.
Received by editor(s): December 17, 2004
Received by editor(s) in revised form: April 1, 2005
Published electronically: February 27, 2006
Additional Notes: This research was supported in part by the National Science Foundation under grants DMS-0073056 and CCR-0204157
Article copyright: © Copyright 2006 American Mathematical Society

American Mathematical Society