High-Dimensional Probability : An Introduction with Applications in Data Science / Roman Vershynin.

Format:

Book

Author/Creator:

Vershynin, Roman, author.

Series:

Cambridge Series in Statistical and Probabilistic Mathematics.

Cambridge Series in Statistical and Probabilistic Mathematics

Language:

English

Subjects (All):

Probabilities.

Random variables.

Stochastic processes.

Physical Description:

1 online resource (346 pages) : digital, PDF file(s).

Edition:

2nd ed.

Place of Publication:

Cambridge : Cambridge University Press, 2026.

Summary:

'High-Dimensional Probability,' winner of the 2019 PROSE Award in Mathematics, offers an accessible and friendly introduction to key probabilistic methods for mathematical data scientists. Streamlined and updated, this second edition integrates theory, core tools, and modern applications. Concentration inequalities are central, including classical results like Hoeffding's and Chernoff's inequalities, and modern ones like the matrix Bernstein inequality. The book also develops methods based on stochastic processes - Slepian's, Sudakov's, and Dudley's inequalities, generic chaining, and VC-based bounds. Applications include covariance estimation, clustering, networks, semidefinite programming, coding, dimension reduction, matrix completion, and machine learning. New to this edition are 200 additional exercises, alongside extra hints to assist with self-study. Material on analysis, probability, and linear algebra has been reworked and expanded to help bridge the gap from a typical undergraduate background to a second course in probability.

Contents:

Cover

Half-title page

Series page

Title page

Copyright page

Contents

Foreword

Preface

Who Is This Book For?

Why This Book?

What Is This Book about?

Are You Ready?

Exercises and Hints

What's New in the Second Edition?

Acknowledgements

Appetizer Using Probability to Cover a Set

0.1 Notes

0.2 Exercises

1 A Quick Refresher on Analysis and Probability

1.1 Convex Sets and Functions

1.2 Norms and Inner Products

1.3 Random Variables and Random Vectors

1.4 Union Bound

1.5 Conditioning

1.6 Probabilistic Inequalities

1.7 Limit Theorems

1.8 Notes

1.9 Exercises

2 Concentration of Sums of Independent Random Variables

2.1 Why Concentration Inequalities?

2.2 Hoeffding Inequality

2.3 Chernoff Inequality

2.4 Application: Median-of-Means Estimator

2.5 Application: Degrees of Random Graphs

2.6 Subgaussian Distributions

2.6.1 The Subgaussian Norm

2.7 Subgaussian Hoeffding and Khintchine Inequalities

2.7.1 Subgaussian Hoeffding Inequality

2.7.2 Subgaussian Khintchine Inequality

2.7.3 Maximum of Subgaussians

2.7.4 Centering

2.8 Subexponential Distributions

2.8.1 Subexponential Properties

2.8.2 The Subexponential Norm

2.9 Bernstein Inequality

2.10 Notes

2.11 Exercises

3 Random Vectors in High Dimensions

3.1 Concentration of the Norm

3.2 Covariance Matrices and Principal Component Analysis

3.2.1 What Can We Learn from the Covariance Matrix?

3.2.2 Principal Component Analysis

3.2.3 Isotropic Distributions

3.3 Examples of High-Dimensional Distributions

3.3.1 Standard Normal

3.3.2 General Normal

3.3.3 Uniform on the Sphere

3.3.4 Uniform on a Convex Set

3.3.5 Frames

3.4 Subgaussian Distributions in Higher Dimensions

3.4.1 Gaussian, Rademacher, and More

3.4.2 Uniform on the Sphere.

3.4.3 Non-Examples

3.5 Application: Grothendieck Inequality and Semidefinite Programming

3.5.1 Semidefinite Programming

Semidefinite Relaxations

The Guarantee of Relaxation

3.6 Application: Maximum Cut for Graphs

3.6.1 A Simple 0.5-Approximation Algorithm

3.6.2 Semidefinite Relaxation

3.7 Kernel Trick, and Tightening of Grothendieck Inequality

3.7.1 Tensors

3.7.2 Proof of Theorem 3.5.1

3.7.3 Kernels and Feature Maps

3.8 Notes

3.9 Exercises

4 Random Matrices

4.1 A Quick Refresher on Linear Algebra

4.1.1 Singular Value Decomposition

4.1.2 Min-Max Theorem

4.1.3 Frobenius and Operator Norms

4.1.4 The Matrix Norms and the Spectrum

4.1.5 Low-Rank Approximation

4.1.6 Perturbation Theory

4.1.7 Isometries

4.2 Nets, Covering, and Packing

4.2.1 Covering Numbers and Volume

4.3 Application: Error-Correcting Codes

4.3.1 Metric Entropy and Complexity

4.3.2 Error-Correcting Codes

4.4 Upper Bounds on Subgaussian Random Matrices

4.4.1 Computing the Norm on an ε-Net

4.4.2 The Norms of Subgaussian Random Matrices

4.4.3 Symmetric Matrices

4.5 Application: Community Detection in Networks

4.5.1 Stochastic Block Model

4.5.2 The Expected Adjacency Matrix Holds the Key

4.5.3 The Actual Adjacency Matrix Is a Good Approximation

