Matrix Decompositions and Sparse Graph Regularity
share
We introduce and study a matrix decomposition that is a common generalization of the singular value decomposition (SVD), cut decomposition, CUR decomposition, and others. For any given set of pairs P ⊆R^m ×R^n and matrix A ∈R^m × n, we write A as a weighted sum of rank one matrices formed by some pairs in P. The resulting projection value decomposition (PVD) inherits several useful properties of the SVD; for example, the decomposition can be obtained by greedily peeling off rank one matrices, and the norm of the coefficients of the decomposition is the Frobenius norm of the matrix. Perhaps most interesting is that, in analogy with low-rank approximation from SVD, truncating the decomposition gives matrix approximations of small error. When applied to the adjacency matrices of graphs, the PVD lets us derive the weak regularity lemma of Frieze and Kannan as well as Szemeredi's strong regularity lemma. Whereas these regularity lemmas in their usual forms are nontrivial only for dense graphs on Ω(n^2) edges, our generalization implies extensions to a new class of sparse graphs which we call cut pseudorandom, which are roughly those with small leading coefficients in the appropriate PVD. It turns out that cut pseudorandomness unifies several important pseudorandomness concepts in prior work: we show that L_p upper regularity and a version of low threshold rank are both special cases, thus implying weak and strong regularity lemmas for these graph classes where only weak ones were previously known.
READ FULL TEXT