Fetching the paper…
Reading the bibliography…
We study the problem of testing whether a matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$ with bounded entries ($\|\mathbf{A}\|_\infty \leq 1$) is positive semi-definite (PSD), or $\epsilon$-far in Euclidean distance from the PSD cone, meaning that $\min_{\mathbf{B} \succeq 0} \|\mathbf{A} - \mathbf{B}\|_F^2 > \epsilon n^2$, where $\mathbf{B} \succeq 0$ denotes that $\mathbf{B}$ is PSD.
Remarks to maurice frechet’s article“sur la definition axiomatique d’une classe d’espace distances vectoriellement applicable sur l’espace de hilbert
Isaac J Schoenberg · 1935
Earlier work this paper cites.
Rounding-off errors in matrix processes
Alan M Turing · 1948
Earlier work this paper cites.
Principal submatrices ix: Interlacing inequalities for singular values of submatrices
Robert C Thompson · 1972
Earlier work this paper cites.
Non commutative khintchine and paley inequalities
Françoise Lust-Piquard and Gilles Pisier · 1991
Earlier work this paper cites.
Applied nonlinear control
Jean-Jacques E Slotine, Weiping Li, et al · 1991
Earlier work this paper cites.
Heat conduction
M Necati Ã-zisik, M Necati Özısık, and M Necati Özışık · 1993
Earlier work this paper cites.
Stability, instability and chaos: an introduction to the theory of nonlinear differential equations
Paul Glendinning · 1994
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X Goemans and David P Williamson · 1995
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.
Lectures on spectral graph theory
Fan RK Chung · 1996
Earlier work this paper cites.
Semidefinite programming
Lieven Vandenberghe and Stephen Boyd · 1996
Earlier work this paper cites.
Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems
Sanjeev Arora · 1998
Earlier work this paper cites.
Property testing and its connection to learning and approximation
Oded Goldreich, Shari Goldwasser, and Dana Ron · 1998
Earlier work this paper cites.
Property testing of data dimensionality
Robert Krauthgamer and Ori Sasson · 2003
Earlier work this paper cites.
Testing metric properties
Michal Parnas and Dana Ron · 2003
Earlier work this paper cites.
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.
Fast algorithms for approximate semidefinite programming using the multiplicative weights update method
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2005
Earlier work this paper cites.
Exact kolmogorov and total variation distances between some familiar discrete distributions
José A Adell and Pedro Jodrá · 2006
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.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Earlier work this paper cites.
Fast matrix multiplication is stable
James Demmel, Ioana Dumitriu, Olga Holtz, and Robert Kleinberg · 2007
Earlier work this paper cites.
Sampling from large matrices: An approach through geometric functional analysis
Mark Rudelson and Roman Vershynin · 2007
Earlier work this paper cites.
Norms of random submatrices and sparse approximation
Joel A Tropp · 2008
Earlier work this paper cites.
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2009
Earlier work this paper cites.
Geometry of cuts and metrics
Michel Marie Deza and Monique Laurent · 2009
Earlier work this paper cites.
Matrix factorization techniques for recommender systems
Yehuda Koren, Robert Bell, and Chris Volinsky · 2009
Earlier work this paper cites.
Sines and cosines of angles in arithmetic progression
Michael P Knapp · 2009
Earlier work this paper cites.
Remarks on the non-commutative khintchine inequalities for 0< p< 2
Gilles Pisier · 2009
Earlier work this paper cites.
Convex optimization & Euclidean distance geometry
Jon Dattorro · 2010
Cited alongside, same era.
Sparse recovery using sparse matrices
Anna Gilbert and Piotr Indyk · 2010
Cited alongside, same era.
Introduction to testing graph properties
Oded Goldreich · 2010
Cited alongside, same era.
On the exact space complexity of sketching and streaming small norms
Daniel M Kane, Jelani Nelson, and David P Woodruff · 2010
Cited alongside, same era.
1-pass relative-error lp-sampling with applications
Morteza Monemizadeh and David P Woodruff · 2010
Cited alongside, same era.
Fast sdp algorithms for constraint satisfaction problems
David Steurer · 2010
Cited alongside, same era.
Low-rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 2017
Later among the works it cites.
Introduction to property testing
Oded Goldreich · 2017
Later among the works it cites.
Approximating spectral sums of large-scale matrices using stochastic chebyshev approximations
Insu Han, Dmitry Malioutov, Haim Avron, and Jinwoo Shin · 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.
Sublinear time low-rank approximation of positive semidefinite matrices
Cameron Musco and David P Woodruff · 2017
Later among the works it cites.
The non-commutative khintchine inequalities for 0 < p < 1 0<p<1
Gilles Pisier and Éric Ricard · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Roman Vershynin · 2010
Cited alongside, same era.
Learning submodular functions
Maria-Florina Balcan and Nicholas JA Harvey · 2011
Cited alongside, same era.
Tail bounds for all eigenvalues of a sum of random matrices
Alex Gittens and Joel A Tropp · 2011
Cited alongside, same era.
Tight bounds for lp samplers, finding duplicates in streams, and related problems
Hossein Jowhari, Mert Sağlam, and Gábor Tardos · 2011
Cited alongside, same era.
Spectral sparsification of graphs
Daniel A Spielman and Shang-Hua Teng · 2011
Cited alongside, same era.
Topics in random matrix theory
Terence Tao · 2011
Cited alongside, same era.
Testing sparsity over known and unknown bases
Siddharth Barman, Arnab Bhattacharyya, and Suprovat Ghoshal · 2018
Later among the works it cites.
Matrix norms in data streams: Faster, multi-pass and row-order
Vladimir Braverman, Stephen Chestnut, Robert Krauthgamer, Yi Li, David Woodruff, and Lin Yang · 2018
Later among the works it cites.
Sublinear time low-rank approximation of distance matrices
Ainesh Bakshi and David Woodruff · 2018
Later among the works it cites.
A matrix expander chernoff bound
Ankit Garg, Yin Tat Lee, Zhao Song, and Nikhil Srivastava · 2018
Later among the works it cites.
Perfect lp sampling in a data stream
Rajesh Jayaram and David P Woodruff · 2018
Later among the works it cites.
A matrix chernoff bound for strongly rayleigh distributions and spectral sparsifiers from a few random spanning trees
Rasmus Kyng and Zhao Song · 2018
Later among the works it cites.
Robust and sample optimal algorithms for psd low-rank approximation
Ainesh Bakshi, Nadiia Chepurko, and David P Woodruff · 2019
Later among the works it cites.
Schatten norms in matrix streams: Hello sparsity, goodbye dimension
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, and Roi Sinoff · 2019
Later among the works it cites.
Testing matrix rank, optimally
Maria-Florina Balcan, Yi Li, David P Woodruff, and Hongyang Zhang · 2019
Later among the works it cites.
Jess Banks, Jorge Garza Vargas, Archit Kulkarni, and Nikhil Srivastava · 2019
Later among the works it cites.
Optimal sketching for kronecker product regression and low rank approximation
Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, and David Woodruff · 2019
Later among the works it cites.
Recent advances in algorithmic high-dimensional robust statistics
Ilias Diakonikolas and Daniel M Kane · 2019
Later among the works it cites.
Sample-optimal low-rank approximation of distance matrices
Piotr Indyk, Ali Vakilian, Tal Wagner, and David Woodruff · 2019
Later among the works it cites.
Weighted reservoir sampling from distributed streams
Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, and David P Woodruff · 2019
Later among the works it cites.
Towards optimal moment estimation in streaming and distributed models
Rajesh Jayaram and David P Woodruff · 2019
Later among the works it cites.
On approximating matrix norms in data streams
Yi Li, Huy L Nguyen, and David P Woodruff · 2019
Later among the works it cites.
Querying a matrix through matrix-vector products
Xiaoming Sun, David P Woodruff, Guang Yang, and Jialin Zhang · 2019
Later among the works it cites.
High-dimensional statistics: A non-asymptotic viewpoint
Martin J Wainwright · 2019
Later among the works it cites.
A framework for adversarially robust streaming algorithms
Omri Ben-Eliezer, Rajesh Jayaram, David P Woodruff, and Eylon Yogev · 2020
Closest in time.
Four deviations suffice for rank 1 matrices
Rasmus Kyng, Kyle Luh, and Zhao Song · 2020
Closest in time.
Hyperbolic polynomials i: Concentration and discrepancy
Zhao Song and Ruizhe Zhang · 2020
Closest in time.