An Introduction to Matrix Concentration Inequalities

1.1 Historical Origins

• Random matrices emerged from geometry of numbers, multivariate statistics, numerical linear algebra, and nuclear physics, later spreading to graph theory and number theory.Wishart studied sample covariance estimators, while von Neumann and Goldstine obtained high-probability bounds for random floating-point errors.Source: §1.1 · pp. 7–8

1.2 The Modern Random Matrix

• Random matrix theory supports randomized algorithms, models data and physical phenomena, and provides mathematical examples, while its models may not closely match reality.Applications include matrix approximation, sparsification, subsampling, dimension reduction, optimization, compressed sensing, signal modeling, networks, and wireless communication.Source: §1.2 · p. 8, §1.2.1 · p. 8, §1.2.2 · pp. 9–10

1.2.3 Theoretical Aspects

• Theoretical applications include expander construction, stability of Gaussian elimination under random perturbations, high-dimensional geometry, and counterexamples in quantum information theory.A random perturbation is well conditioned with high probability, while random matrix constructions show that paired quantum channels can have greater capacity than a single channel.Source: §1.2.3 · p. 10

1.3 Random Matrices for the People

• The monograph aims to make random matrix theory accessible by showing that straightforward arithmetic can yield useful information for computational scientists.Classical methods can be brittle beyond a small set of thoroughly studied matrix classes.Source: §1.3 · p. 11

1.4 Basic Questions in Random Matrix Theory

• The work focuses on expectations and deviations of extreme eigenvalues, then uses these results to control expected spectral norms and large deviations for general matrices.Questions about other eigenvalues, singular values, eigenvectors, and general operator norms are left outside the work’s scope.Source: §1.4 · p. 11

1.5 Random Matrices as Independent Sums

• A central principle is that random matrices arising in applications can often be expressed as sums of independent random matrices.This decomposition is the organizing paradigm for the notes and enables concentration tools.Source: §1.5 · p. 12

1.5.1 Example: The Sample Covariance Estimator

• For a zero-mean random vector, the sample covariance estimator is unbiased and decomposes as a sum of independent random matrices.Specifically, EY = A, and this structure permits application of the monograph’s tools.Source: §1.5.1 · p. 12

1.6 Exponential Concentration Inequalities for Matrices

• Matrix concentration asks whether a random matrix deviates substantially from its mean in spectral norm, extending scalar concentration questions for independent sums.The Bernstein framework combines global information such as mean and variance with local bounds on summand fluctuations.Source: §1.6 · pp. 12–13, §1.6.1 · p. 13

1.6.1 The Bernstein Inequality

• The scalar Bernstein inequality supplies the independent-sum, centering, uniform-boundedness, and exponentially decaying-deviation framework that matrix Bernstein generalizes.The scalar theorem concerns independent centered uniformly bounded real variables and exponential concentration around the mean.Source: §1.6.1 · p. 13

1.6.2 The Matrix Bernstein Inequality

• Matrix Bernstein provides exponential spectral-norm concentration for sums of independent, centered, uniformly bounded random matrices, lifting scalar Bernstein to the matrix setting.The result uses global variance information and local spectral-norm bounds on summands.Source: §1.6.2 · pp. 13–14

1.6. EXPONENTIAL CONCENTRATION INEQUALITIES FOR MATRICES

• The expectation bound is identified as the most important aspect of matrix Bernstein and is often more useful than its dimension-dependent tail bound.The tail bound includes d1+d2, while the expectation estimate controls E∥Z∥ directly.Source: Introduce the sum · p. 14, §1.6 · p. 15

1.6.3 Example: The Sample Covariance Estimator

• With bounded random vectors, matrix Bernstein yields n = Const·ε−2p logp samples for relatively accurate covariance estimation, a qualitatively sharp worst-case bound.The analysis assumes ∥x∥2 ≤B and applies L = 2B/n with v(Z ) ≤B ∥A∥/n.Source: §1.6.3 · pp. 15–16

1.6.4 History of this Example

• The covariance example follows earlier work by Rudelson and related noncommutative Khintchine results, adapting analysis from [GT14].The chapter presents a result similar to Rudelson’s bound for bounded random vectors.Source: §1.6.4 · p. 16

1.6.5 Optimality of the Matrix Bernstein Inequality

• Matrix Bernstein is difficult to sharpen substantially: expected spectral norm must reflect matrix variance and an average summand bound, while a logarithmic dimensional gap can remain.No known method distinguishes cases where the lower or upper expectation bound better describes E∥Z∥2 under the stated model.Source: §1.6.5 · p. 17

1.7.1 What’s Here...

• The monograph focuses on Gaussian and Rademacher series, Chernoff, Bernstein, and intrinsic-dimension bounds, selected for illustrative value and concrete applications.Applications include sparsification, matrix multiplication, random features, submatrix norms, and random-graph Laplacians.Source: §1.7.1 · pp. 17–18

1.7.2 What’s Not Here...

• Beyond its core scope, the chapter notes Hoeffding, Bennett, unbounded and nonnegative Bernstein variants, martingale extensions, polynomial moment inequalities, and exchangeable-pairs methods.Exchangeable-pairs methods yield polynomial and exponential Efron–Stein inequalities for matrices [PMT14].Source: §1.7.2 · p. 18, §1.7 · p. 19

1.7. THE ARSENAL OF RESULTS

• Exchangeable pairs can sometimes treat dependent random matrices, but the more useful inequalities require substantial effort and are omitted; matrix logarithmic Sobolev variants are less useful than scalar results [BBLM05].The omitted exchangeable-pairs material is described as accessible to a narrower audience.Source: §1.7 · p. 20

1.8 About This Monograph

• The monograph emphasizes worked examples and applications showing how matrix concentration inequalities address practical questions.These applications form a major part of the notes.Source: §1.8 · p. 20
• It unifies expectation bounds for random-matrix spectral norms and extreme eigenvalues, including results previously scattered across the literature [MJC+14].The bounds cover the expected spectral norm and the smallest and largest eigenvalues of random symmetric matrices.Source: §1.8 · p. 20
• The presentation explains why each matrix concentration inequality is nearly optimal, using examples to show that every bound term is needed for some phenomenon.The supplied passages state that each term in each bound is necessary in at least one example.Source: §1.8 · p. 20
• A new framework makes intrinsic-dimension refinements of basic matrix concentration bounds easier to prove [HKZ12, Min11].These refinements improve the dependence on dimension.Source: §1.8 · p. 20
• The monograph provides a complete proof of Lieb’s theorem [Lie73, Thm. 6] and the background needed to understand it.The theorem is a deep matrix-analysis result on which the monograph’s concentration inequalities depend.Source: §1.8 · p. 20

Overview

• The chapter reviews matrix theory and probability prerequisites, enabling readers to proceed to the theoretical development and later discussions of matrix concentration inequalities.Sections 2.1 and 2.2 cover matrix functions and probability, with cross-references to foundational results.Source: Matrix Functions & Probability with… · p. 23, Overview · p. 23

2.1.1 Conventions

• Matrices are treated over complex fields, with real-valued results requiring no essential modification; vectors and matrices use standard inner products, norms, and algebraic conventions.The framework includes C^d, R^d, rectangular matrix spaces, square-matrix algebras, zero and identity matrices, basis elements, and unitary matrices.Source: §2.1.1 · p. 23, §2.1.2 · pp. 23–24, §2.1.3 · p. 24

2.1.6 Hermitian Matrices and Eigenvalues

• Hermitian matrices admit unitary eigenvalue decompositions with real spectra, while trace is unitarily invariant, equals the eigenvalue sum, and connects to the Frobenius norm.The chapter emphasizes minimum and maximum eigenvalues and their positive homogeneity.Source: §2.1.6 · p. 25, §2.1.7 · p. 26

2.1.8 The Semidefinite Partial Order

• The semidefinite order is defined through positive-semidefinite differences, whose cone structure and conjugation invariance support matrix inequalities.Positive-semidefinite matrices have nonnegative eigenvalues, while positive-definite matrices have positive eigenvalues; trace also dominates the maximum eigenvalue in the semidefinite case.Source: §2.1.8 · pp. 26–27

