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/