Computational Mathematics seminars

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 implementation, applications, and open questions.

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.

Alexander Barg explores research questions inspired by Reed–Muller codes. The first concerns storage codes on triangle-free graphs, where neighboring vertices determine parity checks. Certain graphs admit codes approaching the maximum size of 2^n; whether Reed–Muller codes yield similar constructions remains open. The second extends the construction of Reed–Muller codes from cosets in an elementary abelian group to Coxeter groups, including permutation groups. Questions include analogues of the |u|u+v| construction and modern decoders, whether these codes share Reed–Muller codes' capacity achievement on the binary erasure channel, and a conjectured minimum-distance formula.

Alex Gittens studies how many data points must be labelled to fit a linear regression model with nearly the predictive power of a fully labelled dataset. Existing coreset and iterative approaches handle constant-factor approximations, but tighter approximations that improve with dataset size need different methods. The talk presents a polynomial-time algorithm that reduces label complexity by an additive O(sqrt(n)), using a sharp analysis of regression error for a coreset formed by backward selection.

Networks are widely used as mathematical models of complex systems across many scientific disciplines, and in particular within neuroscience. In this talk, we introduce two aspects of our collaborative research: (1) machine learning and networks, and (2) graph dimensionality. Machine learning and networks. Decades of work have produced a vast corpus of research characterising the topological, combinatorial, statistical and spectral properties of graphs. Each graph property can be thought of as a feature that captures important (and sometimes overlapping) characteristics of a network. We have developed hcga, a framework for highly comparative analysis of graph data sets that computes several thousands of graph features from any given network. Taking inspiration from hctsa, hcga offers a suite of statistical learning and data analysis tools for automated identification and selection of important and interpretable features underpinning the characterisation of graph data sets. We show that hcga outperforms other methodologies (including deep learning) on supervised classification tasks on benchmark data sets whilst retaining the interpretability of network features, which we exemplify on a dataset of neuronal morphologies images. Graph dimensionality. Dimension is a fundamental property of objects and the space in which they are embedded. Yet ideal notions of dimension, as in Euclidean spaces, do not always translate to physical spaces, which can be constrained by boundaries and distorted by inhomogeneities, or to intrinsically discrete systems such as networks. Deviating from approaches based on fractals, here, we present a new framework to define intrinsic notions of dimension on networks, the relative, local and global dimension. We showcase our method on various physical systems.

Interpreting high-dimensional datasets requires new computational and analytical methods. We developed such methods to extract and analyze neural activity from 20,000 neurons recorded simultaneously in awake, behaving mice. The neural activity was not low-dimensional as commonly thought, but instead was high-dimensional and obeyed a power-law scaling across its eigenvalues. We developed a theory that proposes that neural responses to external stimuli maximize information capacity while maintaining a smooth neural code. We then observed power-law eigenvalue scaling in many real-world datasets, and therefore developed a nonlinear manifold embedding algorithm called Rastermap that can capture such high-dimensional structure.

This talk examines randomized sampling methods for approximating positive semidefinite matrices. Fast leverage-score approximation combined with the Nystrom method yields provably accurate, linear-time algorithms for kernel ridge regression and kernel principal-component analysis, avoiding the usual quadratic-time cost. Related sampling techniques give relative-error low-rank approximations of positive semidefinite matrices in sublinear time without assumptions about incoherence or condition number. The results illustrate how randomized algorithms can exploit positive semidefinite structure beyond the capabilities of traditional methods. The talk concludes with open questions, particularly about oblivious sketches of kernel matrices.

Building on the preceding linear-algebra tutorials, this lecture presents two further approaches to matrix sketching: leverage-score sampling and the Subsampled Randomized Hadamard Transform. It examines how these methods produce effective compressed matrix representations for a variety of applications.

This tutorial surveys nearly optimal algorithms for regression, low-rank approximation and related numerical problems. The central approach is sketch and solve: compress a large problem into a smaller representation, then apply an algorithm to that reduced problem. These techniques provide fast methods for fundamental machine-learning and numerical-linear-algebra tasks, with running times proportional to the number of nonzero entries in the input.