Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices

被引：0

作者：

Mercado, Sergio ^{[1
]}

Villagra, Marcos ^{[2
]}

机构：

[1] Univ Nacl Asuncion, Fac Politecn, Campus Univ, San Lorenzo 111421, Paraguay

[2] Univ Nacl Asuncion, Dept Matemat, Campus Univ, San Lorenzo 111421, Paraguay

来源：

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2022年 / 14卷 / 02期

关键词：

Spectral sparsification; symmetric matrices; nonnegative matrices; spectral graph theory;

D O I：

10.1142/S1793830921501093

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We say that a square real matrix M is off-diagonal nonnegative if and only if all entries outside its diagonal are nonnegative real numbers. In this paper, we show that for any off-diagonal nonnegative symmetric matrix M, there exists a nonnegative symmetric matrix (M) over cap which is sparse and close in spectrum to M.

引用

页数：9

共 10 条

[1] Bhatia M., 1997, Matrix Analysis
[2] ROTATION OF EIGENVECTORS BY A PERTURBATION .3.
DAVIS, C
KAHAN, WM
[J]. SIAM JOURNAL ON NUMERICAL ANALYSIS, 1970, 7 (01) : 1 - &
[3] Jolliffe I.T., 2002, PRINCIPAL COMPONENT, V2 2, DOI DOI 10.1007/978-1-4757-1904-8_1
[4] AN ITERATION METHOD FOR THE SOLUTION OF THE EIGENVALUE PROBLEM OF LINEAR DIFFERENTIAL AND INTEGRAL OPERATORS
LANCZOS, C
[J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS, 1950, 45 (04): : 255 - 282
[5] CONSTRUCTING LINEAR-SIZED SPECTRAL SPARSIFICATION IN ALMOST-LINEAR TIME
Lee, Yin Tat
Sun, He
[J]. SIAM JOURNAL ON COMPUTING, 2018, 47 (06) : 2315 - 2336
[6] Pardalos P. M., 1991, J. Global Optim., V1, P15, DOI DOI 10.1007/BF00120662
[7] SPECTRAL SPARSIFICATION OF GRAPHS
Spielman, Daniel A.
Teng, Shang-Hua
[J]. SIAM JOURNAL ON COMPUTING, 2011, 40 (04) : 981 - 1025
[8] Stewart G. W., 1990, MATRIX PERTURBATION
[9] A useful variant of the Davis-Kahan theorem for statisticians
Yu, Y.
Wang, T.
Samworth, R. J.
[J]. BIOMETRIKA, 2015, 102 (02) : 315 - 323
[10] Zouzias A, 2012, LECT NOTES COMPUT SC, V7391, P846, DOI 10.1007/978-3-642-31594-7_71

← 1 →