# Registered Data

## [00107] Randomized numerical linear algebra

**Session Date & Time**:- 00107 (1/3) : 4C (Aug.24, 13:20-15:00)
- 00107 (2/3) : 4D (Aug.24, 15:30-17:10)
- 00107 (3/3) : 4E (Aug.24, 17:40-19:20)

**Type**: Proposal of Minisymposium**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.**Classification**:__65F55__,__65C99__,__68T09__**Speakers Info**:- Yijun Dong (University of Texas at Austin)
- Tyler Chen (New York University)
- Jocelyn Chi (University of California, Los Angeles)
- Ethan Epperly (California Institute of Technology)
- Zachary Frangella (Stanford University)
- Eric Hallman (North Carolina State University)
- Joe Kileel (University of Texas at Austin)
- Maike Meier (University of Oxford)
- Riley Murray (University of California, Berkeley)
- Taejun Park (University of Oxford)
- Katherine Pearce (University of Texas at Austin)
**Robert Webber**(California Institute of Technology)

**Talks in Minisymposium**:**[03344] Randomized low-rank approximation: Where we've been and where we're going****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.

**[03373] Sketched Gaussian Model Linear Discriminant Analysis via the Randomized Kaczmarz Method****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****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.

**[03767] Randomized Nyström approximation for symmetric indefinite matrices****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.

**[04049] Efficient Bounds for Canonical Angles in Randomized Subspace Approximations****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.

**[04463] How and why to "uncompute" the randomized SVD****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.

**[04484] Krylov-aware stochastic trace estimation****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.

**[04567] The Cluster and the Gap in Randomized Subspace Iteration****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.

**[04802] Are sketch-and-precondition least squares solvers numerically stable?****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.

**[04810] Error Estimation in Randomized Algorithms for Rank-Revealing Factorizations****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.

**[04913] RandBLAS and RandLAPACK - Toward Standard Libraries for RandNLA****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.

**[04958] RandNLA for Faster Convex Optimization****Author(s)**:**Zachary Frangella**(Stanford University)

**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.