Random Matrices and Applications
23 papers on this topic
Bias for the Trace of the Resolvent and Its Application on Non-Gaussian and Non-centered MIMO Channels
The mutual information (MI) of Gaussian multi-input multi-output (MIMO) channels has been evaluated by utilizing random matrix theory (RMT) and shown to asymptotically follow Gaussian...
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
We study efficient algorithms for Sparse PCA in standard statistical models (spiked covariance in its Wishart form). Our goal is to achieve optimal recovery guarantees while being resilient to...
Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
Generalized linear models (GLMs) arise in high-dimensional machine learning, statistics, communications and signal processing. In this paper we analyze GLMs when the data matrix is random, as...
Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles
This paper proposes a new algorithm, named Householder Dice (HD), for simulating dynamics on dense random matrix ensembles with translation-invariant properties. Examples include the Gaussian...
Gradient flow in the gaussian covariate model: exact solution of learning curves and multiple descent structures
A recent line of work has shown remarkable behaviors of the generalization error curves in simple learning models. Even the least-squares regression has shown atypical features such as the...
Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated...
Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable...
Statistical Optimal Transport via Factored Couplings
We propose a new method to estimate Wasserstein distances and optimal transport plans between two probability distributions from samples in high dimension. Unlike plug-in rules that simply replace...
The adaptive interpolation method: A simple scheme to prove replica formulas in Bayesian inference
In recent years important progress has been achieved towards proving the validity of the replica predictions for the (asymptotic) mutual information (or "free energy") in Bayesian inference...
The Geometry of Community Detection via the MMSE Matrix
The information-theoretic limits of community detection have been studied extensively for network models with high levels of symmetry or homogeneity. The contribution of this paper is to study a...
Understanding Phase Transitions via Mutual Information and MMSE
The ability to understand and solve high-dimensional inference problems is essential for modern data science. This article examines high-dimensional inference problems through the lens of...
Hypothesis testing with low-degree polynomials in the Morris class of exponential families
Analysis of low-degree polynomial algorithms is a powerful, newly-popular method for predicting computational thresholds in hypothesis testing problems. One limitation of current techniques for...
Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits
Over the past few years, insights from computer science, statistical physics, and information theory have revealed phase transitions in a wide array of high-dimensional statistical problems at two...
The Layered Structure of Tensor Estimation and its Mutual Information
We consider rank-one non-symmetric tensor estimation and derive simple formulas for the mutual information. We start by the order 2 problem, namely matrix factorization. We treat it completely in...
Expectation Propagation for Approximate Inference: Free Probability Framework
We study asymptotic properties of expectation propagation (EP) -- a method for approximate inference originally developed in the field of machine learning. Applied to generalized linear models, EP...
An $\ell_p$ theory of PCA and spectral clustering
Principal Component Analysis (PCA) is a powerful tool in statistics and machine learning. While existing study of PCA focuses on the recovery of principal components and their associated...
Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
Many problems in statistics and machine learning require the reconstruction of a rank-one signal matrix from noisy data. Enforcing additional prior information on the rank-one component is often...
A likelihood-ratio type test for stochastic block models with bounded degrees
A fundamental problem in network data analysis is to test Erd\"{o}s-R\'{e}nyi model $\mathcal{G}\left(n,\frac{a+b}{2n}\right)$ versus a bisection stochastic block model...