Matrix Decompositions and Sparse Graph Regularity. (arXiv:1911.11868v1 [cs.DS])
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 \subseteq \mathbb{R}^m \times \mathbb{R}^n$ and matrix $A \in \mathbb{R}^{m \times n}$, we write $A$ as a weighted sum of rank one matrices formed by…