Cheat sheets

Linear Algebra for ML

Vectors, transforms, eigenvalues, SVD and Ax = b solvers. From-scratch Python and NumPy from the lessons.

  • Concepts and terms
  • Tasks and commands
  • Annotated code
  • Diagrams
  • Defaults and numbers
  • Troubleshooting
  • Questions and tips

Source

SVD: rotate, scale, rotate#

VUInput spacen-dimV^TrotateSigmascale by sigma_iUrotateA^T Aeigenvectors are VA A^Teigenvectors are UOutput spacem-dimVUInput spacen-dimV^TrotateSigmascale by sigma_iUrotateA^T Aeigenvectors are VA A^Teigenvectors are UOutput spacem-dim

From Lesson 01.11

Gaussian elimination with partial pivoting#

1Pivotin column k, find the largest entry at or belowrow k.2Swapswap that row with row k. A small pivotamplifies rounding errors.3Checka pivot below 1e-12 raises ValueError.4Eliminatefor each row i below k, compute m = A[i][k] /A[k][k]. Subtract m times row k.5Back substitutesolve the last equation first, then go upward.6ReuseL stores the multipliers. U is the eliminatedmatrix. PA = LU.

From Lesson 01.17, 01.17 code/linear_systems.py

Tasks in NumPy#

TaskCode
Dot product and lengthnp.dot(a, b), np.linalg.norm(a)
Matrix multiplyA @ B
Element-wise multiplyA * B
Ranknp.linalg.matrix_rank(A)
Eigenvalues and eigenvectorsnp.linalg.eig(A)
Thin SVDnp.linalg.svd(A, full_matrices=False)
Least squaresnp.linalg.lstsq(A, b, rcond=None)[0]
QR, check Qnp.allclose(Q @ Q.T, np.eye(3))

From Lesson 01.01, Lesson 01.02, Lesson 01.03, Lesson 01.11, Lesson 01.17

Truncate, compress and invert with SVD#

U, S, Vt = np.linalg.svd(A, full_matrices=False)S sorted in decreasing order
A_k = U[:, :k] @ np.diag(S[:k]) @ Vt[:k, :]best rank-k approximation
compressed_size = k * (rows + cols + 1)storage for rank k
A_pinv = Vt.T @ np.diag(1.0 / S) @ U.Tpseudoinverse, nonzero S only
x_svd = A_pinv @ bleast-squares solution
x_pinv = np.linalg.pinv(A) @ bsame result from NumPy
U, S, V = svd_from_scratch(A)power iteration and deflation
A_pinv = pseudoinverse_via_svd(A, tol=1e-10)1/s only for s above tol

From Lesson 01.11, 01.11 code/svd.py

Solve Ax = b from scratch#

x = gaussian_elimination(A, b)partial pivoting, O(n^3)
P, L, U = lu_decompose(A)PA = LU, pay O(n^3) one time
x = lu_solve(P, L, U, b)O(n^2) for each new b
L = cholesky(A)A = L L^T, symmetric positive definite only
x = cholesky_solve(L, b)forward, then back substitution
w_ols = least_squares_normal(X, y)solves A^T A x = A^T b
w_ridge = ridge_regression(X, y, lam=1.0)adds lam * np.eye(n)
x, iters = conjugate_gradient(A, b)SPD, at most n iterations
kappa = condition_number(A)S[0] / S[-1], inf if singular

From Lesson 01.17, 01.17 code/linear_systems.py

Transformation matrices#

CommandWhat it does
rotation_2d(theta)[[c, -s], [s, c]]. Keeps distances. det 1
scaling_2d(sx, sy)[[sx, 0], [0, sy]]. det is sx * sy
shearing_2d(kx, ky)[[1, kx], [ky, 1]]. Rectangles become parallelograms
reflection_y()[[-1, 0], [0, 1]]. Flips orientation. det -1
reflection_x()[[1, 0], [0, -1]]. det -1
mat_mul(S, R)Rotate first, then scale. Order matters
eigenvalues_2x2(matrix)Roots of the characteristic equation. Complex if discriminant < 0
eigenvector_2x2(matrix, eigenvalue)Unit eigenvector for one eigenvalue

From Lesson 01.03, 01.03 code/transformations.py

