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
- Lecture: 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
- Lecture: 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
- Lecture: 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
- Lecture: 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
- Lecture: 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
- Lecture: 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
- Lecture: 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
- Lecture: 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
- Lecture: 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
- Lecture: 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
- Lecture: 2 Hour(s) per week x 14 weeks
- Exercises: 2 Hour(s) per week x 14 weeks
- Type: optional