Numerical Linear Algebra - Spring Semester 2020
Update: Due to the global state of emergency caused by COVID 19 , the IMM has suspended on-site lessons until further notice and will complete the rest of the semester through online lessons. This includes the Numerical Linear Algebra course, which is taught through a combination of pre-recorded video lectures, Google Classroom assignments and interactive teacher-to-students Q&A/exercise sessions through the Zoom video conferencing tool. These Zoom interactive sessions are also recorded and made available to any students who miss a session.
Faculty:
Part 2 (22/06/-03/07/2020) :
Jean Barbier (Trieste, Italy)
Part 1 (04/05-09/06/2020): Krerley Oliveira (Alagoas, Brazil)
Thales Vieira (Alagoas, Brazil)
Krerley Oliveira
Thales Vieira
Jean Barbier
Part 1
The main textbooks will be:
[Str] Strang, G., 2006. Linear algebra and its applications, Thomson Learning. Inc., London. This textbook will be used for the Theoretical Concepts part.
[BF] Burden, R. and Faires, J.D., 2004. Numerical analysis. Cengage Learning. This textbook will be used for the Numerical Methods and Applications part.
The first part of the Numerical Linear Algebra course will run for 4 weeks. The Monday and Wednesday interactive video meetings (approximate duration: 1h 40 min each) will be given by Professor Oliveira and the Tuesday and Thursday meetings will be run by Professor Vieira.
Syllabus:
Theoretical Concepts
Gaussian Elimination: Linear systems, LU decomposition, Inverses. Vector Spaces, Basis and Linear Transformations: Subspace Ax=0, Independence, Graphs, Linear Transformations. Ortogonality: Projections (in a line and least squares), Gram-Schimdt. Eigenvalues and Eigenvectors: Introduction, Diagonalization of Symmetric matrices.
Numerical Methods and Applications
Introduction to Python programming, focused on matrix computations. Gaussian elimination implementation, LU decomposition implementation. Application 1 - Least squares for polynomial fitting, Application 2 - Scattered-Data Interpolation (RBF) (optional). The Power Method. QR decomposition. Application 1 - Principal component analysis (PCA), Application 2 - PCA-based feature selection (optional), Application 3 - eigenfaces for face image recognition with PCA (optional).
Course Materials:
Theoretical Concepts
This part of the course closely follows the [Str] textbook and the related MIT Linear Algebra course webpage, relying on the lecture videos, lecture summaries and problem sets associated to the following units:
Numerical Methods and Applications
This part of the course focuses briefly on introducing some programming concepts in Python; presenting numerical methods for solving linear systems of equations and finding eigenvalues and eigenvectors; and introducing some basic Machine Learning applications that can be solved with Computational Linear Algebra. It is strongly based on algorithms implented through Python Notebooks using the Google Colab environment. A comprehensive reference book for the Python computational language can be found here.
Computational Language Notebooks:
Worksheets:
Worksheet 1 - Jupyter Notebook
Worksheet 2 - Gaussian Elimination and LU Decomposition
Slides corresponding to [BF]:
Exams:
Intermediate exam - theoretical concepts
Timetable:
Week 1:
Monday, May 4th:
morning: students watch the assigned video lectures and solve the related exercises (from Google Drive)
16:00 PM (Pakistan time): interactive lesson with professor Krerley on Zoom (topic: Gaussian Elimination)
Tuesday, May 5th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Thales on Zoom (topic: Python programming)
Wednesday, May 6th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Krerley on Zoom (topic: Gaussian Elimination)
Thursday, May 7th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Thales on Zoom (topic: Python programming)
Friday, May 8th:
students solve the assigned exercises
Week 2:
Monday, May 11th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Krerley on Zoom (topic: Vector Spaces, Basis and Linear Transformations)
Tuesday, May 12th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Thales on Zoom (topic: Gaussian elimination implementation, LU decomposition implementation)
Wednesday, May 13th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Krerley on Zoom (topic: Vector Spaces, Basis and Linear Transformations)
Thursday, May 14th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Thales on Zoom (topic: Application 1 - Least squares for polynomial fitting)
Friday, May 15th:
students solve the assigned exercises
Week3:
Monday, May 18th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Krerley on Zoom (topic: Ortogonality)
Tuesday, May 19th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Thales on Zoom (topic: Application 2 - Scattered-Data Interpolation (RBF), The Power Method)
Wednesday, May 20th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Krerley on Zoom (topic: Ortogonality)
Thursday, May 21st:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Thales on Zoom (topic: QR decomposition)
Friday, May 22nd:
students solve the assigned exercises
Week 4:
Monday, May 25th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Krerley on Zoom (topic: Eigenvalues and Eigenvectors)
Tuesday, May 26th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Thales on Zoom (topic: Application 1 - Principal component analysis (PCA))
Wednesday, May 27th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Krerley on Zoom (topic: Eigenvalues and Eigenvectors)
Thursday, May 28th:
morning: students watch the assigned video lectures and solve the related exercises
16:00 PM: interactive lesson with professor Thales on Zoom (topic: Application 2 - PCA-based feature selection, Application 3 - eigenfaces for face image recognition with PCA)
Friday, May 29th:
Midterm exam
Part 2 (Machine Learning)
Detailed Syllabus:
I. Introduction
What is Machine Learning?
II. Why is Machine Learning difficult?
Setting up a problem in ML and data science
Polynomial Regression
III. Basics of Statistical Learning Theory
Three simple schematics that summarize the basic intuitions from Statistical Learning Theory
Bias-Variance Decomposition
V. Overview of Bayesian inference
Bayes rule
Bayesian Decisions
Hyperparameters
VI. Linear Regression
Least-square regression
Ridge-regression
LASSO and sparse regression
Using linear regression to learn the Ising Hamiltonian
Convexity of regularizer
Bayesian formulation of linear regression
VII. Logistic Regression for MNIST classification
The cross-entropy as a cost function for logistic regression
Softmax Regression
Course Materials: The course will be based on chapters 1-3 and 5-6 and chapter 9 of the paper by P. Mehta, M. Bukov, C. H. Wang, A. G. R. Day, C. Richardson, C. K. Fisher, D. J. Schwab A high-bias, low-variance introduction to Machine Learning for physicists, Phys. Rep. 810 (2019), 1-124.
The suggested reading materials can be found on the EPFL Machine Learning course page.
Computational Language Notebooks:
2. Notebook 2 (Diabetes Data, Chapter VI)
3. Notebook 3 (Linear Regression for the Ising Model, Chapter VI) Alternative data sets for this notebook can be found here.
Course notes:
1. Notes from lessons 1 and 2 (Chapters I and II)
2. Notes from lesson 3 (Chapter III)
3. Notes from lesson 5 (Chapters V and VI)
Timetable:
Week 1:
Monday, June 22nd:
morning: students read the assigned chapters and prepare the assigned notebook
16:00 PM (Pakistan time): interactive lesson on Zoom
Tuesday, June 23rd:
morning: students read the assigned chapters and prepare the assigned notebook
16:00 PM: interactive lesson on Zoom
Thursday, June 24th:
morning: students read the assigned chapters and prepare the assigned notebook
16:00 PM: interactive lesson on Zoom
Friday, June 25th:
morning: students read the assigned chapters and prepare the assigned notebook
13:30 PM: interactive lesson on Zoom
Week 2:
Monday, June 29th:
morning: students read the assigned chapters and prepare the assigned notebook
13:00 PM (Pakistan time): interactive lesson on Zoom
Tuesday, June 30th:
morning: students read the assigned chapters and prepare the assigned notebook
13:00 PM: interactive lesson on Zoom
Thursday, July 2nd:
morning: students read the assigned chapters and prepare the assigned notebook
13:00 PM: interactive lesson on Zoom
Friday, July 3rd:
morning: students read the assigned chapters and prepare the assigned notebook
13:00 PM: interactive lesson on Zoom
Course Gallery
MTH607 - Numerical Linear Algebra
Course ContentsFundamentals: matrix multiplication, orthogonal vectors, orthogonal matrices, norms; Gaussian Elimination and its variants: Cholesky decomposition, LU decomposition, pivoting strategies; Sensitivity of linear systems: conditioning and stability; The least squares problem and SVD; Eigen values & Eigen vectars Ill-posedness & Regularization.
Books
Matrix Computations by G.H Golub and c.P Van Loan.
Fundamentals of Matrix Computations by D.S Watkins.
Numerical Linear Algebra by Lloyd N. Trefethen and David Bau
Numerical Linear Algebra and Applications by B.N Datta.