Singular values of Gaussian matrices and permanent estimators

DOI10.1002/rsa.20564zbMath1362.15028arXiv1301.6268OpenAlexW1981026751WikidataQ128213489 ScholiaQ128213489MaRDI QIDQ3467585

Ofer Zeitouni, M. V. Rudel'son

Publication date: 3 February 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.6268

zbMATH Keywords

random matricesspectrumpermanentssingular valuesperfect matchingsGaussian matricesBarvinok-Godsil-Gutman estimator

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Inequalities involving eigenvalues and eigenvectors (15A42) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52)

Related Items

On the Expectation of Operator Norms of Random Matrices, A general law of large permanent, Lower bounds for the smallest singular value of structured random matrices, Hafnians, perfect matchings and Gaussian matrices, Matrix concentration inequalities and free probability, Quantitative invertibility of non-Hermitian random matrices, The circular law for random regular digraphs with random edge weights, Circular law for the sum of random permutation matrices, Non-Hermitian random matrices with a variance profile. I: Deterministic equivalents and limiting esds, The circular law for random regular digraphs

Cites Work

• Unnamed Item
• On the expectation of the norm of random matrices with non-identically distributed entries
• The complexity of computing the permanent
• Moment-generating operators for determinants of product moments in samples from a normal system
• An analysis of Monte Carlo algorithm for estimating the permanent
• Concentration of permanent estimators for certain large matrices.
• The Littlewood-Offord problem and invertibility of random matrices
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• The Integral of a Symmetric Unimodal Function over a Symmetric Convex Set and Some Probability Inequalities
• Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
• Concentration of Random Determinants and Permanent Estimators
• Smallest singular value of a random rectangular matrix
• Spaces with Large Distance to ℓ n ∞ and Random Matrices
• A Monte-Carlo Algorithm for Estimating the Permanent
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• The Distribution of the Determinant of a Complex Wishart Distributed Matrix
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents