I've got a little conjecture I need to prove for a theoretical result related to causal Bayes net search with latent variables under sparsity constraints. If you're interested in the application please feel free to email me at adambrod@andrew.cmu.edu.

Here's the problem:

Suppose we have a $p\times q$ real matrix $A$ such that 1) $A$ is rank deficient so $\textrm{rk}(A)=r<\min(p,q)$, and 2) there are no zero elements in $A$.

I want to prove that there is no factorization of $A$ into two matrices with fewer total non-zero elements than some factorization of $A$ into two matrices $B$ and $C$ of dimensions $p\times r$ and $r\times q$.

The proof strategy I'm employing is proof by induction on rank.

The base case, $\textrm{rk}(A)=1$ is trivial ($B$ and $C$ must have at least $p+q$ non-zero elements between the two of them in order for every element of $A$ to be non-zero and that is the maximum number of elements in a pair of matrices with dimensions $p\times r$ and $r\times q$).

The induction step is as follows: Subtract a matrix $D$ of rank 1 from $A$ such that the resulting matrix $S$ is of rank $r-1$. This corresponds to removing all of the "influence" of some specific row vector $v$ from $A$, such that $v$ is linearly independent of the remainder, $S$. $D$ can be expressed as the outer product of some column vector $w$ with $v$. Suppose $wv$ is the sparsest factorization of $D$ (the possibility of this is implied by our base case). Let $RT$ be the sparsest factorization of $S$ of dimensions $p\times r-1$ and $r-1\times q$ respectively. My conjecture is that the sparsest factorization of $A$ is achieved by appending these two sparsest factorizations, that is, the sparsest factorization of $A$ is the product of $R$ with $w$ appended as the $r$th column and $T$ with $v$ appended as the $r$th row. Because $D$ and $S$ are linearly independent this seems quite plausible, but a rigorous demonstration eludes me.

Any solutions, suggestions, or references would be greatly appreciated, and of course, if you provide me with personal information (name/department affiliation), I would be happy to acknowledge your assistance in any publications I apply this result in.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.