Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the "User's guide to viscosity solutions" by Crandall, Ishii and Lions (link), they make the following claim (inequality (A.4) p. 58) :

Given $x$, $\xi$ $\in \mathbb{R}^n$, $A \in \cal{S}(n)$ (space of symmetric $n \times n$ matrices) , for all $\varepsilon >0$, the Cauchy-Schwarz inequality yields

$$\langle Ax,x \rangle \leq \langle (A+\varepsilon A^2) \xi,\xi \rangle+\left(\frac{1}{\varepsilon} + \|A\|\right)|x-\xi|^2,$$

where I guess $\|A\|$ is the spectral radius of $A$.

I have tried without success to prove this inequality and would appreciate some help.

share|improve this question

2 Answers 2

up vote 11 down vote accepted

So first of all I will use $y$ instead of $\xi$ because I love my eyes and I will use $e$ for $\varepsilon$ because it is simpler to type. I hope you don't get offended by that.

I think they use some sort of a triangle inequality of the form, $\|x-y\| + \|y\| \geq \|x\|$ and $x^TAx\leq\lambda_{max}x^Tx$. But I couldn't see it and I doubt that C-S is needed anyway. Let's do the dirty work, take the LHS to the right and denote that expression with $(\star)$, then: $$\begin{align} (\star) &\geq -x^TAx +y^T(A+e A^2)y+(x-y)^T\left(\frac{1}{e}I + A \right)(x-y) \\ &=y^T(A+e A^2)y+(x-y)^T\frac{1}{e}I(x-y) + y^TAy - 2x^TAy\\ &=y^TA(I+e A)y+y^TAy + \frac{1}{e}y^Ty-2\frac{1}{e}x^Ty+\frac{1}{e}x^Tx-2x^TAy\\ &=y^TA(I+e A)y + y^T(\frac{1}{e}I+A)y -2x^T(\frac{1}{e}I+A)y + \frac{1}{e}x^Tx\\ &= \frac{1}{e}y^T(I+e A)^2y -2\frac{1}{e}x^T(I+eA)y + \frac{1}{e}x^Tx\\ &=\frac{1}{e}\|x-(I+eA)y\|^2\\ &\geq 0 \end{align} $$

To be honest, this type of math snobbery makes me sick. Maybe there is a direct argument using C-S inequality. Then it would be shorter than this so why not including it in the document. But anyway, hope it helps.

EDIT: by the way the norm definition is given on page 17.

share|improve this answer
    
Thanks, this looks good. I will wait a bit to see if someone finds a shorter proof with C-S before accepting your answer. –  pgassiat Sep 14 '11 at 19:42
    
You're welcome. –  user13838 Sep 14 '11 at 19:50
2  
I think calling it "snobbery" is unfair. I also don't see how the inequality follows from Cauchy-Schwarz, and it would certainly have been nice if the authors included more explanation. But I presume they found such arguments routine, and expected (mistakenly, it seems) that the reader would too. I think Hanlon's razor applies here. –  Nate Eldredge Sep 15 '11 at 14:59
1  
@Nate : It is not the omission of the derivation but the style of skipping it drives me nuts. They don't even say from where C-S yields this expression. It just goes "...If $\epsilon > 0,$ the Cauchy-Schwarz inequality yields..."! Ingenuity and novelty can not be an excuse for horrible style choices. –  user13838 Sep 15 '11 at 15:10
1  
+1 for not using $\xi$ because you love your eyes. –  Tyler Sep 16 '11 at 18:34

I only post this answer since you asked how to prove this using the Cauchy–Schwarz inequality. Here's the best argument I could come up with (and there's not much difference to percusse's argument, of course).

Write $B = \varepsilon A$ and multiply the inequality by $\varepsilon \gt 0$ to get $\DeclareMathOperator{\eps}{\varepsilon}$ $$\langle Bx,x \rangle \leq \langle (B+B^2)\xi,\xi \rangle + (1 + \|B\|)\, \|x - \xi\|^2.$$

Now estimate using the symmetry condition $\langle Sy,z\rangle = \langle y, Sz\rangle = \langle Sz,y\rangle$ several times $$\begin{align*} \langle Bx, x\rangle &\leq \langle Bx, x\rangle + \|(1+B)\xi - x\|^2 \\ %&= %\langle Bx, x\rangle+ %\|(1+B)\xi\|^2-2\langle(1+B)\xi,x\rangle +\|x\|^2\\ &= \color{green}{\langle Bx, x\rangle}+ \color{red}{\langle (1+B)\xi,\xi\rangle}+ \color{blue}{\langle(1+B)\xi,B\xi\rangle}- \color{red}{2\langle(1+B)\xi,x\rangle}+\color{green}{\langle x,x\rangle} \\ &=\color{blue}{\langle(B+B^2)\xi,\xi\rangle}+ \color{red}{\langle(1+B)\xi,\xi-x\rangle}- \color{red}{\langle(1+B)\xi,x\rangle}+ \color{green}{\langle(1+B)x,x\rangle} \\ &=\langle(B+B^2)\xi,\xi\rangle+ \langle(1+B)(\xi-x),\xi\rangle -\langle(1+B)(\xi-x),x\rangle \\ &=\langle(B+B^2)\xi,\xi\rangle + \langle (1+B)(\xi-x),\xi-x\rangle. \end{align*}$$ Now we are in position to apply the Cauchy–Schwarz inequality: $$\langle(1+B)(\xi-x),\xi-x\rangle \leq \|(1+B)(\xi-x)\|\,\|\xi-x\|.$$ Using $\|(1+B)(\xi-x)\| \leq \|1+B\|\,\|\xi-x\| \leq (1+\|B\|)\|\xi-x\|$ by definition of the operator norm, we get $$\langle Bx,x\rangle \leq \langle(B+B^2)\xi,\xi\rangle + (1+\|B\|)\,\|\xi-x\|^2,$$ as desired.

share|improve this answer
    
+1 for the effort went into coloring, it makes a huge difference. –  user13838 Sep 16 '11 at 15:12
    
Thanks, but coloring is not a big deal, just insert \color{xxx}{...} where xxx is the color you like and ... the formula you want to paint by that color :) But yes, I agree, it sometimes helps increasing the readability... –  t.b. Sep 17 '11 at 0:12
    
Thanks for the reply. I still have to agree with percusse about the way this was poorly worded. Basically since C-S is used only in a completely trivial way after having done most of the work, I feel like had they written "straightforward computations show that...", I would have not spent a decent amount of time trying to find a clever trick to get a 2-line proof (that may or may not exist). –  pgassiat Sep 18 '11 at 11:29
1  
@pgassiat: I agree that it could have been phrased in a clearer way (simply say what one has to add on the left hand side), but I disagree that it is snobbery. Be a bit charitable with the authors: when you have spent long enough doing the same computations over and over again you simply don't see anymore that things that are obvious routine to you are not obvious and routine to others. It is extremely hard to write up things homogeneously in difficulty. Maybe they just thought that hinting at CS makes it clear enough what one has to do. –  t.b. Sep 18 '11 at 11:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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