User-Friendly Tail Bounds for Sums of Random Matrices III: The Matrix Chernoff Inequality for Sums of Independent Positive-Semidefinite Random MatricesResearch Paper
The classical Chernoff bound controls the probability that a sum of independent, nonnegative, uniformly bounded random variables deviates from its mean, with exponentially small tails governed by the Kullback–Leibler divergence between two Bernoulli laws. Many problems in numerical linear algebra, graph sparsification, compressed sensing and randomized…