How do I find the matrix X that multiplied with another one A equals Y (matrices are not square)

Question

I have the following matrices:

• $A$: shape 7,9 constant values not to be changed
• $X$: shape 402,7 with values that multiplied with A should result in the desired solution
• $Y$: shape 402,9

Equation: $Y = A X$

Constraints: Values in X must be >= 0

Since they aren't square, algorithms solving the equations don't work (as in $A^{-1} Y = X$)

Does a good algorithm exist for getting matrix $X$ in this problem?

Edit:

I'm currently using scipy.optimize.minimize() (python) to minimize the error by optimizing X with L-BFGS-B. MeanError between $Y$ and $AX$ is currently around 34% on average.

Answer 1

As $X$ has $402 \times 7$ unknown entries, and $Y$ has $402 \times 9$ entries, these unknown entries will have to be solutions of an overdetermined linear system, i.e., with more equations than there are unknowns.

In general, in such a case, we will have no solutions.

But it is not excluded that solutions exist in particular cases, for example if there is a "physical" reason for such an existence.

A more reasonable attitude in this case (too many constraints vs. number of unknowns) is to consider your issue as an optimization problem, i.e., find $X$ such that

$$\|AX-Y\|$$

is minimum (where $\| ... \|$) is a matrix norm, e.g., Frobenius norm.

Edit :

Probably the simpler approach is to multiply left and right hand side of matrix equation $AX=Y$ by $A^T$, giving :

$$AX=Y \ \implies \ A^TA=A^TY \ \iff \ X=(A^TA)^{-1}A^T Y \tag{1}$$

Three remarks :

1) Why are we authorized to take the inverse of $A^TA$ ? Because it is square and moreover semi-definite positive, therefore has $\geq 0$ eigenvalues. It can happen that some of its eigenvalues are very close to zero generating a numerical error (we say that it is an unstable method, but maybe in your application you will not suffer from this phenomenon).

2) Why do we find a solution $X=...$ whereas we have said that no solution exists ? Because in (1) you may have noticed that there is an implication symbol : we have enlarged the set of solutions. This is not an equivalence sign : with this $X$ we cannot go the other way and say that $AX=Y$ ! Nevertheless it is not difficult to show that this $X$ is the solution of the minimization problem mentionned above (see http://www.sci.utah.edu/~gerig/CS6640-F2012/Materials/pseudoinverse-cis61009sl10.pdf).

3) Matrix $A^+:=(A^TA)^{-1}A^T$ is called the pseudo-inverse of $A$ ; in this way we can reduce (1) to

$$AX=Y \ \implies \ X=A^+ Y \tag{2}$$

More elaborate methods using SVD (Singular Value Decomposition) are less prone to instability...

Answer 2

As I'm sure you've noticed, what you need is $YA^{-1}$ , which is an issue since A is not square. This is where the concept of generalized inverses comes in.

First realize that if any such X exists, then the rows of Y will be linear combinations of the rows of A. If this is true, now find a g-inverse of A.

All non 0 matrices have one and they suffice your needs. The overall process you'll need to go through is this:

1. Find a rank-factorization for A, say (P,Q).
2. Find a left inverse of P, say C.
3. Find a right inverse of Q, say D.
4. Define $A^{-1}$ = DC

Use this to get $X$.