For the current offering of this course, please go to: http://math.ucla.edu/~dakuang/math191_2017/

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. Students will read and implement recent research papers on large-scale machine learning involving matrix computations as final projects. 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:
Linear algebra (33A or equivalent) required. Introductory programming (PIC 10A or equivalent) required.
Linear algebra (115AB or equivalent) recommended. Familiarity with Matlab or Python (numpy) programming recommended. You will need to learn Python yourself by reading tutorials and working on projects.

Relationship with other courses:
In terms of numerical algorithms, this course is in some sense complementary to topics in 151A and 151B.
In terms of applications of numerical linear algebra, this course is devoted to data analysis, as opposed to solving PDEs in the graduate course MATH 270.

*New* Selected Final Project Report

• Kexin Yu, Yunqing Jin: Predict attribute labels for restaurants using user-submitted photos
• Neil Liu, Ruochen Jiang, Wenqiao Xie: Evaluation of Locality-constrained Linear Coding for Image Classification
• Zigeng Liu, Ruichao Min, Xiaochen Zhang: Convolutional Neural Network for Multi-label Image Classification
• Lauren Dunlap, Kevin Stangl, Aaron Zhou Qian: Evaluation of Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares

Syllabus

• Foundations
• Understanding matrix-vector and matrix-matrix multiplication
• Singular value decomposition (SVD)
• Conditioning of a matrix
• Algorithms for least-squares fitting
• Matrix factorizations
• 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

Textbooks and references

• Trefethen and Bau, Numerical linear algebra, 1997.
- Free access option: [google book] (no longer available)
- Purchase option: [amazon] [SIAM] (for the SIAM store link, you can register for free student membership and get 30% discount)


• Additional references (posted here as the course proceeds):
• 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
• 20% In-class midterm
• 40% Final project and presentation

Late Submissions Policy

• 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.

Homework

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
• [10%] HW2
• [10%] HW3
• [10%] HW4

Projects

Project Instructions

In the final project, you will:

• Form groups of 2-3 persons
• Read and implement the algorithm described in one of the following papers
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.
If the implementation is available online, you should write it in a different programming language. Bonus points for significant improvement of the original algorithm/implementation.

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.
• Collaborative filtering for implicit feedback, 2008.
• Robust principal component analysis?, 2011.
• A non-local algorithm for image denoising, 2005.
• Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment, 2004.
• Multiclass data segmentation using diffuse interface methods on graphs, 2013.
• Spectral regularization algorithms for learning large incomplete matrices, 2010.
• Maximum-margin matrix factorization, 2005.
• Efficient sparse coding algorithms, 2007
• Locality-constrained linear coding for image classification, 2010.

Schedule

Date	Mon	Wed	Fri
Jan 4 Jan 6 Jan 8	Introduction Python learning: Set up	Matrix-vector multiplication Reading: NLA, Lecture 1 Python learning: Introduction	Matrix-matrix multiplication Range, subspace, norms Reading: NLA, Lecture 1, 3 Python learning: Strings
Jan 11 Jan 13 Jan 15	Numerical software stack Python exercises: string1.py	K-means clustering HW1 out Optional reading: MMDS, Chap 7 Python learning: Lists	Singular value decomposition Reading: NLA, Lecture 2, 4 Python learning: Sorting
Jan 18 Jan 20 Jan 22	(MLK holiday)	Singular value decomposition HW1 due; HW2 out Reading: NLA, Lecture 4, 5 Python exercises: list1.py	Singular value decomposition Principal component analysis Reading: NLA, Lecture 5 Python learning: Dicts and files
Jan 25 Jan 27 Jan 29	Principal component analysis Code Data Optional reading: ESL Chap 14.5.1 Python exercises: wordcount.py	Conditioning Reading: NLA, Lecture 12 HW2 due; HW3 out Python exercises: string2.py	Projectors Reading: NLA, Lecture 6 Team formation due Python exercises: list2.py
Feb 1 Feb 3 Feb 5	Projectors Least squares problem Reading: NLA, Lecture 11 Python exercises: mimic.py	Techniques for introducing zeros for computing LU, QR, SVD/EVD Reading: NLA, Lecture 10 HW4 out Python learning: Regular expressions	Project overview (object recognition, movie recommendation, Yelp challenge) HW3 due Python exercises: Baby names
Feb 8 Feb 10 Feb 12	Project overview (paper walk-through) Python learning: Utilities	Sparse coding HW4 due Python exercises: Copy files	Sparse coding Python exercises: Log puzzle
Feb 15 Feb 17 Feb 19	(Presidents' Day holiday)	Midterm	Locally linear embedding
Feb 22 Feb 24 Feb 26	Locally linear embedding Project proposal due	Sparse matrices	Spectral clustering
Feb 29 Mar 2 Mar 4	Spectral clustering	Nonnegative matrix factorization	Random projection Randomized SVD
Mar 7 Mar 9 Mar 11	Final presentation	Final presentation	Final presentation
Mar 14 Mar 16 Mar 18			Final project report due (No final exam)

---