5
$\begingroup$

Say there is a data table $D$ that we cannot see, with $M$ columns. We are given exact cross-tabulation frequencies for all ${M \choose 2}$ pairs of columns, that is how often each combination of two values occurs.

From the cross-tabulations, we can derive a set of possible rows $R$ of $D$ and maximum frequencies for each possible row.

How can we reconstruct the original table $D$? If there is not enough information to do so, how can we construct a possible table $D'$ that has the same cross-tab frequencies? In this case, is it possible to count the number of possible tables?

(Edit: As Vor noted, define a table as an unordered collection of rows. A permutation of the rows of a table yields the same table.)


For example, if $D$ has rows:

X  A  j
Y  A  k
X  B  j
X  B  j

We have three sets of cross-tab frequencies:

X  A  1
X  B  2
Y  A  1
Y  B  0

X  j  3
X  k  0
Y  j  0
Y  k  1

A  j  1
A  k  1
B  j  2
B  k  2

I would like an algorithm which will take the cross-tab frequencies as input and output the original table or a possible original table.

$\endgroup$
  • $\begingroup$ My gut says it's NP-hard, but I don't see a reduction right now. $\endgroup$ – Raphael Sep 29 '12 at 12:29
  • 2
    $\begingroup$ @Sarkom: I think that if you pick a permutation of the rows of the source table you get the same cross-table frequences, so in order make the unique solutions question more interesting you should add the constrain that all tables are presented in lexicographic order. $\endgroup$ – Vor Sep 29 '12 at 12:43
  • $\begingroup$ You should specify the input as a list of (repeated) pairs or unarily encode the multiplicities otherwise the table may become exponentially large. $\endgroup$ – frafl Apr 6 '13 at 13:15
  • $\begingroup$ @frafl: Can you clarify your comment? Are you suggesting that the input should be only pairs with no frequencies? If so, I don't understand how that would be more helpful. $\endgroup$ – Sarkom Apr 7 '13 at 16:00
  • 1
    $\begingroup$ Of course each pair has to occur $k$ times if its frequency in the original table is $k$, so $(X,j,11_{2})$ becomes $(X,j)(X,j)(X,j)$. So the size of the input is $\approx \binom{M}{2}$ the size of the original table. $\endgroup$ – frafl Apr 7 '13 at 16:47
2
$\begingroup$

We have $M$ columns $C_1, \dots, C_M$ in the original table, each with a finite set of distinct values $V_1, \dots, V_M$.

Given the cross-table frequencies $c_{i,j}(a,b)$ (frequency of $a$ in $V_i$ and $b$ in $V_j$ occurring together), proceed as follows:

  1. Determine $V_1, \dots, V_M$ and denote $V_i = \{v^{(i)}_j \mid j \in [1,n_i] \}$ where $n_i = |V_i|$.
  2. Solve the following integer program:

    $\qquad\displaystyle \min \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1,\dots,i_M)} \\ \qquad \begin{align} \text{s.t. } \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_{l-1} = 1}^{n_{l-1}} \sum_{i_{l+1} = 1}^{n_{l+1}} \cdots \sum_{i_{r-1} = 1}^{n_{r-1}} \sum_{i_{r+1} 1}^{n_{r+1}} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1, \dots, i_M)} &= c_{(l,r)}(i_l,i_r) \\ \qquad \text{for all } 1 \leq l < r \leq M, i_l \in [1,n_l], i_r \in [1,n_r], \\ x_{(i_1, \dots, i_M)} &\in \mathbb{N} \\ \qquad \text{for all } i_1 \in [1,n_1], \dots, i_M \in [1,n_M] \end{align}$

The $x_{(i_1, \dots, i_M)}$ now indicate which row should occur how often, and we get a solution with the minimum number of rows possible. If we can influence the search, we can abort as soon as we find any feasible solution.

This is not likely to be efficient, but there are honed solvers for integer programs around so it's simple to implement. It may be possible to use an LP-solver and round to a feasible solution.

$\endgroup$
  • $\begingroup$ How about $$\sum_{(i_1,\dots,i_M)\in V_1\times \dots \{i_l\}\dots\{i_r\}\dots \times V_M}$$? $\endgroup$ – frafl Apr 7 '13 at 14:29
  • $\begingroup$ @frafl Not really prettier, isn't it? :/ I guess one could define some notatation like $\mathbf{V}[l\to\{i_l\}, r\to \{i_r\}]$ for $V_1 \times \dots \times V_M$ with update components at $l$ and $r$, but that would be hard to read in another way. $\endgroup$ – Raphael Apr 7 '13 at 14:37
  • $\begingroup$ I don't know how "simple" it would be to implement ;) but I like this encoding using straightforward constraint satisfaction and don't see any better solution available. $\endgroup$ – Sarkom Nov 19 '13 at 19:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.