2.1.9 Standard Matrix Functions

• Standard matrix functions apply real functions to Hermitian eigenvalues, preserve spectral mapping, and transfer scalar inequalities into semidefinite inequalities.The matrix logarithm is defined only for positive-definite matrices, non-integer powers require positive-semidefinite matrices, and the transfer rule follows from diagonalization and conjugation.Source: §2.1.9 · pp. 27–28, §2.1.10 · p. 28

2.1.11 The Matrix Exponential

• The matrix exponential is always positive definite, whereas the matrix logarithm preserves semidefinite order; the exponential lacks an analogous operator-monotonicity property.These functions are introduced through standard matrix functions, power series, and functional inversion.Source: §2.1.11 · p. 28, §2.1.12 · p. 29

2.1.13 Singular Values of Rectangular Matrices

• Rectangular matrices use singular value decompositions with unitary factors and nonnegative diagonal entries, linking singular values to the eigenvalues of BB* and B*B.The Frobenius norm can be expressed in terms of singular values.Source: §2.1.13 · p. 29

2.1.14 The Spectral Norm

• The spectral norm is defined through the largest singular value for general matrices and agrees with the Hermitian definition and the ℓ2 norm on vectors.The chapter also records identities for the spectral norm that follow from singular-value and variational representations.Source: §2.1.14 · p. 30

2.1.15 The Stable Rank

• The stable rank measures matrix collinearity continuously and is bounded above by the algebraic rank, making it suitable for numerical applications.It is introduced as an analytic measure of row and column collinearity.Source: §2.1.15 · p. 30

2.1.16 Dilations

• Hermitian dilations embed general matrices into larger Hermitian matrices while preserving key spectral information, including the spectral norm.The squared dilation eigenvalues match the squared singular values of the original matrix, up to zeros.Source: §2.2 · p. 31

2.2 Probability with Matrices

• The probabilistic framework defines random matrices, componentwise expectation, independence, and standard scalar variables, with expectation commuting with fixed multiplication and factoring across independent products.The treatment assumes sufficient regularity for expectations and limit operations, while allowing bounded variables as a sufficient condition.Source: §2.2.1 · p. 32, §2.2.2 · p. 32, §2.2.3 · p. 32

2.2.5 Inequalities for Expectation

• Markov and Jensen inequalities support concentration arguments, expectation preserves semidefinite order, and independent general-matrix sums satisfy analogous variance-statistic identities.The chapter also introduces other norms, including the Schatten 1-norm, and points readers to references for matrix analysis and probability.Source: §2.2.5 · p. 33, §2.2.9 · p. 35

2.2.6 The Variance of a Random Hermitian Matrix

• For random Hermitian matrices, matrix-valued variance is positive semidefinite, while its variance statistic summarizes the maximum variance over unit-vector projections.The chapter develops this statistic as a scalar summary of matrix fluctuations.Source: §2.2.6 · pp. 33–34

2.2.7 The Variance of a Sum of Independent, Random Hermitian Matrices

• For independent Hermitian sums, the matrix variance combines through the summed second moments, with general bounds relating the sum statistic to the summand statistics.When summands are identically distributed, the left-hand bound becomes an identity.Source: §2.2.7 · p. 34

2.2.8 The Variance of a Rectangular Random Matrix

• Rectangular random matrices require separate row and column variances, whose maximum spectral norm defines a variance statistic that reduces to the Hermitian definition.Hermitian dilation explains this construction through a block-diagonal variance matrix.Source: §2.2.8 · pp. 34–35

3.1 Matrix Moments and Cumulants

• For a random Hermitian matrix X, the matrix mgf and cgf are M_X(θ) = E e^(θX) and Ξ_X(θ) = log E e^(θX), encoding variation relevant to eigenvalue control.These functions generalize scalar moments and cumulants, with the first cumulant equal to the mean and the second equal to the variance.Source: §3.1 · p. 38

3.2 The Matrix Laplace Transform Method

• The matrix Laplace transform method bounds extreme-eigenvalue tails and expectations through the trace of a random Hermitian matrix’s mgf.The argument uses monotonicity, Markov’s inequality, spectral mapping, positive definiteness, and trace domination of the maximum eigenvalue.Source: §3.2 · pp. 38–39

3.3 The Failure of the Matrix Mgf

• Unlike scalar mgfs, matrix mgfs do not factor over independent sums because e^(A+H) ≠ e^A e^H unless A and H commute, and trace-based Golden–Thompson bounds fail for three matrices.The scalar cgf addition rule also fails as stated, motivating a deeper matrix generalization.Source: §3.3 · p. 40

3.4 A Theorem of Lieb

• Lieb’s theorem establishes concavity of the trace-exponential function on positive-definite matrices, providing the key probabilistic inequality needed for matrix cgf subadditivity.The matrix result differs from the scalar analogue, where the corresponding function is linear.Source: §3.4 · p. 41

3.5 Subadditivity of the Matrix Cgf

• For independent Hermitian matrices, Lieb’s theorem yields subadditivity of the matrix cgf, extending the scalar cumulant-addition rule to the noncommutative setting.The proof repeatedly applies the probabilistic consequence of Lieb’s theorem using iterated expectations and independence.Source: §3.5 · pp. 41–42

3.6 Master Bounds for Sums of Independent Random Matrices

• Combining Laplace-transform bounds with cgf subadditivity produces master probability and expectation inequalities for sums of independent random Hermitian matrices.The same framework extends to rectangular matrices through Hermitian dilation and therefore controls spectral norms.Source: §3.6 · pp. 42–43

3.7.1 The Matrix Laplace Transform Method

• The chapter’s historical account identifies as an origin of the matrix Bernstein trick, while introduced the Lieb-based probabilistic approach leading to cgf subadditivity and master tail bounds.The account contrasts Lieb’s sharper concentration results with the potentially dimension-dependent Golden–Thompson approach of Ahlswede and Winter, while noting Oliveira’s martingale extension [Oli10a].Source: §3.7.1 · p. 43, §3.7.2 · pp. 43–44

3.7.3 Noncommutative Moment Inequalities

• Matrix Laplace-transform concentration complements older noncommutative moment inequalities, while its strongest tools arise from quantum statistical mechanics through quantum information theory.Related work includes the noncommutative Khintchine inequality and matrix Rosenthal–Pinelis inequalities [MJC+14].Source: §3.7.3 · p. 44, §3.7.4 · p. 44

3.7.4 Quantum Statistical Mechanics

• The Golden–Thompson inequality is a major result from quantum statistical mechanics, treated in matrix theory by Bhatia [Bha97, Sec. IX.3] and with more physical content by Thirring.Source: §3.7.4 · p. 45
• The Golden–Thompson inequality fails for three matrices, as shown by simple examples involving combinations of Pauli spin matrices [Bha97, Exer. IX.8.4].Source: §3.7.4 · p. 45
• Lieb’s Theorem [Lie73, Thm. 6] originated in Elliott Lieb’s work establishing concavity properties for a function measuring information in a quantum system.Source: §3.7.4 · p. 45

Matrix Gaussian Series & Matrix Rademacher Series

• Matrix Gaussian and Rademacher series extend scalar random series to sums of fixed matrices with independent Gaussian variables or random signs, covering Wigner, Toeplitz, and randomly signed matrices.The formulation provides a simple, versatile framework for random matrices whose dependencies may be difficult for classical methods.Source: Matrix Gaussian Series & Matrix… · p. 47

4.1.1 Discussion

• Theorem 4.1.1 controls the expected spectral norm and its tail through the matrix variance statistic v(Z), with analogous bounds for Gaussian and Rademacher series.The tail is subgaussian, while the expectation scales as the square root of 2v(Z)log(d1+d2).Source: §4.1.1 · p. 48, §4.1 · p. 48

About the Dimensional Factor

