View Item 

Show simple item record

Singular values of Gaussian matrices and permanent estimators

dc.contributor.authorRudelson, Mark
dc.contributor.authorZeitouni, Ofer
dc.date.accessioned2017-06-16T20:16:05Z
dc.date.available2017-06-16T20:16:05Z
dc.date.issued2016-01
dc.identifier.citationRudelson, Mark; Zeitouni, Ofer (2016). "Singular values of Gaussian matrices and permanent estimators." Random Structures & Algorithms 48(1): 183-212.
dc.identifier.issn1042-9832
dc.identifier.issn1098-2418
dc.identifier.urihttps://hdl.handle.net/2027.42/137570
dc.description.abstractWe 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
dc.publisherAmerican Mathematical Society
dc.publisherWiley Periodicals, Inc.
dc.subject.othersingular values
dc.subject.otherrandom matrices
dc.subject.otherperfect matchings
dc.subject.otherpermanents
dc.titleSingular values of Gaussian matrices and permanent estimators
dc.typeArticleen_US
dc.rights.robotsIndexNoFollow
dc.subject.hlbsecondlevelMathematics
dc.subject.hlbtoplevelScience
dc.description.peerreviewedPeer Reviewed
dc.description.bitstreamurlhttps://deepblue.lib.umich.edu/bitstream/2027.42/137570/1/rsa20564.pdf
dc.identifier.doi10.1002/rsa.20564
dc.identifier.sourceRandom Structures & Algorithms
dc.identifier.citedreferenceT. W. Anderson, The integral of a symmetric unimodal function over a symmetric convex set and some probability inequalities, Proc Am Math Soc Vol. 6, ( 1955 ), 170 – 176.
dc.identifier.citedreferenceA. Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Struct Algor 14 ( 1999 ), 29 – 61.
dc.identifier.citedreferenceI. Bezáková, D. Štefankovič, V. V. Vazirani, E. Vigoda, Accelerating simulated annealing for the permanent and combinatorial counting problems, SIAM J Comput 37 ( 2008 ), 1429 – 1454.
dc.identifier.citedreferenceK. P. Costello and V. Vu, Concentration of random determinants and permanent estimators, SIAM J Discrete Math 23 ( 2009 ), 1356 – 1371.
dc.identifier.citedreferenceS. Friedland, B. Rider, and O. Zeitouni, concentration of permanent estimators for certain large matrices, Ann Appl Prob 14 ( 2004 ), 1359 – 1576.
dc.identifier.citedreferenceA. Frieze and M. Jerrum, An analysis of a Monte Carlo algorithm for estimating the permanent, Combinatorica 15 ( 1995 ), 67 – 83.
dc.identifier.citedreferenceC. D. Godsil and I. Gutman, On the matching polynomial of a graph, In: Algebraic methods in graph theory I‐II, L. Lóvasz and V. T. Sós (Editors), Amsterdam, North‐Holland. 1981, pp. 67 – 83.
dc.identifier.citedreferenceN. R. Goodman, Distribution of the determinant of a complex Wishart distributed matrix, Ann Stat 34 ( 1963 ), 178 – 180.
dc.identifier.citedreferenceM. Jerrum, A. Sinclair, and E. Vigoda, A polynomial‐time approximation algorithm for the permanent of a matrix with non‐negative entries, J ACM 51 ( 2004 ), 671 – 697.
dc.identifier.citedreferenceE. Kalfoten and G. Villard, On the complexity of computing determinants, Comput Complex 13 ( 2004 ), 91 – 130.
dc.identifier.citedreferenceN. Karmarkar, R. Karp, R. Lipton, L. Lovász, and M. Luby, A Monte Carlo algorithm for estimating the permanent, SIAM J Comput 22 ( 1993 ), 284 – 293.
dc.identifier.citedreferenceM. Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001.
dc.identifier.citedreferenceN. Linial, A. Samorodnitsky, and A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica 20 ( 2000 ), 545 – 568.
dc.identifier.citedreferenceS. Riemer and C. Schütt, On the expectation of the norm of random matrices with non‐identically distributed entries, Electron J Probab 18 ( 2013 ), 13.
dc.identifier.citedreferenceM. Rudelson and R. Vershynin, The Littlewood‐Offord Problem and invertibility of random matrices, Adv Math 218 ( 2008 ), 600 – 633.
dc.identifier.citedreferenceM. Rudelson and R. Vershynin, The smallest singular value of a random rectangular matrix, Commun Pure Appl Math 62 ( 2009 ), 1707 – 1739.
dc.identifier.citedreferenceS. Szarek, Spaces with large distance to ℓ ∞ n and random matrices, Am J Math 112 ( 1990 ), 899 – 942.
dc.identifier.citedreferenceL. Valiant, The complexity of evaluating the permanent, Theor Comput Sci 8 ( 1979 ), 189 – 201.
dc.identifier.citedreferenceS. S. Wilks, Moment generating operators for determinants of product moments in samples from a normal system, Ann Math 35 ( 1934 ), 312 – 340.
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Name:
rsa20564.pdf
Size:
233.0KB
Format:
PDF
View/Open

Show simple item record

Remediation of Harmful Language

The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.

Accessibility

If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.