Generalized Leverage Scores: Geometric Interpretation and Applications
In problems involving matrix computations, the concept of leverage has found
a large number of applications. In particular, leverage scores, which relate
the columns of a matrix to the subspaces spanned by its leading singular
vectors, are helpful in revealing column subsets to approximately factorize a
matrix with quality guarantees. As such, they provide a solid foundation for a
variety of machine-learning methods. In this paper we extend the definition of
leverage scores to relate the columns of a matrix to arbitrary subsets of
singular vectors. We establish a precise connection between column and
singular-vector subsets, by relating the concepts of leverage scores and
principal angles between subspaces. We employ this result to design
approximation algorithms with provable guarantees for two well-known problems:
generalized column subset selection and sparse canonical correlation analysis.
We run numerical experiments to provide further insight on the proposed
methods. The novel bounds we derive improve our understanding of fundamental
concepts in matrix approximations. In addition, our insights may serve as
building blocks for further contributions.