# Singular values of Gaussian matrices and permanent estimators

arXiv: https://arxiv.org/abs/1301.6268 · HTML: https://mlsanity.com/paper/1301.6268/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2013.

## Built on by (most cited first, 2 of 2)

- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)
- [Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers](https://mlsanity.com/paper/2409.04320/) (2024)

## Abstract (arXiv)

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.