|
ECE 367: Matrix Algebra and Optimization (Fall 2024)
Course Description
This course provides students with a grounding in optimization methods and the matrix algebra upon which they are based. The first part of the course focuses on fundamental building blocks in linear algebra and their geometric interpretation: matrices, their use to represent data and as linear operators, and the matrix decompositions (such as eigen-, spectral-, and singular-vector decompositions) that reveal structural and geometric insight. The second part of the course focuses on optimization, both unconstrained and constrained, linear and non-linear, as well as convex and nonconvex; conditions for local and global optimality, as well as basic classes of optimization problems are discussed. Applications from machine learning, signal processing, and engineering are used to illustrate the techniques developed.
Personnel
Instructor:
Teaching Assistants:
Kareem Attiah <kareem.attiah@mail.utoronto.ca>
Adnan Hamida <adnan.hamida@mail.utoronto.ca>
Faeze Moradi Kalarde <faeze.moradi@mail.utoronto.ca>
Nick Kwan <nick.kwan@mail.utoronto.ca>
Mustafa Ammous <mustafa.ammous@mail.utoronto.ca>
Lectures: (Starting September 3rd, 2024)
Tutorials: (Starting September 6th, 2024)
Textbooks
Giuseppe Calafiore and Laurent El Ghaoui, Optimization Models, Cambridge University Press, 2014. (Main textbook)
Stephen Boyd and Lieven Vandenberghe, Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares, Cambridge University Press, 2018. (Some homework problems are taken from this textbook. PDF available at authors’ website.)
Course Schedule
The course (roughly) follows the following schedule.
| Week | Topics | Text References | Assessment | Tutorial |
| Sept 3 | Vectors, Norms, Inner Products | Ch. 2.1-2.2 | Homework #1: Due Sept 17, 11:59pm
(Word Vector, Fourier Series) | Homework #1:
Theory |
| Sept 9-10 | Orthogonal Decomposition, Projection onto Subspaces, Gram-
Schmidt, QR decomposition, Hyperplanes and Half-Spaces | Ch. 2.2-2.3 | | Homework #1:
Applications |
| Sept 16-17 | Non-Euclidean Projection, Projection onto Affine Sets,
Functions, Gradients and Hessians | Ch. 2.3-2.4 | Homework #2: Due Oct 1, 11:59pm
(Function Approximation, PageRank) | Homework #2:
Theory |
| Sept 23-24 | Matrices, Range, Null Space, Eigenvalues,
Eigenvectors, Matrix Diagonalization | Ch. 3.1-3.5 | | Homework #2:
Applications |
Sept 30 -
Oct 1 | Symmetric matrices, Orthogonal Matrices, Spectral Decomposition,
Positive Semidefinite Matrices, Ellipsoids | Ch. 4.1-4.4 | Homework #3: Due Oct 15, 11:59pm
(Latent Semantic Indexing, EigenFace) | Homework #3:
Theory |
| Oct 7-8 | Singular Value Decomposition,
Principal Component Analysis | Ch. 5.1, 5.3.2 | | Homework #3:
Applications |
| Oct 15 | Interpretations of SVD, Low-Rank Approximation | Ch. 5.2, 5.3.1 | | Previous
Midterm |
| Oct 21-22 | Midterm Review | | Midterm:
Tuesday, October 22, 2024 | |
| Oct 28-29 | Study Break,
No Classes | | | |
| Nov 4-5 | Least Squares, Overdetermined and
Underdetermined Linear Equations | Ch. 6.1-6.4 | Homework #4: Due Nov 19, 11:59pm
(Optimal Control, CAT Scan) | Homework #4:
Theory |
| Nov 11-12 | Regularized Least-Squares,
Convex Sets and Convex Functions | Ch. 6.7.3,
Ch. 8.1-8.4 | | Homework #4:
Applications |
| Nov 18-19 | Lagrangian Method for Constrained Optimization,
Linear Programming and Quadratic Programming | Ch. 8.5,
Ch. 9.1-9.6 | Homework #5: Due Dec 3, 11:59pm
(Portfolio Design, Sparse Coding of Image) | Homework #5:
Theory |
| Nov 25-26 | Numerical Algorithms for Unconstrained
and Constrained Optimization | Ch. 12.1-12.3 | | Homework #5:
Applications |
| Dec 2-3 | Revision | | | Previous
Final
|
Grading
Homework: 20%
Midterm exam: 35%
Final exam: 45%
Syllabus
A pdf version of the syllabus that includes all the details can be downloaded here.
|