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:
- Column Selection: Identifying a subset of columns $K$ that captures the matrix's range.
- Orthogonalization: Computing a matrix $R$ to ensure the compressed representation has orthonormal columns.
- 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.
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.
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