1
$\begingroup$

Let $\mathbf G$ be a given $m \times n$ matrix, $\mathbf y$ a given $m \times 1$ column vector and $\mathbf x$ an unknown $n \times 1$ column vector such that $\mathbf x \ge 0$.

1) How do you find $\displaystyle \min_{\mathbf x} (\mathbf y - \mathbf G\mathbf x)^T(\mathbf y - \mathbf G\mathbf x)$?

2) Whether there is a solution of that problem similar to the simple pseudo-inverse $x=(G^TG)^{−1}G^Ty$ used for solving the least-squares problem?

3) And what if we have $n \times n$ matrix $\mathbf C$ and the constraint $\mathbf C\mathbf x \ge 0$ instead of $\mathbf x \ge 0$?

  • 0
    Looks like least-squares with positivity constraint. I was about to write up on the three usual methods for solving least squares problems until I noticed the $\mathbf x \geq \mathbf 0$ part. I'll have to check on how the usual schemes are modified for finding positive solutions.2010-12-05
  • 0
    [This](http://dx.doi.org/10.1137/S1052623494240456) might have what you're looking for. I'm not posting this as an answer for now since I don't have access to the paper at the moment for me to substantially discuss this.2010-12-05
  • 4
    This is just quadratic programming. There are lots of classical algorithms available. Your particular instance is nice because the matrix involved is positive definite, and the constraints are all bound constraints. Some recent algorithms focus on such special cases, such as the one J.M. pointed to.2010-12-05
  • 2
    "the matrix involved is positive definite" - iff $\mathbf G$ has rank $n$; otherwise, it's positive semidefinite.2010-12-06
  • 0
    @J.M.: Whoops, you're right.2010-12-06
  • 0
    @J.M.: I still will be happy to get a clear answer instead of the specified link to some useful book.2010-12-06
  • 0
    Max, I'll write one when I find time to download and read the paper. I'm just pointing it out in the hope that somebody with access to the paper and/or is smarter than me can write something about it in the interim.2010-12-06
  • 1
    @Max: You haven't said whether you want (a) an analytical solution (there isn't one), (b) a numerical algorithm (there are many), (c) an *efficient* numerical algorithm ().2010-12-08

2 Answers 2