Q10 2018

Hey,
how can the bound for the L_i=\norm(a_i)^2 be obtained? I tried to apply triangle inequality...
Thank you.

Top comment

Triangle inequality is the right thing to do here :
\(f(x + \gamma e_i) = \frac{1}{2} ||Ax-b + \gamma a_i||^2 \leq \frac{1}{2} ||Ax-b||^2 + \frac{||a_i||^2}{2} \gamma^2 \)
where we found \( a_i \) thanks to \( a_i = Ae_i \).
By identification (equation 10.5 page 183 of the notes) : \( L_i = ||a_i||^2 \)

Thank you very much, "anonymous" for helping to answer questions! Much appreciated.

Aren't we missing the gradient though?

So sorry I don't understand your question..

When applying the triangle inequality, we only have two terms. However, equation 10.5 has three terms, where one of them is a gradient. How can we affirm the coordinate-wise smoothness is ||a_i||^2 if we're missing this gradient in our inequality?

And my bad, it wasn't clear! :)

It is indeed not complete. Sorry for that! You can use
\( f(x+\gamma e_i) = \frac{1}{2} ||Ax - b + \gamma a_i||^2 = \frac{1}{2} ||Ax-b||^2 + 2\gamma a_i^T(Ax-b) + \frac{||a_i||^2}{2}\gamma^2 \)

Oh I see! Thank you very much!

Page 1 of 1

Add comment

Post as Anonymous Dont send out notification