Linear Algebra seminars

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

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, Diana Halikias, Cameron Musco, and David Persson.

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.

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.

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.

Spectral methods for high-dimensional nearest-neighbor search can perform well in practice even when random projections appear preferable under worst-case theory. This talk studies that difference in a semi-random model: points lie in an unknown low-dimensional subspace and are then perturbed by Gaussian noise in the full ambient space. The algorithms repeatedly compute a leading principal component or subspace and achieve query times polynomial in the ambient dimension and logarithm of the number of points over substantial parameter ranges. They can remain effective when noise is much larger than the distances among the original points. The work is joint with Amirali Abdullah, Ravi Kannan and Robi Krauthgamer.