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

Li, Chi-Kwong; Poon, Yiu-Tung; Schulte-Herbrüggen, Thomas

doi:10.1090/S0025-5718-2010-02450-0

Least-squares approximation by elements from matrix orbits achieved by gradient flows on compact lie groups
HTML articles powered by AMS MathViewer

by Chi-Kwong Li, Yiu-Tung Poon and Thomas Schulte-Herbrüggen PDF

Math. Comp. 80 (2011), 1601-1621 Request permission

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 \[ \min \Big \{\big \|X_1+ \cdots + X_N - A_0\big \|: X_j \in S(A_j), \ j = 1, \dots , N\Big \}.\] Connections of the results to different pure and applied areas are discussed.

References

Andreas Arvanitoyeorgos, An introduction to Lie groups and the geometry of homogeneous spaces, Student Mathematical Library, vol. 22, American Mathematical Society, Providence, RI, 2003. Translated from the 1999 Greek original and revised by the author. MR 2011126, DOI 10.1090/stml/022
Anthony Bloch (ed.), Hamiltonian and gradient flows, algorithms and control, Fields Institute Communications, vol. 3, American Mathematical Society, Providence, RI, 1994. MR 1297981, DOI 10.1007/978-1-4615-2722-0_{7}
R. W. Brockett, Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems, Linear Algebra Appl. 146 (1991), 79–91. MR 1083465, DOI 10.1016/0024-3795(91)90021-N
Anders Skovsted Buch, The saturation conjecture (after A. Knutson and T. Tao), Enseign. Math. (2) 46 (2000), no. 1-2, 43–60. With an appendix by William Fulton. MR 1769536
Che-Man Cheng, Roger A. Horn, and Chi-Kwong Li, Inequalities and equalities for the Cartesian decomposition of complex matrices, Linear Algebra Appl. 341 (2002), 219–237. Special issue dedicated to Professor T. Ando. MR 1873621, DOI 10.1016/S0024-3795(01)00373-1
Man Duen Choi, Completely positive linear maps on complex matrices, Linear Algebra Appl. 10 (1975), 285–290. MR 376726, DOI 10.1016/0024-3795(75)90075-0
Man Duen Choi and Pei Yuan Wu, Convex combinations of projections, Linear Algebra Appl. 136 (1990), 25–42. MR 1061537, DOI 10.1016/0024-3795(90)90019-9
Man-Duen Choi and Pei Yuan Wu, Finite-rank perturbations of positive operators and isometries, Studia Math. 173 (2006), no. 1, 73–79. MR 2204463, DOI 10.4064/sm173-1-5
Matthias Christandl, A quantum information-theoretic proof of the relation between Horn’s problem and the Littlewood-Richardson coefficients, Logic and theory of algorithms, Lecture Notes in Comput. Sci., vol. 5028, Springer, Berlin, 2008, pp. 120–128. MR 2507008, DOI 10.1007/978-3-540-69407-6_{1}3
Moody T. Chu, Fasma Diele, and Ivonne Sgura, Gradient flow methods for matrix completion with prescribed eigenvalues, Linear Algebra Appl. 379 (2004), 85–112. Tenth Conference of the International Linear Algebra Society. MR 2039299, DOI 10.1016/S0024-3795(03)00393-8
Jane Day, Wasin So, and Robert C. Thompson, The spectrum of a Hermitian matrix sum, Linear Algebra Appl. 280 (1998), no. 2-3, 289–332. MR 1644987, DOI 10.1016/S0024-3795(98)10019-8
Ky Fan and Gordon Pall, Imbedding conditions for Hermitian and normal matrices, Canadian J. Math. 9 (1957), 298–304. MR 85216, DOI 10.4153/CJM-1957-036-1
William Fulton, Eigenvalues, invariant factors, highest weights, and Schubert calculus, Bull. Amer. Math. Soc. (N.S.) 37 (2000), no. 3, 209–249. MR 1754641, DOI 10.1090/S0273-0979-00-00865-X
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.
U. Helmke, K. Hüper, J. B. Moore, and Th. Schulte-Herbrüggen, Gradient flows computing the $C$-numerical range with applications in NMR spectroscopy, J. Global Optim. 23 (2002), no. 3-4, 283–308. Nonconvex optimization in control. MR 1923048, DOI 10.1023/A:1016582714251
U. Helmke and J. B. Moore, Optimisation and Dynamical Systems, Springer, Berlin, 1994.
Alfred Horn, Eigenvalues of sums of Hermitian matrices, Pacific J. Math. 12 (1962), 225–241. MR 140521
Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
Alexander A. Klyachko, Stable bundles, representation theory and Hermitian operators, Selecta Math. (N.S.) 4 (1998), no. 3, 419–445. MR 1654578, DOI 10.1007/s000290050037
Karl Kraus, States, effects, and operations, Lecture Notes in Physics, vol. 190, Springer-Verlag, Berlin, 1983. Fundamental notions of quantum theory; Lecture notes edited by A. Böhm, J. D. Dollard and W. H. Wootters. MR 725167, DOI 10.1007/3-540-12732-1
Allen Knutson and Terence Tao, The honeycomb model of $\textrm {GL}_n(\textbf {C})$ tensor products. I. Proof of the saturation conjecture, J. Amer. Math. Soc. 12 (1999), no. 4, 1055–1090. MR 1671451, DOI 10.1090/S0894-0347-99-00299-4
Allen Knutson and Terence Tao, Honeycombs and sums of Hermitian matrices, Notices Amer. Math. Soc. 48 (2001), no. 2, 175–186. MR 1811121
Tian-Gang Lei, Congruence numerical ranges and their radii, Linear and Multilinear Algebra 43 (1998), no. 4, 411–427. MR 1616480, DOI 10.1080/03081089808818540
Chi-Kwong Li, $C$-numerical ranges and $C$-numerical radii, Linear and Multilinear Algebra 37 (1994), no. 1-3, 51–82. Special Issue: The numerical range and numerical radius. MR 1313758, DOI 10.1080/03081089408818312
Chi-Kwong Li and Yiu-Tung Poon, Diagonals and partial diagonals of sum of matrices, Canad. J. Math. 54 (2002), no. 3, 571–594. MR 1900764, DOI 10.4153/CJM-2002-020-1
Chi-Kwong Li and Nam-Kiu Tsing, On the unitarily invariant norms and some related results, Linear and Multilinear Algebra 20 (1987), no. 2, 107–119. MR 878289, DOI 10.1080/03081088708817747
E. Marques de Sá, On the inertia of sums of Hermitian matrices, Linear Algebra Appl. 37 (1981), 143–159. MR 636216, DOI 10.1016/0024-3795(81)90174-9
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
Francesco Mezzadri, How to generate random matrices from the classical compact groups, Notices Amer. Math. Soc. 54 (2007), no. 5, 592–604. MR 2311982
L. Mirsky, Symmetric gauge functions and unitarily invariant norms, Quart. J. Math. Oxford Ser. (2) 11 (1960), 50–59. MR 114821, DOI 10.1093/qmath/11.1.50
Thomas Schulte-Herbrüggen, Gunther Dirr, Uwe Helmke, and Steffen J. Glaser, The significance of the $C$-numerical range and the local $C$-numerical range in quantum control and quantum information, Linear Multilinear Algebra 56 (2008), no. 1-2, 3–26. MR 2378299, DOI 10.1080/03081080701544114
Thomas Schulte-Herbrüggen, Steffen J. Glaser, Gunther Dirr, and Uwe Helmke, Gradient flows for optimization in quantum information and quantum dynamics: foundations and applications, Rev. Math. Phys. 22 (2010), no. 6, 597–667. MR 2665760, DOI 10.1142/S0129055X10004053
Helene Shapiro, A survey of canonical forms and invariants for unitary similarity, Linear Algebra Appl. 147 (1991), 101–167. MR 1088662, DOI 10.1016/0024-3795(91)90232-L
Luis O’Shea and Reyer Sjamaar, Moment maps and Riemannian symmetric pairs, Math. Ann. 317 (2000), no. 3, 415–457. MR 1776111, DOI 10.1007/PL00004408
Robert C. Thompson and Linda J. Freede, On the eigenvalues of sums of Hermitian matrices, Linear Algebra Appl. 4 (1971), 369–376. MR 288132, DOI 10.1007/bf01817787
Robert C. Thompson and Linda J. Freede, On the eigenvalues of sums of Hermitian matrices. II, Aequationes Math. 5 (1970), 103–115. MR 292866, DOI 10.1007/BF01819276
Robert C. Thompson, Singular values and diagonal elements of complex symmetric matrices, Linear Algebra Appl. 26 (1979), 65–106. MR 535680, DOI 10.1016/0024-3795(79)90173-3
Robert C. Thompson, The congruence numerical range, Linear and Multilinear Algebra 8 (1979/80), no. 3, 197–206. MR 560560, DOI 10.1080/03081088008817318
Hermann Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung), Math. Ann. 71 (1912), no. 4, 441–479 (German). MR 1511670, DOI 10.1007/BF01456804