Reception and Poster Session

Apoorv Vikram Singh (New York University)

Title: Algorithms and Lower Bounds for Spectral Density Estimation

Description: I will present the problem of estimating the uniform distribution over eigenvalues of graph (normalized) adjacency matrix. I will also present algorithms and lower bounds for the problem under different query access model (random walk access to graph, and mat-vec access to the adjacency matrix).

Chris Camaño (Caltech)

Title: Faster Linear Algebra Algorithms with Structured Random Matrices

Description: To achieve the greatest possible speed, practitioners regularly implement randomized algorithms for low-rank approximation and least-squares regression with structured dimension reduction maps. Despite significant research effort, basic questions remain about the design and analysis of randomized linear algebra algorithms that employ structured random matrices.

This poster presents a new theoretical framework for studying structured random matrices, and details various algorithm acceleration techniques based on sketching with random matrices possessing sparse or tensor product structure.

Daniel Appelö (Virginia Tech)

Title: EigenWave: An Optimal O(N) Method for Computing Eigenvalues and Eigenvectors by Time-Filtering the Wave Equation

Description: An algorithm named EigenWave is described to compute eigenvalues and eigenvectors of elliptic boundary value problems. The algorithm, based on the recently developed WaveHoltz scheme, solves a related time-dependent wave equation as part of an iteration. At each iteration, the solution to the wave equation is filtered in time. As the iteration progresses, the filtered solution generally contains relatively larger and larger proportions of eigenmodes whose eigenvalues are near a chosen target frequency (target eigenvalue). The ability to choose an arbitrary target frequency enables the computation of eigenvalues anywhere in the spectrum, without the need to invert an indefinite matrix, as is common with other approaches. Furthermore, the iteration can be embedded within a matrix-free Arnoldi algorithm, which enables the efficient computation of multiple eigenpairs near the target frequency. For efficiency, the time-dependent wave equation can be solved with implicit time-stepping and only about 10 time-steps per-period are needed, independent of the mesh spacing. When the (definite) implicit time-stepping equations are solved with a multigrid algorithm, the cost of the resulting EigenWave scheme scales linearly with the number of grid points N as the mesh is refined, giving an optimal O(N) algorithm. The approach is demonstrated by finding eigenpairs of the Laplacian in complex geometry using overset grids. Results in two and three space dimensions are presented using second-order and fourth-order accurate approximations.  

David Persson (NYU & Flatiron Institute)

Title: Quasi-optimal hierarchically semi-separable matrix approximation

Description: We present a randomized algorithm for producing a quasi-optimal hierarchically semi-separable (HSS) approximation to an $N\times N$ matrix $\bm{A}$ using only matrix-vector products with $\bm A$ and $\bm A^\T$. We prove that, using $O(k \log(N/k))$ matrix-vector products and ${O}(N k^2 \log(N/k))$ additional runtime, the algorithm returns an HSS matrix $\bm{B}$ with rank-$k$ blocks whose expected Frobenius norm error $\mathbb{E}[\|\bm{A} - \bm{B}\|_\F^2]$ is at most $O(\log(N/k))$ times worse than the best possible approximation error by an HSS rank-$k$ matrix. In fact, the algorithm we analyze in a simple modification of an empirically effective method proposed by [Levitt \& Martinsson, SISC 2024]. As a stepping stone towards our main result, we prove two results that are of independent interest: a similar guarantee for a variant of the algorithm which accesses $\bm{A}$'s entries directly, and explicit error bounds for near-optimal subspace approximation using \textit{projection-cost-preserving sketches}. To the best of our knowledge, our analysis constitutes the first polynomial-time quasi-optimality result for HSS matrix approximation, both in the explicit access model and the matrix-vector product query model.

Feyza Duman Keles (New York University)

Title: Fixed-sparsity matrix approximation from matrix-vector products

Description: We will study the problem of approximating a matrix A with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when A is accessed only by matrix-vector products. We describe a simple randomized algorithm that returns an approximation with the given sparsity pattern with Frobenius-norm error at most (1+eps) times the best possible error. When each row of the desired sparsity pattern has at most s nonzero entries, this algorithm requires O(s/eps) non-adaptive matrix-vector products with A. We also prove a matching lower-bound, showing that, for any sparsity pattern with O(s) non-zeros per row and column, any algorithm achieving (1+eps) approximation requires s/eps matrix-vector products in the worst case. We thus resolve the matrix-vector product query complexity of the problem up to constant factors, even for the well-studied case of diagonal approximation, for which no previous lower bounds were known.

Jackie Lok (Princeton University)

Title: Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations

Description: The poster will describe a subspace-constrained randomized coordinate descent (SC-RCD) method for solving positive semidefinite linear systems, in which the dynamics of the classical randomized coordinate descent method are restricted to an affine subspace corresponding to a column Nyström approximation, efficiently computed using an algorithm such as the recently proposed RPCholesky algorithm. The convergence rate of the method is unaffected by large spectral outliers, making it an effective and memory-efficient solver for large-scale, dense linear systems with rapidly decaying spectra, such as those encountered in kernel ridge regression. The theoretical results are derived by developing a more general subspace-constrained framework for the sketch-and-project method, and provides a flexible, implicit preconditioning strategy for a variety of iterative solvers, which may be of independent interest.

