# 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?

• Incomplete Cholesky is a possible starting point. – Federico Poloni May 9 '18 at 6:05
• Wouldn't trying all $2^9 = 512$ binary matrices work? – Rodrigo de Azevedo May 9 '18 at 14:51
• @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. – user135939 May 9 '18 at 17:09
• @FedericoPoloni There may be some connections but it's not obvious to me. In particular, $A$ in my case is not necessarily lower triangular. – user135939 May 9 '18 at 17:12
• – Rodrigo de Azevedo May 10 '18 at 8:30

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:

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.

• 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. – user135939 Jun 24 '18 at 20:15
• That's good to know! However, one can construct (more elaborate) examples with multiple non-isomorphic adjacency matrices that share the same covariance matrix. – Bill Bradley Jun 24 '18 at 23:39
• (I mean, fixing the dimensions doesn't dodge the problem.) – Bill Bradley Jun 24 '18 at 23:44