• The expectation bound is generally accurate, but its dimensional logarithm can be unavoidable: examples attain either E∥Z∥2 ≈ v(Z) or E∥Z∥2 ≈ v(Z)log(d1+d2).More commutative coefficients tend to produce the logarithmic factor, whereas less commutativity can yield cancellations; no simple deciding statistic is known, and current methods cannot remove the factor entirely.Source: §4.1.2 · p. 49, About the Dimensional Factor · p. 50

The Tail Bound

• The tail bound can be substantially weaker than the expectation bound because large deviations are governed by the weak variance v⋆(Z), and its exponent may be too large by a factor min{d1,d2}.For weak tails, the text recommends scalar concentration inequalities; matrix Chernoff and Bernstein inequalities can reduce this problem in later chapters.Source: The Tail Bound · p. 50, §4.2 · p. 51, Expectations and Tails · p. 51

4.2.1 Gaussian Wigner Matrices

• For Gaussian Wigner matrices, the matrix-series method gives a reasonable spectral-norm expectation estimate with only a short variance calculation, though it is not sharp compared with specialized classical results.The classical comparison relies on a substantially longer moment calculation with challenging combinatorial arguments.Source: §4.2 · p. 51, §4.2.1 · p. 52

4.3 Example: Matrices with Randomly Signed Entries

• For randomly signed matrices, the general bound matches the established leading term up to a logarithmic factor, producing a near-optimal result with minimal arithmetic rather than specialized combinatorial analysis.The established estimate is comparable to the maximum ℓ2 norm of any row or column, and the general method reproduces this leading scale.Source: §4.3 · p. 54

4.4. EXAMPLE: GAUSSIAN TOEPLITZ MATRICES

• For unsymmetric Gaussian Toeplitz matrices, the argument gives the correct scaling and an estimate within 21% of the optimal constant.The corresponding inequality is known to be correct up to the precise constant, while the limiting top-eigenvalue value is available for scaled symmetric Gaussian Toeplitz matrices [SV13, Thm. 1].Source: §4.4 · p. 56

4.5 Application: Rounding for the MaxQP Relaxation

• The MAXQP rounding method forms a Rademacher matrix series and scales it so the rounded matrix satisfies the spectral norm constraint with high probability.The scaling parameter α is chosen using the matrix variance and tail bound, and is typically small relative to d1, d2, and n.Source: §4.5 · p. 56, §4.6 · p. 57

4.6. ANALYSIS OF MATRIX GAUSSIAN & RADEMACHER SERIES

• The resulting MAXQP solution is feasible and has objective value within a factor of 2log(d1 +d2) of the maximum possible value.Because α is usually small, the scaling has limited effect on the objective function.Source: §4.6 · p. 57

4.6.1 Random Series with Hermitian Coefficients

• Theorem 4.6.1 establishes Gaussian and Rademacher concentration bounds for the extreme eigenvalues of finite Hermitian matrix series using the matrix variance statistic.The same bounds hold when independent standard normal variables are replaced by independent Rademacher variables.Source: §4.6.1 · p. 57

4.6.2 Discussion

• Unlike the general norm bound, the Hermitian theorem gives one-sided tail bounds for minimum and maximum eigenvalues, which can be valuable when their behaviors differ.For Gaussian and Rademacher series this distinction is not generally useful, but it matters for other random Hermitian matrices.Source: §4.6.2 · p. 58

4.6.3 Analysis for Hermitian Gaussian Series

• The Gaussian proof derives the matrix cgf from Gaussian moments and applies master expectation and tail bounds, optimizing at θ = 2v(Y )^-1 logd and θ = t/v(Y ).The Rademacher proof follows the same structure, using semidefinite mgf and cgf bounds based on logcosh(a) ≤a2/2.Source: §4.6.3 · p. 58, §4.6 · pp. 59–60, §4.6.4 · p. 60

4.6.5 Analysis of Matrix Series with Rectangular Coefficients

• Rectangular Gaussian and Rademacher series inherit the Hermitian bounds through Hermitian dilation, which preserves spectral information and connects the variance statistics.Applying Theorem 4.6.1 to the dilation yields Theorem 4.1.1 for matrix norms.Source: §4.6.5 · p. 61

4.7 Notes

• The notes trace the main results to and [Oli10b], contrast them with noncommutative Khintchine inequalities, and emphasize their efficient random-matrix applications.Later advances in [Oli10a] produced optimal concentration results that analyze many random matrices with little effort; Theorem 4.6.1 is an exponential-moment analogue of the polynomial-moment inequality.Source: §4.7.1 · p. 61, §4.7.2 · p. 62, §4.7.3 · p. 62

4.7.4 Wigner and Marˇcenko–Pastur

• For rectangular Gaussian matrices, Marˇcenko and Pastur established the limiting squared-singular-value distribution, while Bai–Yin gave the almost-sure limit of the largest singular value.The expectation bound (4.2.5) is attributed to Davidson and Szarek and derives from Gaussian-process comparison results of Férnique and Gordon.Source: §4.7.4 · p. 63

4.7.5 Randomly Signed Matrices

• For randomly signed matrices, (4.3.1) is due to Seginer, with later Gaussian and independent-entry extensions by Latała, Riemer and Schütt, and Bandeira and Van Handel [BV14].The analysis here uses Theorem 4.1.1 and is drawn from [Tro11c, §4].Source: §4.7.5 · p. 63

4.7.6 Gaussian Toeplitz Matrices

• For Gaussian Toeplitz matrices, prior work established limiting spectral distributions and expected-norm bounds, while this analysis based on Theorem 4.1.1 is new.The lower bound for E∥Γ_d∥ follows from Sen and Virág, and differing entry variances would be handled by a simple modification of the §4.4 argument.Source: §4.7.6 · p. 63

4.7.7 Relaxation and Rounding of MAXQP

• The MAXQP analysis, based on Theorem 4.1.1, is essentially equivalent to but achieves slightly better bounds for the constants.Nemirovski introduced semidefinite relaxation and rounding for MAXQP, while So showed that matrix moment inequalities yield an optimal result and connected matrix concentration inequalities to robust optimization.Source: §4.7.7 · pp. 63–64

A Sum of Random Positive-Semidefinite Matrices

• Matrix Chernoff inequalities control the extreme eigenvalues of sums of independent positive-semidefinite matrices, yielding information about matrix norms and nonsingularity.The summands satisfy 0 ≤ λmin(Xk) and λmax(Xk) ≤ L; the bounds concern λmax(Y) and λmin(Y).Source: A Sum of Random Positive-Semidefinite… · p. 65, §5.1 · p. 66

Aspects of the Matrix Chernoff Inequality

• The expectation bounds place λmin(Y) below and λmax(Y) above their corresponding expectation eigenvalues by fluctuation terms depending on L and dimension d.The tail bounds predict subgaussian lower-tail decay for λmin(Y) and faster-than-exponential upper-tail decay for λmax(Y), although they can overestimate actual probabilities at large deviations.Source: Aspects of the Matrix Chernoff… · p. 67

Related Results

• The matrix Rosenthal refinement [CGT12a, Thm. A.1] is valuable for unbounded, especially heavy-tailed, summands because its bound can improve on the uniform upper bound L.The chapter also notes that the dimensional factor d can be moderated when the random matrix has limited spectral content in most directions.Source: Related Results · p. 67

The Upper Chernoff Bounds

• Both terms in the upper matrix Chernoff bound are necessary: Eλmax(Yn) approaches a quantity of order logd/loglogd, so the logarithmic factor cannot generally be removed.The tail bound accurately predicts the order in the example, and the logarithm is necessary in the random-submatrix application.Source: The Upper Chernoff Bounds · p. 68

The Lower Chernoff Bounds

• The lower matrix Chernoff bounds are numerically sharp: in a coupon-collector example, the transition to λmin(Yn)>0 occurs at n = d logd.This matches the threshold for λmax(Yn)>0 and validates both lower bounds (5.1.3) and (5.1.5).Source: The Lower Chernoff Bounds · p. 69

5.2 Example: A Random Submatrix of a Fixed Matrix

