Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a vector-valued function given by $f(x) = \sqrt{1 + \|x\|^2_2}$. Show that the gradient of $f$ is Lipschitz continuous, in particular with Lipschitz constant $L = 1$.
I want to show this directly from $\|\nabla f(x) - \nabla f(y)\|_2 \leq \|x - y\|_2 \; \forall x, y \in \mathbb{R}^n$. However, the gradient of $f$ is not exactly very clean, and I get lost in the algebra. Is there a simpler way to do this that I'm missing?
I managed to show it for 1.1 - if we look at the Hessian we get:
$\nabla^2f(x) = \frac{1}{(1+x^Tx)^{3/2}} [(1+x^Tx)I - xx^T]$
So the 2-norm of the Hessian is:
$\begin{align} ||\nabla^2f(x)||_2 &= ||(1+x^Tx)^{-3/2} [(1+x^Tx)I - xx^T]||_2 \\ &\underset{triangle}{\le} (1+x^Tx)^{-3/2} [||(1+x^Tx)I||_2 + ||xx^T||_2]\\ &= \frac{1+2x^Tx}{(1+x^Tx)^{3/2}} \end{align}$
Where the inequality is the triangle inequality. This function is bounded by ~ $1.1$.
EDIT:
Here's a solution (that a classmate of mine found):
Notice that $||I +x^Tx I - xx^T||_2 = ||I + ||x||^2_2(I - \frac{1}{||x||^2_2}xx^T) ||_2$
Now, $\frac{1}{||x||^2_2}xx^T$ is an orthogonal projection into $x$. So $I - \frac{1}{||x||^2_2}xx^T$ is the orthogonal projection into the null space, i.e. it's 2-norm is less than or equal to 1.
So now:
$\begin{align} ||\nabla^2f(x)||_2 &= ||(1+x^Tx)^{-3/2} [I + ||x||^2_2(I - \frac{1}{||x||^2_2}xx^T)]||_2 \\ &\underset{triangle}{\le} (1+x^Tx)^{-3/2} [||I||_2 + ||x||^2_2||I - \frac{1}{||x||^2_2}xx^T||_2] \\ &\le \frac{1+x^T x}{(1+x^Tx)^(3/2)} = \frac{1}{\sqrt{1 + x^Tx}} \le 1 \end{align}$
