Topic: Randomized algorithms

Misha Kilmer develops structured matrix approximation by an invertible matrix-to-tensor transformation, tensor approximation, and a mapping back to matrix space. Different tensor decompositions yield sums of structured Kronecker products, block low-rank matrices, or combinations of both. The framework exposes latent operator structure useful for large computations, and the talk considers where randomization could help. Joint work with Arvind Saibaba at North Carolina State University.

Robert Gower introduces Polar Express for the polar decomposition and matrix sign function, motivated by Muon neural-network training. Using only matrix-matrix products makes the method suited to high-throughput GPUs. Each iteration adapts its polynomial update through minimax optimization, building on Chen and Chow and Nakatsukasa and Freund. Worst-case error minimization gives rapid initial and asymptotic convergence. The talk addresses finite-precision implementation in bfloat16 and reports improved validation loss when training GPT-2 on one billion FineWeb tokens across several learning ra

David Woodruff develops sampling bounds for estimating the spectrum of symmetric matrices with bounded entries. Principal-submatrix sampling achieves epsilon times n additive error using roughly 1/epsilon² samples, eliminating dependence on n and improving prior epsilon dependence up to logarithmic factors. Squared row-norm sampling gives epsilon times the Frobenius norm accuracy with roughly 1/epsilon² samples, improving a previous 1/epsilon⁸ bound. For bounded-entry positive-semidefinite matrices, O(1/epsilon) sampled columns permit nonadaptive approximation of the leading eigenvector with e

Robert Webber connects partial pivoted Cholesky, effective for nearly low-rank matrices, with Vecchia approximation, effective when inverse Cholesky factors are nearly sparse. Combining a partial Cholesky approximation with a Vecchia approximation of its residual produces another Vecchia approximation of the original matrix with an enlarged sparsity pattern. This unifies several factored matrix-approximation approaches and explains the broader applicability of the Vecchia framework.

Alice Cortinovis presents Adaptive Randomized Pivoting for selecting representative matrix columns through adaptive leverage-score sampling. Its expected Frobenius approximation error matches the optimal existence guarantee. The method is a randomized counterpart to an approach by Osinsky and offers a simpler, less costly alternative to volume sampling with the same theoretical guarantee. The talk extends the strategy to the Discrete Empirical Interpolation Method, cross or skeleton approximation, and Nyström approximation of positive-semidefinite matrices.

Tyler Chen presents randomized block conjugate gradient for one positive-definite linear system. The method can provably outperform conjugate gradient with a broad class of Nyström preconditioners while avoiding explicit preconditioner construction. Its analysis also yields guarantees for new Nyström-preconditioned variants. Applications include computing a complete ridge-regression regularization path and drawing multiple independent samples from a high-dimensional Gaussian distribution.

Michal Dereziński discusses oblivious subspace embeddings, random dimension-reduction maps that approximately preserve all vector norms in a low-dimensional subspace. Such maps support least-squares regression and low-rank approximation, yet efficient optimal embedding dimensions have left a gap between theory and practice. Analyzing universality in sparse random matrices leads to a resolution of the Nelson–Nguyen conjecture up to sub-polylogarithmic factors in SODA 2026. Joint work with Shabarish Chenakkod, Xiaoyu Dong, and Mark Rudelson.

Alex Townsend examines what greedy pivoting can guarantee in rank-revealing factorizations, which remain important alongside randomized sampling and sketching. A local maximum-volume viewpoint gives sharp criteria for reliable rank revelation by pivoted Gaussian elimination and QR. The comparison with pivoted Cholesky on smooth-kernel matrices shows that greedy pivoting there cannot exhibit Kahan-like behavior. These results clarify the theoretical strengths and limitations of deterministic steps in matrix approximation.

Chris Musco studies how to approximate an unknown matrix by a structured one using a limited, adaptively chosen sequence of matrix-vector products. This models operator learning in scientific machine learning as well as computational algorithms. Randomized SVD provides strong guarantees for low-rank targets; analogous results for sparse and hierarchical structures are less developed. The talk presents progress on efficient algorithms for these classes and a broader complexity theory. Joint work with Noah Amsel, Pratyush Avi, Tyler Chen, Prathamesh Dharangutte, Chinmay Hegde, Feyza Duman Keles,

