I'm attempting to formulate the following problem as a standard matrix decomposition. So far, I've managed to express it formally but not convert it into a standard kind of decomposition. Any help would be appreciated!

The classification problem: I am trying to create a type classification scheme for my collection of unusual objects. I know that each object belongs to a particular type category; the total number of types is unknown. I would like to make a guess as to how many types there are.

For evidence, I can measure the interaction strength between any two objects. Given any two objects, their interaction strength is a signed integer completely determined by their types. The interaction strength is antisymmetric in the sense that $S(a,b) = -S(b,a)$.

So, I take a set of objects $A=\{a_1, \ldots, a_m\}$ and another set of objects $B=\{b_1, \ldots, b_n\}$ and measure the interaction strength between them, generating an $m \times n$ sized matrix of interaction strengths $M$.

From this interaction strengths matrix $M$, I would like to infer a minimal set of types that explains the data. That is, I would like to find a matrix decomposition $$M_{m\times n} = P_{m\times k}\cdot \widehat{S}_{k\times k} \cdot Q_{k\times n}$$ such that:

  1. $\widehat{S}$ is a square matrix which is antisymmetric in the sense that $\widehat{S} = -\widehat{S}^\top$.
  2. $P$ and $Q$ are permutation matrices with exactly one 1 entry per row and per column, respectively, and zeroes everywhere else.
  3. The dimension $k$ of the matrix $\widehat{S}$ is as small as possible.

In other words, $k$ will be the number of types, $\widehat{S}$ will list the complete pairwise interaction strengths of all the type pairs, and $P$ and $Q$ will assign types to the original objects (multiple objects can and should be assigned to the same type).

I have formulated this problem formally, but I'm not sure if there's a more elegant formulation in terms of existing well-known decompositions or an integer optimization problem.

I have also wondered whether this version of the problem is, perhaps trivial to solve because two objects in $B$ have the same type combination if and only if they have the same interaction strength with every object in $A$. (The only if direction is straightforward; the if direction is implied by the fact that we're looking for the simplest possible explanation).

  • $\begingroup$ Two questions: (a) why is the interaction strength antisymmetric rather than symmetric; and (b) are you only creating types for the B objects (and not the A objects)? $\endgroup$ – prubin Jul 9 '18 at 17:53

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.