Wilson’s Algorithm for Randomized Linear Algebra
| Quand ? |
Le 09/06/2022, de 13:00 à 15:00 |
|---|---|
| Participants |
Yusuf Yigit Pilavci |
| Ajouter un événement au calendrier |
vCal
iCal
|
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 : https://y2p.github.io/