Faster Algorithms for Schatten-p Low Rank Approximation

On the asymptotic complexity of rectangular matrix multiplication

Grazia Lotti and Francesco Romani · 1983

Earlier work this paper cites.

Numerical linear algebra

Lloyd N. Trefethen and David Bau, III · 1997

Earlier work this paper cites.

Pinchings and norms of scaled triangular matrices

Rajendra Bhatia, William Kahan, and Ren-Cang Li · 2002

Earlier work this paper cites.

Improved analysis of the subsampled randomized hadamard transform

Original

Joel A Tropp · 2011

Earlier work this paper cites.

Faster algorithms for rectangular matrix multiplication

François Le Gall · 2012

Earlier work this paper cites.

Faster algorithms via approximation theory

Sushant Sachdeva and Nisheeth K Vishnoi · 2014

Earlier work this paper cites.

Randomized block krylov methods for stronger and faster approximate singular value decomposition

Cameron Musco and Christopher Musco · 2015

Cited alongside, same era.

LazySVD: Even faster SVD decomposition yet without agonizing pain

Zeyuan Allen-Zhu and Yuanzhi Li · 2016

Cited alongside, same era.

Low-rank approximation and regression in input sparsity time

Kenneth L. Clarkson and David P. Woodruff · 2017

Cited alongside, same era.

Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor

François Le Gall and Florent Urrutia · 2018

Cited alongside, same era.

Stability of the Lanczos method for matrix function approximation

Cameron Musco, Christopher Musco, and Aaron Sidford · 2018

Cited alongside, same era.

Input-sparsity low rank approximation in schatten norm

Yi Li and David Woodruff · 2020

Low-rank approximation with 1 / ε 1 / 3 1/\varepsilon^{1/3} matrix-vector products

Original

Ainesh Bakshi, Kenneth L Clarkson, and David P Woodruff · 2022

Later among the works it cites.

Faster matrix multiplication via asymmetric hashing

Original

Ran Duan, Hongxun Wu, and Renfei Zhou · 2022

Later among the works it cites.

Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time

Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava · 2023

Later among the works it cites.

Hermitian pseudospectral shattering, cholesky, hermitian eigenvalues, and density functional theory in nearly matrix multiplication time

Original

Aleksandros Sobczyk, Marko Mladenović, and Mathieu Luisier · 2023

Later among the works it cites.

Faster rectangular matrix multiplication by combination loss analysis