Relating multiway discrepancy and singular values of nonnegative rectangular matrices

详细信息    查看全文

• 作者：Marianna Bolla ^{marib@math.bme.hu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Discrepancy ; Normalized matrix ; Singular values ; Spectral clusters
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 April 2016
• 年：2016
• 卷：203
• 期：Complete
• 页码：26-34
• 全文大小：396 K

文摘

The minimum k$k$-way discrepancy ${\mathrm{md}}_k\left(C\right)$ of a rectangular matrix $C$ of nonnegative entries is the minimum of the maxima of the within- and between-cluster discrepancies that can be obtained by simultaneous k$k$-clusterings (proper partitions) of its rows and columns. In Theorem 2, irrespective of the size of $C$, we give the following estimate for the k$k$th largest nontrivial singular value of the normalized matrix: $s_k\le 9{\mathrm{md}}_k\left(C\right)(k+2-9kln{\mathrm{md}}_k\left(C\right))$, provided $0<{\mathrm{md}}_k\left(C\right)<1$ and $k<\mathrm{rank}\left(C\right)$. This statement is a certain converse of Theorem 7 of Bolla (2014), and the proof uses some lemmas and ideas of Butler (2006), where the k=1$k=1$ case is treated. The result naturally extends to the singular values of the normalized adjacency matrix of a weighted undirected or directed graph.