2016

Four lectures on probabilistic methods for data science

Vershynin, Roman

Understand

Methods of high-dimensional probability play a central role in applications for statistics, signal processing theoretical computer science and related fields.

These lectures present a sample of particularly useful tools of high-dimensional probability, focusing on the classical and matrix Bernstein's inequality and the uniform matrix deviation inequality.
We illustrate these tools with applications for dimension reduction, network analysis, covariance estimation, matrix completion and sparse signal recovery.
The lectures are geared towards beginning graduate students who have taken a rigorous course in probability but may not have any experience in data science applications.

Built on

P. W. Holland, K. B. Laskey, S. Leinhardt, |em Stochastic blockmodels: first steps, Social Networks 5 (1983), 109–137
1983
Earlier work this paper cites.
W. B. Johnson, J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space
1984
Earlier work this paper cites.
Y. Gordon, Some inequalities for Gaussian processes and applications,
1985
Earlier work this paper cites.
Y. Gordon, On Milman’s inequality and random subspaces which escape through a mesh in ℝ n \mathbb{R}^{n} ,
1986
Earlier work this paper cites.
Y. Gordon, Elliptically contoured distributions,
1987
Earlier work this paper cites.
M. Ledoux, M. Talagrand, Probability in Banach spaces. Isoperimetry and processes
1991
Earlier work this paper cites.
Y. Gordon, Majorization of Gaussian processes and geometric applications,
1992
Earlier work this paper cites.
R. Bhatia, Matrix Analysis
1997
Earlier work this paper cites.
M. Ledoux, The concentration of measure phenomenon
2001
Earlier work this paper cites.
F. McSherry, Spectral partitioning of random graphs
2001
Earlier work this paper cites.
R. Ahlswede, A. Winter, Strong converse for identification via quantum channels
2002
Earlier work this paper cites.
J. Matou¨ek, Lectures on discrete geometry
2002
Earlier work this paper cites.
D. Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins
2003
Earlier work this paper cites.
S.Mendelson,S.Mendelson, A few notes on statistical learning theory,
2003
Earlier work this paper cites.
O. Bousquet1, S. Boucheron, G. Lugosi, Introduction to statistical learning theory,
2004
Earlier work this paper cites.
U. Feige, E. Ofek, Spectral techniques applied to sparse random graphs,
2005
Earlier work this paper cites.
B. Klartag, S. Mendelson, Empirical processes and random projections,
2005
Earlier work this paper cites.
N. Ailon, B. Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
2006
Earlier work this paper cites.

Similar

E. Candes, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,
2006
Cited alongside, same era.
G. Schechtman, Two observations regarding embedding subsets of Euclidean spaces in normed spaces
2006
Cited alongside, same era.
S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Reconstruction and subgaussian operators in asymptotic geometric analysis
2007
Cited alongside, same era.
R. Baraniuk, M. Davenport, R. DeVore, M. Wakin, A simple proof of the restricted isometry property for random matrices,
2008
Cited alongside, same era.
E. Candes, B. Recht, Exact Matrix Completion via Convex Optimization,
2009
Cited alongside, same era.
M. E. Newman, Networks. An introduction
2010
Cited alongside, same era.
R. I. Oliveira, Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
Original
2010
Cited alongside, same era.
R. I. Oliveira, Sums of random Hermitian matrices and an inequality by Rudelson
2010
Cited alongside, same era.
D. Gross, Recovering low-rank matrices from few coefficients in any basis,
2011
Cited alongside, same era.
B. Recht, A simpler approach to matrix completion,
2011
Cited alongside, same era.
R. Chen, A. Gittens, J. Tropp, The masked sample covariance estimator: an analysis using matrix concentration inequalities,
2012
Cited alongside, same era.
M. Davenport, M. Duarte, Yonina C. Eldar, Gitta Kutyniok, Introduction to compressed sensing,
2012
Cited alongside, same era.

Then

D. Amelunxen, M. Lotz, M. McCoy, J. Tropp, Living on the edge: phase transitions in convex programs with random data,
2014
Later among the works it cites.
M. Davenport, Y. Plan, E. van den Berg, M. Wootters, 1-bit matrix completion,
2014
Later among the works it cites.
D. Kane, J. Nelson, Sparser Johnson-Lindenstrauss Transforms
2014
Later among the works it cites.
P. Chin, A. Rao, and V. Vu, |em Stochastic block model and community detection in the sparse graphs: A spectral algorithm with optimal rate of recovery, preprint, 2015
2015
Later among the works it cites.
S. Dirksen, Tail bounds via generic chaining,
2015
Later among the works it cites.
J. Tropp, An introduction to matrix concentration inequalities
2015
Later among the works it cites.
R. Vershynin, Estimation in high dimensions: a geometric perspective
2015
Later among the works it cites.
E. Abbe, A. S. Bandeira, G. Hall. Exact recovery in the stochastic block model,
2016
Closest in time.
A. Bandeira, R. van Handel, Sharp nonasymptotic bounds on the norm of random matrices with independent entries
2016
Closest in time.
T. Cai, R. Zhao, H. Zhou, Estimating structured high-dimensional covariance and precision matrices: optimal rates and adaptive estimation,
2016
Closest in time.
S. Fortunato, Santo; D. Hric, Community detection in networks: A user guide
2016
Closest in time.
O. Guedon, R. Vershynin, Community detection in sparse networks via Grothendieck’s inequality,
2016
Closest in time.
A. Javanmard, A. Montanari, F. Ricci-Tersenghi, Phase transitions in semidefinite relaxations,
2016
Closest in time.
B. Hajek, Y. Wu, J. Xu, Achieving exact cluster recovery threshold via semidefinite programming,
2016
Closest in time.
E. Mossel, J. Neeman, A. Sly, Belief propagation, robust reconstruction and optimal recovery of block models
2016
Closest in time.
Y. Plan, R. Vershynin, E. Yudovina, High-dimensional estimation with geometric constraints,
2016
Closest in time.
V. Koltchinskii, K. Lounici, Concentration inequalities and moment bounds for sample covariance operators,
2017
Closest in time.
E. Candes, T. Tao, The power of convex relaxation: near-optimal matrix completion,
2080
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…