# Lipschitz Continuity of $\sqrt{1 + \|x\|^2_2}$ [duplicate]

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?

• Maybe a direct computation of the gradient and looking for an upper bound... Commented Feb 14, 2020 at 2:52
• did you ever solve this? Commented Apr 28, 2020 at 10:21
• Haven't solved it from the direct definition of Lipschitz continuity. Commented Apr 29, 2020 at 16:40
• @JoonasIlmavirta Why do you vote for this question as a duplicate? The question you linked was asked after this question here.
– Jan
Commented May 1, 2020 at 5:46
• @Jan The order doesn't matter. Considering both questions and their answers, which one is a better representative of the topic? That's all that matters, and I understand if there are different opinions. Commented May 1, 2020 at 6:52

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}

• I think the triangle inequality is probably too weak here, and hence leads to a bound of 1.1 Commented Apr 29, 2020 at 16:36
• @rw435 yeah, got something better? :-) Commented Apr 29, 2020 at 19:16
• @rw435 check the update Commented Apr 30, 2020 at 9:34
• Hi @MaverickMeerkat, can you please elaborate on the last part of your answer? Regarding the projections etc. Is there another explanation, maybe? Commented Apr 22, 2021 at 15:57