Sensitivity of least squares solution to a data point change 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$?

 A: 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}$$
