# Intuitive idea for the margin complexity of a matrix

I am trying to get a more intuitive understanding of the margin complexity of a matrix. In order to clarify what the margin complexity is let me first review a few definitions. For a binary matrix $$U \in \{ -1,1\}^{m \times n}$$ we define the set of sign consistent matrices as $$SP(U) := \{ V \in \mathbb R^{m \times n}: \forall_{i,j} \;V_{ij}U_{ij} >0 \}.$$

Using this definition the margin complexity is defined to be $$mc(U):= \inf_{PQ^T \in SP(U)} \max_{ij} \frac{|P_i| |Q_j|}{|\langle P_i, Q_j \rangle |},$$ where the infimum is over the $$P \in \mathbb R^{m \times k}$$ and $$U \in \mathbb R^{k \times n}$$.

I understand what the equation tells me to optimize but I have no real intuition what the margin complexity would be an indicator for?