• Matrix Chernoff bounds transfer to singular-value estimates for random submatrices, showing that sampled columns or rows and columns receive a fair share of squared spectral mass with controlled fluctuations.For column sampling, the fluctuation depends on the largest column norm and log d, while row-and-column sampling additionally depends on maximum row and column norms, the largest entry, and ambient dimensions.Source: §5.2 · p. 69, §5.2.1 · p. 70, §5.2.2 · p. 71

5.3.1 Background on Graph Theory

• The graph-theoretic setup defines adjacency, degree, Laplacian, and normalized Laplacian matrices, with Laplacian connectivity determined by its second-smallest eigenvalue.The Laplacian is positive semidefinite, has the all-ones vector as a zero-eigenvalue eigenvector, and the normalized Laplacian governs random-walk convergence under appropriate assumptions.Source: §5.3.1 · p. 73

5.3.2 The Model of Erd˝os & Rényi

• In G(n,p), each distinct vertex pair receives an independent Bernoulli(p) edge, allowing the adjacency and Laplacian matrices to be represented as sums of independent random matrices.Each present edge contributes one to the two incident diagonal Laplacian entries and −1 to the corresponding off-diagonal entries.Source: §5.3.2 · pp. 73–74

5.3.3 Connectivity of an Erd˝os–Rényi Graph

• Connectivity is analyzed by compressing the Laplacian to the orthogonal complement of the all-ones vector, producing independent positive-semidefinite summands whose minimum eigenvalue equals the Laplacian’s second-smallest eigenvalue.The summands have eigenvalues bounded above by L = 2, enabling application of matrix Chernoff.Source: §5.3.3 · p. 75
• A sufficient condition for G(n,p) to be connected with high probability is obtained from a matrix Chernoff lower-tail bound, and is near-optimal up to a factor of two.The argument studies the second-smallest eigenvalue of the random Laplacian, which is positive exactly when connectivity holds; the optimal result lacks the factor two on the right-hand side.Source: §5.3.3 · pp. 75–76

5.4 Proof of the Matrix Chernoff Inequalities

• The matrix Chernoff proof begins with a semidefinite mgf/cgf bound derived by applying convexity to e^(θx) on [0,L] and then using operator monotonicity of the logarithm.The argument assumes each positive-semidefinite summand has eigenvalues in [0,L].Source: §5.4 · p. 76

5.4. PROOF OF THE MATRIX CHERNOFF INEQUALITIES

• The theorem proof derives maximum- and minimum-eigenvalue expectation and tail bounds from the cgf estimates, master inequalities, trace-exponential monotonicity, and optimized changes of variables.The minimum-eigenvalue argument is more delicate because θ < 0 makes g(θ) negative and reverses relevant scaling behavior.Source: §5.4 · pp. 77–78

5.5.1 Matrix Chernoff Inequalities

• The notes place matrix Chernoff among earlier scalar and matrix results, identifying for the matrix mgf bound, [Tro11c, §5] for the tail bounds, and new expectation bounds in this chapter.They also mention information-theoretic formulations and extensions covering all eigenvalues of sums of independent positive-semidefinite matrices.Source: §5.5.1 · p. 79

5.5.2 The Matrix Rosenthal Inequality; 5.5.3 Random Submatrices; 5.5.4 Random Graphs

• Related notes trace matrix Rosenthal inequalities from Rudelson’s rank-one specialization through later refinements, and describe matrix Chernoff applications to random submatrices and graphs.Random-submatrix work includes an optimal minimum-singular-value estimate, while Laplacian compression extends to tail bounds for all eigenvalues [GT14].Source: §5.5.2 · p. 79, §5.5.3 · p. 80, §5.5.4 · p. 80

A Sum of Bounded Random Matrices

• Matrix Bernstein bounds spectral-norm deviations of independent, zero-mean random-matrix sums using the matrix variance statistic, uniform summand bound, and ambient dimension.The framework extends scalar Bernstein concentration from bounded random variables to bounded random matrices.Source: A Sum of Bounded Random Matrices · p. 81, §6.1 · p. 82, Introduce the random matrix · p. 82

Overview

• The chapter applies matrix Bernstein to randomized sparsification, approximate matrix multiplication, and random features for approximating specified matrices.These applications include sparse spectral proxies, error-controlled matrix products, and kernel-matrix approximation.Source: A Sum of Bounded Random Matrices · p. 81, Overview · p. 82

Related Results

• The standard bounds depend on ambient dimensions rather than intrinsic dimension, while matrix Chernoff can provide better results when applicable.Intrinsic-dimension refinements are developed in Chapter 7.Source: A Sum of Bounded Random Matrices · p. 81, Related Results · p. 84

6.1.1 Discussion

• The expectation bound places E∥Z∥ on the scale of the square root of v(Z), L, and a weak dependence on ambient dimension, although it need not be tight.When summands are Hermitian, the two variance terms coincide; the inequality also extends to uncentered sums by bounding deviation from the mean.Source: Aspects of the Matrix Bernstein… · p. 83, Introduce the sum · p. 83

Aspects of the Matrix Bernstein Inequality

• For moderate deviations, the tail is Gaussian-like with variance comparable to v(Z), while for large deviations it is exponential-like with scale comparable to L.The dimensional factor d1+d2 reduces the range where the tail inequality is informative, and the bound may overestimate actual tails.Source: Aspects of the Matrix Bernstein… · p. 83

Introduce the sum

• The same framework yields a matrix Bernstein corollary for independent, uncentered matrices whose deviations from their means are uniformly bounded.Its variance statistic and expectation bound follow immediately from the centered theorem.Source: Aspects of the Matrix Bernstein… · p. 83, Introduce the sum · p. 83

Related Results

• When the uniform bound L is unsuitable, heavy-tailed summands motivate an expectation bound related to the Rosenthal–Pinelis inequality [Pin94, Thm. 4.1].Other variants include matrix Bennett bounds, moment-growth assumptions, and separate upper- and lower-tail control in the Hermitian setting.Source: Related Results · p. 84

6.1.2 Optimality of the Matrix Bernstein Inequality; The Expectation Bound

• Lower-bound examples show that the expectation inequality requires both a variance-dependent term and, under symmetry, a term reflecting the summands’ uniform bound.Matching estimates for symmetric summands show that both terms are necessary, although the logarithmic factors are not always required.Source: §6.1.2 · p. 84, The Expectation Bound · p. 84

Examples where the Logarithms Appear

• The variance logarithm in (6.1.6) is necessary: a Rademacher construction and a Gaussian limit show that it cannot be removed.The argument uses the central limit theorem and Skorokhod representation to transfer the behavior to independent standard normal variables.Source: Examples where the Logarithms Appear · p. 85
• For Bernoulli summands, the bound requires a logarithm on the summand-norm term but is suboptimal by a loglog factor, whereas matrix Chernoff and Bennett capture the iterated logarithm.The comparison uses a Poisson(1) limit and the asymptotic behavior E maxk |Qk −1| ≈const· logd loglogd.Source: Examples where the Logarithms Appear · p. 85
• These logarithmic effects are not confined to the displayed commutative examples: many practical problems require the logarithms in matrix Bernstein, although no simple criterion is known.The examples rely on commutativity and infinite divisibility, but the broader applicability remains an ongoing research question.Source: Examples where the Logarithms Appear · p. 86

6.2 Example: Matrix Approximation by Random Sampling

• Empirical approximation represents a target matrix as an expectation and averages independent structured random matrices to trade approximation fidelity against complexity.The framework is intended for tasks such as sparse or low-rank matrix approximation and supports later applications in randomized linear algebra and machine learning.Source: §6.2 · p. 86

6.2.1 Setup

• The setup decomposes a target matrix into simple summands and assigns positive sampling probabilities, with the key challenge being to identify which summands are most important.Choosing an effective sampling distribution requires problem-specific insight and ingenuity.Source: §6.2.1 · p. 86

6.2. EXAMPLE: MATRIX APPROXIMATION BY RANDOM SAMPLING

• Sampling one summand with its prescribed probability produces an unbiased estimator, while averaging n independent copies preserves unbiasedness and remains structured when n is small relative to N.The central problem is to quantify the error as a function of n and balance sample complexity against approximation quality.Source: §6.2.1 · p. 86, §6.2 · p. 87

