Singular values of Gaussian matrices and permanent estimators

DOI10.1002/RSA.20564MaRDI QIDQ3467585zbMATH OpenOpenAlexWikidataFDO

Authors Ofer Zeitouni, Mark Rudelson

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, http://hdl.handle.net/2027.42/137570

zbMATH Keywords

singular valuesperfect matchingsrandom matricesspectrumpermanentsGaussian matricesBarvinok-Godsil-Gutman estimator

Mathematics Subject Classification ID

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

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.

Recommendations

• Concentration of random determinants and permanent estimators
• Approximating the permanent: A simple approach
• Hafnians, perfect matchings and Gaussian matrices
• Concentration of permanent estimators for certain large matrices.
• An analysis of Monte Carlo algorithm for estimating the permanent

Cites work

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

Cited in

(17)

• Circular law for the sum of random permutation matrices
• The circular law for random regular digraphs with random edge weights
• Concentration of random determinants and permanent estimators
• A general law of large permanent
• Asymptotic geometric analysis: achievements and perspective
• Non-Hermitian random matrices with a variance profile. I: Deterministic equivalents and limiting esds
• Hafnians, perfect matchings and Gaussian matrices
• The circular law for random regular digraphs
• Lower bounds for the smallest singular value of structured random matrices
• On the singular values of Gaussian random matrices
• On the expectation of operator norms of random matrices
• Non-asymptotic results for singular values of Gaussian matrix products
• Universality and sharp matrix concentration inequalities
• Estimation for matrix singular values
• A singular woodbury and pseudo-determinant matrix identities and application to Gaussian process regression
• Matrix concentration inequalities and free probability
• Quantitative invertibility of non-Hermitian random matrices

This page was built for publication: Singular values of Gaussian matrices and permanent estimators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3467585)