Course plan

Week 3

Activity 0: Asynchronous learning

Activity 1: Lecture 1

Reading: block1.pdf: pg 1-3
Contents: Course intro, Low rank approximation applications (image processing, machine learning). Matrix factorizations. QR-factorization.

Activity 2: Asynchronous learning

Reading: block1.pdf: §1.2

Activity 3: Lecture 2

Reading: block1.pdf: §1.2-§1.3
Contents: QR-factorization variants / examples, Index vectors, CPQR, Low-rank approximation via partial QR

Activity 4: Asynchronous learning

Reading: block1.pdf: §1.4-§1.4.3
Activity 4a: SVD intro and properties
Activity 4b: Eckart-Young therem
Optional: An introduction to the singular value decomposition by Steve Brunton Links to an external site.
Optional: The data matrix and SVD by Steve Brunton Links to an external site.
Optional: SVD and the netflix challange by Steve Brunton Links to an external site.

Week 4

Activity 5: Lecture 3

Reading: block1.pdf: §1.3.4,§1.5,§1.6
Contents: SVD by partial QR. Numerical rank. Randomized SVD (part 1).
Optional: An introduction to random SVD by Steve Brunton Links to an external site.

Activity 6: Asynchronous learning

Reading: block1.pdf: §1.6, §1.3.2
Activity 6a: Index vectors
Activity 6b: Randomized SVD by PGM
Optional: Watch more of the talk Randomized SVD in a research talk by PGM Links to an external site. most important: time-point 01:59-19:50.
Optional: Enthusiastic talk by Madeleine Udele about the worst data set ever Links to an external site.

Activity 7: Lecture 4

Reading: block1.pdf: §1.6
Contents: Randomized SVD (part 2), Applications.
Recommended exercises: AL20: 1-13, 1-41, 1-69, AL19: 1-13

Activity 8: Asynchronous learning

Reading: block1.pdf: §1.7.1
Activity 8a: ID introduction

Week 5

Activity 9: Lecture 5

Reading: block1.pdf: §1.7
Contents: Interpolatory decomposition, CUR
Recommended exercises: AL20: 1-45, 1-55, 1-54, AL19: 1-16
Optional: CUR introduction (video + quiz) (Not mandatory)
Optional: A talk by PGM on containing ID (mostly focused on PDE-applications) Links to an external site.

Activity 10: Nothing. (Recommend: Work on homework.)

Activity 11: Lecture 6

Reading: block2.pdf Download block2.pdf §2 - §2.2
Contents: Intro to clustering and K-means. Image processing applications. Plastic collection clustering application. K-means. Similarity graphs.
Deadline for homework 1
Recommended exercises: AL20: 2-2, 2-55, 2-6, AL19: 2-1, 2-18
Optional: Alternative explanation of K-means Links to an external site. (youtube)
Optional: K-means example with indicator vector notation.

Activity 12: Asynchronous learning

Reading: block2.pdf Download block2.pdf §2.4.1
Activity 12c: Algebraic and geometric multiplicity (for spectral clustering)

Week 6

Activity 13: Lecture 7

Reading: block2.pdf Download block2.pdf §2.3
Contents: Intro to graphs and data on graphs. Connectedness. Subgraph connectedness. Unnormalized laplacian. Eigenvectors of the Laplacian and indicator vectors
Optional: Lecture 32 in an AI course at Stanford corresponding to graph theory basics Links to an external site.
Optional: Matlab demo for illustrating Laplacian properties
Recommended exercises: AL20 2-14, 2-21, 2-19, 2-27, 2-28, AL19: 2-2

Activity 14: Asynchronous learning

Reading: block2.pdf Download block2.pdf §2.4.2:Rayleigh-Ritz theorem, for algebraic/geometric multiplicity see this wikipedia page. Links to an external site.
Activity 14a: Rayleigh-Ritz theorem
Activity 14c: Mincut
Recommended exercises: AL22: 2-3

Activity 15: Lecture 8

Reading: block2.pdf Download block2.pdf §2.3
Contents: Unnormalized Laplacian spectral clustering. K-means in spectral clustering. RatioCUT interpretation of spectral clustering
Recommended exercises: AL19: 2-19, 2-8, AL20: 2-7, 2-19, 2-21, 2-42, 2-66, AL22: 2-37

Activity 16: Asynchronous learning

Reading: block2.pdf Download block2.pdf §2.5
Contents: Eigenvalue continuity / differentiability
Activity 16a: Eigenvalue derivatives
Recommended exercises: AL21 2-25

Week 7

Activity 17: Lecture 9

Reading: block2.pdf Download block2.pdf pg §2.4-2.5 + UvL
Contents: RatioCut (k>2). Perturbation viewpoint. Normalized Laplacians. NCut.
Recommended exercises: AL19:2-5, 2-20, 2-17, AL20: 2-27, 2-45, AL22: 2-45

Activity 18: Asynchronous learning

Reading: block2.pdf Download block2.pdf §2.4.2:Rayleigh-Ritz theorem
Activity 18a: Proof of the Rayleigh-Ritz theorem

Activity 19: Lecture 10

Reading: block3.pdf Download block3.pdf: §3.1
Contents: Introduction to applications in signal processing. FFT, Cooley-Tukey,
Recommended exercises: AL20: 3-2, 3-3, 3-7, 3-11, AL21: 3-1, 3-2, 3-8
Deadline for homework 2

Activity 20: Asynchronous learning

Reading: block3.pdf Download block3.pdf: §3.2
Activity 20a: How do Toeplitz matrices arise from convolution?
Optional: A youtube summary of Fast Algorithms for Convolutional Neural Networks by Andrew Lavin and Scott Gray Links to an external site. giving an example how FFT (Winograd version) is used in deep learning, in particular convolutional neural networks.

Week 8

Activity 21: Lecture 11

Reading: block3.pdf Download block3.pdf: §3.4
Contents: Toeplitz-like matrices. Action and inverse action for circulant matrices via diagonalization and FFT
Recommended exercises: AL19: 3-6, AL20: 3-21, 3-15, AL21: 3-19, 3-30

Activity 22: Asynchronous learning