Sums of random Hermitian matrices and an inequality by Rudelson

By Roberto Imbuzeiro Oliveira. 2010

150 citations recorded by the source corpus.

We give a new, elementary proof of a key inequality used by Rudelson in the derivation of his well-known bound for random sums of rank-one operators. Our approach is based on Ahlswede and Winter's technique for proving operator Chernoff bounds. We also prove a concentration inequality for sums of random matrices of rank one with explicit constants.

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/6743f73ded9b430163d39d43845ea3d984f53c94

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 Mathematical Physics

In Statistics and Probability

Citations in the corpus

Group Lasso for high dimensional sparse quantile regression models (2011, background): “By Theorem 1 of Rudelson (1999), there exists a universal constant L such that provided that the last expression is smaller than n (an explicit value of the constant L and an elementary proof of Rudelson’s inequality are given in Oliveira (2010)).”
Tail inequalities for sums of random matrices that depend on the intrinsic dimension (2012, background): “There are some previous works that also give tail inequalities for sums of random matrices that do not depend on the explicit matrix dimension, at least in some special cases.”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, methodology): “Finally, let me mention Roberto Oliveira’s elegant work [40] on matrix probability inequalities, which originally spurred me to pursue this project.”
A Probabilistic and RIPless Theory of Compressed Sensing (2010, methodology): “Here, we use a more modern technique based on the matrix Bernstein inequality of Ahlswede and Winter [1], developed for this setting by Gross [26], and tightened in [48] by Tropp and in [32] by Oliveira.”
Time-uniform Chernoff bounds via nonnegative supermartingales (2018, background): “In cases when supt∈T rank(Ut+Wt) ≤ r d a.s., the pre-factor d in our bounds may be replaced by r via an argument originally due to Oliveira (2010b).”
Sharp nonasymptotic bounds on the norm of random matrices with independent entries (2014, background): “Tail bounds on ‖X‖ have appeared widely in the recent literature under the name “matrix concentration inequalities”; see [15, 24].”
Matrix concentration inequalities via the method of exchangeable pairs (2012, background): “Previous authors have applied deep results from matrix analysis to accomplish this bound: the Golden–Thompson inequality is central to [1, 35, 36], while Lieb’s result [26], Theorem 6, animates [20, 48, 49].”
Excess risk bounds for multitask learning with trace norm regularization (2012, methodology): “(cid:22) Summing this relation over k and passing to the largest eigenvalue yields Now we combine Markov’s inequality with Theorem 6 (i) and the last inequality to obtain (cid:0) (cid:1) (cid:0) (cid:1) The next result and its proof are essentially due to Oliveira ([24], Lemma 1, but see also [23].”
Loss Minimization and Parameter Estimation with Heavy Tails (2013, unknown): “Lemma 22 (Specialization of Lemma 1 in Oliveira (2010)) Fix any λ ≥ 0 , and assume X , ( Σ + λ Id) − 1 X X ≤ r 2 λ almost surely.”
Faster least squares approximation (2007, methodology): “Similar to [23] we shall view the matrix AA T as the true mean of a bounded operator valued random variable, whereas CC T = AS(AS) T = ASS T A T will be its empirical mean. Then, we will apply Lemma 1 of [ 21 ].”
Simple and deterministic matrix sketching (2012, background): “Similarly, matrix sketching by row sampling [24][14] requiresO(r log(r)/ε(2)) row samples where r = ‖A‖(2)f/‖A‖(2)2 to ensure that ‖AA − BB‖ ≤ ε‖AA‖.”