2
$\begingroup$

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?

$\endgroup$

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.