Premium
Singular values of Gaussian matrices and permanent estimators
Author(s) -
Rudelson Mark,
Zeitouni Ofer
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20564
Subject(s) - estimator , gaussian , mathematics , social connectedness , class (philosophy) , measure (data warehouse) , singular value , random matrix , exponential function , statistics , pure mathematics , statistical physics , mathematical analysis , eigenvalues and eigenvectors , computer science , physics , quantum mechanics , psychology , database , artificial intelligence , psychotherapist
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