Davide Palitta introduces the S^T S-SVD, a decomposition of A derived from the SVD of its sketch SA. It is exact with high probability, preserves singular values probabilistically, and makes left singular vectors orthonormal in the sketch-induced seminorm, with lower computational cost. The talk relates this perspective to subspace embeddings and least-squares residuals, assesses sketch quality, and bounds departures from ordinary orthogonality in randomized QR. A further application extends the nearest-orthogonal-matrix problem to S^T S-orthogonality. The work builds on Gilbert, Park, and Wak

Lior Horesh presents tensor-tensor algebra designed to retain key properties of matrix algebra while representing multidimensional correlations. An Eckart–Young-like tensor representation theorem underpins computationally feasible, provably optimal decompositions. Matrix-mimetic operations allow existing computational workflows to be adapted to tensors. Examples include tensorized neural-network structures and tensor graph convolutional networks for time-evolving graphs. The discussion concludes with tensor group symmetries and extensions to equivariant learning.

Daniel Kressner surveys randomized algorithms for joint eigenvalue problems: finding common eigenvectors and their eigenvalues across a family of matrices. The talk covers algorithm development and analysis, with examples from signal processing and multivariate root finding. Joint work with Haoze He and Bor Plestenjak.

Joel Tropp studies structured dimension reduction through the injectivity of random maps, motivated by fast low-rank approximation and least-squares regression. This viewpoint sharpens guarantees for sparse maps and gives exponential improvements for tensor-product dimension reduction. Experiments assess the resulting structured random matrices on synthetic problems and scientific applications. Joint work with Chris Camaño, Ethan Epperly, and Raphael Meyer, available as arXiv:2508.21189.

Sherry Xiaoye Li surveys randomized construction of hierarchically low-rank matrices, including H/H2, HODLR, HSS, and butterfly formats with different off-diagonal structures. Applications include integral equations, boundary elements, discretized PDEs, and statistical or machine-learning kernel matrices, using either iterative matrix-vector products or direct factorization and solves. Constructing these representations from an implicit dense operator is often the main cost. The talk offers a unified view of sketch distributions, sketch sizes, approximation error bounds, high-performance imple

Alberto Bucci develops single-pass randomized and streaming low-rank approximation, beginning with large matrices and the strengths and limitations of streaming algorithms. The discussion extends to Tucker, tensor-train, and tree tensor-network representations. Tensor-train approximations are then incorporated into Krylov solvers, including sketched GMRES, to reduce expensive intermediate contractions. The framework is presented as applicable beyond tensor trains to other tensor-network architectures.

Daniel Szyld analyzes rand-cholQR, a randomized method for tall-and-skinny QR factorization using one or two sketch matrices. For numerically full-rank inputs, its orthogonality error is bounded with high probability at the scale of unit roundoff. NVIDIA A100 experiments compare multisketching with CholeskyQR2, reporting comparable or better speed and stronger stability with little additional memory or computation. Joint work with Andrew Higgins, Erik Boman, and Ichitaro Yamazaki.

Per-Gunnar Martinsson presents randomized black-box algorithms that compress rank-structured matrices, including H-matrices and HSS matrices, into data-sparse representations. Access is through matrix-vector products, which suits Schur-complement construction and matrix multiplication. When both the operator and its transpose admit O(N) application, the overall compression can also have linear complexity. A featured method combines compression and factorization of an H-matrix under strong admissibility.

Yuji Nakatsukasa explains how CUR decompositions approximate a matrix using selected columns and rows, without inspecting every entry once the indices are chosen. Near-optimal CUR approximations exist relative to the truncated singular value decomposition, and efficient algorithms make them useful for large problems. The talk covers computation and theoretical guarantees before exploring applications to approximation theory, model reduction, and parameter-dependent problems.

Ilse Ipsen examines full-column-rank least-squares systems solved through normal equations with symmetric or nonsymmetric randomized preconditioning computed at lower arithmetic precision. Effective preconditioning can deliver accuracy close to QR-based MATLAB backslash even for badly conditioned matrices. The analysis separates the solution's accuracy from the accuracy of the preconditioner: the original least-squares residual controls the error. The talk develops realistic relative-error perturbation bounds. Joint work with James Garrison.