Skip to content. | Skip to navigation

Personal tools


UMR 5672

logo de l'ENS de Lyon
logo du CNRS
You are here: Home / Seminars / Machine Learning and Signal Processing / Wilson’s Algorithm for Randomized Linear Algebra

Wilson’s Algorithm for Randomized Linear Algebra

Yusuf Yigit Pilavci (PhD Student, GIPSA-lab, Grenoble ; encadrants : Pierre-Olivier Amblard ; Nicolas Tremblay ; Simon Barthelmé)
When Jun 09, 2022
from 01:00 to 03:00
Attendees Yusuf Yigit Pilavci
Add event to calendar vCal

Title :Wilson’s Algorithm for Randomized Linear Algebra

Asbtract :   The tools of numerical linear algebra are indispensable in many scientific computations. However, some essential operations, such as matrix inversion, eigendecomposition or SVD, become impractical when dealing with the large dimensional input matrices (e.g. large datasets). 
Since these operations scale cubically in the input dimension, the exact numerical computations run too slowly and stay behind the faster approximate methods. A recent branch of approximate methods, called "Randomized Linear Algebra" (RLA), proposes to use Monte Carlo methods. Generically, these methods approximate the result of the algebraic operation by a sketch-and-solve scheme; first, they sample a typically small portion (rows and columns) of the input matrix at random (sketch). They then compute the expensive operation on this small part of the matrix rather than the original input, giving a Monte Carlo estimate. Under certain conditions, the result may yield a small approximation error. In this talk, we will look at a different way of performing RLA. Instead of sampling from the input matrix, we leverage fascinating links between graph theory and linear algebra. In particular, we focus on the problems in Laplacian-based numerical linear algebra and benefit from the rich theoretical connections between graph Laplacians and a special random process called Random Spanning Forests (RSF). Leveraging these links and Wilson's algorithm, i.e., an efficient sampling algorithm for RSFs, we propose RLA algorithms for estimating inverses and trace estimations of certain classes of matrices, yielding applications in graph signal processing and machine learning.

More information :

Exposé en salle M7 101 (ENS de Lyon, site Monod, 1er étage côté Recherche au M7)