Singular values of Gaussian matrices and permanent estimators1. Issue 1 (30th July 2014)

• Record Type: Journal Article
• Authors: Rudelson, Mark; Zeitouni, Ofer
• Is Part Of: Random structures & algorithms. Volume 48:Issue 1(2016)
• Page Start: 183
• Page End: 212
• Publication Date: 2014-07-30
• Subjects: permanents -- singular values -- random matrices -- perfect matchings; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20564
• Languages: English
• ISSNs: 1042-9832

Abstract

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