2015

An Introduction to Matrix Concentration Inequalities

Tropp, Joel A.

Understand

In recent years, random matrices have come to play a major role in computational mathematics, but most of the classical areas of random matrix theory remain the province of experts.

Over the last decade, with the advent of matrix concentration inequalities, research has advanced to the point where we can conquer many (formerly) challenging problems with a page or two of arithmetic.
The aim of this monograph is to describe the most successful methods from this area along with some interesting examples that these techniques can illuminate.

Built on

The generalised product moment distribution in samples from a multivariate normal population
J. Wishart · 1928
Earlier work this paper cites.
Über monotone Matrixfunktionen
K. Löwner · 1934
Earlier work this paper cites.
Über konvexe Matrixfunktionen
F. Kraus · 1936
Earlier work this paper cites.
Numerical inverting of matrices of high order
J. von Neumann and H. H. Goldstine · 1947
Earlier work this paper cites.
Numerical inverting of matrices of high order. II
H. H. Goldstine and J. von Neumann · 1951
Earlier work this paper cites.
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations
H. Chernoff · 1952
Earlier work this paper cites.
Monotone and convex operator functions
J. Bendat and S. Sherman · 1955
Earlier work this paper cites.
Characteristic vectors of bordered matrices with infinite dimensions
E. P. Wigner · 1955
Earlier work this paper cites.
On the evolution of random graphs
P. Erdős and A. Rényi · 1960
Earlier work this paper cites.
A general class of coefficients of divergence of one distribution from another
S. M. Ali and S. D. Silvey · 1966
Earlier work this paper cites.
A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming
L. M. Brègman · 1967
Earlier work this paper cites.
Information-type measures of difference of probability distributions and indirect observations
I. Csiszár · 1967
Earlier work this paper cites.
Distribution of eigenvalues in certain sets of random matrices
V. A. Marčenko and L. A. Pastur · 1967
Earlier work this paper cites.
An introduction to probability theory and its applications. Vol. I
W. Feller · 1968
Earlier work this paper cites.
An introduction to probability theory and its applications. Vol. II
W. Feller · 1971
Earlier work this paper cites.
A new proof of A. Dvoretzky’s theorem on cross-sections of convex bodies
V. D. Milman · 1971
Earlier work this paper cites.
A bound for the error in the normal approximation to the distribution of a sum of dependent random variables
C. Stein · 1972
Earlier work this paper cites.
Remarks on two theorems of E. Lieb
H. Epstein · 1973
Earlier work this paper cites.
Convex trace functions and the Wigner–Yanase–Dyson conjecture
E. H. Lieb · 1973
Earlier work this paper cites.
Entropy, information and quantum measurements
G. Lindblad · 1973
Earlier work this paper cites.
The pair correlation of zeros of the zeta function
H. L. Montgomery · 1973
Earlier work this paper cites.
Entropy for automorphisms of
A. Connes and E. Størmer · 1975
Earlier work this paper cites.
Regularité des trajectoires des fonctions aléatoires gaussiennes
X. Fernique · 1975
Earlier work this paper cites.
On tail probabilities for martingales
D. A. Freedman · 1975
Earlier work this paper cites.
Functional calculus for sesquilinear forms and the purification map
W. Pusz and S. L. Woronowicz · 1975
Earlier work this paper cites.
Concavity of certain maps on positive definite matrices and applications to Hadamard products
T. Ando · 1979
Earlier work this paper cites.
Means of positive linear operators
F. Kubo and T. Ando · 1979
Earlier work this paper cites.
Multivariate analysis
K. V. Mardia, J. T. Kent, and J. M. Bibby · 1979
Earlier work this paper cites.
The symmetric eigenvalue problem
B. N. Parlett · 1980
Earlier work this paper cites.
Probability
A. N. Shiryaev · 1980
Earlier work this paper cites.
Quantum mathematical physics
W. Thirring · 1980
Earlier work this paper cites.
Remarques sur un résultat non publié de B. Maurey
G. Pisier · 1981
Earlier work this paper cites.
Jensen’s inequality for operators and Löwner’s theorem
F. Hansen and G. K. Pedersen · 1982
Earlier work this paper cites.
Aspects of multivariate statistical theory
R. J. Muirhead · 1982
Earlier work this paper cites.
Stochastic blockmodels: First steps
P. W. Holland, K. B. Laskey, and S. Leinhardt · 1983
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
W. B. Johnson and J. Lindenstrauss · 1984
Earlier work this paper cites.
On Lipschitz embedding of finite metric spaces in Hilbert space
J. Bourgain · 1985
Earlier work this paper cites.
Inequalities of Bernstein–Jackson-type and the degree of compactness in Banach spaces
B. Carl · 1985
Earlier work this paper cites.
Some inequalities for Gaussian processes and applications
Y. Gordon · 1985
Earlier work this paper cites.
Quasi-entropies for finite quantum systems
D. Petz · 1986
Earlier work this paper cites.
Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis
J. Bourgain and L. Tzafriri · 1987
Earlier work this paper cites.
The volume of convex bodies and Banach space geometry
G. Pisier · 1989
Earlier work this paper cites.
On a problem of Kadison and Singer
J. Bourgain and L. Tzafriri · 1991
Earlier work this paper cites.
Topics in matrix analysis
R. A. Horn and C. R. Johnson · 1991
Earlier work this paper cites.
Noncommutative Khintchine and Paley inequalities
F. Lust-Piquard and G. Pisier · 1991
Earlier work this paper cites.
Probability in Banach Spaces: Isoperimetry and Processes
M. Ledoux and M. Talagrand · 1991
Earlier work this paper cites.
Universal approximation bounds for superpositions of a sigmoidal function
A. R. Barron · 1993
Earlier work this paper cites.
Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix
Z. D. Bai and Y. Q. Yin · 1993
Earlier work this paper cites.
Some remarks on coordinate restriction of operators to coordinate subspaces
B. Kashin and L. Tzafriri · 1994
Earlier work this paper cites.
A survey of certain trace inequalities
D. Petz · 1994
Earlier work this paper cites.
Optimum bounds for the distributions of martingales in Banach spaces
I. Pinelis · 1994
Earlier work this paper cites.
The geometry of graphs and some of its algorithmic applications
N. Linial, E. London, and Y. Rabinovich · 1995
Earlier work this paper cites.
Randomized Algorithms
R. Motwani and P. Raghavan · 1995
Earlier work this paper cites.
Efficient agnostic learning of neural networks with bounded fan-in
W. S. Lee, P. L. Bartlett, and R. C. Williamson · 1996
Earlier work this paper cites.
Matrix Analysis
R. Bhatia · 1997
Earlier work this paper cites.
Fast Monte Carlo algorithms for finding low-rank approximations
A. Frieze, R. Kannan, and S. Vempala · 1998
Earlier work this paper cites.
Learning with Kernels
B. Schölkopf and S. Smola · 1998
Earlier work this paper cites.
Clustering in large graphs and matrices
P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay · 1999
Earlier work this paper cites.
Random vectors in the isotropic position
M. Rudelson · 1999
Earlier work this paper cites.
The probabilistic method
N. Alon and J. H. Spencer · 2000
Earlier work this paper cites.
The expected norm of random matrices
Y. Seginer · 2000
Earlier work this paper cites.
Fast computation of low rank matrix approximations
D. Achlioptas and F. McSherry · 2001
Earlier work this paper cites.

