Normal Equations error bounds

Question

$A^TAx = A^Tb$
$A^TA\hat{x} = A^Tb + f$

where $\lVert f\rVert \leq cu\lVert A\rVert\lVert b\rVert$

Show that $\frac{\lVert x-\hat{x}\rVert}{\lVert x\rVert} \leq cuK(A)^2\frac{\lVert A\rVert\lVert b\rVert}{\lVert A^Tb\rVert}$

My approach was to use the fact that
$\lVert(A^TA)^{-1}A\rVert = \frac 1{{\sigma}_n(A)}$ and $K_2(A) = \frac {{\sigma}_1(A)}{{\sigma}_n(A)}$

But I always ended up cancelling $K$ from both numerator and denominator.

Are you sure there's $K(A)$ in the bound and not $K^2(A)$? – Algebraic Pavel Mar 21 '15 at 09:40 — Algebraic Pavel, Mar 21 '15 at 09:40
Oops that's a typo. I've corrected it. – Srinivas Eswar Mar 21 '15 at 11:16 — Srinivas Eswar, Mar 21 '15 at 11:16

Algebraic Pavel · Accepted Answer · 2015-03-21T22:00:51.360

1

From $A^TA(\hat{x}-x)=f$ and the assumption on $\|f\|$, we have $$\|\hat{x}-x\|\leq\|(A^TA)^{-1}\|\|f\|\leq cu\|(A^TA)^{-1}\|\|A\|\|b\|.$$ From $A^TAx=A^Tb$, we have $$\|A^TA\|\|x\|\geq\|A^Tb\|.$$ Combining the two, $$ \frac{\|\hat{x}-x\|}{\|x\|}\leq cu\|(A^TA)^{-1}\|\|A^TA\|\frac{\|A\|\|b\|}{\|A^Tb\|}=cuK^2(A)\frac{\|A^T\|\|b\|}{\|A^Tb\|}. $$

edited Mar 21 '15 at 22:00

answered Mar 21 '15 at 12:12

Algebraic Pavel

22,928

I have a question with regards to these inequalities. In order to preserve the <= or >= direction on multiplication we need to ensure that both equations are either >= |1| or <= |1|. How're we reasoning about that here? – Srinivas Eswar Mar 23 '15 at 15:03
@SrinivasEswar I'm not sure what do you mean. The first inequality follows from the submultiplicativity of the matrix norm and the assumption on $|f|$, the second again from the submultiplicativity. Then the two are simply combined and the final touch follows from $K(A)^2=|A^TA||(A^TA)^{-1}|$. – Algebraic Pavel Mar 23 '15 at 17:21

Normal Equations error bounds

1 Answers1