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/