2
$\begingroup$

I am trying to solve $$A B = C$$ $B$ is a known $N\times M$ matrix, $C$ is a partially known $L\times M$ matrix, and $A$ is an unknown $L\times N$ matrix, with $L<N$. If $C$ were fully known, I could just use a least-squares solution, which can be calculated efficiently. Alas, of some entries of $C$ I know only that they are positive (in fact, all entries of $C$ are either known to be $0$, or known to be positive. We can scale the problem such that all positive entries of $C$ are, say, $>1$). I'm trying to solve for $A$ (up to a factor). Can $A$ be determined efficiently and if so, how?

A significant amount of literature exists on the subject of least squares solutions with inequality constraints (see e.g. this question), but it is not clear to me if this problem can be reduced to the form typically found in the literature: $$\text{min}\|A x-b\|\text{ s.t. }G x\geq h$$ In fact, I suspect that it cannot be reduced to that form.

$\endgroup$
1
$\begingroup$

How about this? \begin{equation} \underset{{\underset{ \text{and }\left(AB\right)_{i,j}\geq 0 }{ A \text{ such that } \left(AB\right)_{\text{known} }}=C_{\text{known}}}}{\min}\left\|AB-C\right\|_{\text{some suitable matrix norm, root of elementwise sum of squares for instance}} \end{equation} Here you would have a mixture of equality and inequality constraints.

Also, if you need inequality constraints only, but you have let's say $e\left(x\right)=0$, you can always realize these constraints as $e\left(x\right)\leq0$ and $-e\left(x\right)\leq0.$

remark: uniqueness does not nescessairily hold.

$\endgroup$
2
  • $\begingroup$ Alas, the system is over-determined, constructing a search space of exact solutions is not possible. $\endgroup$
    – Wouter
    Oct 5 '15 at 15:08
  • $\begingroup$ Not neccessairily. That depends on the rank of $B$ and on the known entries for $C$. (Take $B=0$ and $\text{known}=\emptyset$ for instance.) $\endgroup$
    – Max
    Oct 5 '15 at 15:17

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.