Estimating Leverage Scores via Rank Revealing Methods and Randomization

Aleksandros Sobczyk, Efstratios Gallopoulos

Abstract

Statistical leverage scores are critical for identifying influential data points and accelerating large-scale linear algebra operations. However, computing these scores for massive datasets presents a significant computational challenge. This paper introduces a suite of high-performance algorithms that integrate randomized dimensionality reduction (sketching) with Strong Rank Revealing QR (SRRQR) factorizations. By leveraging the "CountGauss" transform and rank-revealing techniques, the proposed methods achieve state-of-the-art speeds and robust theoretical guarantees, particularly for "tall-and-thin" matrices and rank-deficient data.

1. Introduction

In modern data analytics, the diagonal elements of the hat matrix $H = A(A^\top A)^\dagger A^\top$, known as leverage scores, serve as essential metrics for outlier detection and data compression. For a matrix $A \in \mathbb{R}^{n \times d}$ where $n \gg d$, standard computation via QR or SVD requires $O(nd^2)$ operations, which is infeasible for datasets with billions of entries. While randomized sketching has emerged as a solution, existing techniques often falter when faced with rank-deficient data or the high cost of computing row norms in sparse matrices.

2. Methodology

The authors propose a unified three-step framework for leverage score estimation:

  1. Column Selection: Identifying a subset of columns $K$ that captures the matrix's range.
  2. Orthogonalization: Computing a matrix $R$ to ensure the compressed representation has orthonormal columns.
  3. Norm Computation: Calculating squared row norms to derive the final scores.

2.1 The CountGauss Transform and SRRQR

A key innovation is the CountGauss transform, which combines sparse CountSketch with dense Gaussian projections. This hybrid approach enables more efficient matrix compression than standard Gaussian methods. Furthermore, the integration of Strong Rank Revealing QR (SRRQR) allows the algorithms to prioritize the most informative columns. This is especially beneficial for approximately low-rank matrices, where using $k < \text{rank}(A)$ columns can still yield high-accuracy approximations.

Table 3: Complexity and success probabilities for the proposed suite of algorithms (Alg 5.1 - 5.6).

3. Experimental Evaluation

The algorithms were tested on a variety of datasets, ranging from synthetic matrices with controlled spectral gaps to massive real-world data:

  • timg80: A dataset derived from Tiny Images, containing 80 million rows and 1,024 columns (~1.6 billion non-zero elements).
  • kl02: A numerically rank-deficient matrix from the SuiteSparse collection.

3.1 Key Insights

  • Spectral Gap Influence: The accuracy of leverage score approximations is highly dependent on the "gap" in singular values. A significant gap allows for excellent results with minimal column subsets.
  • The Sparse Matrix Paradox: For highly sparse matrices, computing the Gram matrix $A^\top A$ in $O(\text{nnz}_2(A))$ time can outperform modern sketching methods.
  • Preconditioning: The methods naturally produce high-quality preconditioners, significantly accelerating iterative least-squares solvers.

4. Results

The proposed LS-HRN-exact and LS-HRN-approx (Algorithm 5.6) demonstrated superior scalability and speed. On the timg80 dataset, these methods outperformed standard SVD-based approaches. Algorithm 5.6, in particular, achieved lower complexity for dense matrices while maintaining high success probabilities and accurate rank detection in challenging scenarios.

Table 1: Comparison of complexity and approximation bounds for column selection algorithms.

5. Conclusion

By combining randomization with rank-revealing factorizations, this work provides a scalable solution for leverage score estimation in the big data era. While the dependence on the spectral gap remains a theoretical constraint, the empirical performance on billion-scale datasets underscores the practical utility of these methods. Future work will explore extensions to kernel matrices and regularized ridge leverage scores.

Summary updated

Abstract

We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms. We first develop a set of fast novel algorithms for rank estimation, column subset selection and least squares preconditioning. We then describe the design and implementation of leverage score estimators based on these primitives. These estimators are also effective for rank deficient input, which is frequently the case in data analytics applications. We provide detailed complexity analyses for all algorithms as well as meaningful approximation bounds and comparisons with the state-of-the-art. We conduct extensive numerical experiments to evaluate our algorithms and to illustrate their properties and performance using synthetic and real world data sets.
BibTeX
@article{sobczyk2021estimating,
  author = {Aleksandros Sobczyk and Efstratios Gallopoulos},
  title = {{Estimating Leverage Scores via Rank Revealing Methods and Randomization}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2021},
  url = {https://openreview.net/forum?id=rsu_F-H7eyw},
}
Figure