8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How about if you wait on the MSE question for a few days? Also, your link to it is faulty, there are some extraneous characters before the http. I tried to fix it with no luck math.stackexchange.com/questions/1719656/… $\endgroup$ – Will Jagy Mar 30 '16 at 18:19
  • 1
    $\begingroup$ You don't give enough information to make this a rigorous maths question. You need to tell us exact running times for the two systems before someone can minimise the overall computational cost. And presumably you are well aware that a gazillion man-hours have already gone into the problem of multiplying a matrix by a vector whilst minimising the overall computational cost. Are you trying to re-invent the wheel? $\endgroup$ – znt Mar 30 '16 at 18:25
  • 1
    $\begingroup$ Yes, the question looks better now. Good luck with it! $\endgroup$ – znt Mar 30 '16 at 18:41
  • 1
    $\begingroup$ Gerry Myerson: (Thanks for catching a typo... now fixed.) The cost of ${\bf C}$ is zero (so long as its entries are non-negative), and the cost of ${\bf B}$ is the total count of its non-zero entries. In short, the "${\bf C}$" process is "free." $\endgroup$ – David G. Stork Mar 30 '16 at 22:35
  • 1
    $\begingroup$ A computationally intractable formulation is: $\min \|A-BC\|_F$ subject to $\|B\|_0 \le \delta, C \ge 0$. Performing alternating minimization over $B$ and $C$ can help obtain a reasonable solution. You can replace $\|B\|_0 \le \delta$ by a sparsity promoting convex constraint such as $\|B\|_1 \le \delta'$. The problem as stated is intractable. $\endgroup$ – Suvrit Mar 31 '16 at 19:18
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, @Will Shawn. Let me try coding this up and seeing if it works on a few simple cases and how sensitive it might be to changes in entries to ${\bf C}$. (This will take a two or three days...) $\endgroup$ – David G. Stork Apr 1 '16 at 16:03
  • $\begingroup$ Will Shawn (@Will Shawn): Your third line should be $\nu_1 = cu + a_2 \nu_2 + \ldots a_n \nu_n$. Right? $\endgroup$ – David G. Stork Apr 1 '16 at 21:27
  • $\begingroup$ @DavidG.Stork Right. $\endgroup$ – Will Sawin Apr 2 '16 at 0:32
  • $\begingroup$ And the $2n$ entries need not be optimal, as my simple example shows... right? $\endgroup$ – David G. Stork Apr 2 '16 at 2:48
  • $\begingroup$ @DavidG.Stork Yes. Of course it is off by a factor of at most $2$. I thought a simple modification of my argument gives the optimum but that turns out not to be the case. $\endgroup$ – Will Sawin Apr 2 '16 at 3:09
1
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Thanks. The application area involves optics, in which a particular class of optical devices can perform a linear operation. "Addition" of vectors would involve shining extra light, which here is impossible; "subtraction" of vectors is very hard and would involve rejecting light, which would reduce signal and is hence undesirable. (An optical filter multiplies the values in the light by a number < 1.0.) I don't understand your answer, though, because it relies on steps that "produce C," but C is unknown. $\endgroup$ – David G. Stork Mar 31 '16 at 19:05
  • $\begingroup$ If for example A has the first row all positive entries, and say only negative entries in the second and third rows, then an elementary matrix R which adds a large multiple of the first row to each of the second and third rows produces a C (=RA) which has all positive entries. R has n+2 nonzero entries and because of how I did it B will also have n+2 nonzero entries. The only way to improve on this is if the second or third rows had no positive entries, in which case addition by the first row is not needed. Gerhard "Hopefully You Get The Picture" Paseman, 2016.03.31. $\endgroup$ – Gerhard Paseman Mar 31 '16 at 19:12
  • $\begingroup$ If you could adapt your system to have B factored into DE, then E could cost n+s and D could cost 2n-1. Maybe this would work? Gerhard "Likes Adding Even More Filters" Paseman, 2016.03.31. $\endgroup$ – Gerhard Paseman Mar 31 '16 at 19:20
  • $\begingroup$ Multiple linear matrices is of course fine, so long as the right-most (first to operate on ${\bf x}$) has only non-negative entries. In short, ${\bf S}{\bf T}{\bf U}{\bf W}{\bf C} = {\bf B}^\prime {\bf C}$ is of course fine. The cost remains the non-zero entries in ${\bf B}^\prime$, though. $\endgroup$ – David G. Stork Mar 31 '16 at 20:30
  • $\begingroup$ Then you can do it with two matrices with a cost of under 2n for each matrix. Find a linear combination of rows which has coefficients of the same sign, then add the proper multiple of this to all rows that need it. C will be positive, B will invert the adding and R will invert the linear combination. A=RBC. However, RB may have more than 4n nonzero entries. Gerhard "At Least Has Upper Bound" Paseman, 2016.03.31. $\endgroup$ – Gerhard Paseman Apr 1 '16 at 1:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.