Lipschitz constant of $\|Ax-b\|_2^2$ and $A^T(Ax-b)$

Question

The Lipschitz constant $L$ of a function $f$ is defined as follows

$$\| f(y) - f(x) \|_2 \leq L \|y-x\|_2$$

I want to find the Lipschitz constants for the following functions:

$$f_1(x) = \|Ax-b\|_2^2$$

$$f_2(x) = A^T (Ax-b)$$

where $A \in \mathbb{R}^{m \times n}, x \in \mathbb{R}^n, b\in\mathbb{R}^m$.

Any help?

Answer 1

By definition, a Lipschitz function can have at most linear growth at infinity: $\|f(x)\|=O(\|x\|)$ as $\|x\|\to\infty$. Since $f_1$ grows quadratically, it is not a Lipschitz function.

For $f_2$, note that $$\|f_2(x)-f_2(y)\| = \|A^TA(x-y)\| \le \|A^TA\| \|x-y\|$$ and the inequality is sharp by the definition of the operator norm. Thus, the Lipschitz constant of $f_2$ is $\|A^TA\|$ (which further simplifies to $\|A\|^2$, reference).