How reliable is the linear problems like $ \min \|Ax - b\|^2$?

Question

The following linear optimization is common used

$$\min_x \|Ax - b\|^2$$

Here, $A$ is the matrix; $x,b$ are the vectors. I am curious about how reliable is the solution $x$ by solving above optimization.

For example, if I add some very small noise to $A$ with $\delta(A)$ and $B$ with $\sigma(b)$. The new optimization is

$$\min_y \|(A+ \delta(A))y - (b+ \sigma(b))\|^2$$

then the solution $y$ can be solve by solving above objective.

---

My question is how difference between $x$ and $y$ due to the small noise on the $A$ and $B$?

Any refernce to reliability of linear equation?

Thanks a lot

Answer 1

We call the error here the backward error.

Suppose that $x$ solves $\min ||Ax-b||^2$, and $x^{*}$ solves $\min ||(A+\delta A)x-(b+\sigma b)||^2$.

We are interested in quantifyig the error $\Delta x = x^{*} - x$. Usually what we do if look at the errors individually, i.e. find the error coming from the pertubation $\delta A$ in $\Delta x$, and then for $\sigma b$ and sum them. So let us look at $\delta A$.

We know that $x$, $x^{*}$ solve the normal equations:

$x = (A^T A)^{-1} A^T b$,

$x^{*} = (((A+\delta A)^{T} (A+\delta A))^{-1} (A+\delta A)^T b$

So $(A+\delta A)^T (A + \delta A)x^{*} - A^T A x = \delta A^T b$

So $A^T A (x^{*}-x) = \delta A^T b - A^T \delta A x^{*} - \delta A ^TAx^{*}-\delta A^T \delta A x^{*}$.

Then very roughly: $||A^T A|| * ||\Delta x|| \leq \delta ||A^T b||+ \delta ||A^T A||*||x^{*}||+\delta^2 ||A^TA|| * ||x^{*}||$.

So you can see the error as a function of your input $\delta$. We would neglect second order terms in $\delta$.

As mentioned Golub is the go to text on this topic.

Answer 2

Your problem has been discussed in the book "Matrix Computations" by Golub and van Loan (http://web.mit.edu/ehliu/Public/sclark/Golub%20G.H.,%20Van%20Loan%20C.F.-%20Matrix%20Computations.pdf).

Let us assume that the equation system is overdetermined and the length $n$ of $x$ is smaller than the length of vector $b$. If we consider the solution using the normal equations we have the solution $x^\star = (A^T A)^{-1} A^T b$.

The reliability of a computed solution depends on the matrix $A$.

Let ${\rm rank}(A)< n $ then we run probably into numerical problems as the matrix $(A^T A)^{-1} $ has the same rank as $A$. Moreover, numerical problems are expected when the condition number of $A$ is in the region of $1/u$, where $u$ is the machine precision.