Generalized Leverage Scores: Geometric Interpretation and Applications

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

1 Citation (Scopus)
37 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the 39th International Conference on Machine Learning
PublisherJMLR
Pages17056-17070
Publication statusPublished - 2022
MoE publication typeA4 Conference publication
EventInternational Conference on Machine Learning - Baltimore, United States
Duration: 17 Jul 202223 Jul 2022
Conference number: 39

Publication series

NameProceedings of Machine Learning Research
PublisherPMLR
Volume162
ISSN (Electronic)2640-3498

Conference

ConferenceInternational Conference on Machine Learning
Abbreviated titleICML
Country/TerritoryUnited States
CityBaltimore
Period17/07/202223/07/2022

Fingerprint

Dive into the research topics of 'Generalized Leverage Scores: Geometric Interpretation and Applications'. Together they form a unique fingerprint.

Cite this