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 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.
 A: 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.
A: 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.
