Linear Algebra 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.

Charles Bordenave revisits von Neumann and Goldstine's proposal to model numerical computing errors as probabilistic noise. This perspective helps explain large errors in computed eigenvalues of badly conditioned matrices. Toeplitz matrices provide a case study: they occur throughout mathematics, physics, and engineering, are highly sensitive to small perturbations, and possess a rich spectral theory that supports precise descriptions under random perturbations. The talk is based on joint work with Mireille Capitaine and François Chapon.

Jeroen Zuiddam examines whether repeated tasks permit economies of scale, focusing on fast matrix multiplication and graph Shannon capacity as unresolved direct-sum problems. The talk introduces Strassen's asymptotic-spectrum duality, originally developed for asymptotic tensor rank and later applied to Shannon capacity and other problems. It then explores approximation by sequences of easier instances: suitable notions of convergence, construction of the sequences, asymptotic-spectrum distance, and approaches using polynomials and algebraic geometry. Based on joint work with David de Boer, Pjotr Buys, Sven Polak, Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer, and Péter Vrana.

Matrix multiplication underpins scientific computing and artificial intelligence, yet practical numerical libraries and hardware accelerators commonly retain the classical cubic-time algorithm despite decades of subcubic theoretical advances. This talk reviews the effort to make faster multiplication algorithms useful in practice. It examines why arithmetic complexity alone does not determine performance: some algorithms require enormous matrices or incur large hidden constants, while communication costs, numerical stability and the match between software and hardware create additional obstacles. The historical perspective connects asymptotic algorithm design to actual performance and power consumption.

Ryann Cartor introduces multivariate public-key cryptography, whose fast and compact post-quantum schemes use polynomial systems over finite fields. The tutorial surveys past and current multivariate cryptosystems before examining MinRank as a central cryptanalytic problem. MinRank attacks have broken prominent schemes in both multivariate and code-based cryptography. The material assumes basic algebra and connects these foundations to current research directions.

Eimear Byrne introduces q-matroids and rank-metric codes as vector-space analogues of classical matroids and Hamming-metric codes. The tutorial compares the connections between codes and matroids with those between rank-metric codes and q-matroids. It develops equivalent definitions of q-matroids, relates them to classical definitions, and explains how q-matroid invariants provide invariants for rank-metric codes.

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.

Felice Manganiello introduces network coding, in which intermediate nodes combine incoming packets algebraically before forwarding them. This can improve communication efficiency, latency, and resilience to packet loss and congestion. The tutorial develops theoretical foundations and practical applications, including linear network coding, multicast communication, and coding across networks.

Youming Qiao develops connections between graphs and linear spaces of matrices. Tutte and Lovász linked graph perfect matchings to full-rank matrices; further correspondences relate independent sets to totally isotropic spaces, connectivity to orthogonal decompositions, and graph isomorphism to matrix-space isomorphism. These connections extend graph-theoretic questions and techniques to matrix spaces, including alternating paths, independence polynomials, Turán and Ramsey problems, expanders, and threshold phenomena. The methods connect to invariant theory, group theory, quantum information, and geometry. Based on joint work with Avi Wigderson, Yuval Wigderson, Gábor Ivanyos, Yinan Li, Chuanqi Zhang, and Markus Bläser.

Networks of excitatory and inhibitory (EI) neurons form a canonical circuit in the brain. Classical theoretical analyses of dynamics in EI networks have revealed key principles such as EI balance or paradoxical responses to external inputs. These seminal results assume that synaptic strengths depend on the type of neurons they connect but are otherwise statistically independent. However, recent synaptic physiology datasets have uncovered connectivity patterns that deviate significantly from independent connection models. Simultaneously, studies of task-trained recurrent networks have emphasized the role of connectivity structure in implementing neural computations. Despite these findings, integrating detailed connectivity structures into mean-field theories of EI networks remains a substantial challenge. In this talk, I will outline a theoretical approach to understanding dynamics in structured EI networks by employing a low-rank approximation based on an analytical computation of the dominant eigenvalues of the full connectivity matrix. I will illustrate this approach by investigating the effects of pair-wise connectivity motifs on linear dynamics in EI networks. Specifically, I will present recent results demonstrating that an over-representation of chain motifs induces a strong positive eigenvalue in inhibition-dominated networks, generating a potential instability that challenges classical EI balance criteria. Furthermore, by examining the effects of external input, we found that chain motifs can, on their own, induce paradoxical responses, wherein an increased input to inhibitory neurons leads to a counterintuitive decrease in their activity through recurrent feedback mechanisms. Altogether, our theoretical approach opens new avenues for relating recorded connectivity structures with dynamics and computations in biological networks. Presented in the van Vreeswijk Theoretical Neuroscience Seminar series (formerly WWTNS) on 2025-01-22. Recording duration: 00:47:27.

Doron Puder studies probability distributions on finite groups obtained by evaluating a free-group word on uniformly random group elements. Earlier work connected such distributions on symmetric groups with the partially ordered set of finitely generated free-group subgroups. The talk introduces free groups and free-group algebras, then develops new connections between word distributions on matrix groups over finite fields and free-group algebras. It compares these findings with the symmetric-group case and presents related conjectures. Joint work with Danielle Ernst-West and Matan Seidel.

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.