Pick a solver#

CommandWhat it does
Gaussian eliminationSquare, nonsingular A. O(n^3). One solve
LU decompositionMany solves with the same A. O(n^2) for each solve
QR decompositionLeast squares with m >= n. Numerically stable
CholeskySymmetric positive definite A. Twice as fast as LU
Normal equationsOverdetermined, small n. Linear regression
SVD / pseudoinverseRank-deficient A. Minimum-norm solution
Conjugate gradientLarge sparse SPD A. Iterative

From Lesson 01.17

Key formulas#

Shapes
(m x n) @ (n x p) = (m x p). The inner dimensions must match.
Cosine
\cos\theta = \frac{a \cdot b}{\lvert a\rvert \lvert b\rvert}. 1 is the same direction, 0 is orthogonal.
Projection
\text{proj}_b a = \frac{a \cdot b}{b \cdot b} b. The residual is perpendicular to b.
Eigen
Av = \lambda v. Eigenvalues are roots of \det(A - \lambda I) = 0.
2x2 eigenvalues
\lambda^2 - (a+d)\lambda + (ad - bc) = 0.
SVD
A = U \Sigma V^T and A v_i = \sigma_i u_i. Rank is the count of nonzero \sigma_i.
Normal equations
A^T A x = A^T b. Ridge adds \lambda I to A^T A.
Condition number
\kappa = \sigma_{\max} / \sigma_{\min}.

From Lesson 01.01, Lesson 01.02, Lesson 01.03, Lesson 01.11, Lesson 01.17

Numbers and defaults#

SettingDefaultNote
Zero test in rank()1e-10Smaller entries count as zero
Pivot test in elimination1e-12Smaller pivot raises ValueError
power_iteration num_iters200Stops early at tol=1e-10
conjugate_gradient tol1e-10max_iter defaults to n
Safe condition number< 100The solution is accurate
Meaningless for float6410^{16}The matrix is effectively singular
Image at rank k=5014.6%Of the 800 x 600 values
LoRA rank16131K parameters, not 16M

From Lesson 01.01, 01.01 code/vectors.py, Lesson 01.11, 01.11 code/svd.py, Lesson 01.17, 01.17 code/linear_systems.py

Troubleshooting#

SymptomCauseFix
Shape mismatch errorInner dimensions differWrite each shape before you multiply
inverse_2x2 raises ValueErrorDeterminant is 0Use the pseudoinverse
"Matrix is not positive definite"A is not SPDAdd lambda I, or use LU
Weights swing on small input changesCollinear features, rank deficientDrop features or add regularization
Answer loses digitskappa near 10^k loses k digitsRegularize, or use QR or SVD
np.linalg.eig(A.T @ A) is impreciseIt squares the condition numberUse np.linalg.svd(A)
Composition gives the wrong pointB @ A applies A firstMultiply in reverse order of application
Gram-Schmidt dots are not exactly 0Floating pointCompare with a tolerance such as 1e-9

From Lesson 01.01, Lesson 01.02, Lesson 01.03, Lesson 01.11, Lesson 01.17

Questions#

Why factor with LU?
The O(n^3) cost is paid one time. Each new b costs O(n^2).
When does Cholesky work?
A is symmetric positive definite. X^T X + \lambda I is SPD for \lambda > 0.
What does the determinant tell you?
The area scale. 0 crushes a dimension. -1 flips orientation.
Why is truncated SVD the best rank k?
Eckart-Young. The spectral error is \sigma_{k+1}.
What do eigenvalues say about stability?
Magnitude above 1 explodes. Below 1 vanishes.

From Lesson 01.03, Lesson 01.11, Lesson 01.17

Tips#

  • PCA is SVD on centered data. The components are the right singular vectors V.
  • Explained variance for each component is sigma_i^2 / (n-1).
  • Look for a clear gap in the singular values. Keep the values above it to denoise.
  • Ridge improves the condition number to (\sigma_{\max} + \lambda) / (\sigma_{\min} + \lambda).
  • The pseudoinverse gives the solution with the smallest norm when many solutions exist.
  • Orthogonal initialization uses QR to make orthonormal weight columns.

From Lesson 01.01, Lesson 01.11, Lesson 01.17