# Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2018.

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

- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)

## Abstract (arXiv)

In this paper, we obtain improved running times for regression and top eigenvector computation for numerically sparse matrices. Given a data matrix A ∈ ℝn × d where every row a ∈ ℝd has |a|22 ≤ L and numerical sparsity at most s, i.e. |a|12 / |a|22 ≤ s, we provide faster algorithms for these problems in many parameter settings. For top eigenvector computation, we obtain a running time of tildeO(nd + r(s + √r s) / gap2) where gap > 0 is the relative gap between the top two eigenvectors of A^top A and r is the stable rank of A. This running time improves upon the previous best unaccelerated running time of O(nd + r d / gap2) as it is always the case that r ≤ d and s ≤ d. For regression, we obtain a running time of tildeO(nd + (nL / μ) √s nL / μ) where μ > 0 is the smallest eigenvalue of A^top A. This running time improves upon the previous best unaccelerated running time of tildeO(nd + n L d / μ). This result expands the regimes where regression can be solved in nearly linear time from when L/μ = tildeO(1) to when L / μ = tildeO(d2/3 / (sn)1/3). Furthermore, we obtain similar improvements even when row norms and numerical sparsities are non-uniform and we show how to achieve even faster running times by accelerating using approximate proximal point [Frostig et. al. 2015] / catalyst [Lin et. al. 2015]. Our running times depend only on the size of the input and natural numerical measures of the matrix, i.e. eigenvalues and ℓp norms, making progress on a key open problem regarding optimal running times for efficient large-scale learning.