Glossary

Theorems and definitions from the lecture and supplementary notes

Every definition, theorem, proposition, and lemma from the published notes, in the order they appear. Click a result to jump to it.

Result Type Where
Observation and feature vector Definition Lecture 1
Data matrix Definition Lecture 1
Point cloud Definition Lecture 1
Euclidean balls and cubes Definition Lecture 1
Volumes of Euclidean balls and cubes Proposition Lecture 1
Volume near the boundary Proposition Lecture 1
Random variable Definition Lecture 1
Distribution and event Definition Lecture 1
Expectation Definition Lecture 1
Linearity of expectation Proposition Lecture 1
Independent and identically distributed Definition Lecture 2
Expectations of products Proposition Lecture 2
Variance and standard deviation Definition Lecture 2
Covariance Definition Lecture 2
Averaging away independent noise Proposition Lecture 2
Law of the Lazy Data Scientist Theorem Lecture 2
Convex hull Definition Lecture 2
Carathéodory’s theorem Theorem Lecture 2
Approximate Carathéodory theorem Theorem Lecture 2
Eigenvalue and eigenvector Definition Lecture 3
Spectral theorem Theorem Lecture 3
Positive semidefinite matrix Definition Lecture 3
PSD matrices have non-negative eigenvalues Proposition Lecture 3
\(\bfA^\top\bfA\) and \(\bfA\bfA^\top\) are PSD Proposition Lecture 3
Singular values Definition Lecture 3
Building the left singular vectors Lemma Lecture 3
Expansion in an orthonormal basis Lemma Lecture 4
Singular value decomposition Theorem Lecture 4
Singular vectors Definition Lecture 4
Full singular value decomposition Theorem Lecture 4
The SVD and eigendecomposition Proposition Lecture 4
Truncated singular value decomposition Definition Lecture 4
Frobenius norm Definition Lecture 4
Spectral norm Definition Lecture 4
Eckart–Young theorem Theorem Lecture 4
Eckart–Young theorem, Frobenius norm Theorem Lecture 4
\(\bfA\) in singular-vector coordinates Lemma Lecture 5
The spectral norm is the largest singular value Proposition Lecture 5
Trace Definition Lecture 5
Properties of the trace Proposition Lecture 5
The Frobenius norm and all the singular values Proposition Lecture 5
Centered data matrix Definition Lecture 5
Orthogonal projection Definition Lecture 5
Pythagorean theorem Theorem Lecture 5
Properties of orthogonal projection Proposition Lecture 5
Reconstruction error Definition Lecture 6
Reconstruction error is a Frobenius norm Proposition Lecture 6
Best-fitting subspaces come from the SVD Theorem Lecture 6
Principal component analysis Definition Lecture 6
Total variance Definition Lecture 6
Minimum error equals maximum retained variance Proposition Lecture 6
Explained variance ratio Definition Lecture 6
Linear model Definition Lecture 7
Least squares Definition Lecture 7
Least squares is orthogonal projection Theorem Lecture 7
Normal equations Theorem Lecture 7
\(\bfX^\top\bfX\) and \(\bfX\) have the same null space Proposition Lecture 7
The set of least squares solutions Theorem Lecture 7
Column space and null space from the SVD Lemma Lecture 7
The hat matrix Proposition Lecture 7
Minimum-norm least squares Theorem Lecture 7
Moore–Penrose pseudoinverse Definition Lecture 7
Properties of the pseudoinverse Proposition Lecture 7
Mean and covariance of a random vector Definition Lecture 8
Means and covariances under linear maps Proposition Lecture 8
Standard assumptions for the linear model Definition Lecture 8
Mean and covariance of the least squares estimator Theorem Lecture 8
Where the least squares error lives Corollary Lecture 8
Expected squared distance from the mean Lemma Lecture 9
Linear unbiased estimator Definition Lecture 9
Gauss-Markov theorem Theorem Lecture 9
Bias and mean squared error Definition Lecture 9
Bias-variance decomposition Theorem Lecture 9
Bias-variance decomposition for prediction Corollary Lecture 9
Ridge regression Definition Lecture 10
The SVD of \(\bfX^\top\bfX+\lambda\bfI_d\) Lemma Lecture 10
The ridge solution Theorem Lecture 10
Ridge regression filters the singular values Theorem Lecture 10
Bias and variance of ridge regression Proposition Lecture 10
Ridge beats least squares for small \(\lambda\) Theorem Lecture 10
Link matrix Definition Lecture 11
Column-stochastic matrix Definition Lecture 11
Column-stochastic matrices do not increase the \(\ell_1\) norm Lemma Lecture 11
The spectrum of a column-stochastic matrix Proposition Lecture 11
The power method, symmetric case Proposition Lecture 11
Google matrix Definition Lecture 11
PageRank is well defined, and the power method finds it Theorem Lecture 11
The k-means problem Definition Lecture 12
Sum of squares around a point Lemma Lecture 12
Optimal centers and optimal assignments Proposition Lecture 12
Total = within + between Theorem Lecture 12
Lloyd’s algorithm Algorithm Lecture 12
Lloyd’s algorithm terminates Theorem Lecture 12
k-means++ seeding Algorithm Lecture 12
A PCA lower bound for k-means Theorem Lecture 12
More clusters never hurt the cost Proposition Lecture 12
k-means clusters are convex Proposition Lecture 12
Hyperparameter Definition Notes: Choosing Hyperparameters
Training error always prefers \(\lambda=0\) Proposition Notes: Choosing Hyperparameters
\(K\)-fold cross-validation Algorithm Notes: Choosing Hyperparameters
Prediction error Proposition Notes: Choosing Hyperparameters
Vector in \(\Rbb^n\) Definition Notes: The Algebra of Data
Matrix and matrix–vector product Definition Notes: The Algebra of Data
Matrices define linear maps Theorem Notes: The Algebra of Data
Transpose and symmetry Definition Notes: The Algebra of Data
Matrix multiplication Definition Notes: The Algebra of Data
Subspace Definition Notes: The Algebra of Data
Span Definition Notes: The Algebra of Data
Linear independence Definition Notes: The Algebra of Data
Basis and dimension Definition Notes: The Algebra of Data
Uniqueness of coordinates Theorem Notes: The Algebra of Data
Invertibility Definition Notes: The Algebra of Data
Column space and null space Definition Notes: The Algebra of Data
Rank–nullity Theorem Notes: The Algebra of Data
The four fundamental subspaces Definition Notes: The Algebra of Data
Inner product Definition Notes: The Algebra of Data
Dot product Definition Notes: The Algebra of Data
Induced norm Definition Notes: The Algebra of Data
\(\ell^p\) norms Definition Notes: The Algebra of Data
Cauchy–Schwarz inequality Theorem Notes: The Algebra of Data
Angle and cosine similarity Definition Notes: The Algebra of Data
Orthogonality Definition Notes: The Algebra of Data
Orthogonal sets are linearly independent Proposition Notes: The Algebra of Data
Orthogonal projection Definition Notes: The Algebra of Data
Properties of projection matrices Theorem Notes: The Algebra of Data
Orthogonality of the fundamental subspaces Theorem Notes: The Algebra of Data
Eigenvalue and eigenvector Definition Notes: The Algebra of Data
Characteristic polynomial Proposition Notes: The Algebra of Data
Algebraic and geometric multiplicity Definition Notes: The Algebra of Data
Eigenvectors for distinct eigenvalues are linearly independent Proposition Notes: The Algebra of Data
Diagonalizability Definition Notes: The Algebra of Data
Diagonalizability criterion Theorem Notes: The Algebra of Data
Symmetric matrices have real eigenvalues Proposition Notes: The Algebra of Data
Eigenvectors for distinct eigenvalues are orthogonal Proposition Notes: The Algebra of Data
Spectral theorem for symmetric matrices Theorem Notes: The Algebra of Data
Eigenvalue characterization of PSD and PD Theorem Notes: The Algebra of Data