Relating multiway discrepancy and singular values of nonnegative rectangular matrices

The minimum kk-way discrepancy mdk(C) 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 kk-clusterings (proper partitions) of its rows and columns. In Theorem 2, irrespective of the size of C, we give the following estimate for the kkth largest nontrivial singular value of the normalized matrix: sk≤9mdk(C)(k+2−9klnmdk(C)), provided 0