PACM IDeAS Seminar · Princeton

Feb262026

Sparser, better, faster, stronger: Emerging approaches in the theory and practice of randomized dimensionality reduction

Ethan N. Epperly · UC Berkeley

2:00 PM · Jadwin Hall 111

Abstract

For approaching thirty years, randomized dimensionality reduction techniques have been a core tool in the theory and practice of computation. But despite this robust history, basic questions remain hotly debated: Which dimensionality reduction map should be used? How can the map be adapted to structure in the problem? What is the right theoretical approach to analyzing randomized dimensionality reduction? This talk presents a new approach to the theory of randomized dimensionality reduction under which the core feature of a good dimensionality map is injectivity: It is fine if the map stretches things out a bit as long as it does not annihilate any element of the data space. This new approach yields new analysis of sparse and tensor-structured dimensionality reduction maps that comes closer to describing how these maps behave in practice. This talk is designed for a general audience and assumes no prior familiarity with randomized dimensionality reduction.

Event page

Mar052026

Randomized algorithms for linear algebraic computations

Per-Gunnar Martinsson · The University of Texas at Austin

2:00 PM · Jadwin Hall 111

Abstract

The talk will describe how randomized algorithms can effectively, accurately, and reliably solve linear algebraic problems that are omnipresent in scientific computing and in data analysis. We will focus on techniques for low rank approximation, since these methods are particularly simple and powerful, and are well understood mathematically. The talk will also briefly survey how randomized techniques can be applied to approximate global operators that arise in scientific computing such as solution operators to elliptic PDEs, boundary-to-boundary operators such as the Dirichlet-to-Neumann map, and time evolution operators of parabolic PDEs.

Event page

Mar192026

Operator learning without the adjoint

Diana Halikias · NYU

2:00 PM · Fine Hall 224

Abstract

There is a mystery at the heart of operator learning: how can one recover a non-self-adjoint operator from data without probing the adjoint? Current practical approaches suggest that one can accurately recover an operator while only using data generated by the forward action of the operator without access to the adjoint. However, naively, it seems essential to sample the action of the adjoint. We partially explain this mystery by proving that without querying the adjoint, one can approximate a family of non-self-adjoint infinite-dimensional compact operators via projection onto a Fourier basis. We then apply the result to recovering Green's functions of elliptic partial differential operators and derive an adjoint-free sample complexity bound. While existing theory justifies low sample complexity in operator learning, ours is the first adjoint-free analysis that attempts to close the gap between theory and practice. We also explore a closely related question in numerical linear algebra: when is access to both forward and transpose matrix-vector products essential? We discuss the role of transpose access in sketching algorithms for low-rank approximation, least-squares problems, and norm estimation.

Event page

Mar262026

Leveraging latent mathematical structure in geometry processing

Leticia Mattos Da Silva · MIT

2:00 PM · Fine Hall 224

Abstract

Myriad problems in geometry processing are readily formulated through continuous mathematics, including variational energies, stochastic dynamics, geometric constraints, and partial differential equations. Often, the challenge in solving these formulations in practice is not the absence of a principled theoretical formulation, but that standard computational approaches are limited by design constraints or technical barriers, resulting in instability or poor scalability. Common numerical techniques resort to fragile nonlinear solvers, repeated large optimizations, or forgo analytical or physical properties of the continuous problem.

In this talk, I will present methods that tackle these limitations by recognizing and exploiting latent problem structure, including convexity, variational reformulations, and symmetry. After a prelude illustrating the value of this approach in two problems of interest in geometry — simulating elastodynamics and solving PDEs on surfaces — I will describe a new approach to resampling that leverages a time-symmetric variant of the Schrödinger bridge problem. In each of these works, we discuss how algorithmic design, when carefully guided by underlying mathematical structure, can yield numerical tools that offer practitioners greater control and flexibility.

Event page

Apr022026

Toward information geometric mechanics

Florian Schäfer · NYU

2:00 PM · Fine Hall 224

Abstract

Shock waves in high-speed gas dynamics cause severe numerical difficulties for classical solvers and scientific machine learning. They are fundamentally a multiscale problem: While viscous effects ensure smoothness on microscopic scales, shocks manifest as macroscopic discontinuities. This talk begins with the observation that shock formation arises from the flow map reaching the boundary of the manifold of diffeomorphisms. We modify its geometry such that geodesics approach but never reach the boundary. The resulting information geometric regularization (IGR) has smooth solutions while avoiding the excessive dissipation of viscous regularizations, accelerating and simplifying the simulation of flows with shocks. We prove the existence of global strong IGR solutions in the unidimensional pressureless case and illustrate its practical utility on multidimensional examples with complex shock interactions. With S. Bryngelson and other collaborators, we use IGR to conduct the first compressible flow simulation exceeding a quadrillion degrees of freedom.

The modified geometry of the diffeomorphism manifold is the information geometry of the mass density. The last part of the talk explains how this observation motivates information geometric mechanics that views the solutions of continuum mechanical PDEs as parameters of probability distributions originating from statistical physics. Replacing the Euclidean geometry of individual particles with the information geometry of statistical families promises performant numerical methods that preserve the positivity of densities and energies and readily integrate with scientific machine learning.

