4

$A$ is a $n \times m$ matrix with known real elements and $b$ is a known real $n$-dimensional vector.

I would like to find all $x$ such that $\| Ax-b \|$ is a minimum.

Is there a theorem that deals with it?

Update: What changes if we add the constraint that all $x$'s coordinates must be positive reals?

Sangchul Lee
  • 167,468
tchronis
  • 143
  • 1
  • 1
  • 6
  • 2
    This is called "least-squares approximation/regression/solution". Googling any of those terms will give you lots of info. – Alex Becker Mar 24 '14 at 19:56
  • meanwhile, standardized methodology used in the setting of Kalman filters, so, books on that... – Will Jagy Mar 24 '14 at 20:02
  • What do you mean by $bI$? Is it a matrix or a vector? Also is $x$ a matrix or a vector (according to how you define $bI$). – user2566092 Mar 24 '14 at 20:03
  • Thank you all for your answers. I have updated the question as I need solutions for x coordinates positive. – tchronis Mar 25 '14 at 19:47

2 Answers2

7

You want to minimize $$ |Ax-b|^2 = (Ax-b)^t (Ax-b) = x^t A^t A x - 2 x^t A^t b + |b|^2 $$ derive to obtain $$ 2 A^t A x - 2A^t b = 0 $$ which gives $$ x = (A^t A)^{-1} A^t b. $$

Emanuele Paolini
  • 21,447
2

The vector x is given by $$x=(A^{T}A)^{-1}A^{T}b$$ As suggested by commentators, read up on least-squares approximations.

user137500
  • 645