Singular values of Gaussian matrices and permanent estimators

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. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 183–212, 2016

Locations

• arXiv (Cornell University) - View - PDF
• CiteSeer X (The Pennsylvania State University) - View - PDF
• Deep Blue (University of Michigan) - View - PDF
• Random Structures and Algorithms - View