Maryam Dehghan (University of Illinois at Urbana-Champaign)

Title: Solving BGK Equation with Low-Rank Tensor Decomposition and Collocation Method

Description: This work develops an explicit time-stepping scheme for the BGK (Bhatnagar-Gross-Krook) equation, by combining low-rank tensor decompositions and the collocation method at Chebyshev points to advance the solution efficiently in high dimensions. The main idea of the proposed method is to represent the distribution function f as a sum of separable basis functions but not exactly in spatial and velocity spaces. The proposed low-rank form of f is different from existing methods in the literature.

Noah Amsel (New York University)

Title: The Polar Express: Optimal Matrix Sign Methods for GPUs

Description: Computing the polar decomposition and the related matrix sign function, has been a well-studied problem in numerical analysis for decades. More recently, it has emerged as an important subroutine in deep learning, particularly within the Muon optimization framework. However, the requirements in this setting differ significantly from those of traditional numerical analysis. In deep learning, methods must be highly efficient and GPU-compatible, but high accuracy is often unnecessary. As a result, classical algorithms like Newton-Schulz (which suffers from slow initial convergence) and methods based on rational functions (which rely on QR decompositions or matrix inverses) are poorly suited to this context. In this work, we introduce Polar Express, a GPU-friendly algorithm for computing the polar decomposition. Like classical polynomial methods such as Newton-Schulz, our approach uses only matrix-matrix multiplications, making it GPU-compatible. Motivated by earlier work of Chen & Chow and Nakatsukasa & Freund, Polar Express adapts the polynomial update rule at each iteration by solving a minimax optimization problem, and we prove that it enjoys a strong worst-case optimality guarantee. This property ensures both rapid early convergence and fast asymptotic convergence. We also address finite-precision issues, making it stable in bfloat16 in practice. We apply Polar Express within the Muon optimization framework and show consistent improvements in validation loss on large-scale models such as GPT-2, outperforming recent alternatives across a range of learning rates.

Phuc Tran (Yale University)

Title: Perturbation of eigenspaces: Beyond Davis-Kahan Theorem: Better bound with weaker gap condition.

Description: We study the perturbation of leading eigenspaces of a symmetric matrix $A$ under additive noise $\tilde{A}=A+E$. The classical Davis–Kahan theorem provides worst-case bounds that are elegant but often loose in modern applications, where A is typically low rank and E is (pseudo)random. We go beyond Davis–Kahan by exploiting the skewness between the signal and noise eigenspaces. Using contour integration combined with combinatorial ideas, we develop a new framework that delivers sharper perturbation bounds with broad applicability.

Pratyush Avi (New York University)

Title: Query Efficient Structured Matrix Learning

Description:  We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix A given access to matrix-vector product (matvec) queries of the form x \rightarrow Ax and x \rightarrow A^Tx. This problem is of central importance to algorithms across scientific computing and machine learning, with applications to fast multiplication and inversion for structured matrices, building preconditioners for first-order optimization, and as a model for differential operator learning. Prior work focuses on obtaining query complexity upper and lower bounds for learning specific structured matrix families that commonly arise in applications.We initiate the study of the problem in greater generality, aiming to understand the query complexity of learning approximations from general matrix families. Our main result focuses on finding a near-optimal approximation to A from any finite-sized family of matrices, \mathcal{F}. Standard results from matrix sketching show that O(\log|\mathcal{F}|) matvec queries suffice in this setting. This bound can also be achieved, and is optimal, for vector-matrix-vector queries of the form x,y\rightarrow x^TAy, which have been widely studied in work on rank-1 matrix sensing.
Surprisingly, we show that, in the matvec model, it is possible to obtain a nearly quadratic improvement in complexity, to \tilde{O}(\sqrt{\log|\mathcal{F}|}). Further, we prove that this bound is tight up to log-log factrs. Via covering number arguments, our result extends to well-studied infinite families. As an example, we establish that a near-optimal approximation from any \emph{linear matrix family} of dimension q can be learned with \tilde{O}(\sqrt{q}) matvec queries, improving on an O(q) bound achievable via sketching techniques and vector-matrix-vector queries.

Rajarshi Bhattacharjee (University of Massachusetts Amherst)

Title: Near-optimal Spectral Density Estimation via Explicit and Implicit Deflation

Description: We study algorithms for approximating the spectral density of a symmetric matrix that is accessed through matrix-vector product queries. By combining a previously studied Chebyshev polynomial moment matching method with a deflation step that approximately projects off the largest magnitude eigendirections, we give an algorithm which can approximate the spectral density up to some specified error in the Wasserstein-1 metric using nearly optimal (up to logarithmic factors) number of matvces. In the common case when the matrix exhibits fast singular value decay, our bound can be much stronger than prior work.

