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
    It all depends: how many $\,x_i's\,,\,y_i's\,$ are there? Are there some zero or negative $\,y_i's\,$? This kind of problems can be easily (more or less) solved by means of matrix theory within linear algebra.2012-12-14
  • 0
    You have to regularize the problem. For instance, by imposing an $L_2$ norm (determine $x$'s such that the sum of their squares is minimal).2012-12-14
  • 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
    Sounds pretty good for a simple answer :) Will this give me positive $x_i$? Is there any simplification for the inverse if I only have 0/1 entries?2012-12-14
  • 0
    @Gerenuk: See [here](http://mathworld.wolfram.com/01-Matrix.html).2012-12-14
  • 0
    Thanks. Do you think with this method some $x_i$ can become negative?2012-12-14
  • 0
    @Gerenuk: Try to work a simple case and see what you get.2012-12-14
  • 1
    @MhenniBenghorbal The OP asks for a positive solution. Your answer does not promise that. For example, consider $A=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$ and $y=(3,1)^T$. Obviously $Ax=y$ has a positive solution, but $A^T(AA^T)^{-1}y=\frac13(5,-1,4)^T$ isn't one. Not to mention that $AA^T$ may be singular for a general binary matrix $A$.2012-12-14
  • 0
    @user1551: I already provided him with the reference, so he knows what kind of solution he's already had.2012-12-14
  • 0
    @Downvoter: What's the downvote for?2012-12-19
  • 1
    *What's the downvote for?* Why do you ask since you do not care, as you have shown again and again? Somebody who cares would not react to @user1551's fully justified remark with the shameful comment you posted.2012-12-19
  • 0
    @did: Did he complain to you?2012-12-19
  • 0
    If user did, then what? If user did not, then what? Evading the point again, as usual...2012-12-19
  • 0
    @MhenniBenghorbal For the record, I have neither complained to anybody nor downvoted your answer. The answer and comments I gave here are all the contributions I have ever made about the OP's question or your answer. And if someone votes your answer downward, please don't feel offended. I get downvotes from time to time. I think the downvoting mechanism is actually a good device for training me to avoid giving useless or irrevalent answers.2012-12-20
  • 0
    @user1551: I really liked what you did. You did a good job by working out an example. 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.