SI231B: Matrix Computations

Course Descriptions

 

Matrix analysis and computations are widely used in engineering fields  —  such as statistics, optimization, machine learning, computer vision, systems and control, signal and image processing, communications and networks, smart grid, and many more  —  and are considered key fundamental tools.

SI231B Matrix Computations (Matrix Methods for Data Analysis, Machine Learning, and Signal Processing) covers topics at an advanced or research level especially for people working in the general areas of Data Analysis, Machine Learning, and Signal Processing.

This course consists of several parts.

  • The first part focuses on various matrix factorizations, such as eigendecomposition, singular value decomposition, Schur decomposition, QZ decomposition and nonnegative factorization.

  • The second part considers important matrix operations and solutions such as matrix inversion lemmas, linear system of equations, least squares, subspace projections, Kronecker product, Hadamard product and the vectorization operator. Sensitivity and computational aspects are also studied.

  • The third part explores presently frontier or further advanced topics, such as matrix calculus and its various applications, deep learning, tensor decomposition, and compressive sensing (or managing undetermined systems of equations via sparsity). Especially, matrix concepts are key for understanding and creating machine learning algorithms, and hence, a special focus will be given on how matrix computations are applied to neural networks.

In each part, the relevance to engineering fields is emphasized and applications are showcased.

(Acknowledgement to Wing-Kin (Ken) Ma (CUHK) for material for part of this course.)

Announcements

  1. [Course Syllabus]

  2. Time: Tue/Thu 10:15am-11:55am, Venue: Rm. 101, Teaching Center.

  3. Piazza: https://piazza.com/shanghaitech/fall2020/si231b

  4. Gradescope: see the HW's

Prerequisites

  1. Compulsory: Linear Algebra, Mathematical Analysis or Advanced Calculus, Probability and Statistics, Linear Programming, SI151 Optimization and Machine Learning.

  2. Recommended/Postrequisites: Mathematical and Numerical Optimization, Machine Learning.

Textbooks and Optional References

Textbook

  1. Gene H. Golub and Charles F. Van Loan, Matrix Computations (Fourth edition), The John Hopkins University Press, 2013.

References

  1. Roger A. Horn and Charles R. Johnson, Matrix Analysis (Second Edition), Cambridge University Press, 2012.

  2. Jan R. Magnus and Heinz Neudecker, Matrix Differential Calculus with Applications in Statistics and Econometrics (Third Edition), John Wiley and Sons, New York, 2007.

  3. Gilbert Strang, Linear Algebra and Learning from Data, Wellesley-Cambridge Press, 2019.

  4. Carl D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM (Society for Industrial and Applied Mathematics), 2000.

  5. Alan J. Laub, Matrix Analysis for Scientists & Engineers, SIAM (Society for Industrial and Applied Mathematics), 2004.

  6. Xianda Zhang, Matrix Analysis and Applications, Cambridge University Press, 2017.

  7. Xianda Zhang, Matrix Analysis and Applications (Second Edition), Tsinghua University Press, 2013. (a ref. in Chinese)

Schedule

Part I

  1. Lecture 0: Overview (0.5 week)

  2. Lecture 1: Basic Concepts (1 week)

Part II

  1. Lecture 2: Linear Systems (1.5 week)

  2. Lecture 3: Least Squares (1 weeks)

  3. Lecture 4: Orthogonalization and QR Decomposition (1 week)

  4. Lecture 5: Eigenvalues, Eigenvectors, and Eigendecomposition (2.5 weeks)

  5. Lecture 6: Positive Semidefinite Matrices (0.5 week)

  6. Lecture 7: Singular Values, Singular Vectors, and Singular Value Decomposition (1 week)

  7. Lecture 8: Least Squares Revisited (1 week)

  8. Lecture 9: Kronecker Product and Hadamard Product (0.5 week)

  9. Lecture 10: Review (0.5 week)

Part III (optional)

  1. Extra Lecture 1: Multilinear/Tensor Algebra and Tensor Decomposition (guest lecture: [Part 1 slides] [Part 2 slides]) (Last updated: Nov. 28th)

  2. Extra Lecture 2: Neural Networks

  3. Extra Lecture 3: Matrix Calculus

  4. Extra Lecture 4: Reduced-Rank Regression

  5. Extra Lecture 5: Randomized Linear Algebra

  6. Extra Lecture 6: Gaussian Mixture Models

  7. Extra Lecture 7: Regression, Lasso, and Graphical Lasso

Assessment

30% assignments, 40% mid-term exam, 30% final project.

Academic Integrity Policy

Group study and collaboration on problem sets are encouraged, as working together is a great way to understand new materials. Students are free to discuss the homework problems with anyone under the following conditions:

  • Students must write down their own solutions. Plagiarism is never allowed. Similar answers, MATLAB/Python/R codes, etc., found in HWs will invite you into suspected plagiarism investigation.

  • Students must list the names of their collaborators (i.e., anyone with whom the assignment was discussed).

  • Students can not use old solution sets from other classes under any circumstances, unless the instructor grants special permission.

Students are encouraged to read the ShanghaiTech Policy on Academic Integrity.