# Input-Sparsity Low Rank Approximation in Schatten Norm

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2020.

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

- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)

## Abstract (arXiv)

We give the first input-sparsity time algorithms for the rank-k low rank approximation problem in every Schatten norm. Specifically, for a given n× n matrix A, our algorithm computes Y,Z∈ ℝn× k, which, with high probability, satisfy |A-YZT|p ≤ (1+ε)|A-Ak|p, where |M|p = left (sumi=1n σi(M)p right )1/p is the Schatten p-norm of a matrix M with singular values σ1(M), ldots, σn(M), and where Ak is the best rank-k approximation to A. Our algorithm runs in time tildeO(operatornamennz(A) + mnαpoperatornamepoly(k/ε)), where αp = 0 for p∈ [1,2) and αp = (ω-1)(1-2/p) for p>2 and ω ≈ 2.374 is the exponent of matrix multiplication. For the important case of p = 1, which corresponds to the more "robust" nuclear norm, we obtain tildeO(operatornamennz(A) + m · operatornamepoly(k/ε)) time, which was previously only known for the Frobenius norm (p = 2). Moreover, since αp < ω - 1 for every p, our algorithm has a better dependence on n than that in the singular value decomposition for every p. Crucial to our analysis is the use of dimensionality reduction for Ky-Fan p-norms.