1
$\begingroup$

I have some unknown numbers $x_i$ and I know only certains sums $y_i$ over them:

$\mathbf{A}\mathbf{x}=\mathbf{y}$

where this equation is underdetermined. Moreover, due to the origin of the problem I know that all $x_i>0$ are positive. I do know all $A_{ij}\in \{0,1\}$.

Do you know a way to find a solution? One "average and simple" solution would suffice.

EDIT: Some more information for that particular problem. All $x_i>0$ and $y_i>0$ and all $A_{ij}\in \{0,1\}$. There are more $x_i$ than $y_i$. And there are a lot of them, so that the method to solve it should be simple for the computer :) Something iterative would be nice.

  • 0
    @Johannes: For that particular problem I'm not sure what the most sensible real-world regularization is. Maybe all $x_i$ should be concentrated maybe spread. I actually think making them rather spread and equal would be better. But any suggestion for an easy algorithm will do for now.2012-12-14

2 Answers 2

1

The solution is given by

$ x = A^T (A A^T )^{-1}y .$

Here is the reference.

  • 0
    @user1551: I really liked what you did. You did a good job by working out an exam$p$le. It's up to the OP to follow up with your comment. As you can see I replied to all of his comments. And what's important is that we assist as much as we can. Thanks for the comment.2012-12-20
1

Although a bit inelegant, you may try to convert the problem into a linear programming problem: \begin{align} \textrm{maximize }&\ 0\\ \textrm{subject to }&\ Ax=y,\\ &\ x_i\ge0, \textrm{ for all } i. \end{align} (It's not elegant because we actually have nothing to maximize here; we just want to find a feasible $x$.) You may search the internet for "simplex method", or look up any undergraduate textbook on operations research to see how to solve the above linear program (sec. 10.8 the online version of the 2/e of Numerical Recipes also describes the simplex algorithm).

In the standard formulation of a linear program, each $x_i$ is only nonnegative. Some software libraries allow you to specify strict inequalities. If not, you may roll your own modified version of the simplex method, but you need to learn the details of the simplex method first.