Consider computing the least squares solution in $x$:
$$
\text{min}.~\|Ax – b\|^2,
$$
when $A$ is an $m \times n$ matrix, and $b$ is a column vector. Let's suppose we now switch exactly one row of $A$ and $b$ (the same row) to obtain $A', b'$ and re-solve this problem. Can we say anything about how far these two solutions are?
More specifically, let
$$
x_\ast \in \arg\min_x \|Ax – b\|^2 \quad \text{and} \quad
x_\ast' \in \arg\min_x \|A'x – b'\|^2
$$
Let's also assume that each row of $A$ and $A'$ has norm bounded by some constant $C$ and each entry of the vector $b$ and $b'$ is bounded (in absolute value) by some constant $c$.
Is it possible to give a bound on $\|x_\ast – x_\ast'\|$ as a function of $m, n, c, C$?
Best Answer
You can use the matrix inversion lemma, in particular the special case of a rank 1 update:
$$ (A + uv^T)^{-1} = A^{-1}-\frac{A^{-1} u v^{\top} A^{-1}}{1+v^{\top} A^{-1} u}$$
Actually, you probably want to use a generalisation of this Lemma that uses the Moore-Penrose-Pseudoinverse. This was discussed over at mathoverflow: cf. https://mathoverflow.net/q/146831/107094 one answer points to this paper which provides the formula, but there is a bit of ugly case distinction involved... In any case, the important takeaway is that the formula will look like $(A+uv^T)^+ = A^+ +\Delta$. According to the paper, $\Delta$ will be obtained from sums and products of $A, A^+, u, v$ and their conjugate transposes.
Then, since the solution of the Least Squares problem $\min_x \|Ax-b\|_2^2$ is given as $x_*=A^+ b$ - note that often given formula $x=(A^{T}\!A)^{-1}A^T b$ does not work when $A^{T}\!A$ is singular - the difference between the perturbed solution $x_*' = \arg\min \|(A+uv^T)x - (b+\delta)\|_2^2$ and unperturbed solution is
$$\begin{aligned} \|x_*' - x_*\| &= \|(A+uv^T)^+(b+\delta) - A^+b \| \\&= \|(A^+ +\Delta)(b+\delta) - A^+b \| \\&=\| A^+\delta + \Delta(b+\delta)\| \\&\le \|A^+\|\cdot\|\delta\| + \|\Delta\|\cdot\|b+\delta\| \\&\sim \|A^+\|\cdot\|\delta\| + \|\Delta\|\cdot\|b\| \end{aligned}$$