# Generalized Leverage Scores: Geometric Interpretation and Applications

arXiv: https://arxiv.org/abs/2206.08054 · HTML: https://mlsanity.com/paper/2206.08054/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 33 references that are in the map.
- First posted on arXiv 16 Jun 2022.

## Builds on (most cited first, 8 of 8)

- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [A Tutorial on Canonical Correlation Methods](https://mlsanity.com/paper/1711.02391/) (2017)
- [Provable Deterministic Leverage Score Sampling](https://mlsanity.com/paper/1404.1530/) (2014)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [Column subset selection is NP-complete](https://mlsanity.com/paper/1701.02764/) (2017)
- [Distributed Adaptive Sampling for Kernel Matrix Approximation](https://mlsanity.com/paper/1803.10172/) (2018)
- [Random Fourier Features via Fast Surrogate Leverage Weighted Sampling](https://mlsanity.com/paper/1911.09158/) (2019)

## Built on by (most cited first, 3 of 3)

- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [Active Learning for Conditional Generative Compressed Sensing](https://mlsanity.com/paper/2605.05435/) (2026)
- [Semantic Fibers and Cross-Gram Interference: A Calculus of Safety Drift in Overcomplete Representations](https://mlsanity.com/paper/2609.14861/) (2026)

## Abstract (arXiv)

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.