Past offerings:

Winter 2016

Instructor: Da Kuang

Course description:
This course introduces numerical linear algebra from a data analysis perspective. Emphasis will be given to matrix computation arising from unsupervised clustering, dimension reduction, and optimization. In the first half of the course, students will work on mini-projects that relate numerical linear algebra to data analysis tasks; in the second half, students will read and implement a recent research paper on large-scale machine learning involving matrix computations. Overall, this course offers a solid understanding of the theory and practical implementation of matrix algorithms, which is important for effectively using existing machine learning tools and packages as well as creating new ones.

Prerequisites:

• MATH 115A (or equivalent) required.
• PIC 10B (or equivalent) or PIC 20A (or equivalent) or PIC 97 (Python) required.
• MATH 151A/B (or equivalent such as EE 133A) recommended.
• You will be expected to learn Python yourself by reading tutorials and working on projects.
• For the students who do not satisfy the programming prerequisites but still want to register, please complete this tutorial and send me an email with your answers to all the programming exercises in it, in order to gain an exception for registration.

Syllabus

• Foundations
• Singular value decomposition (SVD)
• Conditioning of a matrix
• Algorithms for least-squares fitting
• Matrix factorizations
• Overview of iterative solvers and eigensolvers
• Applications in data analysis
• Sparse coding
• Locally linear embedding
• Principal component analysis
• Nonnegative matrix factorization
• Spectral clustering
• Implementation issues
• Numerical software stack
• Sparse matrices and special structures
• Parallel matrix algorithms

References

• Trefethen and Bau, Numerical linear algebra, 1997. [amazon] [SIAM]
• Chapters 1-7 available on [google books].


• Additional references:
• Leskovec, Rajaraman, and Ullman, Mining massive datasets (online book)
• Trevor Hastie, Robert Tibshirani, and Jerome Friedman, Elements of Statistical Learning (online book)
• Google Python class
• Python tutorial
• numpy tutorial

Slides

Slides are available on your CCLE website.

Grading

• 40% Homework
• 40% Final project and presentation
• 20% Final exam

Disclaimer

• No late homework allowed. However, there are no penalties for medical reasons or emergencies. You must submit a doctor's note or an official letter explaining the emergency.
• Attendance is not counted towards your final grade. However, if you missed a class without a valid reason, the instructor will not answer your questions that have been addressed in-class.

Homework (tentative)

Each homework assignment includes 1~2 theoretical questions and a mini-project.
Please note that while discussion is allowed and encouraged, individual students must write up their own answers and computer programs.
All the students must observe the conduct code.

• [10%] HW1: K-means
• [10%] HW2: Principal component analysis
• [10%] HW3: Spectral clustering
• [10%] HW4: Collaborative filtering

Final Project

Project Instructions

In the final project, you will:

• Form groups of 2-3 persons
• Read a research paper and implement the algorithm in Python
• Reproduce the experiment results
• Apply the algorithm to a real data set

Each group should communicate with the instructor about the scope of experiments and the deliverables. You will very likely need a little literature search in order to understand the algorithms.

Example paper list: (for papers considered for implementation for the current quarter, please refer to the "Paper walk-through" slides on CCLE)

• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, 2009.
• Matrix completion and low-rank SVD via fast alternating least squares, 2014.
• Spectral regularization algorithms for learning large incomplete matrices, 2010.
• Collaborative filtering for implicit feedback, 2008.
• Maximum-margin matrix factorization, 2005.
• Robust principal component analysis?, 2011.
• Multiclass data segmentation using diffuse interface methods on graphs, 2013.
• Efficient sparse coding algorithms, 2007
• Locality-constrained linear coding for image classification, 2010.

Schedule

Date	Mon	Wed	Fri
Jan 9 Jan 11 Jan 13	Introduction	Topics in Python	Numerical software stack K-means HW1 out
Jan 16 Jan 18 Jan 20	(MLK holiday)	Matrix-vector multiplication	Vector and matrix norms Singular value decomposition
Jan 23 Jan 25 Jan 27	Singular value decomposition (cont'd)	Low-rank approximation HW1 due; HW2 out	Principal component analysis
Jan 30 Feb 1 Feb 3	Spectral clustering	Spectral clustering HW2 due; HW3 out Team formation due	Sparse matrices
Feb 6 Feb 8 Feb 10	Project overview	Collaborative filtering HW3 due; HW4 out	Sparse coding
Feb 13 Feb 15 Feb 17	Image classification pipeline	Conditioning of a matrix HW4 due	(buffer)
Feb 20 Feb 22 Feb 24	(President's Day holiday)	Projectors Least squares algorithms Project proposal due	Techniques for introducing zeros for dense LU, QR, SVD/EVD
Feb 27 Mar 1 Mar 3	Locally linear embedding	Locally linear embedding	Nonnegative matrix factorization
Mar 6 Mar 8 Mar 10	Iterative solvers and eigensolvers	Iterative solvers and eigensolvers	Review session
Mar 13 Mar 15 Mar 17	Final presentations	Final presentations	Final presentations

---

Final exam: Mar 21 (Tuesday), 8:00-11:00am

Final report due: Mar 24 (Friday) 11:59pm