Principal Angles Between Subspaces in an A-Based Scalar Product: Dense
and Sparse Matrix Algorithms
Merico E. Argentati (the
speaker), Andrew V. Knyazev
Center for Computational Biology
University of Colorado at Denver
Campus Box 170, P.O. Box 173364
Denver, Colorado 80217-3364
Abstract Computation of principal angles between subspaces
is important in many applications, e.g., in statistics, where the angles are
closely related to measures of dependency and covariance of random variables.
Another important application is measuring the accuracy of approximations to
eigenspaces and invariant subspaces computed by block iterative eigenvalue
solvers. In the latter case, when a generalized symmetric positive definite
eigenvalue problem is solved, it is necessary to compute principal angles in a
general scalar product, given by one of symmetric and positive definite matrices
of the original matrix pencil. Here, subspaces are given as column spaces of
n-by-p matrices with n >> p, and the matrix A, used to generate the scalar
product, may be only available in a form of a function that computes the product
Ax for a given vector x. Thus, we are interested in "matrix-free" methods, such
that no n-by-n matrices are used, which rules out cosine-sine decomposition
based algorithms.
We first observe that all current popular software codes compute only the
cosine of principal angles, making it impossible to find small angles accurately
due to round-off errors. We present a combination of sine and cosine based
algorithms that provide accurate results for all angles in a general scalar
product. We consider separately the cases of subspaces given by full and sparse
matrices. For the sparse case, which has applications in information retrieval,
we test several algorithms and analyze the resulting fill-in in the original
matrices. We also discuss a no-fill-in method, based on an iterative solver, to
compute principal angles.
An overview of interesting properties of principal angles is presented as
well as numerical examples.
This talk is partially based on a recent paper by A. V. Knyazev and M. E.
Argentati, Principal Angles between Subspaces in an A-Based Scalar Product:
Algorithms and Perturbation Estimates, which has been accepted for publication
in the SIAM Journal on Scientific Computing.
The developed MATLAB software is publicly available at
http://www.mathworks.com/matlabcentral/fileexchange/Files.jsp?type=category&id=&fileId=55
and http://math.cudenver.edu/~aknyazev/software/MATLAB/