CPBS 7620 - Lecture 11 - Matrix Decompositions

Overview

Nicholas Dwork explains how matrix structure turns solving AX = B into more efficient operations, from orthogonal transformations and triangular back substitution to LU and QR factorizations. He also introduces positive-definite matrices, Cholesky decomposition, and SVD, including how thresholding singular values produces a pseudoinverse for rank-deficient systems.

Key takeaways

Orthogonal matrices make linear solves efficient because Q inverse = Q transpose, and they preserve both vector lengths and angles.
Triangular systems avoid general matrix inversion: lower triangular systems use forward-order substitution, while upper triangular systems are solved from the last variable backward.
Pivoted LU separates a square system into a row permutation and two triangular solves, reusing the same factorization for multiple right-hand sides.
QR handles tall full-rank systems through an orthonormal basis and an upper triangular solve; the corresponding LQ form for short, wide systems yields a least-norm solution.
Cholesky factorization represents a symmetric positive-definite matrix as LL transpose and reduces a linear solve to two triangular substitutions.
SVD supports pseudoinverse computation for rank-deficient matrices by inverting only singular values larger than a chosen threshold epsilon.

Chapters

0:00 Matrix Products, Orthogonality, and Triangular Solves

For A of size M by K and B of size K by N, AB has size M by N and can be computed by applying A to each column of B.
Block matrix multiplication treats rectangular sections as matrices; for example, the first product block is AU + BW.
Orthogonal Q satisfies Q inverse = Q transpose, preserves vector norms and perpendicularity, and makes QX = B solvable as X = Q transpose B.
Lower triangular systems can be solved by back substitution, and a triangular matrix is invertible when every diagonal entry is nonzero.

5:55 LU and QR Factorizations for Solving AX = B

LU decomposition writes a square matrix as A = PLU, with permutation P, invertible lower triangular L, and upper triangular U.
Solving with PLU applies P transpose to B, then uses two triangular solves; U is invertible exactly when A is invertible.
A tall, full-rank matrix has QR factorization A = QR, where Q has orthonormal columns and R is upper triangular.
For a short, wide, full-row-rank matrix, transposing a QR factorization gives A = LQ tilde; X = Q tilde transpose L inverse B is a least-norm solution.

10:03 Cholesky and SVD: Positive Definiteness and Pseudoinverses

Positive semidefinite A satisfies x transpose A x >= 0, making the quadratic function x transpose A x convex; sums of positive semidefinite matrices remain positive semidefinite.
A symmetric positive-definite matrix has Cholesky factorization A = LL transpose, so solving Ax = B requires two triangular back substitutions.
Every matrix has an SVD A = U sigma V transpose, with orthogonal U and V and nonnegative diagonal singular values ordered from largest to smallest.
For rank-deficient A, the SVD pseudoinverse uses reciprocal singular values above a threshold epsilon and sets smaller-value reciprocals to zero.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Nicholas Dwork.