Form the matrix sampling estimator

• The sampling estimator is formed from independent copies of the single-sample random matrix, and its error analysis proceeds by centering these copies and applying matrix Bernstein.The proof controls the summands’ norm and matrix variance before invoking the concentration inequality.Source: Form the matrix sampling estimator · p. 87, Then the estimator satisfies · p. 88

6.2.2 Error Estimate for Matrix Sampling Estimators

• Corollary 6.2.1 uses the matrix Bernstein inequality to bound the approximation error of an unbiased matrix sampling estimator under a uniform norm bound.The resulting bound involves the per-sample second moment, log(d1 + d2), the sample count n, and the norm bound L.Source: Then the estimator satisfies · pp. 87–88, §6.2.2 · p. 87

6.2. EXAMPLE: MATRIX APPROXIMATION BY RANDOM SAMPLING

• The required sample count scales with the per-sample second moment m2(R) and uniform upper bound L, and achieving tolerance ε requires n proportional to ε^-2.The ε^-2 dependence reflects a central-limit-theorem limitation: highly accurate approximations require many samples.Source: §6.2 · p. 89
• Spectral-norm error bounds simultaneously control every linear function of the approximation and each singular value, while singular-vector errors are bounded when B has singular-value gaps.The singular-vector guarantee follows from perturbation theory under a gap between the relevant singular values.Source: §6.2 · p. 89

A General Sampling Model

• The general sampling model represents B as an average of simple matrices B(ω) over a probability measure, allowing an infinite family and motivating machine-learning applications.This extends the finite-expansion sampling model underlying Corollary 6.2.1.Source: A General Sampling Model · p. 89

Suboptimality of Sampling Estimators

• Sampling estimators can be substantially worse than the best structured approximation, especially when singular values decay quickly rather than remaining comparable.When singular values are comparable, the sampling estimator is within a logarithmic factor of optimal error; rapid decay can make its error much worse.Source: Suboptimality of Sampling Estimators · p. 90

Warning: Frobenius-Norm Bounds

• Frobenius-norm error bounds are typically vacuous for practical matrix approximation, including data-analysis problems involving white or pink noise.The warning is illustrated by low-rank approximation with additive white Gaussian noise, where E has independent NORMAL(0,d^-1) entries.Source: Warning: Frobenius-Norm Bounds · p. 90

6.3. APPLICATION: RANDOMIZED SPARSIFICATION OF A MATRIX

• The Frobenius-norm error can be quite large even when the required spectral-norm approximation is achieved.Thus, spectral accuracy does not imply comparable Frobenius accuracy for this sparsification procedure.Source: §6.3 · p. 91
• A small Frobenius error alone does not ensure recovery of the desired approximation, because an approximation consisting only of noise can satisfy the bound.The example bB = αE satisfies the error bound with ε = d^-1/2 despite having no relationship with Bopt.Source: §6.3 · p. 91

6.3 Application: Randomized Sparsification of a Matrix

• Sparsification is useful because sparse matrices require less storage and enable more efficient spectral computations, especially for approximately low-rank data matrices.The approach replaces a dense target by a sparse matrix close in spectral norm while preserving most information.Source: §6.3 · p. 91

6.3.1 Problem Formulation & Randomized Algorithm

• The method samples a small number of matrix entries using a non-obvious probability distribution, retaining each sampled entry in a one-entry random estimator.The sampling probabilities form a valid distribution and are designed to support the concentration analysis.Source: §6.3 · p. 91, §6.3.1 · pp. 91–92
• Averaging n independent estimators produces a matrix with at most n nonzero entries that remains unbiased for B, while making the error depend on n.The single-sample estimator has high variance because it contains only one nonzero entry, motivating independent averaging.Source: §6.3.1 · p. 92

6.3.2 Performance of Randomized Sparsification

• When srank(B) ≪ min{d1, d2}, a matrix with at most n nonzero entries can achieve small relative spectral-norm error, dramatically reducing sparsity.The stable rank emerges naturally in the error estimate and governs when the reduction is substantial.Source: §6.3 · p. 93

6.3.3 Analysis of Randomized Sparsification

• The analysis applies Corollary 6.2.1 by bounding the per-sample variance and uniform upper bound through lower bounds on sampling probabilities, using L = ∥B∥ℓ1 and m2(R) ≤2max{d1,d2}.Source: §6.3.3 · pp. 93–94

6.4.1 Problem Formulation & Randomized Algorithm

• When N substantially exceeds d1 and d2, sampling columns of B and rows of C provides a proxy for the full product because both factors contain linear dependencies.The direct multiplication cost is O(N · d1d2), while practical alternatives such as Strassen’s method are described as generally impractical.Source: §6.4.1 · p. 94

6.4. APPLICATION: RANDOMIZED MATRIX MULTIPLICATION

• The method writes BC as a sum of outer products and samples rank-one terms using probabilities based on the factors’ Frobenius norms, producing an unbiased estimator R.Computing the sampling probabilities costs at most O(N · (d1 + d2)), and E[R] = BC.Source: §6.4 · p. 95
• Averaging n independent copies of R reduces variance while preserving E[¯R_n] = BC, and forming the approximation costs O(n · d1d2) operations when n is much smaller than N.The averaged estimator provides an inexpensive approximate representation of the product, requiring no computation beyond sampling row and column indices.Source: §6.4 · p. 95

6.4.2 Performance of Randomized Matrix Multiplication

• The performance analysis assumes unit spectral norms and shows that the error depends on the average stable rank asr and logarithmically on d1 + d2 through the sample count n.The spectral-norm normalization is considered reasonable because the norm can be computed accurately at relatively low cost.Source: §6.4.2 · p. 96
• When asr is substantially smaller than N, the randomized estimate ¯R_n achieves small error relative to the scale of B and C.The stated result gives a relative error bound under a sample-size condition involving a positive tolerance ε.Source: §6.4.2 · p. 96

6.4.3 Analysis of Randomized Matrix Multiplication

• The randomized multiplication guarantee is an immediate application of empirical approximation analyzed through Corollary 6.2.1.The proof explicitly uses the unit-norm assumption and the parameter choices L = asr and m2(R) ≤ 2·asr.Source: §6.4.3 · pp. 96–97
• The analysis uniformly bounds the product estimator using sampling probabilities, unit spectral norms, and average stable rank, then estimates its per-sample second moment via positive-semidefinite relations.Source: §6.4.3 · pp. 96–97

6.5.1 Kernel Matrices

• Positive-definite kernel matrices generalize Gram matrices, support classification, regression, and feature selection, but require O(N^2) storage and O(dN^2) construction time.Their advantage is that kernel evaluations provide task-specific similarity measures beyond the Euclidean domain.Source: §6.5.1 · p. 98

6.5.2 Random Features and Low-Rank Approximation of the Kernel Matrix

• A random feature map makes G = E(zz∗), so R = zz∗ is an unbiased rank-one estimator, and n independent features produce a low-rank empirical approximation.This construction applies to positive-definite kernels and raises the question of how many features are needed for accuracy.Source: §6.5.1 · p. 98, §6.5.2 · p. 99

6.5.3 Examples of Random Feature Maps

• Angular similarity admits a random feature map from a uniformly sampled sphere, while Bôchner’s Theorem supplies complex and real maps for continuous positive-definite translation-invariant kernels.The Gaussian radial basis function kernel is reproduced by a map with w distributed as NORMAL(0,αI_d).Source: §6.5.3 · pp. 99–101

6.5.4 Performance of the Random Feature Approximation

• The performance bound uses the kernel’s intrinsic dimension, with positive definiteness and Φ(x,x) = +1 implying trG = N in its derivation.The required feature count is stated through the intrinsic-dimension condition and the uniform feature-map bound b.Source: §6.5.4 · p. 101
• When intdim(G) ≪ N, averaging n random features yields an accurate relative approximation of the kernel matrix G under the stated feature-count bound.The guarantee is expressed in (6.5.7), with b denoting the uniform bound on the feature map.Source: §6.5.4 · p. 101

