Factoring a positive semidefinite matrix into binary matrices 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.

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?
 A: 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.
A: 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:

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.
