University of Texas at Austin, Spring 2024

CSE 392: Matrix and Tensor Algorithms for Data

Instructor

Shashanka Ubaru
  • Email: shashanka.ubaru(at)austin.utexas.edu or (at)ibm.com
  • Office hours: Mondays 1:30pm - 2:30pm.
  • Location: POB 3.134.

    • Class time and Location:
  • Mondays and Wednesdays, 11:00am - 12:30pm, GDC 2.402.

    • Course description

    With the advent of modern technology, internet, and social networks, machine learning and data scientists today have to deal with large volumes of data of massive sizes. In this course, we study the mathematical foundations of large-scale data processing, designing algorithms and learning to (theoretically) analyze them. We explore randomized numerical linear algebra (sketching and sampling) and tensor methods for processing and analyzing large-scale databases, graphs, data streams, and large multidimensional data. We will also have presentations on linear algebra concepts of quantum computing.

    Prerequisites: The minimum requirements for the course are basics concepts of probability, algorithms, and linear algebra. Knowledge and experience with machine learning algorithms will be helpful. For the course, we will rely most heavily on probability, linear and tensor algebra, but we will also learn some approximation theory, high dimensional geometry, and quantum computing. The course will involve rigorous theoretical analysis and some programming (practical implementation and applications).

    Programming language: The programming languages for the course will be Matlab and/or Python.

    Syllabus: PDF

    Grading

    Grading is based on problem sets, scribing a lecture, and a presentation/project. There will be no exams. The breakdown is as follows: Assignments are to be submitted through Canvas, and should be individual work. You are allowed to discuss the problems with your classmates and to work collaboratively. The preferred format is to upload your work as a single PDF, preferably typewritten (using LaTeX, Markdown, or some other mathematical formatting program). In general, late assignments will not receive credit.

    Lectures

    Dates
    		 Topics covered
    		 Slides
    		 Scribed notes
    Week 1 (Jan 17, 2024) Lecture 1: Vector spaces, matrices, norms.
    		Lecture 1
    Week 2 (Jan 22, 2024)
    		Lecture 2: Probability review, concentration of measure.
    Lecture 3: Least squares regression, kernel methods.     		Lecture 2
    Lecture 3
    		Scribe Notes 2
    Scribe Notes 3
    Week 3 (Jan 29, 2024)
    		Lecture 4: Matrix factorizations I - SVD, QR.
    Lecture 5: Matrix factorizations II - eigenvalue decomposition, PCA.     		Lecture 4
    Lecture 5
    		Scribe Notes 4
    Scribe Notes 5
    Week 4 (Feb 5, 2024)
    		Lecture 6: Approximate matrix product, sampling.
    Lecture 7: Johnson–Lindenstrauss(JL) lemma, subspace embedding.     		Lecture 6
    Lecture 7
    		Scribe Notes 6
    Week 5 (Feb 12, 2024)
    		Lecture 8: Sketching, types of sketching matrices.
    Lecture 9: Sketch and solve - least squares regression.     		Lecture 8
    Lecture 9
    		Scribe Notes 8
    Scribe Notes 9
    Week 6 (Feb 19, 2024)
    		Lecture 10: Sampling for least squares, preconditioned LS.
    Lecture 11: Randomized SVD.     		Lecture 10
    Lecture 11
    		Scribe Notes 10
    Scribe Notes 11
    Week 7 (Feb 26, 2024)
    		Lecture 12: Subspace iteration (power) method.
    Lecture 13: Krylov subspace method.     		Lecture 12
    Lecture 13
    		Scribe Notes 12
    Scribe Notes 13
    Week 8 (Mar 4, 2024)
    		Lecture 14: Stochastic trace estimation.
    Lecture 15: Introduction to tensors, tensor-matrix product.     		Lecture 14, Spectral sums
    Lecture 15     		Scribe Notes 14
    Scribe Notes 15
    Week 9 (Mar 11, 2024) Spring Break
    Week 10 (Mar 18, 2024)
    		Lecture 16: Canonical Polyadic (CP) decomposition.
    Lecture 17: Randomized CP - I.     		Lecture 16
    Lecture 17
    		Scribe Notes 16
    Scribe Notes 17
    Week 11 (Mar 25, 2024)
    		Lecture 18: Randomized CP - II.
    Lecture 19: Tucker decomposition, HOSVD.     		Lecture 18
    Lecture 19
    		Scribe Notes 18
    Scribe Notes 19
    Week 12 (Apr 1, 2024)
    		Lecture 20: Randomized Tucker, TensorSketch.
    Lecture 21: Tube-fiber product, t-product.     		Lecture 20
    Lecture 21
    		Scribe Notes 20
    Scribe Notes 21
    Week 13 (Apr 8, 2024)
    		Lecture 22: t-SVD, M-product.
    Lecture 23: Randomized t-SVD, t-product applications.     		Lecture 22
    Lecture 23
    		Scribe Notes 22
    Scribe Notes 23
    Week 14 (Apr 15, 2024)
    		Lecture 24: Tensor networks.
    Lecture 25: Introduction to quantum computing I.     		Lecture 24
    Lecture 25
    		Scribe Notes 24
    Scribe Notes 25
    Week 15 (Apr 22, 2024)
    		Lecture 26: Introduction to quantum computing II.
    Lecture 27: Project Presentation I.     		Lecture 26
    Week 16 (Apr 29, 2024)
    		Lecture 28: Project Presentation II.

    Problem Sets

    Homework 1
    Homework 2
    Homework 3
    Homework 4

    Resources