Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Numerical methods for computing angles between linear subspaces


Authors: Ake Björck and Gene H. Golub
Journal: Math. Comp. 27 (1973), 579-594
MSC: Primary 65F30
DOI: https://doi.org/10.1090/S0025-5718-1973-0348991-3
MathSciNet review: 0348991
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Assume that two subspaces F and G of a unitary space are defined as the ranges (or null spaces) of given rectangular matrices A and B. Accurate numerical methods are developed for computing the principal angles $ {\theta _k}(F,G)$ and orthogonal sets of principal vectors $ {u_k} \in F$ and $ {v_k} \in G,k = 1,2, \cdots ,q = \dim (G) \leqq \dim (F)$. An important application in statistics is computing the canonical correlations $ {\sigma _k} = \cos {\theta _k}$ between two sets of variates. A perturbation analysis shows that the condition number for $ {\theta _k}$ essentially is $ \max (\kappa (A),\kappa (B))$, where $ \kappa $ denotes the condition number of a matrix. The algorithms are based on a preliminary QR-factorization of A and B (or $ {A^H}$ and $ {B^H}$), for which either the method of Householder transformations (HT) or the modified Gram-Schmidt method (MGS) is used. Then $ \cos \;{\theta _k}$ and $ \sin \;{\theta _k}$ are computed as the singular values of certain related matrices. Experimental results are given, which indicates that MGS gives $ {\theta _k}$ with equal precision and fewer arithmetic operations than HT. However, HT gives principal vectors, which are orthogonal to working accuracy, which is not generally true for MGS. Finally, the case when A and/or B are rank deficient is discussed.


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

  • [1] S. N. Afriat, "Orthogonal and oblique projectors and the characteristics of pairs of vector spaces," Proc. Cambridge Philos. Soc., v. 53, 1957, pp. 800-816. MR 20 #1389. MR 0094880 (20:1389)
  • [2] Å. Björck, "Solving linear least squares problems by Gram-Schmidt orthogonalization," Nordisk Tidskr. Informationsbehandling (BIT), v. 7, 1967, pp. 1-21. MR 53 #5126. MR 0214275 (35:5126)
  • [3] Å. Björck, "Iterative refinement of linear least squares solutions. II," Nordisk Tidskr. Informationsbehandling (BIT), v. 8, 1968, pp. 8-30. MR 39 #1094. MR 0239737 (39:1094)
  • [4] Å. Björck & C. Bowie, "An iterative algorithm for computing the best estimate of an orthogonal matrix," SIAM J. Numer. Anal., v. 8, 1971, pp. 358-364. MR 0295547 (45:4613)
  • [5] P. Businger & G. H. Golub, "Handbook series linear algebra. Linear least squares solutions by Householder transformations," Numer. Math., v. 7, 1965, pp. 269-276. MR 31 #862. MR 0176590 (31:862)
  • [6] C. Cohen & A. Ben-Israel, "On the computation of canonical correlations," Cahiers Centre Études Recherche Opér., v. 11, 1969, pp. 121-132. MR 40 #6683. MR 0253469 (40:6683)
  • [7] C. Cohen, An Investigation of the Geometry of Subspaces for Some Multivariate Statistical Models, Thesis, Dept. of Indust. Eng., University of Illinois, Urbana, Ill., 1969.
  • [8] G. Dahlquist, B. Sjöberg & P. Svensson, "Comparison of the method of averages with the method of least squares," Math. Comp., v. 22, 1968, pp. 833-845. MR 39 #1099. MR 0239742 (39:1099)
  • [9] C. Davies & W. Kahan, "The rotation of eigenvectors by a perturbation. III," SIAM J. Numer. Anal., v. 7, 1970, pp. 1-46. MR 0264450 (41:9044)
  • [10] C. Eckart & G. Young, "The approximation of one matrix by another of lower rank," Psychometrika, v. 1, 1936, pp. 211-218.
  • [11] C. Eckart & G. Young, "A principal axis transformation for non-Hermitian matrices," Bull. Amer. Math. Soc., v. 45, 1939, pp. 118-121. MR 1563923
  • [12] D. K. Faddeev, V. N. Kublanovskaja & V. N. Faddeeva, Sur les Systèmes Linéaires Algébriques de Matrices Rectangulaires et Mal-Conditionnées (Actes Colloq. Internat. C.N.R.S. No. 165, Besançon, 1966) Éditions C.N.R.S., Paris, 1968, pp. 161-170. MR 37 #6017. MR 0230455 (37:6017)
  • [13] G. Fix & R. Heiberger, "An algorithm for the ill conditioned generalized eigenvalue problem," Numer. Math. (To appear.) MR 0305569 (46:4699)
  • [14] R. J. Hanson & C. L. Lawson, "Extensions and applications of the Householder algorithm for solving linear squares problems," Math. Comp., v. 23, 1969, pp. 787-812. MR 41 #2905. MR 0258258 (41:2905)
  • [15] I. C. Gohberg & M. G. Krein, Introduction to the Theory of Linear Nonselfadjoint Operators, "Nauka," Moscow, 1965; English transl. Transl. Math. Monographs, vol. 18, Amer. Math. Soc., Providence, R. I., 1969. MR 39 #7447. MR 0246142 (39:7447)
  • [16] G. H. Golub, "Numerical methods for solving linear least squares problems," Numer. Math., v. 7, 1965, pp. 206-216. MR 31 #5323. MR 0181094 (31:5323)
  • [17] G. H. Golub & C. Reinsch, "Singular value decompositions and least squares solutions," Numer. Math., v. 14, 1970, pp. 403-420. MR 1553974
  • [18] I. J. Good, The Estimation of Probabilities. An Essay on Modern Bayesian Methods, Research Monograph No. 30, M.I.T. Press, Cambridge, Mass., 1965, pp. 87-89. MR 32 #3186. MR 0185724 (32:3186)
  • [19] H. Hotelling, "Relations between two sets of variates," Biometrika, v. 28, 1936, pp. 321-377.
  • [20] A. van der Sluis, "Condition numbers and equilibration of matrices," Numer. Math., v. 14, 1969/1970, pp. 14-23. MR 40 #6760. MR 0253546 (40:6760)
  • [21] J. M. Varah, "Computing invariant subspaces of a general matrix when the eigensystem is poorly conditioned," Math. Comp., v. 24, 1970, pp. 137-149. MR 41 #9434. MR 0264843 (41:9434)
  • [22] P. ÅWedin, On Pseudoinverses of Perturbed Matrices, Dept. of Comput. Sci., Lund University, Lund, Sweden, 1969.
  • [23] J. Wilkinson, "Error analysis of transformations based on the use of matrices of the form $ I - 2w{w^H}$," Error in Digital Computation, vol. II (Proc. Sympos. Math. Res. Center, U.S. Army, Univ. of Wisconsin, Madison, Wis., 1965), Wiley, New York, 1965, pp. 77-101. MR 32 #6711. MR 0189284 (32:6711)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30

Retrieve articles in all journals with MSC: 65F30


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1973-0348991-3
Keywords: Numerical linear algebra, least squares, singular values, canonical correlations
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society