Powered by Indico
v3.2
Lecturer
Alice Cortinovis alice.cortinovis@unipi.it
Timetable and workload
Lectures: 8 hours
Computational session: 2 hours
Course content
This course provides an introduction to the field of randomized numerical linear algebra. As problem dimensions grow, classical deterministic numerical linear algebra algorithms often become prohibitively expensive in terms of computational cost or memory usage. Randomization provides a powerful alternative and allows us to design algorithms that are both computationally efficient and provably accurate with high probability. The goal of the course is to present the key mathematical principles underlying randomized matrix algorithms, emphasizing both the theoretical analysis and some practical numerical considerations.
We start with a discussion of several reasons why randomization helps numerical linear algebra algorithms to be faster while retaining accuracy. As a first example, we study stochastic trace estimation, which serves as a motivation to study concentration inequalities for random variables and matrices. We introduce subspace embeddings, which are a way to reduce high-dimensional problems to low-dimensional ones while approximately preserving the geometrical structure. This powerful concept is applied to the solution of overdetermined least-squares problems. We then discuss the workhorse of randomized numerical linear algebra: the randomized rangefinder for the solution of low-rank approximation problems. The course also covers other related kinds of low-rank approximations, such as Nyström approximations for symmetric positive semidefinite matrices and approximations based on the selection of rows and columns. At the end of the course, participants will see some of the algorithms at work in a "hands-on" computational session.
Course requirements
The course is intended for students with knowledge of linear algebra and basic probability theory. Familiarity with numerical linear algebra (least-squares problems, standard matrix factorizations) is desirable. The necessary elements of numerical linear algebra will be briefly reviewed before introducing their randomized counterparts.