Generalized Leverage Scores: Geometric Interpretation and Applications

Bruno Ordozgoiti, Antonis Matakos, Aristides Gionis
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:17056-17070, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-ordozgoiti22a, title = {Generalized Leverage Scores: Geometric Interpretation and Applications}, author = {Ordozgoiti, Bruno and Matakos, Antonis and Gionis, Aristides}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {17056--17070}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/ordozgoiti22a/ordozgoiti22a.pdf}, url = {https://proceedings.mlr.press/v162/ordozgoiti22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Generalized Leverage Scores: Geometric Interpretation and Applications %A Bruno Ordozgoiti %A Antonis Matakos %A Aristides Gionis %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-ordozgoiti22a %I PMLR %P 17056--17070 %U https://proceedings.mlr.press/v162/ordozgoiti22a.html %V 162 %X 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.
APA
Ordozgoiti, B., Matakos, A. & Gionis, A.. (2022). Generalized Leverage Scores: Geometric Interpretation and Applications. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:17056-17070 Available from https://proceedings.mlr.press/v162/ordozgoiti22a.html.

Related Material