Factor matrix ${\bf A}$ into the product ${\bf B}{\bf C}$ where ${\bf C}$ has no negative entries and ${\bf B}$ has few non-zero entries

Question

This is a more carefully worded version of this question, here tailored to professional mathematicians.

Consider a matrix ${\bf A}\in{\bf M}_{n\times n}({\mathbb R})$ with possibly positive, negative and zero-valued entries and ${\rm Det}[{\bf A}] \neq 0$.

Is there an algorithm to write ${\bf A}$ as a product of two matrices ${\bf B}{\bf C}$ where ${\bf B} \in{\bf M}_{n\times n}({\mathbb R})$ and ${\bf C} \in{\bf M}_{n\times n}({\mathbb R}_\ge)$ in which ${\bf B}$ has the maximum number of $0$ entries (i.e., is sparse) and all the entries of ${\bf C}$ are non-negative? Again, the cost metric is the number of non-zero entries in ${\bf B}$.

Example

Suppose ${\bf A} = \left( { \ \ 1\ \ \ \ 2 \atop -6\ -8} \right)$.

Here are three factorizations, ${\bf B}{\bf C}$, with their associated costs.

• $\left( { \ \ 1\ \ \ \ \ 2 \atop -6\ -8} \right)\left( {1\ \ \ \ 0 \atop 0\ \ \ \ 1} \right)$, Cost = $4$
• $\left( {0\ \ \ \ \ 2 \atop 1\ \ \ \ -14} \right)\left( {1\ \ \ \ \ \ 6 \atop 1/2\ \ \ \ 1} \right)$, Cost = $3$
• $\left( {1\ \ \ \ \ 0 \atop 0\ \ \ \ -2} \right)\left( {1\ \ \ \ \ 2 \atop 3\ \ \ \ \ 4} \right)$, Cost = $2$

I do not need an algorithm to find a unique decomposition, just a principled method for finding at least one having minimum cost.

As far as I know, despite immense work on matrix factorization, this precise problem has never been solved. (Polar decomposition, Cholesky decomposition, LUD decomposition, Gram-Schmidt orthogonalization and Sparse matrix approximation are not quite appropriate.)

Motivation

The general computational task is to perform the linear operation ${\bf A}{\bf x}$, where ${\bf A}$ has the conditions listed above and ${\bf x}$ is an $n$-dimensional real-valued vector of non-negative entries. The overall computational task can be split into two linear systems. The first system can perform ${\bf C}{\bf x}$ at extremely low computational cost (assume zero cost), but the entries of ${\bf C}$ must be non-negative. The second system can perform ${\bf B}{\bf y}$ (where ${\bf y} = {\bf C}{\bf x}$) and the entries of ${\bf B}$ can be positive or negative or zero but there is a unit cost for each non-zero entry of ${\bf B}$.

We seek to split the overall computation of ${\bf A}{\bf x}$ into the two systems to minimize the overall computational cost.

Answer 1

Let $v_1, \dots, v_n$ denote the rows of $A$.

Let $u$ be a vector with all positive entries that is not a linear combination of $v_2, \dots, v_n$. Then we may write $v_1 = c u + a_2 v_2 + \dots a_n v_n$ for some scalars $c, a_2, \dots, a_n$.

Now choose $\epsilon$ small enough that for all $j$ from $2$ to $n$, $u + \epsilon \sum_{i=2}^j a_i v_i$ has all positive entries.

Let $C$ be the matrix with rows $u + \epsilon \sum_{i=2}^j a_i v_i$ for $j$ from $1$ to $n$. Then by construction $C$ has all positive entries.

Each vector $v_i$ can be written as a linear combination of two rows of $C$. For $v_i$ this is by subtracting two adjacent rows and dividing by $\epsilon$, and for $v_1$ it is $c-1/\epsilon$ times the first row plus $1/\epsilon$ times the last row.

We conclude that there is a sparse matrix $B$ with $2n$ entries such that $BC = A$.

This is optimal assuming each of the $v_i$ has both positive and negative entries, as the corresponding row of $B$ must have both positive and negative entries and hence at least $2$ entries. If $A$ has any rows that are either non-negative or non-positive, then this algorithm might not be optimal, as the example in the original question shows. However, this algorithm produces matrices where $BC$ is very sensitive to slight changes in $C$ and thus may be unsuitable for practical applications.

Answer 2

I find it curious that addition of two vectors can't be used in your system, but that matrix multiplication of a vector by a positive matrix is so cheap. In any case, I doubt that you will be able to find a factorization with minimal cost for B quickly.

Certain cases can be handled cheaply: Find elementary row operations R on A that produce C, and let BR=I and RA=C. This will handle all cases where A has a row with all entries nonzero and of the same sign. B will have a cost of at most 2n-1, and at least n+r (which is minimum) with r the number of rows of A that have both positive and negative entries.

For the general case, you could try to find a small linear combination of rows of A which produces a positive row. I have not worked out the details, but I would hope that if you found s rows to do that, you could combine it with the above to produce a B with cost bounded by sn+n. However, finding a small set of s rows should be reducible to some NP-hard problems in matrix algebra/combinatorics. So I am not hopeful for a quick general algorithm.

Gerhard "Subtracting Vectors Would Help Much" Paseman, 2016.03.31.