Singular values of Gaussian matrices and permanent estimators
dc.contributor.author | Rudelson, Mark | |
dc.contributor.author | Zeitouni, Ofer | |
dc.date.accessioned | 2017-06-16T20:16:05Z | |
dc.date.available | 2017-06-16T20:16:05Z | |
dc.date.issued | 2016-01 | |
dc.identifier.citation | Rudelson, Mark; Zeitouni, Ofer (2016). "Singular values of Gaussian matrices and permanent estimators." Random Structures & Algorithms 48(1): 183-212. | |
dc.identifier.issn | 1042-9832 | |
dc.identifier.issn | 1098-2418 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/137570 | |
dc.description.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 | |
dc.publisher | American Mathematical Society | |
dc.publisher | Wiley Periodicals, Inc. | |
dc.subject.other | singular values | |
dc.subject.other | random matrices | |
dc.subject.other | perfect matchings | |
dc.subject.other | permanents | |
dc.title | Singular values of Gaussian matrices and permanent estimators | |
dc.type | Article | en_US |
dc.rights.robots | IndexNoFollow | |
dc.subject.hlbsecondlevel | Mathematics | |
dc.subject.hlbtoplevel | Science | |
dc.description.peerreviewed | Peer Reviewed | |
dc.description.bitstreamurl | https://deepblue.lib.umich.edu/bitstream/2027.42/137570/1/rsa20564.pdf | |
dc.identifier.doi | 10.1002/rsa.20564 | |
dc.identifier.source | Random Structures & Algorithms | |
dc.identifier.citedreference | T. 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.citedreference | A. Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Struct Algor 14 ( 1999 ), 29 – 61. | |
dc.identifier.citedreference | I. 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.citedreference | K. P. Costello and V. Vu, Concentration of random determinants and permanent estimators, SIAM J Discrete Math 23 ( 2009 ), 1356 – 1371. | |
dc.identifier.citedreference | S. Friedland, B. Rider, and O. Zeitouni, concentration of permanent estimators for certain large matrices, Ann Appl Prob 14 ( 2004 ), 1359 – 1576. | |
dc.identifier.citedreference | A. Frieze and M. Jerrum, An analysis of a Monte Carlo algorithm for estimating the permanent, Combinatorica 15 ( 1995 ), 67 – 83. | |
dc.identifier.citedreference | C. 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.citedreference | N. R. Goodman, Distribution of the determinant of a complex Wishart distributed matrix, Ann Stat 34 ( 1963 ), 178 – 180. | |
dc.identifier.citedreference | M. 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.citedreference | E. Kalfoten and G. Villard, On the complexity of computing determinants, Comput Complex 13 ( 2004 ), 91 – 130. | |
dc.identifier.citedreference | N. 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.citedreference | M. Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. | |
dc.identifier.citedreference | N. Linial, A. Samorodnitsky, and A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica 20 ( 2000 ), 545 – 568. | |
dc.identifier.citedreference | S. 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.citedreference | M. Rudelson and R. Vershynin, The Littlewood‐Offord Problem and invertibility of random matrices, Adv Math 218 ( 2008 ), 600 – 633. | |
dc.identifier.citedreference | M. Rudelson and R. Vershynin, The smallest singular value of a random rectangular matrix, Commun Pure Appl Math 62 ( 2009 ), 1707 – 1739. | |
dc.identifier.citedreference | S. Szarek, Spaces with large distance to ℓ ∞ n and random matrices, Am J Math 112 ( 1990 ), 899 – 942. | |
dc.identifier.citedreference | L. Valiant, The complexity of evaluating the permanent, Theor Comput Sci 8 ( 1979 ), 189 – 201. | |
dc.identifier.citedreference | S. S. Wilks, Moment generating operators for determinants of product moments in samples from a normal system, Ann Math 35 ( 1934 ), 312 – 340. | |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
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.