6.5.5 Analysis of the Random Feature Approximation

• Applying Corollary 6.2.1 with L = bN and m2(R) ≤ bN∥G∥ yields the random-feature estimate (6.5.7).The bounds follow from positive semidefiniteness of zz∗, ∥z∥2 ≤ bN, and unbiasedness of R.Source: §6.5.5 · p. 102

6.6 Proof of the Matrix Bernstein Inequality

• The general matrix Bernstein inequality follows as a corollary of the bounded-Hermitian concentration result.The section presents the Hermitian result first and then explains how to obtain the general case.Source: §6.6 · p. 102

6.6.1 A Sum of Bounded Random Hermitian Matrices

• The Hermitian-case theorem concerns independent random Hermitian matrices whose eigenvalues are bounded above.The summands have common dimension d and satisfy E X_k = 0 and λmax(X_k) ≤ L.Source: §6.6.1 · p. 102

Introduce the random matrix

• The concentration bound is expressed using the matrix variance statistic v(Y) of the sum and holds for all t ≥ 0.The displayed bound also depends on the dimension through log d and on the eigenvalue bound L.Source: Introduce the random matrix · p. 102

6.6.2 Discussion

• The lower-eigenvalue analysis applies to independent zero-mean Hermitian matrices with λmin(Xk) ≥ −L and develops a tail bound for λmin(Y).The resulting lower-tail parameters can differ sharply from those governing λmax(Y).Source: §6.6.2 · p. 103
• Because the upper and lower spectral parameters may differ substantially, the maximum-eigenvalue assumption in Theorem 6.6.1 is less restrictive than a spectral-norm assumption.The discussion explicitly contrasts the separate parameters L and L for λmax(Y) and λmin(Y) with the norm condition in Theorem 6.1.1.Source: §6.6.2 · p. 103

6.6.3 Bounds for the Matrix Mgf and Cgf

• The proof’s central technical challenge is controlling the matrix mgf for a uniformly bounded, zero-mean random matrix with an estimate suited to the stated Bernstein theorem.The argument is intentionally not the sharpest possible; it is selected for direct use in the theorem.Source: §6.6.3 · p. 103
• The matrix mgf and cgf are bounded for a zero-mean Hermitian matrix with λmax(X) ≤ L, yielding a quadratic variance-dependent expression with denominator 1−θL/3.The proof expands e^θX into linear and quadratic terms, bounds the remainder using monotonicity, and then takes expectations and logarithms.Source: §6.6.3 · pp. 103–104

6.6.4 Proof of the Hermitian Case

• For independent zero-mean Hermitian summands satisfying λmax(Xk) ≤ L, the cgf bound, trace-exponential master inequalities, and variance additivity establish the Bernstein expectation bound for λmax(Y).The proof bounds the trace by d times the maximum eigenvalue, identifies v(Y), extracts logarithms, and optimizes over θ.Source: §6.6.4 · p. 104, §6.6 · p. 105

6.6. PROOF OF THE MATRIX BERNSTEIN INEQUALITY

• The upper-tail bound for λmax(Y) follows from the master tail inequality using θ = t/(v(Y)+Lt/3), which produces the stated elegant Bernstein form.The exact optimizing infimum is described as messy, so the proof uses this inspired parameter choice instead.Source: §6.6 · p. 105

6.6.5 Proof of the General Case

• Applying the Hermitian Bernstein theorem to the Hermitian dilation of a sum of general matrices derives the corresponding general-matrix result under ESk = 0 and ∥Sk∥ ≤ L.The dilation preserves the relevant norm and expresses the general-matrix variance statistic through the Hermitian variance calculation.Source: §6.6.5 · pp. 105–106

6.7.1 Matrix Bernstein Inequalities

• Theorem 6.6.1 improves earlier matrix Bernstein results by using the correct variance statistic, while its Lieb-based proof also yields expectation bounds, a matrix Bennett inequality, and extensions to unbounded matrices.Gross and Recht developed earlier versions with a potentially suboptimal variance parameter; Oliveira [Oli10a] obtained the correct statistic and a matrix Freedman inequality.Source: §6.7.1 · p. 106

6.7.2 The Matrix Rosenthal–Pinelis Inequality

• The matrix Rosenthal–Pinelis inequality derives from noncommutative Khintchine using the same pattern as matrix Rosenthal, extending earlier noncommutative martingale and Burkholder inequalities.The result is attributed to [CGT12a, Thm. A.1], with a related elementary proof in [MJC+14, Cor. 7.4] and antecedents in.Source: §6.7.2 · p. 107

Empirical Bounds for Covering Numbers

• For ∥ek∥≤L, randomized sampling controls the expected approximation error for every u ∈ E through a Banach-space type-two constant T2(X).The estimate follows from symmetrization, Hölder’s inequality, and a Khintchine-type inequality; the matrix spectral-norm space provides a relevant concrete example.Source: Empirical Bounds for Covering Numbers · pp. 107–108
• At most N^n norm balls of radius ε cover E = conv{e1,...,eN} after randomized sampling selects n points with repetition satisfying the required approximation condition.The probabilistic method provides the selected points, while counting the N^n possible selections gives the covering bound.Source: Empirical Bounds for Covering Numbers · p. 108

History and Applications of Empirical Approximation

• Maurey’s empirical approximation method originated in entropy-number arguments and later supported Fourier-matrix restricted isomorphism, neural-network approximation, sparse modeling, random features, and approximate Nash equilibria.Early references include Pisier [Pis81, Lem. 1] and Carl [Car85, Lem. 1], while applications include [RV06],,,, and [Bar14].Source: History and Applications of Empirical… · p. 108

6.7.4 Randomized Sparsification

• Randomized sparsification has been applied to accelerate spectral computation, semidefinite programming, and data compression, with later work using matrix concentration to sharpen its analysis.The development includes, [d’A11], [AKL13],, [DZ11], and [KD14].Source: §6.7.4 · pp. 108–109

6.7.5 Randomized Matrix Multiplication

• Randomized matrix multiplication evolved from early sampling ideas into general algorithms with improved performance and spectral-norm error bounds.Key developments are associated with,,, [Sar06],, and later analyses based on and.Source: §6.7.5 · p. 109

6.7.6 Random Features

• Random features summarize data for large-scale kernel machines, with constructions extended from translation-invariant kernels to inner-product and polynomial kernels and analyzed using matrix Bernstein inequalities.The approach was introduced in, extended in and, and analyzed here using.Source: §6.7.6 · p. 109

Results Involving the Intrinsic Dimension

• The chapter’s intrinsic-dimension program develops Chernoff and Bernstein extensions, revisits earlier applications, and supplies the generalized Laplace-transform and intrinsic-dimension arguments needed for their proofs.Intrinsic-dimension improvements are often modest but can be significant enough to produce nontrivial results for infinite-dimensional random matrices.Source: Results Involving the Intrinsic… · p. 111, §7.4 · p. 117, §7.6 · p. 119

7.1 The Intrinsic Dimension of a Matrix

• Intrinsic dimension measures the number of dimensions where a positive-semidefinite matrix has significant spectral content and can substantially improve bounds when eigenvalues decay.It is scale invariant but not monotone under the semidefinite order; it equals one for rank-one matrices and is attained at the opposite extremum for multiples of the identity.Source: §7.1 · p. 112

7.2 Matrix Chernoff with Intrinsic Dimension

• The intrinsic matrix Chernoff inequality controls the maximum eigenvalue of a positive-semidefinite random-matrix sum using the intrinsic dimension of an expectation upper bound instead of ambient dimension.The improvement can be dramatic when eigenvalues decay, although the result incurs an extra factor of two and a narrower ε range, and it does not control the minimum eigenvalue.Source: §7.2 · p. 112, §7.2.1 · p. 113

7.2.2 Example: A Random Column Submatrix

• For random column submatrices, the intrinsic Chernoff estimate depends on log of the stable rank rather than logm, improving substantially when many rows of the fixed matrix are nearly collinear.The example applies the bound to Bernoulli-sampled columns and interprets the intrinsic parameter through the stable rank of the data matrix.Source: §7.2.2 · pp. 113–114

