Minimizing $ \langle (Ax -b ), (Ax -b ) \rangle $

Question

I want to find vector $x$ that minimizes $ \langle (Ax -b ), (Ax -b ) \rangle $ namely minimizes the inner product of the error $(Ax -b )$ with itself. Is it possible to do so even if I don't have the exact definition of the inner product function $\langle ., . \rangle $ and I just know it satisfies the rules of an inner product function ? The $n \times n $ matrix A is known and so the n dimentional vector $b$

Answer 1

Because you're discussing matrices and vectors, I'll assume that this is an inner product over $\Bbb R^n$. A similar line of reasoning can be applied for the case of $\Bbb C^n$.

Every inner product over $\Bbb R^n$ can be written in the form $\langle x,y \rangle = x^TPy$ for some (symmetric) positive definite matrix $P$. Given such a $P$, write $P$ in the form $P = M^TM$ (this can be done using a Cholesky decomposition for instance). Our goal is to minimize the quantity $$ \begin{align} \langle Ax-b,Ax - b \rangle &= (Ax - b)^TP(Ax - b) \\ & = (Ax - b)^TM^TM(Ax - b) \\ & = [M(Ax - b)]^T[M(Ax - b)] = (MAx - Mb)^T(MAx - Bb). \end{align} $$ However, minimizing this quantity simply amounts to the usual least squares. That is, we are simply looking for the least-squares solution, relative to the standard inner product, of $MAx = Mb$. Thus, $x$ is a solution to the problem iff it satisfies $$ (MA)^T(MA)x = (MA)^TMb \implies\\ A^T(M^TM)Ax = A^T(M^TM)b \implies A^TPAx = A^TPb. $$ So, it turns out that we didn't need the decomposition of $P$ after all!

If $A$ has linearly independent columns, then the unique minimizer is given by $$ x = (A^TPA)^{-1}A^TPb. $$ In the more general case, one such minimizer can be found via the Moore-Penrose pseudoinverse. In particular, one solution is $x = (A^TPA)^+A^TPb$.