Singular Values of Gaussian Matrices and Permanent Estimators

被引:10
作者
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
基金
以色列科学基金会; 美国国家科学基金会;
关键词
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
    Townsend, Alex
    Wilber, Heather
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2018, 548 : 19 - 41
  • [22] Note on small singular values of sequences of matrices
    Ashyralyyev, Charyyar
    Cakir, Zafer
    INTERNATIONAL CONFERENCE ON ANALYSIS AND APPLIED MATHEMATICS (ICAAM 2014), 2014, 1611 : 167 - 171
  • [23] Bounds on the Singular Values of Matrices with Displacement Structure
    Beckermann, Bernhard
    Townsend, Alex
    SIAM REVIEW, 2019, 61 (02) : 319 - 344
  • [24] RANDOM MATRICES: THE DISTRIBUTION OF THE SMALLEST SINGULAR VALUES
    Tao, Terence
    Vu, Van
    GEOMETRIC AND FUNCTIONAL ANALYSIS, 2010, 20 (01) : 260 - 297
  • [25] Singular values of differences of positive semidefinite matrices
    Zhan, XZ
    SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2000, 22 (03) : 819 - 823
  • [26] A remark on the smallest singular value of powers of Gaussian matrices
    Huang, Han
    Tikhomirov, Konstantin
    ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2020, 25
  • [27] Non-asymptotic Theory of Random Matrices: Extreme Singular Values
    Rudelson, Mark
    Vershynin, Roman
    PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS, VOL III: INVITED LECTURES, 2010, : 1576 - 1602
  • [28] The singular values of the GOE
    Bornemann, Folkmar
    La Croix, Michael
    RANDOM MATRICES-THEORY AND APPLICATIONS, 2015, 4 (02)
  • [29] Accurate singular values of a class of parameterized negative matrices
    Huang, Rong
    Xue, Jungong
    ADVANCES IN COMPUTATIONAL MATHEMATICS, 2021, 47 (05)
  • [30] A note on singular values of Cauchy-Toeplitz matrices
    Roch, S
    Silbermann, B
    LINEAR ALGEBRA AND ITS APPLICATIONS, 1998, 276 : 531 - 536