Welcome to MAT1850: Linear Algebra and Optimization!

Reference text and notes

The primary reference text is Linear Algebra and Optimization with Applications to Machine Learning, Volumes I and II, by Jean Gallier and Jocelyn Quaintance, also available on the web archive: Vol 1 and Vol 2. Other supplemental references will be added here as they come up, including the matrix calculus cookbook.

Lecture notes after the class will be available online via OneNote; there will also be recordings of lectures online.

Tentative chapters/topics to be covered:

• Vol 1, Chapter 7: Gaussian elimination, LU-factorization, Cholesky factorization (7.2-7.5, 7.9)
• Vol 1, Chapter 8: Vector norms and matrix norms (8.1-8.5)
• Vol 1, Chapter 9: Iterative methods for solving linear systems (probably will only cover briefly, some subset of 9.1-9.4)
• Vol 1, Chapter 11: Euclidean spaces, adjoints, and QR-decomposition (11.1-11.6, 11.8)
• Vol 1, Chapter 12: QR decomposition (12.1-12.2)
• Vol 1, Chapter 13: Hermitian spaces (13.1-13.4)
• Vol 1, Chapter 14: unit quaternions and rotations in SO(3) (15.1-15.4; super high-level without details)
• Vol 1, Chapter 16: spectral theorems (16.1-16.7)
• Vol 1, Chapter 18: Graphs and graph Laplacians (18.1-18.4)
• Vol 1, Chapter 19: Spectral graph drawing (19.1-19.2)
• Vol 1, Chapter 20: SVDs (20.1-20.4)
• Not in textbook: probabilistic matrix sketches (see Chapter 6 of Blum, Hopcroft, and Kannan instead)
• Vol 2, Chapter 4: extrema of real-valued functions (4.1-4.3)
• Vol 2, Chapter 5: Newton's method (5.1-5.2)
• Vol 2, Chapter 6: Quadratic optimization (6.1-6.3)
• Vol 2, Chapter 7: Schur complements (7.1-7.3)
• Vol 2, Chapter 8: Convex sets, cones, and H-polyhedra
• Vol 2, Chapter 9: linear programs
• Vol 2, Chapter 10: simplex algorithm
• Vol 2, Chapter 11: linear programming and duality
• Vol 2,  Chapter 12: Hilbert space review
• Vol 2, Chapter 13: General results of optimization theory
• Vol 2, Chapter 14: Introduction to nonlinear optimization
• Vol 2, Chapter 15: Subgradients and subdifferentials of convex functions
• Vol 2, Chapter 16: Dual ascent methods; ADMM

Note that this is a lot of material. We will be going fairly quickly, but may not end up getting to everything (strikethrough for topics that unfortunately we did not have time for this semester).

Pre-lecture notes and video recording. (video recordings require University of Toronto accounts)

• 1 intro.pdf; video
• 2 Cholesky and matrix norms.pdf;  video
• 3 condition numbers.pdf; video
  (a couple typos are present, including a transpose for a conjugate transpose, and specifying \sigma_2 instead of \sigma_1 in Prop 8.12/8.17)
• 4 iterative methods.pdf; video
• 5 dual space.pdf; video (be warned that there are several typos in pre-lecture notes that were corrected during class)
• 6 QR decomposition.pdf; video (note that I made a mistake about self-adjoint operators, which I corrected later during the break)
• 7 Hermitian spaces and quaternions.pdf; video
• 8 quaternions and spectral theorems.pdf; video
• 9 Matrix spectra.pdf; video
• 10 Eigenvalue inequalities graph laplacians.pdf; video
• 11 Laplacians and graph drawings.pdf;  video
• 12 graph drawing SVDs.pdf; video
• 13 matrix sketching.pdf; video
• 14 local extrema.pdf; video
• 15 local extrema part 2.pdf; video
• 16 Newton’s method.pdf; video
• 17 Quadratic optimization.pdf; video
• 18 quadratic opt 2 Hilbert spaces.pdf; video
• 19 Farkas Minkowski quadratic functionals.pdf; video
• 20 elliptic functionals iterative methods.pdf; video
• 21 conjugate graidents penalties feasible directions.pdf; video
• 22 kkt duality.pdf; video

Homework

All homework should be submitted on Quercus by the due date, ideally as a PDF, though any standard format that I can easily read is fine. Problem numbering is from the primary Gallier and Quaintance textbook, both volumes (Vol.Chap.Problem).

• Problem set 1: 1.7.1, 1.7.4, 1.7.7, 1.7.8, 1.7.10, 1.7.15, 1.8.2, 1.8.4, 1.8.5
• Problem set 2: 1.8.6, 1.8.7, 1.8.8, 1.8.9, 1.8.10, 1.8.11, 1.8.12, 1.9.4
• Problem set 3: 1.10.5, 1.11.1, 1.11.4, 1.11.7, 1.11.16, 1.12.2, 1.12.4, 1.13.1, 1.13.3, 1.13.7
• Problem set 4: 1.15.7, 1.16.4, 1.16.5, 1.16.6, 1.16.7, 1.16.9, 1.16.11
• Problem set 5: 1.18.4, 1.18.5, 1.20.6, 1.20.8, 1.20.9
• "Problem set 6": Project proposal. More details on Quercus.
• Problem set 7: 2.3.2, 2.3.4, 2.3.6, 2.4.3, 2.4.4, 2.4.7, 2.4.8, 2.4.9
• Problem set 8: 2.5.1, 2.5.2, 2.5.4, 2.6.1, 2.6.3, 2.6.4, 2.6.5, 1.12.1
• Problem set 9: Slight modification of 2.13.3
• "Problem set 10": Peer review of project presentations.

Examinations

Final examination: Friday, Dec 18, 12-2pm.
There will be an online final examination. The exam will be administered online, and it will be open-book, but it will be restricted to a 2-hour period. There will be a short 1-on-1 oral exit interview after the class.