Numerical methods for computing angles between linear subspaces
HTML articles powered by AMS MathViewer
- by Ȧke Björck and Gene H. Golub PDF
- Math. Comp. 27 (1973), 579-594 Request permission
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
- S. N. Afriat, Orthogonal and oblique projectors and the characteristics of pairs of vector spaces, Proc. Cambridge Philos. Soc. 53 (1957), 800–816. MR 94880, DOI 10.1017/s0305004100032916
- Ȧke Björck, Solving linear least squares problems by Gram-Schmidt orthogonalization, Nordisk Tidskr. Informationsbehandling (BIT) 7 (1967), 1–21. MR 214275, DOI 10.1007/bf01934122
- Ȧke Björck, Iterative refinement of linear least squares solutions. II, Nordisk Tidskr. Informationsbehandling (BIT) 8 (1968), 8–30. MR 239737, DOI 10.1007/bf01939974
- Ȧ. Björck and C. Bowie, An iterative algorithm for computing the best estimate of an orthogonal matrix, SIAM J. Numer. Anal. 8 (1971), 358–364. MR 295547, DOI 10.1137/0708036
- Peter Businger and Gene H. Golub, Handbook series linear algebra. Linear least squares solutions by Householder transformations, Numer. Math. 7 (1965), 269–276. MR 176590, DOI 10.1007/BF01436084
- Claude Cohen and Adi Ben-Israel, On the computation of canonical correlations, Cahiers Centre Études Rech. Opér. 11 (1969), 121–132. MR 253469 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.
- G. Dahlquist, B. Sjöberg, and P. Svensson, Comparison of the method of averages with the method of least squares, Math. Comp. 22 (1968), 833–845. MR 239742, DOI 10.1090/S0025-5718-1968-0239742-X
- Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal. 7 (1970), 1–46. MR 264450, DOI 10.1137/0707001 C. Eckart & G. Young, "The approximation of one matrix by another of lower rank," Psychometrika, v. 1, 1936, pp. 211-218.
- Carl Eckart and Gale Young, A principal axis transformation for non-hermitian matrices, Bull. Amer. Math. Soc. 45 (1939), no. 2, 118–121. MR 1563923, DOI 10.1090/S0002-9904-1939-06910-3
- D. K. Faddeev, V. N. Kublanovskaya, and V. N. Faddeeva, Sur les systèmes linéaires algébriques de matrices rectangulaires et mal-conditionnées, Programmation en Mathématiques Numériques (Actes Colloq. Internat. C.N.R.S. No. 165, Besançon, 1966) Éditions du Centre National de la Recherche Scientifique (CNRS), Paris, 1968, pp. 161–170 (French, with English summary). MR 0230455
- G. Fix and R. Heiberger, An algorithm for the ill-conditioned generalized eigenvalue problem, SIAM J. Numer. Anal. 9 (1972), 78–88. MR 305569, DOI 10.1137/0709009
- Richard J. Hanson and Charles L. Lawson, Extensions and applications of the Householder algorithm for solving linear least squares problems, Math. Comp. 23 (1969), 787–812. MR 258258, DOI 10.1090/S0025-5718-1969-0258258-9
- I. C. Gohberg and M. G. Kreĭn, Introduction to the theory of linear nonselfadjoint operators, Translations of Mathematical Monographs, Vol. 18, American Mathematical Society, Providence, R.I., 1969. Translated from the Russian by A. Feinstein. MR 0246142, DOI 10.1090/mmono/018
- G. Golub, Numerical methods for solving linear least squares problems, Numer. Math. 7 (1965), 206–216. MR 181094, DOI 10.1007/BF01436075
- G. H. Golub and C. Reinsch, Handbook Series Linear Algebra: Singular value decomposition and least squares solutions, Numer. Math. 14 (1970), no. 5, 403–420. MR 1553974, DOI 10.1007/BF02163027
- Irving John Good, The estimation of probabilities. An essay on modern Bayesian methods, Research Monograph, No. 30, The M.I.T. Press, Cambridge, Mass., 1965. MR 0185724 H. Hotelling, "Relations between two sets of variates," Biometrika, v. 28, 1936, pp. 321-377.
- A. van der Sluis, Condition numbers and equilibration of matrices, Numer. Math. 14 (1969/70), 14–23. MR 253546, DOI 10.1007/BF02165096
- J. M. Varah, Computing invariant subspaces of a general matrix when the eigensystem is poorly conditioned, Math. Comp. 24 (1970), 137–149. MR 264843, DOI 10.1090/S0025-5718-1970-0264843-9 P. ÅWedin, On Pseudoinverses of Perturbed Matrices, Dept. of Comput. Sci., Lund University, Lund, Sweden, 1969.
- J. H. Wilkinson, Error analysis of transformations based on the use of matrices of the form $I-2ww^{H}$, Error in Digital Computation, Vol. 2 (Proc. Sympos. Math. Res. Center, U.S. Army, Univ. Wisconsin, Madison, Wis., 1965) Wiley, New York, 1965, pp. 77–101. MR 0189284
Additional Information
- © Copyright 1973 American Mathematical Society
- Journal: Math. Comp. 27 (1973), 579-594
- MSC: Primary 65F30
- DOI: https://doi.org/10.1090/S0025-5718-1973-0348991-3
- MathSciNet review: 0348991