7.3 Matrix Bernstein with Intrinsic Dimension

• The intrinsic matrix Bernstein inequality gives tail bounds for independent bounded random-matrix sums based on the intrinsic dimension of a block-diagonal variance bound.It always improves dimensional dependence relative to the earlier result, at the cost of an extra factor of four in probability and a more limited t range; integrating the tail yields an intrinsic-dimension expectation bound.Source: §7.3 · p. 114, §7.3.1 · p. 115

7.3.1 Discussion

• The Bernstein intrinsic-dimension parameter need not be comparable to the larger intrinsic dimension of either variance block, and the theorem is stated using variance upper bounds because exact variances may be difficult to calculate.The result also extends straightforwardly to uncentered sums and simplifies for Hermitian matrices.Source: §7.3.1 · p. 115

7.3.2 Example: Matrix Approximation by Random Sampling

• Intrinsic Bernstein bounds extend randomized matrix approximation by sampling and improve randomized matrix multiplication when the average stable rank is small relative to the product dimensions.The multiplication analysis replaces log(d1 + d2) with log(1 + asr) in the sample bound, reducing dependence on ambient dimension.Source: §7.3.2 · p. 115, §7.3.3 · p. 116, §7.4 · p. 117

7.4 Revisiting the Matrix Laplace Transform Bound

• The proof strategy removes ambient-dimension dependence by replacing the exponential Laplace transform with nonnegative convex maps vanishing at zero, then controlling their trace through intrinsic dimension.The generalized matrix Laplace transform bound applies to any nonnegative function nondecreasing on [0,∞), while the intrinsic-dimension lemma handles convex functions with ϕ(0)=0.Source: §7.4 · pp. 117–118, §7.5 · p. 118

7.6 Proof of the Intrinsic Chernoff Bound

• The intrinsic Chernoff proof obtains tail and expectation bounds by combining the matrix Laplace transform with an intrinsic-dimension trace bound, then optimizing the transform parameter.The expectation argument uses the increasing concavity of ψ^-1, Jensen’s inequality, and positivity of ψ(Y).Source: §7.6 · pp. 119–120

7.7.1 The Hermitian Case

• The Hermitian intrinsic Bernstein theorem bounds the maximum eigenvalue of a sum of independent, centered, bounded random Hermitian matrices using the intrinsic dimension and norm of a variance upper bound.The proof applies the matrix Laplace-transform method, bounds the expected trace through the variance proxy, and optimizes θ to obtain the tail inequality.Source: §7.7.1 · p. 121, §7.7.2 · pp. 121–122

7.7. PROOF OF THE INTRINSIC BERNSTEIN BOUNDS

• The intrinsic Bernstein tail bound is stated for t ≥ √(v + L/3), after restricting attention to the nonvacuous regime and bounding the remaining factor by four.Here d = intdim(V) and v = ∥V∥, where V is a semidefinite upper bound for Var(Y).Source: §7.7 · p. 123

7.7.3 Proof of the Rectangular Case

• The rectangular intrinsic Bernstein result follows by applying the Hermitian theorem to the Hermitian dilation, with the dilation’s variance calculation inducing the general intrinsic-dimension parameters.The argument assumes independent centered matrices with operator norm at most L.Source: §7.7.3 · p. 123

7.7.4 Proof of the Intrinsic Bernstein Expectation Bound

• The accompanying expectation bound for the rectangular sum is derived by integrating the tail probability, splitting at μ ≥ √v, and controlling the resulting Gaussian integral.The final expression combines terms involving v, L, and log(1+d).Source: §7.7.4 · pp. 123–124

7.8 Notes

• The notes distinguish rank-based dimension reductions from metric-dimension methods, identify Theorem 7.7.1 as essentially due to Minsker [Min11], and state that the framework’s intrinsic Chernoff bounds are new.The proof of the intrinsic Bernstein bound distills Minsker’s argument while achieving marginally better constants; rank-based results include Rudelson, Oliveira, and Magen & Zouzias.Source: §7.8 · p. 124

8.1.2 Matrix Relative Entropy

• Matrix relative entropy is nonnegative and convex for positive-definite matrix pairs, providing the central structural properties needed for Lieb’s theorem.The chapter identifies matrix relative entropy as a difference measure rather than a metric and notes its connections to quantum information.Source: §8.1.2 · p. 126

8.1.4 A Proof of Lieb’s Theorem

• Lieb’s theorem follows by expressing the trace exponential variationally and applying partial maximization to a jointly concave function derived from convex matrix relative entropy.The proof uses the variational trace formula, matrix relative entropy convexity, and the fact that partial maximization preserves concavity.Source: §8.1.2 · p. 126, §8.1.3 · p. 126, §8.1.4 · p. 127

8.2 Analysis of the Relative Entropy for Vectors

• The vector relative entropy is a diagonal-matrix special case, is nonnegative and convex, and supplies the simpler commutative model for the matrix analysis.Nonnegativity follows from scalar convexity, while convexity follows by representing relative entropy as the perspective of a convex function.Source: §8.2.1 · pp. 127–128, §8.2.2 · p. 128, §8.2.4 · p. 130

8.2.3 The Perspective Transformation

• The perspective transformation converts a convex scalar function into a convex bivariate function, yielding the vector relative-entropy convexity result.The construction is defined by ψ_f(a;h) = a · f(h/a) and preserves convexity for positive arguments.Source: §8.2.3 · p. 128, §8.2 · p. 129, §8.2.4 · p. 129

8.3.1 Trace Functions

• The chapter establishes the supporting framework through trace functions and eigenvalue decompositions, while noting that multivariate matrix-function analysis is harder because eigenvectors interact.The presented conventions assume compatible matrix dimensions and use τ ∈ [0,1] with ¯τ = 1−τ for convex combinations.Source: §8.1.1 · p. 126, §8.3.1 · p. 130, §8.3.3 · p. 131

8.3 Elementary Trace Inequalities

• Trace functions inherit monotonicity from weakly increasing scalar functions: A ≼ H implies tr f(A) ≤ tr f(H), including the trace exponential used in matrix concentration.The argument transfers semidefinite order to eigenvalue order and then sums the scalar inequalities over eigenvalues.Source: §8.3 · p. 131

8.3.5 The Matrix Relative Entropy is Nonnegative

• The matrix relative entropy is nonnegative for all positive-definite A and H, via the generalized Klein inequality and f(a) = a loga −a.The argument lifts scalar tangent-line convexity to matrices.Source: §8.3.5 · p. 132

8.4.1 An Integral Representation of the Logarithm

• The logarithm of a positive-definite matrix admits an integral representation derived by applying the scalar formula to its eigenvalues.The representation expresses the logarithm through matrix inverses, which are easier to analyze.Source: §8.4.1 · p. 133

8.4.2 Operator Monotone Functions

• Operator monotone functions preserve semidefinite order, form a convex cone, and constitute a smaller class than weakly increasing functions.Affine functions with nonnegative slope are operator monotone, whereas t^2 and e^t are not on their stated domains.Source: §8.4.2 · p. 134

8.4.3 The Negative Inverse is Operator Monotone

• For u ≥0, the negative inverse a 7→−(a+u)−1 is operator monotone on the positive real line.Thus A ≼ H implies −(A +uI)−1 ≼−(H +uI)−1 for positive-definite matrices.Source: §8.4.3 · p. 134

8.4.4 The Logarithm is Operator Monotone

• The matrix logarithm is operator monotone on the positive real line: A ≼H implies log A ≼logH.The proof combines the logarithm’s integral representation with monotonicity of the inverse map.Source: §8.4.4 · p. 134

8.4.5 Operator Convex Functions

• Operator convex functions satisfy semidefinite Jensen inequalities, while the inverse is operator convex and the logarithm is operator concave on the positive real line.The inverse result is proved using Schur complements, and the logarithm result uses its integral representation.Source: §8.4.6 · p. 135, §8.4.7 · p. 136

