Error Bounds for Random Matrix Approximation Schemes

S. J. Szarek, On the best constants in the Khintchin-inequality , Studia Math 58

1976

Earlier work this paper cites.

Michel Ledoux and Michel Talagrand, Probability in Banach Spaces , Springer-Verlag, 1991

1991

Earlier work this paper cites.

David R. Karger, Random sampling in cut, flow, and network design problems , Proceedings of the 26th Annual ACM Symposium on Theory of Computing, May 1994, pp. 648–657

1994

Earlier work this paper cites.

by same author, Using randomized sparsification to approximate minimum cuts , Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1994, pp. 424–432

1994

Earlier work this paper cites.

by same author, Random Sampling in Graph Optimization Problems , Ph.D. thesis, Stanford University, 1995

1995

Earlier work this paper cites.

by same author, Approximating s s – t t minimum cuts in O ~ ​ ( n 2 ) \tilde{\text{O}}(n^{2}) time , Proceedings of the 28th Annual ACM Symposium on Theory of Computing, May 1996, pp. 47–55

1996

Earlier work this paper cites.

Aad W. van der Vaart and Jon A. Wellner, Weak Convergence and Empirical Processes: With Applications to Statistics , Springer, 1996

1996

Earlier work this paper cites.

Alan Frieze, Ravi Kannan, and Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations , Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 378–390

1998

Earlier work this paper cites.

J. Rohn, Computing the Norm ‖ A ‖ ∞ → 1 \|A\|_{\infty\rightarrow 1} is NP-Hard , Linear and Multilinear Algebra 47

2000

Cited alongside, same era.

Yoav Seginer, The Expected Norm of Random Matrices , Combinatorics, Probability and Computing 9

2000

Cited alongside, same era.

Dimitris Achlioptas and Frank McSherry, Fast Computation of Low Rank Matrix Approximations , Proceedings of the 33rd annual ACM symposium on Theory of Computing, 2001, pp. 611–618

2001

Cited alongside, same era.

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities using the entropy method , The Annals of Probability 31

2003

Cited alongside, same era.

Noga Alon and Assaf Naor, Approximating the Cut-Norm via Grothendieck’s inequality , Proceedings of the 36th Annual ACM symposium on Theory of Computing, 2004, pp. 72–80

2004

Cited alongside, same era.

Petros Drineas, Ravi Kannan, and Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication , SIAM Journal of Computing 36

2006

Later among the works it cites.

by same author, Fast Monte Carlo Algorithms for Matrices II: Computing Low-Rank Approximations to a Matrix , SIAM Journal of Computing 36

2006

Later among the works it cites.

by same author, Fast Monte Carlo Algorithms for Matrices III: Computing an Efficient Approximate Decomposition of a Matrix , SIAM Journal of Computing 36

2006

Later among the works it cites.

by same author, Fast Computation of Low Rank Matrix Approximations , Journal of the ACM 54

2007

Later among the works it cites.

Mark Rudelson and Roman Vershynin, Sampling from large matrices: An approach through geometric functional analysis , Journal of the ACM 54

2007

Later among the works it cites.