Linear Algebra
Eigenvalues, the SVD, norms and projections.
The core objects of linear algebra (matrices, eigenvalues, the SVD, norms and projections) and what they cost to compute.
Notation
Vector and matrix – A vector is a column of real numbers. A matrix has rows and columns, and is the entry in row , column . The transpose swaps rows and columns, so .
Identity and inverse – The identity has ones on the diagonal and zeros elsewhere, so . A square matrix is invertible if some satisfies .
Symmetric matrix – is symmetric when . Covariance matrices are symmetric.
Rank and subspaces
Linear independence – Vectors are linearly independent if no one of them is a weighted sum of the others.
Column space and null space – The column space of is the set of all vectors , meaning all weighted sums of its columns. The null space (or kernel) is the set of with .
Rank – The rank of is the number of linearly independent columns, which always equals the number of independent rows. For , the rank–nullity theorem says
and . A square matrix is invertible exactly when it has full rank.
Determinant and trace
Trace – The trace is the sum of the diagonal entries, . It is cyclic: .
Determinant – The determinant is the factor by which scales volume. It is zero exactly when is not invertible, and .
Eigenvalues and eigenvectors
Eigenvalue and eigenvector – A nonzero vector is an eigenvector of a square matrix , with eigenvalue , if only stretches it: . The eigenvalues are the roots of the characteristic polynomial
Example: for , gives with and with . Check: trace and determinant .
Link to trace and determinant – and .
Diagonalization – If has independent eigenvectors, stacking them into the columns of gives , where is the diagonal matrix of eigenvalues. Then .
Orthogonal matrix – is orthogonal if its columns are unit length and mutually perpendicular, so and . Orthogonal matrices preserve lengths and have . Rotations and reflections are examples.
Spectral theorem – Every real symmetric matrix has real eigenvalues and orthonormal eigenvectors, so
Rayleigh quotient – For symmetric , the largest value of over unit vectors is the largest eigenvalue , attained at its eigenvector.
Power iteration – Repeatedly computing converges to the top eigenvector, at a rate set by the ratio of the two largest eigenvalues.
Positive semi-definite matrices
Definition – A symmetric matrix is positive semi-definite (PSD), written , if for every . It is positive definite () if the inequality is strict for every . Equivalent tests:
- all eigenvalues are (or for positive definite),
- for some matrix .
Covariance matrices and Gram matrices are always PSD.
Cholesky factorization – A positive definite factors as with lower triangular. It is the fastest way to solve for such matrices.
Singular value decomposition
SVD – Every matrix , square or not, factors as
where and are orthogonal and is diagonal with non-negative singular values . The singular values are the square roots of the eigenvalues of , and the rank of is the number of nonzero ones.
Best low-rank approximation (Eckart–Young) – Keeping only the top singular values and their vectors gives the rank- matrix closest to .
Principal component analysis (PCA) – For a data matrix whose columns have been centred to mean zero, the principal directions are the columns of . The variance along direction is , for data points.
Pseudoinverse – , where inverts the nonzero singular values. is the smallest-norm minimizing .
Condition number – measures how much amplifies relative errors. Solving loses roughly digits of precision.
Norms
Vector norm – The Euclidean norm is . Two vectors are orthogonal when .
Matrix norms
| Norm | Definition | In terms of singular values |
|---|---|---|
| Spectral | largest stretch, | |
| Frobenius | ||
| Nuclear |
The nuclear norm is the standard convex stand-in for rank when fitting low-rank models.
Projections
Projection – A matrix is a projection if , meaning applying it twice changes nothing. An orthogonal projection also has . The orthogonal projection onto the column space of is
which is when the columns of are orthonormal. projects onto the perpendicular complement.
QR decomposition – with having orthonormal columns and upper triangular. It is Gram–Schmidt orthogonalization written as matrices.
Woodbury identity – Updates a known inverse after a rank- change at extra cost:
Computational cost
| Operation | Cost |
|---|---|
| Matrix–vector product, | |
| Matrix product | floating-point operations |
| Inverse, solve, LU, Cholesky, QR, eigen, SVD | |
| Rank- factorization of an matrix | numbers instead of |