Event page

Apr092026

Convergence of randomized and greedy block Gauss–Seidel methods, as well as asynchronous iterations

Daniel B. Szyld · Temple University

2:00 PM · Fine Hall 224

Abstract

We extend results known for the randomized (point and block) Gauss-Seidel and the Gauss-Southwell methods for the case of a Hermitian and positive definite matrix to certain classes of non-Hermitian matrices. We consider cases with overlapping variables (as in Domain Decomposition). We obtain convergence results for a whole range of parameters describing the probabilities in the randomized method or the greedy choice strategy in the Gauss-Southwell-type methods. We identify those choices which make our convergence bounds best possible.

One result is that the best convergence bounds that we obtain for the expected values in the randomized algorithm are as good as the best for the deterministic, but more costly algorithms of Gauss-Southwell type. We use these new results to show a provable convergence rate for asynchronous iterations. (Joint work with Andreas Frommer.)

Event page

Apr162026

On principal component regression in high dimension

Elad Romanov · Yale University

1:30 PM · Fine Hall 224

Abstract

Principal component regression (PCR) is a classical two-step approach to linear regression, where one first reduces the data dimension by projecting onto its leading principal components, and then performs ordinary least squares regression. We study PCR in an asymptotic high-dimensional regression setting, where the number of data points is proportional to the dimension. Our main deliverables are asymptotically exact limiting formulas for the estimation and prediction risks, which depend in a nuanced way on the eigenvalues of the population covariance, the alignment between the population principal components and the true signal, and the number of selected components.

A key challenge in the high-dimensional regime is that the sample covariance matrix is an inconsistent estimate of its population counterpart, and thus sample principal components may fail to capture potential latent low-dimensional structure in the data. We demonstrate this point through several case studies, including that of a spiked covariance matrix. The analysis of (random design) linear regression in high dimension typically builds on powerful results from random matrix theory, such as the Marchenko–Pastur law and deterministic equivalents for the resolvent of a sample covariance matrix. However, these standard tools alone are not sufficient for analyzing the prediction risk of PCR. To that end, we leverage and develop somewhat less standard techniques, which, to our knowledge, have not seen wide use in the statistics literature to date: multi-resolvent traces and their associated eigenvector overlap measures.

Event page

Apr232026

Towards PCA without the SVD: Lanczos-based spike detection

Tom Trogdon · University of Washington

1:30 PM · Fine Hall 224

Abstract

This talk will give an overview of the study of algorithms on random data, and in particular, algorithms from numerical linear algebra (NLA) on random matrices. The combination of ideas from numerical linear algebra and random matrices goes back, at least, to the seminal work of Goldstine and von Neumann. The works of Trotter, Silverstein, Edelman, Dumitriu & Edelman, Pfrang, Deift & Menon, and many others, developed these ideas further. A core subset of NLA algorithms, the Krylov subspace methods, play particularly well with existing random matrix theory. Through the study of random orthogonal polynomials, as perturbations of deterministic orthogonal polynomials, the concentration phenomenon in these methods can be explained using local laws from random matrix theory. We will use these ideas, and methods, to efficiently and robustly perform spike detection in the spiked sample covariance model, and move towards PCA without the SVD.

Event page

Apr302026

Euclidean distance deflation under high-dimensional heteroskedastic noise

Boris Landa · Yale University

2:00 PM · Fine Hall 224

Abstract

Pairwise Euclidean distances are a basic ingredient in many machine learning and data analysis methods. In many applications, however, these distances are distorted by heteroskedastic noise, where different observations are corrupted at different noise levels. This can substantially distort the geometry of the data and complicate downstream tasks that rely on accurate distance information. In this talk, I will discuss the problem of recovering meaningful pairwise distances under high-dimensional heteroskedastic noise. I will describe a principled approach for estimating observation-specific noise levels and correcting the distorted distances with theoretical guarantees, without prior knowledge of the underlying clean data structure or noise distribution. I will also highlight simulations and experiments with real single-cell RNA sequencing data that illustrate the effectiveness of our approach. This is joint work with Keyi Li and Yuval Kluger.

Event page

May072026

Manifold reconstruction and the bird vocalization problem

Nan Wu · UT Dallas

2:00 PM · Fine Hall 224

Abstract

It is often of interest to infer lower-dimensional structures underlying complex data. Riemannian manifolds are commonly used to model such nonlinear lower-dimensional structures. However, most nonlinear dimension reduction algorithms focus on producing lower-dimensional coordinates of the data, without explicitly estimating the underlying manifold or using the manifold structure to denoise the original observations.

In this talk, I will introduce a manifold reconstruction methodology designed to address these limitations. The approach operates under general assumptions on noisy data and allows interpolation of the estimated manifold between observed data points. The key idea is to transform a global manifold reconstruction problem into a collection of local regression problems, enabling the use of Gaussian processes for probabilistic manifold reconstruction. Applications of the method to studying bird species through their vocalizations, as well as other problems in high-dimensional data analysis, will also be discussed.

Event page