This question is motivated by a research problem I recently encountered. Consider two sets of random variables $\mathbf{X}$ and $\mathbf{Y}$, where $\mathbf{Y}$ can be expressed as a linear combination of $\mathbf{X}$'s and $\mathbf X$ is a unit Gaussian random vector with iid entries.

enter image description here

In the example above, $Y_1=X_1+X_2$, $Y_2=X_1+X_3$, and so on. In other words, $\mathbf Y=A\mathbf X$ where $A$ is a matrix with binary entries. The $ij$-th entry of $A$ indicates whether $X_i$ is part of $Y_j$. Moreover, we can assume that the graph is sparsely connected so $A$ is sparse.

Now I observe realizations of $\mathbf Y$'s. The question is, can I figure out the matrix $A$, or equivalently the connection of the bipartite graph?

One thought I had was to first calculate the empirical covariance $\hat \Sigma$, which is close to $\mathbb E[YY^T]=AA^T$ when the number of samples are large. But from here I have no idea how to proceed. The question seems to boil down to finding a sparse, binary $A$ such that the residual $\|\hat \Sigma-AA^T\|$ is small. My question is whether this problem can be efficiently solved. If not, are there any approximation or relaxations?

  • $\begingroup$ Incomplete Cholesky is a possible starting point. $\endgroup$ May 9, 2018 at 6:05
  • $\begingroup$ Wouldn't trying all $2^9 = 512$ binary matrices work? $\endgroup$ May 9, 2018 at 14:51
  • $\begingroup$ @RodrigodeAzevedo For small problem this is doable but the complexity is exponential. The problem I'm considering has a large size; $A$ is a few thousand by a few thousand. Checking every binary matrix will be prohibitively expensive to do. $\endgroup$
    – user135939
    May 9, 2018 at 17:09
  • $\begingroup$ @FedericoPoloni There may be some connections but it's not obvious to me. In particular, $A$ in my case is not necessarily lower triangular. $\endgroup$
    – user135939
    May 9, 2018 at 17:12
  • $\begingroup$ Related: A variant of Cholesky decomposition involving binary matrices $\endgroup$ May 10, 2018 at 8:30

2 Answers 2


The solution I ended up using is simulated annealing. I start from a random binary matrix $A$, and define the potential function to be $$p(A)=e^{-\frac{1}{T}\|AA^T-\hat \Sigma\|^2}$$ Every iteration I use Gibbs sampling to determine if I need to jump from $A$ to $A'$ where they differ by only one entry, i.e. toss a coin with probability $$\frac{p(A')}{p(A)+p(A')}$$ and the temperature $T$ gradually drops from $1$ to $0.1$ in 500 iterations.

This method works for small scale problems ($n=20$, $k=10$ where $n$, $k$ are the number $X$s and $Y$s). For problems with larger scales (like $n=80$, $k=40$), it converges to a near-optimal solution but not always the exact optimal one. For problems with even larger scale, this method seem to be not working so well. Still I will appreciate other solutions, particularly the ones that use a completely different techniques.


This is more of a comment, but:

Depending on exactly how we define the family of sparse matrices, it may not be possible to recover a unique solution. In the example in the original post, the covariance matrix looks like $$ \begin{bmatrix} 2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2 \end{bmatrix} $$ However, that's also the covariance matrix of this distinct bipartite graph / sparse matrix / factor graph: different graph with same covariance

Perhaps our goal is simply to recover some consistent bipartite graph? Alternately, it might be possible to choose some family of matrixes $A$ such that the covariance matrices are guaranteed to be 1-1, but that seems difficult.

  • $\begingroup$ I forgot to mention that the sizes of $X$ and $Y$ are known. In the example, both $X$ and $Y$ have 3 variables. In other words, the dimensions of the adjacency matrix $A$ are known, and it will be good to find a sparse $A$ such that $AA^T$ is close to the empirical covariance matrix. $\endgroup$
    – user135939
    Jun 24, 2018 at 20:15
  • $\begingroup$ That's good to know! However, one can construct (more elaborate) examples with multiple non-isomorphic adjacency matrices that share the same covariance matrix. $\endgroup$ Jun 24, 2018 at 23:39
  • $\begingroup$ (I mean, fixing the dimensions doesn't dodge the problem.) $\endgroup$ Jun 24, 2018 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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