We further show that the popular Stochastic Lanczos Quadrature (SLQ) method matches the above bound, even though SLQ itself is parameter-free and performs no explicit deflation. This bound explains the strong practical performance of SLQ, and motivates a simple variant of SLQ that achieves an even tighter error bound.

Raphael Meyer (UC Berkeley)

Title: Debiasing Polynomial and Fourier Regression

Description: We study the problem of approximating an unknown function f: R -> R by a degree-d polynomial using as few function evaluations as possible, where error is measured with respect to a probability distribution μ. Existing randomized algorithms achieve near-optimal sample complexities to recover a (1+ε)-optimal polynomial but produce biased estimates of the best polynomial approximation, which is undesirable.

We propose a simple debiasing method based on a connection between polynomial regression and random matrix theory. Our method involves evaluating f(λ_1),\ldots,f(λ_{d+1}) where λ_1,...,λ_{d+1} are the eigenvalues of a suitably designed random complex matrix tailored to the distribution μ. Our estimator is unbiased, has near-optimal sample complexity, and experimentally outperforms iid leverage score sampling.

Additionally, our techniques enable us to debias existing methods for approximating a periodic function with a truncated Fourier series with near-optimal sample complexity.

Rupei Xu (The University of Texas at Dallas)

Title: Clifford Max-Linear Systems: Beyond Fermat, Snell and Hamilton

Description: For centuries, the physical behavior of waves at interfaces has been governed by classical principles — Fermat’s least-time rule, Snell’s law of refraction, and Hamilton’s geometrical optics. Yet the rise of programmable electromagnetic surfaces, such as Reconfigurable Intelligent Surfaces, demands a fundamentally new framework: one that transcends scalar paths and angles, and captures the full multigrade structure of electromagnetic fields.

This paper introduces the Clifford Max-Linear System as the central foundation for programmable wave–interface interaction. In contrast to the minimization of path length in Fermat’s principle, the Clifford Max-Linear System formulates wave control as a maximization of grade-wise alignment between incident and target fields. Structured interference, multigrade synthesis, and entropy-aware optimization emerge naturally within this max-linear framework, establishing a new paradigm for field manipulation.

Building on this foundation, we develop two key principles: the Clifford Alignment Principle, which formalizes rotor-based optimization across Clifford grades and extends polarization into multigrade control, and the Clifford Generalized Interface Law, which reformulates reflection and transmission as grade-specific rotor transformations — a direct generalization of Snell’s law into the multivector domain.

Together, these contributions unify and extend classical optics and modern field control, completing the historical arc from Fermat, Snell, and Hamilton to a new era of programmable electromagnetic geometry governed by Clifford max-linear dynamics.

Yifu Wang (University of Chicago)

Title: Minimizing the Arithmetic and Communication Complexity of Jacobi’s Method for Eigenvalues and Singular Values

Description: Jacobi’s method is a classical iterative algorithm for computing eigenvalues and eigenvectors of symmetric matrices, notable for its simplicity, high accuracy, and natural suitability for parallelism. This poster presents rigorous complexity bounds for several Jacobi variants—scalar, blocked, recursive, and parallel. We introduce a recursive scheme with LU-based fast pivoting that guarantees convergence while approaching the optimal complexity of fast matrix multiplication. The results are further extended to singular value decomposition, yielding various bounds via applying the Jacobi methods we introduced. We also provide detailed descriptions and pseudocode for 2D parallel Jacobi, with complexity bounds analyzed under the alpha-beta-gamma model. Numerical experiments confirm convergence and robustness, and open questions point toward achieving scalar Jacobi's high accuracy under the blocked or recursive framework and more efficient parallelism.

Yingda Cheng (Virginia Tech)

Title: Anderson acceleration in Tucker tensor format

Description: We present two algorithms: a new cross approximation for Tucker tensor and Tucker-Anderson acceleration. We show applications of methods in solving PDE problems in 3D+.

Zhanrui Zhang (University of Illinois at Urbana-Champaign)

Title: Rank Reduction Method for CP Tensor Decomposition with Pivoted Cholesky Decomposition
Description: The Canonical Polyadic (CP) decomposition is widely used to represent high-dimensional data in many applications, for example, solving high-dimensional PDEs like kinetic equations. A key challenge in these problems is the efficient estimation and reduction of the CP rank. The CP rank reduction task can be formulated as approximating the Khatri–Rao product of the CP factor matrices with a lower rank. We propose an approach based on the pivoted Cholesky decomposition to construct interpolative decompositions of the Khatri–Rao product. This method can serve as a standalone CP rank reduction technique or be integrated into classical optimization schemes such as CP-ALS. Moreover, the residuals produced at each step of the pivoted Cholesky naturally provide error indicators, enabling effective rank estimation. Preliminary numerical results demonstrate that this method achieves a balance between computational cost and approximation accuracy. Its effectiveness is further validated through applications to the Vlasov–Poisson equation.