Instructor:
Gunnar Martinsson. ECOT 233.
Office Hours: Monday 4:00pm  4:50pm and Wednesday 3:00pm  4:50pm (ECOT 233).
Homeworks: Please submit a hard copy in class on the due date. Group homeworks are permitted and encouraged. The maximum group size is three for 4720, and two for 5720.
Reference homeworks: Each student (not each group) should pick one problem (not "sets") during the course of the semester and submit a solution that is clean enough to be posted on this webpage. Please attach matlabcode when appropriate. To avoid that one problem is picked by more than one student, there is a signup sheet that can be viewed here. Each student who is registered for the course will be emailed a link that allows editing of the signup sheet.
Projects: An important part of the course is the final project, accounting for 40% of your final grade. Several suggested projects will be posted on this webpage. If you find some part of the class particularly relevant to your academic interests, you have the option to propose an individual or a group project on that subject. If you want to create your own project, please consult with the instructor no later than March 15.
Various documents: Syllabus.
Notes:
Week: 
Homework: 
Material covered: 
1 (Jan 11) 

Lowrank approximation  the problem formulation and a brief survey of applications.
The Singular Value Decomposition (SVD) and the EckartYoung theorem on optimality. Slides for the first lecture. Notes for the first week. Latex template for course notes. Summary of the "top 10 algorithms" article. 
2 (Jan 18) 

No class Monday (MLK day). Power iterations, and Krylov methods. GramSchmidt and the QR factorization. How to cheaply get an approximate SVD from a QR factorization. Notes for the second week. 
3 (Jan 25) 

Randomized methods for computing lowrank approximations  the basic idea. Notes: Monday. Wednesday. Friday. 
4 (Feb 1) 
Homework 1 due on Monday. The files hw01p2.m and hw01p3.m. Solutions: Problem 1, Problem 2 with code, Problem 3. 
Randomized methods for computing lowrank approximations  adaptive rank determination. Notes: Wednesday. Friday. Notes from Dr. Voronin. 
5 (Feb 8)


Randomized methods for computing lowrank approximations  single pass algorithms, error analysis, and the SRFT. Notes: Monday. Wednesday and Friday. 
6 (Feb 15) 
Homework 2 due on Friday. The files hw02p1.m and hw02p2.m. Solutions: Problem 1, Problems 2 and 3. 
Connection between randomized methods and Krylov techniques. Notes: Monday. Wednesday. Friday. The latest version of the course notes. 
7 (Feb 22) 

Interpretation of data  the interpolative decomposition (ID) and the CUR decomposition. Notes: Monday. Wednesday. Friday. The latest version of the course notes. 
8 (Feb 29) 

Applications of lowrank approximation: Principal Component Analysis (PCA), Latent
Semantic Indexing (LSI), eigenfaces, pagerank, potential evaluation. Notes: Monday, Wednesday. The latest version of the course notes. 
9 (Mar 7) 
Homework 3 due on Monday. The file hw03p02.m. 
Applications of lowrank approximation: Principal Component Analysis (PCA), Latent
Semantic Indexing (LSI), eigenfaces, pagerank, potential evaluation. Notes: Monday, Friday. 
10 (Mar 14) 

Techniques for nonlinear problems; diffusion geometry. Notify instructor via email of your choice of project by March 19! Notes: Monday. Wednesday. Paper on diffusion geometry (local copy). 
Spring Break 


11 (Mar 28) 

Diffusion geometry, continued.
JohnsonLindenstrauss methods; random projections as a tool for dimensionality reduction.
Nearest neighbor search. Slides on kd trees (local copy). Tutorial lecture by Peter Indyk. JohnsonLindenstrauss notes (local copy). Notes: Monday and Wednesday, Friday.. 
12 (Apr 4) 
Homework 4 due on Friday. The file testmatrices.mat. As a solution key, here is the file used to generate the test matrices. Reference solutions: Problem 1, Problem 2, Problem 3. 
JohnsonLindenstrauss theory. Random projections. Randomized nearest neighbor search. Comparison of slowly converging randomized
methods (Monte Carlo, JL projections) and accurate randomized methods (RSVD, QuickSort). Papers by Jones, Osipov, Rokhlin: 1 and 2. Notes: Monday. Wedesday. 
13 (Apr 11) 

The Fast Multipole Method. Notes: Wedesday. Slides for the Wednesday lecture. Slides for the Friday lecture. 
14 (Apr 18) 

The potential evaluation map and kernel independent FMMs. Clustering and kmean. (Code for the Matlab demo here.) Rankstructured matrices and fast matrix inversion. Slides: Monday, Friday. 
15 (Apr 25) 
Homework 5 due on Friday. The tutorial FMM. The file HW05.m. Reference solutions: Problem 1, Problem 3. 
Project presentations. Slides for the Monday lecture. 
Finals week 

No final exam, but your written final project report is due on Tuesday May 3, by 4pm. 