# Low Rank Matrix Approximation in Linear Time

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

## Key facts

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

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

- [k-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation](https://mlsanity.com/paper/2507.14631/) (2025)

## Abstract (arXiv)

newcommandMatAM newcommandepsvarepsilon newcommandNSizemathsfN newcommandMatBB newcommandFnorm[1]left| #1 right|F newcommandPrcOpt[2]μoptpth#1, #2 newcommandpth[1]left(#1right) Given a matrix MatA with n rows and d columns, and fixed k and eps, we present an algorithm that in linear time (i.e., O(NSize )) computes a k-rank matrix MatB with approximation error FnormMatA - MatB2 ≤ (1+eps) PrcOptMatAk, where NSize = n d is the input size, and PrcOptMatAk is the minimum error of a k-rank approximation to MatA. This algorithm succeeds with constant probability, and to our knowledge it is the first linear-time algorithm to achieve multiplicative approximation.