8.5.1 Matrix Convex Combinations

• Matrix convex combinations generalize scalar averaging by using operators K1 and K2 satisfying K∗1 K1 +K∗2 K2 = I, while preserving positivity and spectral intervals.They include scalar convex combinations as a special case.Source: §8.5.1 · p. 137, Then the Hermitian matrix · pp. 137–138

8.5.2 Jensen’s Inequality for Matrix Convex Combinations

• For an operator convex f and a matrix convex combination of A1 and A2, the operator Jensen inequality bounds f of the combination by the corresponding combination of f(A1) and f(A2).The proof realizes the matrix convex combination by conjugating a block-diagonal matrix with a suitable unitary.Source: §8.5.2 · p. 138

8.6. THE MATRIX PERSPECTIVE TRANSFORMATION

• The chapter’s perspective proof uses unitary-conjugation averaging and block-matrix diagonal restriction to derive operator Jensen inequalities from operator convexity.The argument preserves the relevant block under diagonalization and applies f to block-diagonal matrices before reversing the construction.Source: §8.6 · p. 139

8.6.2 The Matrix Perspective is Operator Convex

• The matrix perspective extends scalar perspectives to positive-definite matrices and is operator convex for every operator-convex function.Its definition uses positive-definite square roots and inverse square roots, and it agrees with the scalar-style formula when the arguments commute.Source: §8.6.2 · p. 140, §8.6.1 · p. 140

8.7 The Kronecker Product

• Kronecker products provide bilinearity, mixed-product and inverse rules, commuting factors, positivity preservation, and a logarithm formula for positive-definite inputs.These properties are used to construct commuting matrices from arbitrary positive-definite matrices and to simplify matrix-function calculations.Source: §8.7.2 · p. 142, §8.7.3 · p. 142, §8.7.4 · p. 142

8.7.6 A Linear Map

• The linear map ϕ extracts tr(AH) from A ⊗H and preserves the semidefinite order, enabling the Kronecker-product representation to yield entropy inequalities.It can be represented as ϕ(A ⊗H) = ι∗(A ⊗H)ι with ι := vec(Id).Source: §8.7.6 · p. 143

8.8 The Matrix Relative Entropy is Convex

• The matrix relative entropy is convex, obtained by representing it as the matrix perspective of f(a) = a −1−loga and applying operator convexity plus a semidefinite-order-preserving linear map.The construction evaluates the perspective at the commuting matrices A ⊗I and I⊗H, then extracts the trace of their product through ϕ.Source: §8.8 · pp. 143–144

8.9.2 The Matrix Relative Entropy

• The notes relate matrix relative entropy to classical results: nonnegativity is attributed to Klein, convexity to Lindblad, and the presented proof is adapted from Effros [Eff09].Alternative proofs and related sources include Lieb, Bhatia [Bha97], Connes & Størmer, Petz, and Ando [And79].Source: §8.9.2 · p. 145

8.9.3 The Relative Entropy for Vectors

• Vector Bregman divergences include squared Euclidean distance and vector relative entropy, while f-divergences are convex through perspective transformations and connect to matrix work.The Shannon entropy produces the principal f-divergence example.Source: §8.9.3 · pp. 145–146

8.9.4 Elementary Trace Inequalities

• The trace-function material draws on classical quantum statistical mechanics, especially Petz’s survey [Pet94, Sec. 2] and Carlen’s lecture notes [Car10, Sec. 2.2].Source: §8.9.4 · p. 146

8.9.5 Operator Monotone & Operator Convex Functions

• Löwner characterized operator-monotone functions through divided differences and semidefinite relations, while Kraus and Bendat–Sherman developed parallel convexity and integral-representation theories [Löw34, Kra36, BS55].These representations use a nonnegative measure and relate to the logarithm’s integral representation.Source: §8.9.5 · p. 146

8.9.6 The Operator Jensen Inequality

• The operator Jensen inequality is situated in work by Hansen and Pedersen, with the presented proof drawn from Petz [Pet11, Thm. 8.4] and Carlen [Car10, Thm. 4.20].Source: §8.9.6 · p. 147

8.9.7 The Matrix Perspective & the Kronecker Product

• Ando showed that matrix relative entropy is convex via matrix perspectives and the matrix logarithm, while Effros [Eff09] and subsequent work developed and generalized this perspective-based approach.The later analysis removes some commutativity assumptions from Effros’s argument.Source: §8.9.7 · pp. 147–148

Matrix Concentration: Resources

• The annotated bibliography is weighted toward theoretical matrix-concentration results rather than applications.Source: Matrix Concentration: Resources · p. 149

Exponential Matrix Concentration Inequalities

• Recent exponential matrix-concentration work develops Gaussian, Rademacher, Chernoff, Bernstein, Hoeffding, Azuma, Freedman, and bounded-difference inequalities using Lieb’s theorem, Golden–Thompson, or alternative methods [Oli10a] [GT14] [MJC+14].These results address independent sums, martingales, bounded differences, interior eigenvalues, and random graph applications.Source: Exponential Matrix Concentration… · p. 149

144 MATRIX CONCENTRATION: RESOURCES

• Stein’s exchangeable-pairs method handles dependent random matrices, yields Bernstein-type exponential and Rosenthal-type polynomial bounds, and gives a simple proof of noncommutative Khintchine.Related work also develops matrix exponential Efron–Stein inequalities [PMT14], covariance-estimation moment bounds, statistical bounds for unbounded matrices [Kol11], sampling-without-replacement results [GN], and quantum-information concentration methods [CT14].Source: 144 MATRIX CONCENTRATION: RESOURCES · p. 150

Bounds with Intrinsic Dimension Parameters

• Intrinsic-dimension methods replace ambient dimension with maximum rank or variance-based intrinsic dimension, supporting applications in randomized matrix multiplication, statistics, and machine learning [Min11].These approaches adapt arguments associated with Rudelson, Ahlswede–Winter, and Tropp, with [Min11] motivating the chapter’s later results.Source: Bounds with Intrinsic Dimension… · pp. 150–151

The Method of Ahlswede & Winter

• Ahlswede–Winter’s matrix Laplace-transform method uses Golden–Thompson to control matrix mgfs and underlies Chernoff, Hoeffding, and Bernstein inequalities.Applications include quantum information, random graphs, and matrix-completion algorithms, although these results generally have suboptimal parameters.Source: The Method of Ahlswede & Winter · p. 151

Noncommutative Moment Inequalities

• Noncommutative martingale moment inequalities apply to sums of independent matrices and can match or exceed exponential bounds, but their proofs are typically abstract, difficult, and lacking explicit constants.The literature concerns noncommutative von Neumann algebras more broadly than finite-dimensional matrix algebras, and recent work connects it with matrix concentration.Source: Noncommutative Moment Inequalities · p. 151

• The classic Rademacher-series bound is important but not optimal, whereas later work analyzes optimal growth rates and supplies simpler matrix-moment proofs [MJC+14].[JX05] surveys noncommutative moment results and optimal constant growth; [MJC+14] contains what are described as probably the simplest available proofs of these results.Source: 146 MATRIX CONCENTRATION: RESOURCES · p. 152
• Optimal noncommutative Khintchine inequalities were developed in broader settings with sharp constants, building on earlier variance-dependent bounds and dual formulations.[LP86] introduced the first noncommutative Khintchine inequality for expected traces of even powers of matrix Rademacher series, while established optimal general results.Source: 146 MATRIX CONCENTRATION: RESOURCES · p. 152
• Noncommutative Burkholder–Davis–Gundy inequalities for martingales were established in, with an application to random matrix theory.Source: 146 MATRIX CONCENTRATION: RESOURCES · p. 152
• A fully noncommutative Bennett inequality was developed using the Ahlswede–Winter method, while [JZ12] applied Oliveira’s argument [Oli10a] to fully noncommutative martingales.Source: 146 MATRIX CONCENTRATION: RESOURCES · p. 152
• The literature also includes a polynomial inequality for sums of independent random matrices in [CGT12a].Source: 146 MATRIX CONCENTRATION: RESOURCES · p. 152