Singular values of Gaussian matrices and permanent estimators

2013/01/26 by Mark Rudelson, Rudelson, Mark, Ofer Zeitouni +1 · 3 citations
Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.1301.6268

openalex publication_date 2013/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present estimates on the small singular values of a class of matrices with independent Gaussian entries and inhomogeneous variance profile, satisfying a broad-connectedness condition. Using these estimates and concentration of measure for the spectrum of Gaussian matrices with independent entries, we prove that for a large class of graphs satisfying an appropriate expansion property, the Barvinok--Godsil-Gutman estimator for the permanent achieves sub-exponential errors with high probability.

Citations

• The Distribution of the Determinant of a Complex Wishart Distributed Matrix

Cited by

• A structural bound for cluster robustness of randomized small-block Lanczos
• Invertibility for non-Hermitian and symmetric random band matrices with sublinear bandwidth and discrete entries
• On the rank of a random symmetric matrix in the large deviation regime

Related

• Concentration of permanent estimators for certain large matrices
• Universality and sharp matrix concentration inequalities
• Fundamental Limits of Low-Rank Matrix Estimation with Diverging Aspect Ratios
• On the Smallest Eigenvalue of General correlated Gaussian Matrices
• Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising