Randomized matrix computations

MATH-403 / 5 credits

Teacher: Kressner Daniel

Language: English

Remark: Cours donné en alternance tous les deux ans

Summary

This course is concerned with randomized algorithms that have been developed during the last decade to solve large-scale linear algebra problems from, for example, scientific computing and statistical learning. Emphasis will be placed on both, the development and analysis of such algorithms.

Content

The most popular randomized linear algebra techniques and algorithms willl be discussed. Examples:

- Embeddings and sketching
- Leverage scores
- Trace estimation
- Randomized eigenvalue solvers
- Randomized solvers for least-squares and related regression problems
- Randomized low-rank approximation
- Randomized interpolative decompositions
- Random features and kernel sampling
- Randomized solvers for graph Laplacians

For the analysis of algorithms, a certain amount of stochastic analysis and random matrix theory is needed. Important concepts include: 
- Moments and tails, concentration inequalities for random variables
- Matrix concentration inequalities
- Spectral properties of random matrix models
- Small ball method
- Gaussian and determinantal point processes

Learning Prerequisites

Required courses

Analysis (multivariate calculus)
Linear algebra
Probability theory
Elements of numerical linear algebra and numerical methods
Programming skills in a language suitable for scientific computation (Matlab, Python, Julia...)

 

Learning Outcomes

By the end of the course, the student must be able to:

  • Manipulate concepts from randomized numerical linear algebra
  • Develop randomized algorithms for specific applications
  • Analyze randomized algorithms for linear algebra problems
  • Implement randomied algorithms
  • Apply the general theory to special cases
  • Prove some of the theorems discussed in class

Transversal skills

  • Assess progress against the plan, and adapt the plan as appropriate.
  • Plan and carry out activities in a way which makes optimal use of available time and other resources.
  • Use a work methodology appropriate to the task.
  • Demonstrate the capacity for critical thinking
  • Demonstrate a capacity for creativity.
  • Take feedback (critique) and respond in an appropriate manner.
  • Use both general and domain specific IT resources and tools

Teaching methods

Lectures + exercise sessions + projects

 

Expected student activities

Students are expected to attend lectures and participate actively in class and exercises. Exercises will include both theoretical work and programming assignments. Students also complete substantial homeworks and projects (possibly in small groups) that likewise include theoretical and numerical work.

 

Assessment methods

Homeworks and projects

Resources

Bibliography

A good resource for the course are the lecture notes by Joel Tropp from https://tropp.caltech.edu/courses.html#lecturenotes . Some of the theory is also covered and in more detail in Roman Vershynin's HDP book https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.html

More references and slides will be provided as the course progresses.

 

Moodle Link

In the programs

  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Oral (winter session)
  • Subject examined: Randomized matrix computations
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional

Reference week

Related courses

Results from graphsearch.epfl.ch.