Matrix Norm Inequalities and Linear Least Squares

Question

I am working through one of my universities old QUALS and came across the following problem:

Let $A,E\in \mathbb{C}^{m\times m}$. Suppose that $\sigma_\min>0$ is the smallest singular value of $A$ and $\|E\|<\sigma_\min$ where $\| \|$ is the matrix 2 norm.

a) Prove that $\|A^{-1}E\|<1$ and $A+E$ is invertible.

b) Let $b\in\mathbb{C}^{m}$. Suppose that $x\in\mathbb{C}^{m}$ is the solution to $Ax=B$ and $y$ is the solution to $(A+E)y=b$. Prove

$$\frac{\|x-y\|}{\|y\|}\leq \frac{1}{1-\frac{\|E\|}{\sigma_\min}}(\|A\|\|A^{-1}\|)\frac{\|E\|}{\|A\|}$$

Now, this is where I have gotten in both parts.

a) I know how to prove the first part; that is $\|A^{-1}E\|<1$ by using the fact that $\|A^{-1}\|=\frac{1}{\sigma_\min}$. However, I am lost on how to prove $(A+E)$ is invertible. I started with

$$(A+E)^{-1}=((I+EA^{-1})A)^{-1}=A^{-1}(I+EA^{-1})^{-1}$$

Since we know A is invertible, then to prove that $A+E$ is invertible we only need to show that $(I+EA^{-1})^{-1}$ is invertible. But this is where I got stuck. I did some research and found a theorem that uses the fact that $\|A^{-1}E\|<1$ to prove this however, the proof does not make sense. If someone could help me proving $(I+EA^{-1})^{-1}$ is invertible that would be great!

b) After some matrix manipulation and cancellations I came up with trying to prove that

$$\|I-(I+EA^{-1})^{-1}\|\leq \|(I-A^{-1}E)^{-1}\|\|A^{-1}E\| \tag{**}$$

then the initial inequality would hold true. What am I missing to prove (**)?

Any help would be great!

Answer 1

Let $x,y,b \in \mathbb{C}^m$ be such that $Ax=b$ and $(A+E)y=b$. Take also $\alpha = \frac{\|E \|}{\sigma_{min}}$.

a) First, note that $$\tag{1} \|A^{-1} E\| \leq \overbrace{\underbrace{\|A^{-1}\|}_{=1/\sigma_{min}} \underbrace{\|E\|}_{<\sigma_{min}}}^{=\alpha} < 1$$ Taking $B=-A^{-1} E$, we can write $$\tag{2}A+E=A(I-B)$$ Hence, to prove that $A+E$ is invertible, knowing that $A$ is invertible, it suffices to prove that $(I-B)$ is invertible. To this end, we resort to the following theorem:

Theorem 1 (Neumann Series)
Let $\|\cdot\|$ be a submultiplicative norm such that $\\\|I\|=1$ and $\|X\|<1$. Then $(I-X)^{-1}$ exists and $$(I-X)^{-1}=\sum_{j=0}^\infty{X^j}.$$

Noting that $\| B \| = \| A^{-1} E \| \leq \alpha <1$ and that $\| \cdot \|_2$ satisfies all the theorem's requirements, we then have that $(I-B)$ is invertible, and we conclude that $(A+E)$ is invertible.

b) Having proven that $A+E$ is invertible, we can write

$$y = (A+E)^{-1}b = (I-B)^{-1} \overbrace{A^{-1}b}^{=x} \; \mathop = \limits^{\text{Th.1}} \; (I+B+B^2+\ldots) \, x = x + B(I+B+B^2+\ldots)x$$

$$\tag{3} \Rightarrow x-y = -B \left( \sum_{j=0}^\infty{B^j} \right) x$$

From (3), we get $$ \| x-y \| \leq \|B\| \left\| \sum_{j=0}^\infty{B^j} \right\| \|x\| \leq \|B\| \sum_{j=0}^\infty{\|B\|^j} \|x\| \leq \| A^{-1} \| \|E\| \|x\| \overbrace{\sum_{j=0}^\infty{\alpha^j}}^{=\frac{1}{1-\alpha}}$$

$$\Rightarrow \frac{\| x-y \|}{\|x\|} \leq \| A^{-1} \| \|E\| \frac{1}{1-\alpha} = \frac{1}{1-\alpha} \left( \|A\| \|{A^{-1}}\| \right) \frac{\|E\|}{\|A\|}$$