Singular Values of Gaussian Matrices and Permanent Estimators

被引：11
作者：
Rudelson, Mark [1 ]
Zeitouni, Ofer [2 ,3 ]
机构：
[1] Univ Michigan, Dept Math, Ann Arbor, MI 48109 USA
[2] Weizmann Inst Sci, Fac Math & Comp Sci, IL-7610001 Rehovot, Israel
[3] NYU, Courant Inst Math Sci, New York, NY 10012 USA
来源：
RANDOM STRUCTURES & ALGORITHMS | 2016年 / 48卷 / 01期
基金：
美国国家科学基金会; 以色列科学基金会;
关键词：
permanents; singular values; random matrices; perfect matchings; MONTE-CARLO ALGORITHM; DETERMINANTS;
D O I：
10.1002/rsa.20564
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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. (c) 2014 Wiley Periodicals, Inc.
引用
收藏
页码：183 / 212
页数：30
相关论文
共 50 条
[21]   On the singular values of matrices with high displacement rank [J].
Townsend, Alex ;
Wilber, Heather .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2018, 548 :19-41
[22]   Bounds on the Singular Values of Matrices with Displacement Structure [J].
Beckermann, Bernhard ;
Townsend, Alex .
SIAM REVIEW, 2019, 61 (02) :319-344
[23]   RANDOM MATRICES: THE DISTRIBUTION OF THE SMALLEST SINGULAR VALUES [J].
Tao, Terence ;
Vu, Van .
GEOMETRIC AND FUNCTIONAL ANALYSIS, 2010, 20 (01) :260-297
[24]   Note on small singular values of sequences of matrices [J].
Ashyralyyev, Charyyar ;
Cakir, Zafer .
INTERNATIONAL CONFERENCE ON ANALYSIS AND APPLIED MATHEMATICS (ICAAM 2014), 2014, 1611 :167-171
[25]   Singular values of differences of positive semidefinite matrices [J].
Zhan, XZ .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2000, 22 (03) :819-823
[26]   Non-asymptotic Theory of Random Matrices: Extreme Singular Values [J].
Rudelson, Mark ;
Vershynin, Roman .
PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS, VOL III: INVITED LECTURES, 2010, :1576-1602
[27]   A remark on the smallest singular value of powers of Gaussian matrices [J].
Huang, Han ;
Tikhomirov, Konstantin .
ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2020, 25
[28]   The singular values of the GOE [J].
Bornemann, Folkmar ;
La Croix, Michael .
RANDOM MATRICES-THEORY AND APPLICATIONS, 2015, 4 (02)
[29]   Accurate singular values of a class of parameterized negative matrices [J].
Huang, Rong ;
Xue, Jungong .
ADVANCES IN COMPUTATIONAL MATHEMATICS, 2021, 47 (05)
[30]   A note on singular values of Cauchy-Toeplitz matrices [J].
Roch, S ;
Silbermann, B .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1998, 276 :531-536
12345