4.5.4 Perturbation Theory

4.5.5 Spectral Clustering

4.6 Two-Sided Bounds on Subgaussian Matrices

4.7 Application: Covariance Estimation and Clustering

4.7.1 Application: Clustering of Point Sets

4.8 Notes

4.9 Exercises

5 Concentration without Independence

5.1 Concentration of Lipschitz Functions on the Sphere

5.1.1 Lipschitz Functions

5.1.2 Concentration via Isoperimetric Inequalities

5.1.3 Blow-up of Sets on the Sphere

5.1.4 Proof of Theorem 5.1.3

5.2 Concentration on Other Metric Measure Spaces.

5.2.1 Gaussian Concentration

5.2.2 Hamming Cube

5.2.3 Symmetric Group

5.2.4 Riemannian Manifolds with Strictly Positive Curvature

5.2.5 Special Orthogonal Group

5.2.6 Grassmannian

5.2.7 Continuous Cube and Euclidean Ball

5.2.8 Densities e[sup(-U(x))]

5.2.9 Random Vectors with Independent Bounded Coordinates

5.3 Application: Johnson-Lindenstrauss Lemma

5.4 Matrix Bernstein Inequality

5.4.1 Matrix Calculus

5.4.2 Trace Inequalities

5.4.3 Proof of Matrix Bernstein Inequality

5.4.4 Matrix Hoeffding and Khintchine Inequalities

5.5 Application: Community Detection in Sparse Networks

5.6 Application: Covariance Estimation for General Distributions

5.7 Notes

5.8 Exercises

6 Quadratic Forms, Symmetrization, and Contraction

6.1 Decoupling

6.2 Hanson-Wright Inequality

6.3 Symmetrization

6.4 Random Matrices with Non-Identically Distributed Entries

6.5 Application: Matrix Completion

6.6 Contraction Principle

6.7 Notes

6.8 Exercises

7 Random Processes

7.1 Basic Concepts and Examples

7.1.1 Covariance and Increments

7.1.2 Gaussian Processes

7.2 Slepian, Sudakov-Fernique, and Gordon Inequalities

7.2.1 Gaussian Interpolation

7.2.2 Proof of the Slepian Inequality

7.2.3 Sudakov-Fernique and Gordon Inequalities

7.3 Application: Sharp Bounds for Gaussian Matrices

7.4 Sudakov Inequality

7.4.1 Application for Covering Numbers in R[sup(n)]

7.5 Gaussian Width

7.5.1 Geometric Meaning of Width

7.5.2 Examples

7.5.3 Gaussian Complexity and Effective Dimension

7.6 Application: Random Projections of Sets

7.7 Notes

7.8 Exercises

8 Chaining

8.1 Dudley Inequality

8.1.1 Variations and Examples

8.2 Application: Empirical Processes

8.2.1 The Monte Carlo Method

8.2.2 Lipschitz Law of Large Numbers

8.2.3 Empirical Measure.

8.3 VC Dimension

8.3.1 Definition and Examples

8.3.2 Pajor Lemma

8.3.3 Sauer-Shelah Lemma

8.3.4 Growth Function

8.3.5 Covering Numbers via VC Dimension

8.3.6 VC Law of Large Numbers

8.4 Application: Statistical Learning Theory

8.4.1 Risk, Fit, and Complexity

8.4.2 Empirical Risk Minimization

8.4.3 VC Generalization Bound

8.5 Generic Chaining

8.5.1 A Makeover of the Dudley Inequality

8.5.2 The γ[sub(2)] Functional and Generic Chaining

8.5.3 Majorizing Measure and Comparison Theorems

8.6 Chevet Inequality

8.7 Notes

8.8 Exercises

9 Deviations of Random Matrices on Sets

9.1 Matrix Deviation Inequality

9.2 Random Matrices, Covariance Estimation, and the Johnson-Lindenstrauss Lemma

9.2.1 Singular Values of Random Matrices

9.2.2 Random Projections of Sets

9.2.3 Covariance Estimation for Low-Dimensional Distributions

9.2.4 Johnson-Lindenstrauss Lemma for Infinite Sets

9.3 Random Sections: The M* Bound and Escape Theorem

9.3.1 The M* Bound

9.3.2 The Escape Theorem

9.4 Application: High-Dimensional Linear Models

9.4.1 Constrained Recovery

9.4.2 Example: Sparse Recovery

9.4.3 Example: Low-Rank Recovery

9.5 Application: Exact Sparse Recovery

9.5.1 Exact Recovery Based on the Escape Theorem

9.5.2 Restricted Isometries

9.6 Deviations of Random Matrices for General Norms

9.7 Two-Sided Chevet Inequality and Dvoretzky-Milman Theorem

9.7.1 Two-Sided Chevet Inequality

9.7.2 Dvoretzky-Milman Theorem

9.8 Notes

9.9 Exercises

Hints for the Exercises

References

Index.

Notes:

Title from publisher's bibliographic system (viewed on 05 Feb 2026).

Description based on publisher supplied metadata and other sources.

ISBN:

1-009-49066-4

1-009-49067-2

OCLC:

1574119956