University of Texas at Austin, Spring 2025

CSE 392/CS 395T/M 397C: Matrix and Tensor Algorithms for Data

Instructor

Shashanka Ubaru
  • Email: shashanka.ubaru(at)austin.utexas.edu
  • Office hours: Wednesdays 12:30pm - 1:30pm.
  • Location: POB: 3.134.

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

    • Course description

    Advances in modern technologies have resulted in huge volumes of data being generated in several scientific, industrial, and social domains. With ever increasing size of data comes the necessity to develop fast and scalable machine learning and data algorithms to process and analyze them. In this course, we study the mathematical foundations of large-scale data processing, with focus on 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 multidimensional data, graphs, and data-streams. We will also have presentations on the 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 few concepts related to approximation theory, high dimensional geometry, and quantum computing. The course will involve rigorous theoretical analyses 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, project/presentation, and class participation. 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
    Week 1 (Jan 13, 2025) Lecture 1: Vector spaces, matrices, and norms.
    Lecture 2: Probability review, concentration of measure.     		Lecture 1
    Lecture 2
    Week 2 (Jan 20, 2025) Martin Luther King, Jr. Day
    Lecture 3: Least squares regression, kernel methods.
    Lecture 3
    Week 3 (Jan 27, 2025) Lecture 4: Matrix factorizations I - SVD, QR.
    Lecture 5: Matrix factorizations II - eigenvalue decomposition, PCA.     		Lecture 4
    Lecture 5
    Week 4 (Feb 3, 2025)
    		Lecture 6: Approximate matrix product, sampling.
    Lecture 7: Johnson–Lindenstrauss(JL) lemma, subspace embedding.     		Lecture 6
    Lecture 7
    Week 5 (Feb 10, 2025)
    		Lecture 8: Sketching, types of sketching matrices.
    Lecture 9: Sketch and solve - least squares regression.     		Lecture 8
    Lecture 9
    Week 6 (Feb 17, 2025)
    		Lecture 10: Sampling for least squares, preconditioned LS.
    Lecture 11: Randomized SVD.     		Lecture 10
    Lecture 11
    Week 7 (Feb 24, 2025)
    		Lecture 12: Subspace iteration (power) method.
    Lecture 13: Krylov subspace method.     		Lecture 12
    Lecture 13
    Week 8 (Mar 3, 2025)
    		Lecture 14: Stochastic trace estimation.
    Lecture 15: Introduction to tensors, tensor-matrix product.     		Lecture 14, Spectral sums
    Lecture 15
    Week 9 (Mar 10, 2025)
    		Lecture 16: Canonical Polyadic (CP) decomposition.
    Lecture 17: Randomized CP - I.     		Lecture 16
    Lecture 17
    Week 10 (Mar 17, 2025) Spring Break
    Week 11 (Mar 24, 2025)
    		Lecture 18: Randomized CP - II.
    Lecture 19: Tucker decomposition, HOSVD.     		Lecture 18
    Lecture 19
    Week 12 (Mar 31, 2025)
    		Lecture 20: Randomized Tucker, TensorSketch.
    Lecture 21: Tube-fiber product, t-product.     		Lecture 20
    Lecture 21
    Week 13 (Apr 7, 2025)
    		Lecture 22: t-SVD, M-product.
    Lecture 23: Randomized t-SVD, t-product applications.     		Lecture 22
    Lecture 23
    Week 14 (Apr 14, 2025)
    		Catch up on previous lectures.
    Lecture 24: Tensor networks.
    Lecture 24
    Week 15 (Apr 21, 2025)
    		Lecture 25: Introduction to quantum computing I.
    Lecture 26: Introduction to quantum computing II.     		Lecture 25
    Lecture 26
    Week 16 (Apr 28, 2025)
    		Project presentations.

    Problem Sets

    Homework 1
    Homework 2
    Homework 3
    Homework 4

    Resources