EECS 551 F25 Class Topics - Jeff Fessler This list will be updated regularly (online) over the course of the semester. Class# topic @01 8/26 *** Course policies (0: c00pol.pdf) *** Intro to book (1: c01int.pdf) *** Intro to Matrices (2: c02mat.pdf) motivation notation 2.3 matrix shapes and classes (circulant, Toeplitz, ...) block matrices transpose, (Hermitian) symmetry 2.4 vector multiplication: inner/dot product, outer product @02 8/28 matrix-vector multiplication matrix multiplication: four forms, properties, array memory matrix versions of 2D plotting in Julia (Read) invertibility left and right inverse properties (Read) DT discussion task: nearest angle classifier @03 9/02 2.5 orthogonal/orthonormal vectors Cauchy-Schwarz inequality orthogonal/unitary matrices unitary invariance of 2 norm 2.6 determinant / properties 2.7 eigenvalues via characteristic equation / properties 2.8 trace X demo: applying convolution to image denoising (moved to HW1) @04 9/04 *** Matrix decompositions (3: c03eig.pdf) 3.2 eigendecomposition spectral theorem for Hermitian matrices geometric interpretation / eigshow1 demo 3.3 SVD geometric interpretation / eigshow2 demo HW1 due @05 9/09 3.4 matrix 2-norm as |Ax| maximization Application: maximize MIMO SNR (read) 3.5 relating SVD and eigendecomposition condition for equivalence of SVD and eigendecomposition basic properties and non-uniqueness @06 9/11 3.6 positive (semi)definite matrices *** Subspaces and rank (4: c04sub.pdf) brief overview 4.2 subspaces definition span HW2 due @07 9/16 linear independence basis dimension subspace sum subspace intersection direct sum orthogonal complement linear transformations (Read) range 4.3 rank row rank = col rank rank bounds @08 9/18 unitary invariance of rank vs eigenvalues and singular values 4.4 nullspace / nullity 4.5 four fundamental subspaces SVD "anatomy" 4.6 orthogonal bases 4.7 spot eig/SVD by hand for simple cases 4.8 Application: nearest-subspace classification projection onto a set HW3 due @09 9/23 projection onto a subspace practical implementation 4.9 Optimization preview convex sets convex functions properties nearest point in a subspace *** Linear equations and LS (5: c05ls.pdf) 5.2 Linear equations 5.3 Linear least-squares (LLS) estimation @10 09/25 gradients normal equations backslash solution for full-rank case compact SVD solution uniqueness 5.4 Moore-Penrose pseudo-inverse product properties relation to SVD DT discussion task: subspace-based classifier HW4 due @11 09/30 LLS solution in full-rank case via pinv 5.5 LLS for under-determined case orthogonality principle minimum-norm LS via pseudo-inverse 5.6 Truncated SVD solution condition number low-rank interpretation noise effects (Read) Tikhonov regularization / ridge regression 5.7 Summary of LLS solutions using SVD @12 10/02 5.8 Frames / tight frames / Parseval tight frames (skip in f23) 5.9 Projection / idempotent matrix orthogonal projection matrix Projection onto convex sets (POCS) Projection onto a subspace SVD-based implementation HW5 due DT discussion task: LS classifier todo: p296 boyd, Tikhonov? extra features? @13 10/07 Orthogonality principle for subspaces Projection onto a subspace's orthogonal complement Projectors and the four fundamental subspaces for a matrix Binary classifier using LS (read / in discussion) 5.10 recursive LS (skip) *** Norms (6: c06norm.pdf) 6.2 Vector norms properties @14 10/09 unitary invariance 6.3 Inner products properties, Cauchy-Schwarz, angle 6.4 Matrix norms defining properties, sub-multiplicative examples: Frobenius, l_p,q (Read) induced matrix norms operator norms defined by singular values Julia implementation with opnorm Properties of matrix norms norm equivalence singular value inequalities [read] HW6 due (with sample exam problem) @xx 10/14 fall study break @15 10/16 unitary invariance spectral radius practical step size for GD 6.5 Convergence of sequences of vectors & matrices (using norms) [Read] 6.6 Generalized inverse of a matrix / Frobenius norm [Read] 6.7 Procrustes analysis (SVD application using Frobenius norm) SVD solution generalizations [Read] Subspace / span comparisons [Read] No HW due (due to fall break and midterm) @xx 10/20 Mon. Midterm on Ch1-6, HW1-6 (tentative coverage) @16 10/21 *** Low-rank approximation (7: c07lr.pdf) 7.2 Problem statement / solution / proof sketch Implementation: choosing rank via scree plot MRI coil compression application (read) Uniqueness 1D example cf LLS Generalization to other unitarily invariant norms Proof for spectral norm (Read) Bases for MxN matrices (Read) Summary / generalizations Stability of rank (Read) 7.3 Sensor localization application (multidimensional scaling) derivation @17 10/23 practical implementation examples (demo) extensions (Read) 7.4 Proximal operators: l1 example l0 example No HW due (due to fall break and midterm) @18 10/28 7.5 Alternative low-rank formulations: UI norm regularized cost functions rank regularizer: singular value hard thresholding (SVHT) nuclear norm: singular value soft thresholding (SVST) Frobenius norm squared as a rank regularizer 7.6 Choosing the rank or regularization parameter NRMSE vs NRMSD behavior SURE @19 10/30 OptShrink optshrink demo 7.7 Relate LR to autoencoders (Read) relate to PCA (Read) 7.8 Subspace learning via low-rank approximation / SVD Subspace clustering (Read) 7.9 Subspace tracking (read) *** Special matrices (8: c08spec.pdf) 8.2 Companion matrices minimal polynomial HW7 due @20 11/04 eigenvectors Vandermonde matrices Kronecker sum to find common polynomial roots (Read/HW) 8.3 Circulant matrices (cf DFT) G_N: companion matrix for z^N - 1 diagonalization of circulant matrices 8.4 Toeplitz matrices (Read) 8.5 power iteration (Read) Geršgorin disk theorem @21 11/06 spectral radius bounds 8.6 nonnegative / positive / primitive matrix power test (read) weighted directed graphs reachability adjacency matrix Strongly connected graphs Irreducible matrix matrix period / aperiodic matrix HW8 due discussion: task5 - 10 digits via subspaces @22 11/11 8.7 Perron-Frobenius theorems for nonnegative matrices primitive matrices irreducible matrices stochastic matrices @23 11/13 [f23 via f21 recording, due to hospitalization] 8.8 Markov chains (Optional reading in F23) transition matrix equilibrium distribution limiting distribution Markov chain simulation example notebook Google PageRank application 8.9 Graph Laplacian / spectral clustering (optional reading) 8.10 Summary Venn diagram [in discussion] clicker questions HW9 due @24 11/18 *** Optimization (9: c09opt.pdf) 9.4 GD for convex functions Lipschitz continuity convexity and Hessian convergence theorem for GD Gradient projection (GP) method @25 11/20 9.5 Machine learning for binary classification: logistic regression Hessian of training loss Lipschitz constant of training loss gradient (Read) example (Read) 9.2 PGD iteration for LS Tool: Matrix square root HW10 due DT discussion task6: logistic regression classifier @26 11/25 Convergence rate analysis of PGD: first steps Tool: Matrix powers Classical GD: step size bounds Optimal step size for GD Practical step size for GD Ideal preconditioner for PGD Tool: Positive (semi)definiteness properties General preconditioners for PGD Matrix majorizers Diagonal majorizer diag(|A'A|1) preconditioning demo (skip in f20, f23) Convergence rates @xx 11/27 thanksgiving day no HW due to break @27 12/02 Tool: commuting matrices (skip in f20, f23) Monotonicity of PGD (skip in f20, f23) 9.3 Preconditioned steepest descent (PSD) Read / [HW only] *** Matrix completion (10: c10mc.pdf) Low-rank matrix completion (LRMC) motivation 10.2 measurement model / sampling set / mask sampling conditions 10.3 noiseless case alternating projection method / Jupyter demo @28 12/04 10.4 noisy case [not covered in f20, brief in f25] rank-constrained formulation rank-regularized formulation convex regularized formulation with nuclear norm Majorize-minimize (MM) iterations MM methods (brief in f20, not in f23, brief in f25) iterative low-rank approximation (alt proj) ISTA iterative SVST (alternate fill / SVST) iterative SVHT FISTA for LRMC / SVST - jupyter demo ADMM for LRMC / SVST - jupyter demo ISTA derivation, extend GD to composite cost (skip) Course review / practice questions HW11 due @xx 12/16 (Tue.) final 10:30AM-12:30PM is official RO time --- below here from F23, except dates are updated