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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.