Similar

Lectures on modern convex optimization
A. Ben-Tal and A. Nemirovski · 2001
Cited alongside, same era.
Operator Khintchine inequality in non-commutative probability
A. Buchholz · 2001
Cited alongside, same era.
Fast Monte Carlo algorithms for approximate matrix multiplication
P. Drineas and R. Kannan · 2001
Cited alongside, same era.
Algebraic Graph Theory
C. Godsil and G. Royle · 2001
Cited alongside, same era.
Probability and random processes
G. R. Grimmett and D. R. Stirzaker · 2001
Cited alongside, same era.
Using the Nyström method to spped up kernel machines
C. K. I. Williams and M. Seeger · 2001
Cited alongside, same era.
Strong converse for identification via quantum channels
R. Ahlswede and A. Winter · 2002
Cited alongside, same era.
Local operator theory, random matrices, and Banach spaces
K. R. Davidson and S. J. Szarek · 2002
Cited alongside, same era.
Near-optimal sparse Fourier representations via sampling
A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss · 2002
Cited alongside, same era.
Inequalities for quantum entropy: A review with conditions for equality
M. B. Ruskai · 2002
Cited alongside, same era.
Concentration inequalities using the entropy method
S. Boucheron, G. Lugosi, and P. Massart · 2003
Cited alongside, same era.
Jensen’s operator inequality
F. Hansen and G. K. Pedersen · 2003
Cited alongside, same era.

