Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Least-squares approximation by elements from matrix orbits achieved by gradient flows on compact lie groups


Authors: Chi-Kwong Li, Yiu-Tung Poon and Thomas Schulte-Herbrüggen
Journal: Math. Comp. 80 (2011), 1601-1621
MSC (2010): Primary 15A18, 15A60, 15A90; Secondary 37N30
DOI: https://doi.org/10.1090/S0025-5718-2010-02450-0
Published electronically: December 13, 2010
MathSciNet review: 2785470
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ S(A)$ denote the orbit of a complex or real matrix $ A$ under a certain equivalence relation such as unitary similarity, unitary equivalence, unitary congruences etc. Efficient gradient-flow algorithms are constructed to determine the best approximation of a given matrix $ A_0$ by the sum of matrices in $ S(A_1), \dots, S(A_N)$ in the sense of finding the Euclidean least-squares distance

$\displaystyle \min\Big\{\big\Vert X_1+ \cdots + X_N - A_0\big\Vert: X_j \in S(A_j), j = 1, \dots, N\Big\}.$

Connections of the results to different pure and applied areas are discussed.


References [Enhancements On Off] (What's this?)

  • 1. A. Arvanitoyeorgos, An Introduction to Lie Groups and the Geometry of Homogeneous Spaces,
    Amer. Math. Soc., Providence, RI, 2003. [especially p. 125 ff]. MR 2011126 (2004i:53059)
  • 2. A. Bloch, Ed.,
    Hamiltonian and Gradient Flows, Algorithms and Control,
    Fields Institute Communications,
    Amer. Math. Soc., Providence, RI, 1994. MR 1297981 (95d:00025)
  • 3. R.W. Brockett, Dynamical Systems that Sort Lists, Diagonalise Matrices, and Solve Linear Programming Problems,
    In Proc. IEEE Decision Control, 1988, Austin, Texas, pages 779-803, 1988;
    reproduced in: Lin. Alg. Appl. 146 (1991), 79-91. MR 1083465 (92j:90043)
  • 4. A.S. Buch, The Saturation Conjecture (after A. Knutson and T. Tao) with an Appendix by William Fulton, Enseign. Math. 46 (2000), 43-60. MR 1769536 (2001g:05105)
  • 5. C.M. Cheng, R.A. Horn, and C.K. Li, Inequalities and Equalities for the Cartesian Decomposition, Lin. Alg. Appl. 341 (2002), 219-237. MR 1873621 (2002m:15012)
  • 6. M.D. Choi, Completely Positive Linear Maps on Complex Matrices, Lin. Alg. Appl. 10 (1975), 285-290. MR 0376726 (51:12901)
  • 7. M.D. Choi and P.Y. Wu, Convex Combinations of Projections, Lin. Alg. Appl. 136 (1990), 25-42. MR 1061537 (91e:15018)
  • 8. M.D. Choi and P.Y. Wu, Finite-Rank Perturbations of Positive Operators and Isometries, Studia Math. 173 (2006), 73-79. MR 2204463 (2006i:47026)
  • 9. M. Christandl, A Quantum Information-Theoretic Proof of the Relation between Horn's Problem and the Littlewood-Richardson Coefficients, Lect. Notes Comput. Sci. 5028 (2008), 120-128. MR 2507008
  • 10. M. T. Chu, F. Diele, and I. Sgura, Gradient Flow Methods for Matrix Completion with Prescribed Eigenvalues, Lin. Alg. Appl., 379 (2004), 85-112 . MR 2039299 (2005b:65041)
  • 11. J. Day, W. So and R.C. Thompson, The Spectrum of a Hermitian Matrix Sum, Lin. Alg. Appl. 280 (1998), 289-332. MR 1644987 (99f:15009)
  • 12. K. Fan and G. Pall, Embedding Conditions for Hermitian and Normal Matrices, Canad. J. Math. 9 (1957), 298-304. MR 0085216 (19:6e)
  • 13. W. Fulton, Eigenvalues, Invariant Factors, Highest Weights, and Schubert Calculus, Bull. Amer. Math. Soc. 37 (2000), 209-249. MR 1754641 (2001g:15023)
  • 14. S. J. Glaser, T. Schulte-Herbrüggen, M. Sieveking, O. Schedletzky, N. C. Nielsen, O. W. Sørensen, and C. Griesinger, Unitary Control in Quantum Ensembles: Maximizing Signal Intensity in Coherent Spectroscopy,
    Science 280 (1998), 421-424.
  • 15. U. Helmke, K. Hüper, J. B. Moore, and T. Schulte-Herbrüggen, Gradient Flows Computing the $ C$-Numerical Range with Applications in NMR Spectroscopy,
    J. Global Optim. 23 (2002), 283-308. MR 1923048 (2003g:90127)
  • 16. U. Helmke and J. B. Moore, Optimisation and Dynamical Systems,
    Springer, Berlin, 1994.
  • 17. A. Horn, Eigenvalues of Sums of Hermitian Matrices, Pacific J. Math. 12 (1962), 225-241. MR 0140521 (25:3941)
  • 18. R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, New York, 1985. MR 832183 (87e:15001)
  • 19. A.A. Klyachko, Stable Bundles, Representation Theory and Hermitian Operators, Selecta Math. (N.S.) 4 (1998), 419-445. MR 1654578 (2000b:14054)
  • 20. K. Kraus, States, Effects, and Operations, Lecture Notes in Physics, Vol. 190, Springer, Berlin, 1983. MR 725167 (86j:81008)
  • 21. A. Knutson and T. Tao, The Honeycomb Model of $ {\rm GL}\sb n(\mathbb{C})$ Tensor Products. I. Proof of the Saturation Conjecture, J. Amer. Math. Soc. 12 (1999), 1055-1090. MR 1671451 (2000c:20066)
  • 22. A. Knutson and T. Tao, Honeycombs and Sums of Hermitian Matrices, Notices Amer. Math. Soc. 48 (2001), 175-185. MR 1811121 (2002g:15020)
  • 23. T.G. Lei, Congruence Numerical Ranges and Their Radii, Lin. Multilin. Alg. 43 (1998), 411-427. MR 1616480 (98k:15039)
  • 24. C.K. Li, $ C$-Numerical Ranges and $ C$-Numerical Radii, Lin. Multilin. Alg. 37 (1994), 51-82. MR 1313758 (95k:15039)
  • 25. C. K. Li and Y. T. Poon, Diagonals and Partial Diagonals of Sum of Matrices, Canadian J. Math. 54 (2002), 571-594. MR 1900764 (2003a:15017)
  • 26. C.K. Li and N.K. Tsing, On Unitarily Invariant Norms and Related Results, Lin. Multilin. Alg. 20 (1987), 107-119. MR 878289 (88c:15015)
  • 27. E. Marques de Sá, On the Inertia of Sums of Hermitian Matrices, Lin. Alg.  Appl. 37 (1981), 143-159. MR 636216 (84h:15026c)
  • 28. A.W. Marshall and I. Olkin, Inequalities: Theory of Majorization and its Applications, Mathematics in Science and Engineering, Vol. 143. Academic Press, New York-London, 1979. MR 552278 (81b:00002)
  • 29. F. Mezzadri, How to Generate Random Matrices from the Classical Compact Groups, Notices Amer. Math. Soc. 54 (2007), 592-604. MR 2311982 (2008e:22005)
  • 30. L. Mirsky, Symmetric Gauge Functions and Unitarily Invariant Norms, Quart. J. Math. Oxford 11 (1960), 50-59. MR 0114821 (22:5639)
  • 31. T. Schulte-Herbrüggen, G. Dirr, U. Helmke and S. Glaser, The Significance of the $ C$-Numerical Range and the Local $ C$-Numerical Range in Quantum Control and Quantum Information, Lin. Multilin. Alg. 56 (2008), 3-26. MR 2378299 (2008m:47005)
  • 32. T. Schulte-Herbrüggen, G. Dirr, U. Helmke and S. Glaser, Gradient Flows for Optimisation in Quantum Information and Quantum Dynamics: Foundations and Applications, Rev. Math. Phys. 22 (2010), 597-667. MR 2665760
  • 33. H. Shapiro, A Survey of Canonical Forms and Invariants for Unitary Similarity, Lin. Alg. Appl. 147 (1991), 101-167. MR 1088662 (92d:15013)
  • 34. L. O'Shea and R. Sjamaar, Moment Maps and Riemannian Symmetric Pairs, Math. Ann. 317 (2000), 415-457. MR 1776111 (2001g:53146)
  • 35. R.C. Thompson and L.J. Freede, On the Eigenvalues of Sums of Hermitian Matrices, Lin. Alg. Appl. 4 (1971) 369-376. MR 0288132 (44:5330)
  • 36. R.C. Thompson and L.J. Freede, On the Eigenvalues of Sums of Hermitian Matrices, II., Aequationes Math. 5 (1970), 103-115. MR 0292866 (45:1948)
  • 37. R.C. Thompson, Singular Values and Diagonal Elements of Complex Symmetric Matrices, Lin. Alg. Appl. 26 (1979), 65-106. MR 535680 (80f:15011)
  • 38. R.C. Thompson, The Congruence Numerical Range, Lin. Multilin. Alg. 8 (1979/80), 197-206. MR 560560 (81b:15026)
  • 39. H. Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen, Math. Ann. 71 (1912), 441-479 MR 1511670

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A18, 15A60, 15A90, 37N30

Retrieve articles in all journals with MSC (2010): 15A18, 15A60, 15A90, 37N30


Additional Information

Chi-Kwong Li
Affiliation: Department of Mathematics, College of William and Mary, Williamsburg, Virginia 23187
Email: ckli@math.wm.edu

Yiu-Tung Poon
Affiliation: Department of Mathematics, Iowa State University, Ames, Iowa 50051
Email: ytpoon@iastate.edu

Thomas Schulte-Herbrüggen
Affiliation: Department of Chemistry, Technical University of Munich, D-85747, Garching, Germany.
Email: tosh@ch.tum.de

DOI: https://doi.org/10.1090/S0025-5718-2010-02450-0
Keywords: Complex Hermitian matrices, real symmetric matrices, eigenvalues, singular values, gradient flows.
Received by editor(s): September 15, 2008
Received by editor(s) in revised form: May 20, 2010
Published electronically: December 13, 2010
Additional Notes: The author is an honorary professor of the University of Hong Kong and an honorary professor of the Taiyuan University of Technology. His research was partially supported by USA NSF and the William and Mary Plumeri Award.
The second author’s research was partially supported by USA NSF
The third author is supported in part by the EU-programmes QAP, Q-ESSENCE and the exchange with COQUIT as well as by the excellence network of Bavaria through QCCC
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society