RANDOMIZED LINEAR ALGEBRA AND APPLICATIONS
Random solvers have been playing increasingly crucial roles in the modern computational tasks. The recent breakthroughs in applied and computational linear algebra that incorporate techniques of randomization have proven to be of great importance in modern applied math, computational sciences and data science, such as inverse problems, machine learning and scientific computing. The guiding principle is that one may greatly reduce computational and storage expenses at the cost of a small probability of failure. Systematic study of these modern methods of randomized linear algebra solvers will be provided, presenting mathematical backgrounds, algorithms, and concrete applications. Core theoretical topics include randomized Kaczmarz and its generalization to stochastic gradient descent, randomized singular value decomposition, random sketching, matrix completion, and compressive sensing, and corresponding applications.
Topics
- randomized Kaczmarz and its generalization to stochastic gradient descent
- randomized singular value decomposition
- random sketching
- matrix completion
- and compressive sensing
- and corresponding applications
Topics explicitly listed in official catalogue description
Prerequisites & course information
Requisites: Graduate/professional standing or declared in Mathematics VISP (graduate or dissertator) Course Designation: Grad 50% - Counts toward 50% graduate coursework requirement Repeatable for Credit: No Last Taught: Spring 2026 Learning Outcomes: 1. Implement, in a computer language, the principal linear algebra solvers, namely, matrix completion, randomized SVD, matrix sketching, and the Kaczmarz algorithm. Audience: Graduate 2. Identify the conditions, assumptions, and effectiveness of the principal linear algebra solvers. Audience: Graduate 3. Reproduce the proof strategies for effectiveness of these algorithms and summarize the main parts of these proofs. Audience: Graduate 4. Apply random linear algebra solvers to problems from image reconstruction, inverse problems and topic modeling. Audience: Graduate 5. Model problems from the physical or social sciences in matrix form and identify regimes to apply linear algebra solvers. Audience: Graduate Learning Outcomes: 1. Implement, in a computer language, the principal linear algebra solvers, namely, matrix completion, randomized SVD, matrix sketching, and the Kaczmarz algorithm. Audience: Graduate 2. Identify the conditions, assumptions, and effectiveness of the principal linear algebra solvers. Audience: Graduate 3. Reproduce the proof strategies for effectiveness of these algorithms and summarize the main parts of these proofs. Audience: Graduate 4. Apply random linear algebra solvers to problems from image reconstruction, inverse problems and topic modeling. Audience: Graduate 5. Model problems from the physical or social sciences in matrix form and identify regimes to apply linear algebra solvers. Audience: Graduate
Sources
- Course catalogue ↗2026-2027