Minimize $\| Ax-b \|$

Question

$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?

Answer 1

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. $$

Answer 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.