| Week | Topic | Due |
|---|---|---|
| September 3(No Class) | Review Intermediate Linear Algebra: finite dimensional vector spaces, inner product spaces, matrices and linear maps, Graham-Schmidt, Jordan Canonical Form, diagonalization and the Spectral Theorem, etc. | Nothing. |
| September 10 | Introduction. Fundamentals and Duality; Least Squares. Zorn's Lemma. | Read: Ch. 1, 2 |
| September 17 | Linear Mappings. Spectral Theory. Singular Value Decomposition and PCA. Schur's Theorem. | Read: Ch. 3, 6 Problem Set 1 (tex) |
| September 24 | Euclidean Structure and Hilbert Space. Spectral Theory of Self-Adjoint Mappings and Definiteness. Covariance and Quadratic forms. | Read: Ch. 7, 8 Problem Set 2 (tex) |
| October 1 | Normed Linear Spaces. Metrics for Data. Banach spaces. Maps between normed spaces. Matrix calculus and applications. | Read: Ch. 14, 15 Problem Set 3 (tex) |
| October 8 | Complex Hahn-Banach Theorem. Perron-Frobenius Theorem. Google's PageRank algorithm. | Read: Ch. 16 Problem Set 4 (tex) |
| October 15 | Concentration. Johnson-Lindenstrauss Lemma and applications to big-data algorithm design. Randomized trace and Schatten-p norm estimators. (notes) | Read: Woodruff Sec. 6.1 Watch: This Lecture |
| October 22 (no class) | Enjoy break! | |
| October 29 (no class) | Work on midterm project. | |
| November 5 | Convexity. Hahn-Banach Separation Theorem. Caratheodory Theorem. Helly's Theorem. Birkhoff Theorem and applications to optimizing over permuation group. | Read: Ch. 12 Small Problem Set 5 (tex) Midterm Project (info) |
| November 12 | Convex optimization. Analysis of iterative optimization algorithms via linear algebra techniques. Chebyshev iteration for solving large linear systems. | Read: Ch. 17 Problem Set 6 (tex) |
| November 19 | Matrix Sketching. Least Squares Problems and Johnson-Lindenstrauss Based Solutions. | Read: Woodruff Intro Problem Set 7 (tex) Literature Review (info) |
| November 26 | Farkas-Minkowski Theorem and Duality. Compressed Sensing by Linear Programming and a proof of correctness. | Read: Ch. 13 Watch: This Lecture |
| December 3 | Lagrange Duality and examples. Slater's Condition. NP-Hard Set Partitioning Problem, Semidefinite Program Lower Bound via the Dual, analytical bound on Duality Gap. (notes) | Read: These Slides Work on final project. |
| December 10 | Come to class for consulting on final project by teaching staff! | Work on final project. |
| December 17 | Presentations. | Final Report (in class) Presentation (in class) |