First let me give the following definition and some tools that may be useful:
If $A$ is $m \times n$ matrix with rank $n$, we know that $A^* A$ is a nonsingular $n \times n$ matrix, and in this case there is exactly one least-squares solution; it is determined uniquely by solving the nonsingular $n \times n$ system of normal equations: $$A^*Ax = A^*b$$ where $A^*A$ is Hermitian and positive definite as well.
Given that $A$ is an $m \times n$ matrix with $m>n$ and has rank $n$, we will consider the normal equations approach for solving the least square problem $Ax=b$. My question is:
Suppose $A^TAx = A^Tb$ and $A^TA\hat{x} = A^Tb + c$ with $\|\ c \|_2 < \epsilon$, show $$\dfrac{\|\ x - \hat{x}\|_2}{\|\ x \|_2} \leq \dfrac{ \epsilon \|\ A \|_2^2 \|\ (A^TA)^{-1} \|_2 }{\|\ A^T b \|_2 }$$
Set $\|\ \cdot \|\ := \|\ \cdot \|_2$ for simplicity. Now, since $A^TAx = A^Tb$ and $A^TA\hat{x} = A^Tb + c$ with $\|\ c \| < \epsilon$, we have that \begin{align*} A^TAx - A^TA\hat{x} = -c &\iff A^TA(x - \hat{x}) = -c \\ &\iff \|\ A^TA(x - \hat{x}) \| = \|\ c \| \\ &\iff \|\ A^TA \| \|\ x - \hat{x} \| < \epsilon \end{align*} Then, since $x = (A^TA)^{-1}A^Tb$, we have that $\|\ x \|\ = \|\ (A^TA)^{-1}A^Tb \|\ $, so that $$\dfrac{1}{\|\ x \|} = \dfrac{1}{\|\ (A^TA)^{-1}A^Tb \|\ }$$ Putting this together we have that $$ \dfrac{ \|\ A^TA \| \|\ x - \hat{x} \| }{\|\ x \|\ } < \dfrac{ \epsilon }{\|\ (A^TA)^{-1}A^Tb \|\ } \iff \dfrac{ \|\ x - \hat{x} \| }{\|\ x \|\ } < \dfrac{ \epsilon }{ \|\ A^Tb \|\ }$$
I'm going wrong somewhere, any help would be appreciated.
First, solve both equations for x and $\hat{x}$, then plug these into $\frac{||x-\hat{x}||}{||x||}$.
$x = A^{-1}b$ and $\hat{x} = A^{-1}b + (A^TA)^{-1}c$.
This gives $\frac{||x-\hat{x}||}{||x||} = \frac{||(A^TA)^{-1}c||}{||A^{-1}b||} \leq \frac{||(A^TA)^{-1}||||c||}{||A^{-1}b||}\leq \epsilon\frac{||A||^2}{||A||^2}\frac{||(A^TA)^{-1}||}{||A^{-1}b||} $
Then use that $||A||^2 = ||A^TA||$ and $||A^TA||||A^{-1}b|| \geq ||A^TAA^{-1}b|| = ||A^Tb||$.
The rest has been left as an exercise for the reader ;)