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 条

[41] Relating multiway discrepancy and singular values of nonnegative rectangular matrices [J].

Bolla, Marianna .

DISCRETE APPLIED MATHEMATICS, 2016, 203 :26-34

[42] Approximating structured singular values for discrete Fourier transformation matrices [J].

Rehman, Mutti-Ur ;

Mehmood, Arshad .

INTERNATIONAL JOURNAL OF ADVANCED AND APPLIED SCIENCES, 2018, 5 (12) :119-125

[43] Singular values of large non-central random matrices [J].

Bryc, Wlodek ;

Silverstein, Jack W. .

RANDOM MATRICES-THEORY AND APPLICATIONS, 2020, 9 (04)

[44] Approximating structured singular values for Chebyshev spectral differentiation matrices [J].

Rehman, Mutti-Ur ;

Ul Islam, Shams ;

Ali, Sadaqat .

INTERNATIONAL JOURNAL OF ADVANCED AND APPLIED SCIENCES, 2018, 5 (11) :67-74

[45] SINGULAR VALUES AND EIGENVALUES OF MATRICES IN son(C) AND spn(C) [J].

Bozkurt, Durmus ;

Tam, Tin-Yau ;

Yan, Wen .

ANNALS OF FUNCTIONAL ANALYSIS, 2014, 5 (01) :94-100

[46] OPTIMAL CLEANING FOR SINGULAR VALUES OF CROSS-COVARIANCE MATRICES [J].

Benaych-Georges, Florent ;

Bouchaud, Jean-Philippe ;

Potters, Marc .

ANNALS OF APPLIED PROBABILITY, 2023, 33 (02) :1095-1126

[47] Sequences of variable-coefficient Toeplitz matrices and their singular values [J].

Mascarenhas, H. ;

Silbermann, B. .

JOURNAL OF FUNCTIONAL ANALYSIS, 2016, 270 (04) :1479-1500

[48] Implicit Cholesky algorithms for singular values and vectors of triangular matrices [J].

Fernando, KV ;

Parlett, BN .

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, 1995, 2 (06) :507-531

[49] Some research problems on the Hadamard product and singular values of matrices [J].

Zhan, XZ .

LINEAR & MULTILINEAR ALGEBRA, 2000, 47 (02) :191-194

[50] PERTURBATIONS, SINGULAR-VALUES, AND RANKS OF PARTIAL TRIANGULAR MATRICES [J].

RODMAN, L ;

WOERDEMAN, HJ .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1995, 16 (01) :278-288

← 1 2 3 4 5 →