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?

4more comments