@article{Rudelson99,
author = {Mark Rudelson},
title = {Random vectors in the isotropic position},
journal = {J. Functional Analysis},
volume = 164,
number = 1,
pages = "60--72",
year = 1999,
}
@article{Alon03,
author = {Noga Alon},
title = {Problems and results in extremal combinatorics--{I}},
journal = {Discrete Mathematics},
volume = {273},
number = {1-3},
pages = {31--53},
year = {2003},
}
@article{LarsenN14,
author = {Kasper Green Larsen and
Jelani Nelson},
title = {The {Johnson}-{Lindenstrauss} lemma is optimal for linear dimensionality reduction},
journal = {CoRR},
volume = {abs/1411.2404},
year = {2014},
}
@inproceedings{KaneMN11,
author = {Daniel M. Kane and
Raghu Meka and
Jelani Nelson},
title = {Almost Optimal Explicit {Johnson}-{Lindenstrauss} Families},
booktitle = {RANDOM},
pages = {628--639},
year = {2011},
}
@article{JayramW13,
author = {T. S. Jayram and
David P. Woodruff},
title = {Optimal Bounds for {Johnson}-{Lindenstrauss} Transforms and Streaming Problems with Subconstant Error},
journal = {{ACM} Transactions on Algorithms},
volume = {9},
number = {3},
pages = {26},
year = {2013},
}
@article{NelsonNW14,
author = {Jelani Nelson and Huy L. Nguy$\tilde{\hat{\mbox{e}}}$n and David P. Woodruff},
title = {On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation},
journal = {Linear Algebra and its Applications, Special Issue on Sparse Approximate Solution of Linear Systems},
volume = 441,
pages = "152--167",
year = 2014,
}
@article{RudelsonV13,
author = {Mark Rudelson and Roman Vershynin},
title = {Hanson-{W}right inequality and sub-gaussian concentration},
journal = {arXiv},
volume = {abs/1306.2872},
year = 2013,
}
@article{HansonW71,
AUTHOR = {David Lee Hanson and Farroll Tim Wright},
TITLE = {A bound on tail probabilities for quadratic forms in
independent random variables},
JOURNAL = {Ann. Math. Statist.},
FJOURNAL = {Annals of Mathematical Statistics},
VOLUME = {42},
YEAR = {1971},
PAGES = {1079--1083},
ISSN = {0003-4851},
MRCLASS = {60.30},
MRNUMBER = {0279864 (43 \#5585)},
MRREVIEWER = {T. M. Liggett},
}
@book {LedouxT91,
AUTHOR = {Michel Ledoux and Michel Talagrand},
TITLE = {Probability in {B}anach spaces},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin},
YEAR = {1991},
}
@BOOK{PenaG99,
author = {Victor de la Pe\~{n}a and Evarist Gin\'{e}},
title = {Decoupling: From dependence to independence},
series = {Probability and its Applications},
address = {New York},
publisher = {Springer-Verlag},
year = 1999,
}
@inproceedings{DiakonikolasKN10,
author = {Ilias Diakonikolas and
Daniel M. Kane and
Jelani Nelson},
title = {Bounded Independence Fools Degree-2 Threshold Functions},
booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science (FOCS)},
pages = {11--20},
year = {2010},
}
@article{KaneN14,
author = {Daniel M. Kane and
Jelani Nelson},
title = {Sparser {Johnson}-{Lindenstrauss} transforms},
journal = {Journal of the ACM},
volume = 61,
number = 1,
pages = 4,
year = 2014,
}
@article{MendelsonPTJ07,
author = {Shahar Mendelson and Alain Pajor and Nicole Tomczak-Jaegermann},
title = {Reconstruction and subgaussian operators in asymptotic geometric analysis},
journal = {Geometric and Functional Analysis},
volume = 17,
pages = "1248--1282",
year = 2007,
}
@article{Gordon88,
author = {Yehoram Gordon},
title = {On {Milman's} inequality and random subspaces which escape through a mesh in $\mathbb{R}^n$},
journal = {Geometric Aspects of Functional Analysis},
publisher = {Springer-Verlag Lecture Notes 1317},
pages = "84--106",
year = 1988,
}
@misc{Lee,
author = {James R. Lee},
title = {Notes on Gaussian processes and majorizing measures},
url = {\url{http://homes.cs.washington.edu/~jrl/mm.pdf}}
}
@article{CohenNW15,
author = {Michael B. Cohen and
Jelani Nelson and
David P. Woodruff},
title = {Optimal approximate matrix product in terms of stable rank},
journal = {CoRR},
volume = {abs/1507.02268},
year = {2015},
}
@article{AilonC09,
author = {Nir Ailon and
Bernard Chazelle},
title = {The Fast {Johnson}--{Lindenstrauss} Transform and Approximate Nearest Neighbors},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {1},
pages = {302--322},
year = {2009},
}
@inproceedings{Sarlos06,
author = {Tam{\'{a}}s Sarl{\'{o}}s},
title = {Improved Approximation Algorithms for Large Matrices via Random Projections},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages = {143--152},
year = {2006},
}
@inproceedings{NelsonN13,
author = {Jelani Nelson and
Huy L. Nguy$\tilde{\hat{\mbox{e}}}$n},
title = {{OSNAP:} Faster Numerical Linear Algebra Algorithms via Sparser Subspace
Embeddings},
booktitle = {Proceedings of the 54th Annual {IEEE} Symposium on Foundations of Computer Science (FOCS)},
pages = {117--126},
year = {2013},
}
@inproceedings{MengM13,
author = {Xiangrui Meng and Michael W. Mahoney},
title = {Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression},
booktitle = {Proceedings of the 45th ACM Symposium on Theory of Computing (STOC)},
year = {2013},
pages = "91--100",
}
@inproceedings{ClarksonW13,
author = {Kenneth L. Clarkson and
David P. Woodruff},
title = {Low Rank Approximation and Regression in Input Sparsity Time},
booktitle = {Proceedings of the 45th ACM Symposium on Theory of Computing (STOC)},
year = {2013},
pages = "81--90",
note = {Full version at \url{http://arxiv.org/pdf/1207.6365v4.pdf}}
}
@article{Woodruff14,
author = {David P. Woodruff},
title = {Sketching as a Tool for Numerical Linear Algebra},
journal = {Foundations and Trends in Theoretical Computer Science},
volume = {10},
number = {1-2},
pages = {1--157},
year = {2014},
}
@article{Candes08,
author = {Emmanuel Cand\`{e}s},
title = {The restricted isometry property and its implications for compressed sensing},
journal = {Comptes Rendus Mathematique},
volume = {346},
number = {9-10},
pages = "589--592",
year = 2008,
}
@article{CandesT06,
author = {Emmanuel J. Cand\`{e}s and Terence Tao},
title = {Near-optimal signal recovery from random projections: universal encoding strategies?},
journal = {IEEE Trans. Inform. Theory},
volume = 52,
year = 2006,
pages = "5406--5425",
}
@article {BaraniukDD08,
AUTHOR = {Baraniuk, R. and Davenport, M. and DeVore, R. and
Wakin, M.},
TITLE = {A simple proof of the restricted isometry property for random matrices},
JOURNAL = {Constr. Approx.},
VOLUME = {28},
YEAR = {2008},
NUMBER = {3},
PAGES = {253--263},
}
@book{FoucartR13,
author={Simon Foucart and Holger Rauhut},
title={A Mathematical Introduction to Compressive Sensing},
publisher={Birkha{\"{u}}ser},
address = {Boston},
year={2013},
}
@article {Donoho06,
AUTHOR = {Donoho, D.},
TITLE = {Compressed sensing},
JOURNAL = {IEEE Trans. Inform. Theory},
VOLUME = {52},
YEAR = {2006},
NUMBER = {4},
PAGES = {1289--1306},
}
@article{BourgainDN15,
author = {Jean Bourgain and Sjoerd Dirksen and Jelani Nelson},
title = {Toward a unified theory of sparse dimensionality reduction in {Euclidean} space},
journal = {Geometric and Functional Analysis (GAFA), to appear},
year = {2015},
note = {Preliminary version in STOC 2015.},
}
@BOOK{Talagrand14,
author = {Michel Talagrand},
title = {Upper and lower bounds for stochastic processes: modern methods and classical problems},
publisher = {Springer},
year = 2014,
}
@article{Fernique75,
author = {Xavier Fernique},
title = {Regularit\'{e} des trajectoires des fonctions al\'{e}atoires gaussiennes},
volume = {480},
pages = "1--96",
journal = {Lecture Notes in Math.},
year = 1975,
}
@article{Dirksen14,
author = {Sjoerd Dirksen},
title = {Dimensionality reduction with subgaussian matrices: a unified theory},
journal = {CoRR},
volume = {abs/1402.3973},
year = {2014},
}
@article{OymakRS15,
author = {Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi},
title = {Dimensionality reduction with subgaussian matrices: a unified theory},
journal = {CoRR},
volume = {abs/1506.03521},
year = {2015},
}
@article{Dirksen13,
author = {Sjoerd Dirksen},
title = {Tail bounds via generic chaining},
journal = {CoRR},
volume = {abs/1309.3522v2},
year = {2013},
}
@article{KlartagM05,
author = {Bo'az Klartag and Shahar Mendelson},
title = {Empirical processes and random projections},
journal = {J. Funct. Anal.},
volume = 225,
number = 1,
pages = "229--245",
year = 2005,
}
@article{KMR14,
author = {Felix Krahmer and Shahar Mendelson and Holger Rauhut},
title = {Suprema of chaos processes and the restricted isometry property},
journal = {{C}omm. {P}ure {A}ppl. {M}ath.},
year = {2014},
number = 11,
pages = {1877--1904},
volume = 67,
}
@article{BDN15,
author = {Jean Bourgain and Sjoerd Dirksen and Jelani Nelson},
year={2015},
journal={Geometric and Functional Analysis},
title={Toward a unified theory of sparse dimensionality reduction in {Euclidean} space},
publisher={Springer Basel},
pages={1-80},
}
@Article{JL84,
author = {William B. Johnson and Joram Lindenstrauss},
title = {Extensions of {Lipschitz} mappings into a {Hilbert} space},
journal = {Contemporary Mathematics},
volume = 26,
pages = "189--206",
year = 1984
}
@article{CharikarCF04,
author = {Moses Charikar and
Kevin C. Chen and
Martin Farach{-}Colton},
title = {Finding frequent items in data streams},
journal = {Theor. Comput. Sci.},
volume = {312},
number = {1},
pages = {3--15},
year = {2004},
}
@article{ThorupZ12,
author = {Mikkel Thorup and
Yin Zhang},
title = {Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {2},
pages = {293--331},
year = {2012},
}