Distance theorems and the smallest singular value of random matrices

Speaker: 

Manuel Fernandez

Institution: 

USC

Time: 

Monday, November 10, 2025 - 2:00pm to 3:00pm

Location: 

340P Rowland Hall

In recent years, significant progress has been made in our understanding of the quantitative behavior of random matrices. One research direction of continued interest has been the estimation of the smallest singular value. A measurement of matrix’s ``invertibility’’, quantitative bounds on the smallest singular value are important for a variety of tasks including establishing a circular law for a non-Hermitian random matrix and for proving stability of numerical methods. In view of the universality phenomena of random matrices, one tries to prove these estimates for more general matrix ensembles satisfying weaker assumptions.

In the geometric approach to proving smallest singular value estimates a key ingredient is the use of a 'distance theorem', which is a small ball estimate for the distance between a random vector and subspace. In this talk we will discuss a new distance theorem and its application to proving smallest singular value estimates for inhomogeneous random rectangular matrix with independent entries. We will also discuss how the recent resolution of the Slicing Conjecture, due to Klartag, Lehec, and Guan, implies smallest singular values estimates for a number of log-concave random matrix ensembles. In some cases, independent entries are no longer necessary!

Variational Inference: Posterior Threshold Improves Network Clustering Accuracy in Sparse Regimes

Speaker: 

Can M. Le

Institution: 

UC Davis

Time: 

Monday, November 17, 2025 - 2:00pm to 3:00pm

Location: 

340P Rowland Hall

Variational inference has been widely used in machine learning literature to fit various Bayesian models. In network analysis, this method has been successfully applied to solve community detection problems. Although these results are promising, their theoretical support is limited to relatively dense networks, an assumption that may not hold for real networks. In addition, recent studies have shown that the variational loss surface has many saddle points, which can significantly impact its performance, especially when applied to sparse networks. This paper proposes a simple method to improve the variational inference approach by hard thresholding the posterior of the community assignment after each iteration. We show that the proposed method can accurately recover the true community labels, even when the average node degree of the network is bounded and the initialization is arbitrarily close to random guessing. An extensive numerical study further confirms the advantage of the proposed method over the classical variational inference and other algorithms.

From mixing time of Markov chains to Tracy-Widom law of inhomogeneous random matrices

Speaker: 

Guangyi Zou

Institution: 

UC Irvine

Time: 

Monday, October 13, 2025 - 2:00pm to 3:00pm

Location: 

340P Rowland Hall

Random matrix statistics appear across diverse fields and are now recognized as exhibiting universal behavior. However, even within random matrix theory itself, the mechanism underlying the universality of local eigenvalue statistics beyond the mean-field setting remains poorly understood.

In this talk, we consider symmetric and Hermitian random matrices whose entries are independent random variables with an arbitrary variance pattern. Under a novel Short-to-Long Mixing condition—sharp in the sense that it excludes any deterministic correction at the spectral edge—we establish GOE/GUE edge universality for such inhomogeneous random matrices, which may be sparse or far from the classical mean-field regime. This condition reduces the universality problem to verifying the mixing properties of Markov chains defined by the variance profile matrix. This talk is based on joint work with Dang-Zheng Liu.

Precise Error Rates for Computationally Efficient Testing

Speaker: 

Alex Wein

Institution: 

UC Davis

Time: 

Monday, November 24, 2025 - 2:00pm to 3:00pm

Location: 

340P Rowland Hall

We consider one of the most basic high-dimensional testing problems: that of detecting the presence of a rank-1 "spike" in a random Gaussian (GOE) matrix. When the spike has structure such as sparsity, inherent statistical-computational tradeoffs are expected. I will discuss some precise results about the computational complexity, arguing that the so-called "linear spectral statistics" achieve the best possible tradeoff between type I & II errors among all polynomial-time algorithms, even though an exponential-time algorithm can do better. This is based on https://arxiv.org/abs/2311.00289 with Ankur Moitra which uses a version of the low-degree polynomial heuristic, as well as forthcoming work with Ansh Nagda which gives a stronger form of reduction-based hardness.

Positivity of Schubert coefficients

Speaker: 

Collen Robichaux

Institution: 

UCLA

Time: 

Wednesday, October 8, 2025 - 3:00pm to 4:00pm

Location: 

RH 340P

Schubert coefficients are nonnegative integers that arise in Algebraic Geometry and play a central role in Algebraic Combinatorics. It is a major open problem whether they have a combinatorial interpretation. A related open problem seeks an algorithm to determine when a Schubert coefficient is positive. In this talk we explore this problem and present an algorithmic solution. This is joint work with Igor Pak.

Pages

Subscribe to RSS - Combinatorics and Probability