Randomized matrix computations

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

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

• https://go.epfl.ch/MATH-403