An Introduction to Matrix Concentration Inequalities

By Joel A. Tropp. 2015

1,345 citations recorded by the source corpus.

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.

Subfields: Applied Mathematics, Statistical and Nonlinear Physics, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Statistical and Nonlinear Physics

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, background): “According to the well-known probabilistic guarantees for the Laplacian of the adjacency matrix of an ER model, λ 2 ( I ∗ ) = Θ p ( ) and v max = Θ p ( dp ) (see, e.g., Tropp, 2015).”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Now we have the following expected decrease of the function value for one update, by the convexity of ω and using Jensen’s inequality, apply Jensen’s inequality using the convexity of (cid:107)·(cid:107) H for some H (cid:23) 0 and that ω is monotonically increasing on the positive domain and the fa”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “This paper initiated a line of literature on matrix sparsification in the randomized NLA community; see Tropp (2015) for more references.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Using standard concentration inequalities for random matrices [55], [56], one derives the following strong convexity and smoothness bounds [27], [57], [58].”
Stochastic Cubic Regularization for Fast Nonconvex Optimization (2017, methodology): “In order to guarantee the uniform concentration in Lemma 4, we can directly apply results from matrix concentration to obtain the desired result [Tropp et al., 2015].”
Training Complex Models with Multi-Task Weak Supervision (2018, methodology): “2017), we develop a simple and scalable matrix completionstyle algorithm, which we are able to analyze by applying strong matrix concentration bounds (Tropp 2015).”
Universality and Sharp Matrix Concentration Inequalities (2022, methodology): “1) of sums of independent random matrices is motivated by a wide variety of applications [28], sums of independent random vectors do not appear to arise as often in practice (except in the special case of independent entries).”
A Fine-Grained Spectral Perspective on Neural Networks (2019, background): “5×10 samples, it will be difficult in the near future for one to have enough data to even detect the smaller eigenvalues κd,k, k > 5, based on standard eigenvalue concentration bounds (Tropp, 2015).”
Provable Filter Pruning for Efficient Neural Networks (2019, background): “However, by the nature of the exponential decay in probability associated with importance sampling schemes (see Theorem 1), sampling schemes perform truly well when the sampling pool and the number of samples is sufﬁciently large (Tropp et al., 2015).”
PARTIAL RECOVERY FOR TOP-K RANKING: OPTIMALITY OF MLE AND SUB-OPTIMALITY OF SPECTRAL METHOD (2020, neutral): “Its Hessian ∇ 2 n ( θ ) = H ( θ ) ∈ R n × n is given by the formula It can be viewed as the Laplacian of the weighted random graph { ψ ) , the spectrum of H ( θ ) can be well controlled via some standard random matrix tool [24].”
Optimal full ranking from pairwise comparisons (2021, background): “By matrix Bernstein inequality in [53], we have”
Analysis of elliptical copula correlation factor model with Kendall's tau (2013, methodology): “1 and the proof of [42], inequality (6.”
Time-uniform Chernoff bounds via nonnegative supermartingales (2018, background): “See Tropp (2015) for a recent exposition and further references.”