8
$\begingroup$

Assume standard inner product and 2-norm. $A$ is any symmetric real-valued $n\times n$ square matrix. $V_k$ is an $n\times k$ matrix whose columns are orthonormal. $T_k$ is a matrix such that it has the following relation with $A$ and $V_k$:

$AV_k=V_kT_k+{\hat v}_{k+1}e_k^T$

where ${\hat v}_{k+1}$ is another vector orthogonal to every column of $V_k$, and $e_k^T = (0,...,0,1)$ is a vector with only the $k$th component being 1. I need to understand the following proof, but got stuck at an inequality. This is a proof about the error bound of Lanczos iteration.

enter image description here enter image description here

Above proof uses

enter image description here

In order to apply Cauchy-Schwarz, which is $<x,y>\le \|x\|\|y\|$, we need to place absolute value operator on both the LHS and RHS of (10.26), but I have trouble understanding how the LHS of (10.26) becomes the LHS of (10.27). Many thanks!


PS: the whole thing for those who are interested. the theorem in question is the last one.

enter image description here enter image description here enter image description here

$\endgroup$
  • $\begingroup$ Note: we can only break $A$ up into a linear combination of orthogonal projection matrices if $A$ is symmetric. I am guessing this assumption has been forgotten either by you or the author $\endgroup$ – Omnomnomnom Jul 7 '17 at 14:05
  • $\begingroup$ @Omnomnomnom Yes. That is my fault. I added this assumption. Thanks! $\endgroup$ – River Jul 7 '17 at 14:08
  • $\begingroup$ Also, the result is certainly believable if $\lambda_i > \lambda$ for all $i$ or if $\lambda_i < \lambda$ for all $i$, but otherwise that step on the LHS requires explanation. $\endgroup$ – Omnomnomnom Jul 7 '17 at 14:09
  • 1
    $\begingroup$ @Omnomnomnom $\left| {\sum\limits_{i = 1}^m {({\lambda _i} - \lambda ){{\left\| {{P_i}({V_k}y)} \right\|}^2}} } \right| \ge \left| {\sum\limits_{i = 1}^m {\min \left| {{\lambda _i} - \lambda } \right|{{\left\| {{P_i}({V_k}y)} \right\|}^2}} } \right| \ge \min \left| {{\lambda _i} - \lambda } \right|\left| {\sum\limits_{i = 1}^m {{{\left\| {{P_i}({V_k}y)} \right\|}^2}} } \right| \ge \min \left| {{\lambda _i} - \lambda } \right|{\left\| {\sum\limits_{i = 1}^m {{P_i}({V_k}y)} } \right\|^2} = \min \left| {{\lambda _i} - \lambda } \right|{\left\| y \right\|^2}$ $\endgroup$ – River Jul 7 '17 at 14:27
  • 2
    $\begingroup$ @River are you still confused about this? It looks like your comment provides the missing step. $\endgroup$ – jschnei Jul 9 '17 at 15:51
4
+500
$\begingroup$

The formula (10.26) says $$\langle (A-\lambda)V_ky,V_ky\rangle = \langle e_k,y\rangle \langle \hat{v}_{k+1},V_ky\rangle$$ Remembering (10.25), the angle between $(A-\lambda)V_ky$ and $V_ky$ is the same as the angle between $\hat{v}_{k+1}$ and $V_ky$, (the book does not say that this is fundamental for deriving (10.27)) so: $$\lVert(A-\lambda)V_ky\rVert \lVert V_ky\rVert = \langle e_k,y\rangle \lVert \hat{v}_{k+1}\rVert\lVert V_ky\rVert$$ For Cauchy-Schwartz applied to the first part of the rhs $$\langle e_k,y\rangle \le \lVert y\rVert$$

As to the lhs, remember that the 2-norm of a symmetric real-valued matrix $A$ is $$\lVert A\rVert=\max\limits_i \lvert \lambda_i\rvert$$ The 2-norm of its inverse, when A is non-singular, is then $$\lVert A^{-1}\rVert=1/\min\limits_i \lvert \lambda_i\rvert$$ So it is (this is an important bound formula, not mentioned in the book, rearranged for our purpose) $$\frac{\lVert(A-\lambda) V_ky\lVert}{\lVert V_ky\rVert} = \frac{\lVert(A-\lambda) V_ky\lVert}{\lVert (A-\lambda)^{-1}(A-\lambda)V_ky\rVert} \ge \frac{\lVert(A-\lambda) V_ky\lVert}{\lVert (A-\lambda)^{-1}\rVert\lVert(A-\lambda)V_ky\rVert} = \min\limits_i \lvert \lambda_i-\lambda\rvert$$ It now follows (10.27), that is $$\min\limits_i \lvert \lambda_i-\lambda\rvert \lVert V_ky\rVert^2 \le \lVert y\rVert \lVert \hat{v}_{k+1}\rVert\lVert V_ky\rVert$$

Let me know whether you need any futher explanation. And don't worry, I will not claim the 500 reputation bounty valid when I first answered.

$\endgroup$
  • $\begingroup$ Thanks a lot for your help. Sorry for the delay. I was traveling. At a quick look I think you are right. I will comment if I still have question :) $\endgroup$ – River Jul 16 '17 at 13:27
2
$\begingroup$

I think it is a typo and the author meant to use $\max$ instead of $\min$.

$$\sum_\limits{i=1}^m (\lambda_i-\lambda)\vert P_i(V_ky)\vert^2$$ $$\le \sum_\limits{i=1}^m \vert(\lambda_i-\lambda)\vert\vert P_i(V_ky)\vert^2$$ $$\le \sum_\limits{i=1}^m\max\vert\lambda_i-\lambda\vert\vert P_i(V_ky)\vert^2$$ $$= \max_\limits{1\le i \le m}\vert\lambda_i-\lambda\vert\sum_\limits{i=1}^m\vert P_i(V_ky)\vert^2$$ $$\le \max_\limits{1\le i \le m}\vert\lambda_i-\lambda\vert\lVert V_ky\rVert^2$$

This works effortlessly, and any version with $\min$ appears to be false.

$\endgroup$
  • $\begingroup$ please, consider reading my proof $\endgroup$ – trying Jul 15 '17 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.