Abstract : Randomized numerical linear algebra (RNLA) is an emerging field of computational mathematics that has enabled matrix computations of unprecedented scale. Given the increasing size of data sets, RNLA is often the only way to reasonably perform computations. In addition to speed, RNLA provides solutions with exceptional accuracy and robustness. Success stories in RNLA include low-rank approximation, least-squares problems, and trace estimation. In addition, the field has witnessed recent progress in linear systems, eigenvalue problems, and tensor approximation. This minisymposium aims to bring together researchers working in RNLA to present recent progress, discuss challenges, and share ideas.
Organizer(s) : Ethan Epperly, Per-Gunnar Martinsson, Yuji Nakatsukasa, Robert Webber
Sponsor : This session is sponsored by the SIAM Activity Group on Computational Science and Engineering.
[03344] Randomized low-rank approximation: Where we've been and where we're going
Format : Talk at Waseda University
Author(s) :
Robert Webber (California Institute of Technology)
Abstract : I will survey randomized algorithms for low-rank matrix approximation. These algorithms are helpful for speeding up computations involving high-dimensional matrices. When the singular values of the target matrix decay quickly, the most efficient low-rank approximation algorithms are "randomized SVD" and, if the matrix is positive semidefinite, "randomized Nyström". When the singular values of the target matrix decay slowly, low-rank approximation becomes more difficult and the best-performing algorithms are instead randomized block Krylov methods.
[04049] Efficient Bounds for Canonical Angles in Randomized Subspace Approximations
Format : Online Talk on Zoom
Author(s) :
Yijun Dong (UT Austin)
Per-Gunnar Martinsson (UT Austin)
Yuji Nakatsukasa (University of Oxford)
Abstract : Randomized subspace approximation is an effective approach for approximating partial SVDs of large matrices, whose accuracy has been extensively analyzed in terms of residual errors. However, our understanding of the computed singular subspaces remains limited. We present bounds and estimates for canonical angles of randomized subspace approximation that can be computed efficiently either a priori or a posteriori. Numerical experiments demonstrate the empirical effectiveness of these canonical angle approximations under various algorithmic choices.
[03767] Randomized Nyström approximation for symmetric indefinite matrices
Format : Talk at Waseda University
Author(s) :
Taejun Park (University of Oxford)
Yuji Nakatsukasa (University of Oxford)
Abstract : In this talk, we present a variant of the Nyström method for symmetric indefinite matrices. The Nyström method is a popular choice for symmetric positive semi-definite matrices. However, the method can fail when the matrix is indefinite, for which the error can be large. We first identify the main challenges in finding a robust Nyström approximation to symmetric indefinite matrices and describe an algorithm, whose robustness for symmetric indefinite matrices is illustrated with experiments.
[04567] The Cluster and the Gap in Randomized Subspace Iteration
Format : Talk at Waseda University
Author(s) :
Eric Hallman (Google)
Abstract : This talk concerns the convergence rates of the singular values and vectors when running randomized subspace iteration. Its aim is to present a single clean approach (based on the techniques of (Yuan/Gu/Li, 2018)) that can be used to derive a variety of existing bounds in the literature, both gap-dependent and gap-independent. Limitations of the proof strategy are discussed, as well as its extensions to randomized block Lanczos.
Abstract : In this talk, we show how to accelerate linear system solves and convex optimization, by exploiting low rank structure. Employing randomized low rank approximation, we design a new randomized preconditioner for the conjugate gradient method, and a method called NysADMM, for composite convex optimization. These methods come with strong theoretical and numerical support. Indeed, a simple implementation of NysADMM solves important problems like lasso, logistic regression, and support vector machines 2--42x faster than standard solvers.
[03373] Sketched Gaussian Model Linear Discriminant Analysis via the Randomized Kaczmarz Method
Format : Talk at Waseda University
Author(s) :
Jocelyn T. Chi (Rice University)
Deanna Needell (University of California at Los Angeles)
Abstract : We present an iterative randomized approach to Gaussian model linear discriminant analysis (LDA) for large data. Harnessing a least squares formulation, we mobilize the stochastic gradient descent framework and obtain a sketched classifier that is very comparable to full data LDA. Our convergence guarantees for the sketched predictions on new data account for both modeling and algorithmic randomness. Our experiments demonstrate that sketched LDA can offer a very viable alternative for very large data.
[03665] Moment Estimation of Nonparametric Mixtures Through Implicit Tensor Decomposition
Format : Talk at Waseda University
Author(s) :
Joe Kileel (UT Austin)
Yifan Zhang (UT Austin)
Abstract : I will present methods to estimate conditionally-independent multivariate mixture models, without assuming parameterizations of the distributions. Following the method of moments, I will tackle an incomplete tensor decomposition problem to compute the mixing weights and componentwise means. Then I will explain how to compute the cumulative distribution functions and other statistics through linear solves. Crucially for computations in high dimensions, methods in this talk evade steep costs associated with high-order tensors, via efficient tensor-free operations.
[04802] Are sketch-and-precondition least squares solvers numerically stable?
Format : Talk at Waseda University
Author(s) :
Maike Meier (University of Oxford)
Yuji Nakatsukasa (University of Oxford)
Alex Townsend ( Cornell University)
Marcus Webb (University of Manchester)
Abstract : Sketch-and-precondition solvers, such as Blendenpik and LSRN, are popular for solving large least squares (LS) problems of the form $Ax=b$ with $A\in\mathbb{R}^{m\times n}$ and $m\gg n$. In this talk, we show that the sketch-and-precondition technique is not numerically stable for highly ill-conditioned LS problems. We propose an alternative method, which we call $\textit{sketch-and-apply}$, based on directly applying the randomized preconditioner and show it is numerically stable under moderate conditions.
[04913] RandBLAS and RandLAPACK - Toward Standard Libraries for RandNLA
Format : Talk at Waseda University
Author(s) :
Riley John Murray (ICSI, LBNL, and UC Berkeley)
James Demmel (UC Berkeley)
Michael Mahoney (ICSI, LBNL, and UC Berkeley)
N. Benjamin Erichson (ICSI and LBNL)
Maksim Melnichenko (UT Knoxville)
Osman Asif Malik (LBNL)
Laura Grigori (INRIA Paris and Sorbonne University)
Piotr Luszczek (UT Knoxville)
Michal Derezinski (University of Michigan)
Miles Lopes (UC Davis)
Tianyu Liang (UC Berkeley)
Hengrui Luo (LBNL)
Jack Dongarra (UT Knoxville)
Burlen Loring (LBNL)
Parth Nobel (Stanford University)
Abstract : This talk concerns an ongoing effort to bring RandNLA further into mainstream computing. It includes highlights from our recently released monograph (arXiv:2302.11474) as well as discussion of software. The software component focuses on our C++ library for sketching called RandBLAS. We showcase RandBLAS' capabilities by using it to implement a recently developed algorithm for pivoted QR decompositions of tall matrices. Experiments show the proposed algorithm is often faster than Intel MKL's unpivoted QR.
[04810] Error Estimation in Randomized Algorithms for Rank-Revealing Factorizations
Format : Online Talk on Zoom
Author(s) :
Katherine Joyce Pearce (The Oden Institute at the University of Texas at Austin)
Chao Chen (The Oden Institute at the University of Texas at Austin)
Yijun Dong (The Oden Institute at the University of Texas at Austin)
Per-Gunnar Martinsson (The Oden Institute at the University of Texas at Austin)
Abstract : Interpolative decompositions involve “natural bases” of row and column subsets of a given matrix that approximately span its row and column spaces.
For large-scale problems, randomized sketching can serve as an initial step in skeleton selection.
In this talk, we describe an adaptive, parallelizable algorithm applying LU with partial pivoting to randomized sketches to determine a target rank for the approximation.
Our algorithm exhibits improved efficiency over adaptive randomized column-pivoted QR while maintaining comparable accuracy.
[04484] Krylov-aware stochastic trace estimation
Format : Talk at Waseda University
Author(s) :
Tyler Chen (New York University)
Eric Hallman (Google)
Abstract : We discuss an algorithm for estimating the trace of a matrix function $f(\mathbf{A})$ using implicit products with a symmetric matrix $\mathbf{A}$. Existing methods for implicit trace estimation of a matrix function tend to treat matrix-vector products with $f(\mathbf{A})$ as a black-box to be computed by a Krylov subspace method. Like other algorithms for implicit trace estimation, our approach is based on a combination of deflation and stochastic trace estimation. However, we take a closer look at how products with $f(\mathbf{A})$ are integrated into these approaches which enables several efficiencies not present in previously studied methods. In particular, we describe a Krylov subspace method for computing a low-rank approximation of a matrix function by a computationally efficient projection onto Krylov subspace.
[04463] How and why to "uncompute" the randomized SVD
Format : Talk at Waseda University
Author(s) :
Ethan Nicholas Epperly (California Institute of Technology)
Abstract : The randomized SVD is a low-rank approximation procedure and is a foundational tool in randomized matrix computations. This talk introduces a novel "uncomputing" operation in which the randomized SVD approximation is downdated by deleting different columns from the random test matrix. Two examples of the use of this "uncomputing" primitive are presented: estimating the trace of a matrix accessed only through matrix–vector products and estimating the error of the randomized SVD low-rank approximation.