Then

Sums of random Hermitian matrices and an inequality by Rudelson
R. I. Oliveira · 2010
Later among the works it cites.
Statistics for high-dimensional data
P. Bühlmann and S. van de Geer · 2011
Later among the works it cites.
Subsampling algorithms for semidefinite programming
A. d’Asprémont · 2011
Later among the works it cites.
A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
P. Drineas and A. Zouzias · 2011
Later among the works it cites.
Perspectives of matrix convex functions
A. Ebadian, I. Nikoufar, and M. E. Gordji · 2011
Later among the works it cites.
John von Neumann’s analysis of Gaussian elimination and the origins of modern numerical analysis
J. F. Grcar · 2011
Later among the works it cites.
Recovering low-rank matrices from few coefficients in any basis
D. Gross · 2011
Later among the works it cites.
Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions
N. Halko, P.-G. Martinsson, and J. A. Tropp · 2011
Later among the works it cites.
Randomized algorithms for matrices and data
M. Mahoney · 2011
Later among the works it cites.
Some extensions of Bernstein’s inequality for self-adjoint operators
Original
S. Minsker · 2011
Later among the works it cites.
Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
A. Magen and A. Zouzias · 2011
Later among the works it cites.
The spectrum of random
R. I. Oliveira · 2011
Later among the works it cites.
Matrix analysis with some applications
D. Petz · 2011
Later among the works it cites.
A simpler approach to matrix completion
B. Recht · 2011
Later among the works it cites.
Information, divergence and risk for binary experiments
M. D. Reid and R. C. Williamson · 2011
Later among the works it cites.
Freedman’s inequality for matrix martingales
J. A. Tropp · 2011
Later among the works it cites.
User-friendly tail bounds for matrix martingales
J. A. Tropp · 2011
Later among the works it cites.
User-friendly tail bounds for sums of random matrices
J. A. Tropp · 2011
Later among the works it cites.
Improved analysis of the subsampled randomized Hadamard transform
J. A. Tropp · 2011
Later among the works it cites.
Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
S. Chrétien and S. Darses · 2012
Later among the works it cites.
The masked sample covariance estimator: An analysis using matrix concentration inequalities
R. Y. Chen, A. Gittens, and J. A. Tropp · 2012
Later among the works it cites.
The masked sample covariance estimator: An analysis using matrix concentration inequalities
R. Y. Chen, A. Gittens, and J. A. Tropp · 2012
Later among the works it cites.
The Convex Geometry of Linear Inverse Problems
V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky · 2012
Later among the works it cites.
Tail inequalities for sums of random matrices that depend on the intrinsic dimension
D. Hsu, S. M. Kakade, and T. Zhang · 2012
Later among the works it cites.
Noncommutative martingale deviation and Poincaré type inequalities with applications
Original
M. Junge and Q. Zeng · 2012
Later among the works it cites.
Random feature maps for dot product kernels
P. Kar and H. Karnick · 2012
Later among the works it cites.
Topics in random matrix theory
T. Tao · 2012
Later among the works it cites.
From joint convexity of quantum relative entropy to a concavity theorem of Lieb
J. A. Tropp · 2012
Later among the works it cites.
Introduction to the non-asymptotic analysis of random matrices
R. Vershynin · 2012
Later among the works it cites.
Near-optimal entrywise sampling for data matrices
D. Achlioptas, Z. Karnin, and E. Liberty · 2013
Later among the works it cites.
Concentration Inequalities
S. Boucheron, G. Lugosi, and P. Massart · 2013
Later among the works it cites.
Low rank approximation and regression in input sparsity time
K. L. Clarkson and D. P. Woodruff · 2013
Later among the works it cites.
A mathematical introduction to compressive sensing
S. Foucart and H. Rauhut · 2013
Later among the works it cites.
Matrix Analysis
R. A. Horn and C. R. Johnson · 2013
Later among the works it cites.
Noncommutative Bennett and Rosenthal inequalities
M. Junge and Q. Zeng · 2013
Later among the works it cites.
Math 247a: Introduction to random matrix theory
T. Kemp · 2013
Later among the works it cites.
Bounding the smallest singular value of a random matrix without concentration
Original
V. Koltchinskii and S. Mendelson · 2013
Later among the works it cites.
The achievable performance of convex demixing
Original
M. B. McCoy and J. A. Tropp · 2013
Later among the works it cites.
Efficient rounding for the noncommutative Grothendieck inequality (extended abstract)
A. Naor, O. Regev, and T. Vidick · 2013
Later among the works it cites.
The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties
Original
R. I. Oliveira · 2013
Later among the works it cites.
On the expectation of the norm of random matrices with non-identically distributed entries
S. Riemer and C. Schütt · 2013
Later among the works it cites.
The top eigenvalue of the random Toeplitz matrix and the sine kernel
A. Sen and B. Virág · 2013
Later among the works it cites.
Randomized primitives for linear algebra and applications
A. Zouzias · 2013
Later among the works it cites.
Exact recovery in the stochastic block model
Original
E. Abbé, A. S. Bandeira, and G. Hall · 2014
Later among the works it cites.
Living on the edge: A geometric theory of phase transitions in convex optimization
Original
D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp · 2014
Later among the works it cites.
An approximate version of Carathéodory’s theorem with applications to approximating Nash equilibria and dense bipartite subgraphs
Original
S. Barman · 2014
Later among the works it cites.
Sharp nonasymptotic bounds on the norm of random matrices with independent entries
Original
A. S. Bandeira and R. Van Handel · 2014
Later among the works it cites.
Subadditivity of matrix
R. Y. Chen and J. A. Tropp · 2014
Later among the works it cites.
Revisiting the Nyström method for improved large-scale machine learning
Original
A. Gittens and M. Mahoney · 2014
Later among the works it cites.
Tail bounds for all eigenvalues of a sum of random matrices
Original
A. Gittens and J. A. Tropp · 2014
Later among the works it cites.
Introduction to Matrix Analysis and Applications
F. Hiai and D. Petz · 2014
Later among the works it cites.
Compact random feature maps
R. Hamid, Y. Xiao, A. Gittens, and D. DeCoste · 2014
Later among the works it cites.
A note on randomized element-wise matrix sparsification
Original
A. Kundu and P. Drineas · 2014
Later among the works it cites.
Randomized nonlinear component analysis
D. Lopez-Paz, S. Sra, A. Smola, Z. Ghahramani, and B. Schölkopf · 2014
Later among the works it cites.
Matrix concentration inequalities via the method of exchangable pairs
Original
L. Mackey, M. I. Jordan, R. Y. Chen, B. Farrell, and J. A. Tropp · 2014
Later among the works it cites.
Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem
Original
A. Marcus, D. A. Spielman, and N. Srivastava · 2014
Later among the works it cites.
Sharp recovery thresholds for convex deconvolution, with applications
Original
M. McCoy and J. A. Tropp · 2014
Later among the works it cites.
Paved with good intentions: analysis of a randomized block Kaczmarz method
D. Needell and J. A. Tropp · 2014
Later among the works it cites.
Efron–Stein inequalities for random matrices
Original
D. Paulin, L. Mackey, and J. A. Tropp · 2014
Later among the works it cites.
Convex recovery of a structured signal from independent random measurements
Original
J. A. Tropp · 2014
Later among the works it cites.
Sketching as a tool for numerical linear algebra
D. Woodruff · 2014
Later among the works it cites.

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…