Projects

Randomized low-rank approximation is an approach for compressing a large matrix to a low-rank factored form while preserving the data as accurately as possible. Randomized low-rank matrix approximation can be used to accelerate machine learning algorithms for prediction and clustering, making it a vital tool for modern data science.

We are developing faster, more accurate algorithms for randomized low-rank matrix approximation, including "randomly pivoted Cholesky" for positive semidefinite kernel matrices and "randomized block Krylov iteration" for general matrices.

For more details, see:

• Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations [Communications on Pure & Applied Mathematics] [CodEx seminar talk]

• Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications [arXiv]

Recently, a class of algorithms combining classical fixed point iterations with repeated random sparsification of approximate solution vectors was successfully applied to eigenproblems with matrices as large as 10108 x 10108. So far, a complete mathematical explanation for this success has proven elusive. Additionally, the family of methods has not been extended to the important case of linear system solves.

With Jon Weare, I recently proposed a new scheme based on repeated random sparsification that is capable of solving sparse linear systems in arbitrarily high dimensions. We provided a complete mathematical analysis of this new algorithm. Our analysis establishes a faster-than-Monte Carlo convergence rate and justifies use of the scheme even when the solution vector itself is too large to store.

For more details, see:

• Randomly sparsified Richardson iteration: A dimension-independent sparse linear solver [arXiv] [1W-Minds seminar talk] 

Rare events can be highly impactful. Yet, estimating the probability p of a rare event by direct numerical simulation requires a very large sample size (>100 p-1). Since generating such a large sample can be prohibitively expensive, are there more practical methods for calculating rare event probabilities?

To help answer this question, we investigated "splitting and killing" algorithms for rare event probability estimation. These algorithms "split" selected trajectories to promote progress toward a rare event and randomly "kill" other trajectories to control the computational cost.

We applied splitting and killing to evaluate the probability that Mercury will become unstable and collide with another celestial body over the next 2.2 billion years. We calculated the probability to be ~10-4 and obtained a speed-up of nearly 100x over direct numerical simulation.

In the press: this work on rare event sampling algorithms has been featured in the California Business Journal, Forbes.com, and SIAM News.

For more details, see:

• Rare event sampling improves Mercury instability statistics, [Astrophysical Journal, 2021] [IGPP seminar talk] 

• Practical rare event sampling for extreme mesoscale weather, [Chaos, 2019]