Fetching the paper…
Reading the bibliography…
Finding a small spectral approximation for a tall $n \times d$ matrix $A$ is a fundamental numerical primitive.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
The huller: a simple and efficient online SVM
Antoine Bordes and Léon Bottou · 2005
Earlier work this paper cites.
Online passive-aggressive algorithms
Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer · 2006
Earlier work this paper cites.
Approaching optimality for solving SDD linear systems
Ioannis Koutis, Gary L Miller, and Richard Peng · 2010
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
Freedman’s inequality for matrix martingales
Joel Tropp · 2011
Earlier work this paper cites.
Twice-ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Earlier work this paper cites.
Low rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2013
Cited alongside, same era.
Spectral sparsification in the semi-streaming setting
Jonathan A Kelner and Alex Levin · 2013
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2013
Cited alongside, same era.
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
Michael W. Mahoney and Xiangrui Meng · 2013
Cited alongside, same era.
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L. Nguyen · 2013
Cited alongside, same era.
Optimal CUR matrix decompositions
Christos Boutsidis and David P Woodruff · 2014
Cited alongside, same era.
Online principal components analysis
Christos Boutsidis, Dan Garber, Zohar Karnin, and Edo Liberty · 2015
Later among the works it cites.
Dimensionality reduction for k-means clustering and low rank approximation
Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu · 2015
Later among the works it cites.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Later among the works it cites.
Ridge leverage scores for low-rank approximation
Michael B Cohen, Cameron Musco, and Christopher Musco · 2015
Later among the works it cites.
Constructing linear-sized spectral sparsification in almost-linear time
Yin Tat Lee and He Sun · 2015
Later among the works it cites.
An algorithm for online k-means clustering
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2014
Cited alongside, same era.
Fast randomized kernel ridge regression with statistical guarantees
Ahmed Alaoui and Michael W Mahoney
Cited in the paper.
Edo Liberty, Ram Sriharsha, and Maxim Sviridenko · 2016
Closest in time.