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.


  • $\begingroup$ You need to format the question a bit for it to be readable, using LaTeX. This is not the place to be looking for collaboration partners, and I believe your question is probably more appropriate at math.stackexchange You also need to define what you consider to be a factorization of matrices here (only two matrices allowed, do they have size restriction?) $\endgroup$ – Per Alexandersson Mar 21 '14 at 22:09
  • $\begingroup$ Rather than math.stackexchange, I'd suggest scicomp.stackexchange. $\endgroup$ – Federico Poloni Mar 21 '14 at 22:20
  • $\begingroup$ Re factorization: as stated, the result I am interested concerns factorization as the product of 2 matrices, the factorization must be exact so the missing dimension must be at least $r$ but may be arbitrarily larger. Re scicomp.stackexchange: thank you for the suggestion! I'll try my luck there. $\endgroup$ – Adam Mar 21 '14 at 22:41

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.