# 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. May 9, 2018 at 6:05
• Wouldn't trying all $2^9 = 512$ binary matrices work? May 9, 2018 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. May 9, 2018 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. May 9, 2018 at 17:12
• May 10, 2018 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. Jun 24, 2018 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. Jun 24, 2018 at 23:39
• (I mean, fixing the dimensions doesn't dodge the problem.) Jun 24, 2018 at 23:44