Fetching the paper…
Reading the bibliography…
We consider algorithms with access to an unknown matrix $M\in\mathbb{F}^{n \times d}$ via matrix-vector products, namely, the algorithm chooses vectors $\mathbf{v}^1, \ldots, \mathbf{v}^q$, and observes $M\mathbf{v}^1,\ldots, M\mathbf{v}^q$.
Singular value decomposition, 2017
Qiaochu Yuan · 1906
Earlier work this paper cites.
Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung)
Hermann Weyl · 1912
Earlier work this paper cites.
Probabilistic computations: Toward a unified measure of complexity
Andrew Chi-Chin Yao · 1977
Earlier work this paper cites.
Aspects of multivariate statistical theory
John T Kent and R J Muirhead · 1984
Earlier work this paper cites.
Linear decision trees: volume estimates and topological bounds
Anders Björner, László Lovász, and Andrew CC Yao · 1992
Earlier work this paper cites.
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1996
Earlier work this paper cites.
On the singular values of gaussian random matrices
Jianhong Shen · 2001
Earlier work this paper cites.
Reductions in streaming algorithms, with an application to counting triangles in graphs
Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar · 2002
Earlier work this paper cites.
Stable signal recovery from incomplete and inaccurate measurements
Emmanuel J Candes, Justin K Romberg, and Terence Tao · 2006
Earlier work this paper cites.
Graph distances in the data-stream model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang · 2008
Earlier work this paper cites.
Lower bounds for sparse recovery
Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff · 2010
Earlier work this paper cites.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2010
Earlier work this paper cites.
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
Haim Avron and Sivan Toledo · 2011
Earlier work this paper cites.
On the power of adaptivity in sparse recovery
Piotr Indyk, Eric Price, and David P. Woodruff · 2011
Cited alongside, same era.
Analyzing graph structure via linear measurements
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2012
Cited alongside, same era.
Property testing lower bounds via communication complexity
Eric Blais, Joshua Brody, and Kevin Matulef · 2012
Cited alongside, same era.
Streaming and communication complexity of clique approximation
Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, and Chengu Wang · 2012
Cited alongside, same era.
Lower bounds for adaptive sparse recovery
Eric Price and David P. Woodruff · 2013
Cited alongside, same era.
On sketching matrix norms and the top singular vector
Yi Li, Huy L. Nguyen, and David P. Woodruff · 2014
Cited alongside, same era.
Tight bounds for sketching the operator norm, schatten norms, and subspace embeddings
Yi Li and David P Woodruff · 2016
Later among the works it cites.
On estimating maximum matching size in graph streams
Sepehr Assadi, Sanjeev Khanna, and Yang Li · 2017
Later among the works it cites.
Approximately counting triangles in sublinear time
Talya Eden, Amit Levi, Dana Ron, and C Seshadhri · 2017
Later among the works it cites.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2017
Later among the works it cites.
Embeddings of schatten norms with applications to data streams
Yi Li and David P. Woodruff · 2017
Later among the works it cites.
Matrix norms in data streams: Faster, multi-pass and row-order
Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, and Lin Yang · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Turnstile streaming algorithms might as well be linear sketches
Yi Li, Huy L. Nguyen, and David P. Woodruff · 2014
Cited alongside, same era.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Cited alongside, same era.
Maximum matching in turnstile streams
Christian Konrad · 2015
Cited alongside, same era.
Randomized block krylov methods for stronger and faster approximate singular value decomposition
Cameron Musco and Christopher Musco · 2015
Cited alongside, same era.
New characterizations in turnstile streams with applications
Yuqing Ai, Wei Hu, Yi Li, and David P. Woodruff · 2016
Cited alongside, same era.
Maximum matchings in dynamic graph streams and the simultaneous communication model
Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev · 2016
Cited alongside, same era.
Later among the works it cites.
Near-optimal linear decision trees for k-sum and related problems
Daniel M. Kane, Shachar Lovett, and Shay Moran · 2018
Later among the works it cites.
Linear sketching over F_2
Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev · 2018
Later among the works it cites.
Improved algorithms for adaptive compressed sensing
Vasileios Nakos, Xiaofei Shi, David P. Woodruff, and Hongyang Zhang · 2018
Later among the works it cites.
Tight query complexity lower bounds for PCA via finite sample deformed wigner law
Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht · 2018
Later among the works it cites.
Testing matrix rank, optimally
Maria-Florina Balcan, Yi Li, David P. Woodruff, and Hongyang Zhang · 2019
Closest in time.
Adaptive sparse recovery with limited adaptivity
Akshay Kamath and Eric Price · 2019
Closest in time.