Let $m,n\in\mathbb N$, $A\in\mathscr L(\mathbb R^n,\mathbb R^m)$, $b\in\mathbb R^m$ and define
$$f:\mathbb R^n\to\mathbb R,\quad x\mapsto \|Ax-b\|^2 $$
We're supposed to determine when this mapping is strongly convex. I think we can omit the translation and simply study $x\mapsto \|Ax\|^2$, instead. So, suppose it is strongly convex, we then start calculating..
$$\lambda \|Ax\|^2 + (1-\lambda)\|Ay\|^2 -\|\lambda Ax + (1-\lambda)Ay\|^2\\
=\lambda\|Ax\|^2 +(1-\lambda)\|Ay\|^2 – \left (\lambda ^2\|Ax\|^2 + (1-\lambda)\|Ay\|^2 + 2\lambda (1-\lambda)\langle Ax,Ay\rangle\right ) \\
= \lambda (1-\lambda ) \left ( \|Ax\|^2 + \|Ay\|^2 – 2\langle Ax,Ay \rangle\right ) = \lambda (1-\lambda )\|Ax-Ay\|^2 \overset{?}\geq \delta ^2\lambda(1-\lambda)\|x-y\|^2,$$
where $\delta >0$ is a fixed constant. For strong convexity it would then suffice that for every $x\in\mathbb R^n$
$$\|Ax\| \geq \delta\|x\| \implies \|A\|\geq \left\| A\frac{x}{\|x\|}\right\| \geq \delta.$$
At this point I'm confused. Are we done or can we specify how operator norm is controlled? Can we pick for every operator $A$ the constant $\delta>0$ such that strong convexity demand is satisfied?
Best Answer
$f$ is twice continuously differentiable. So $f$ is strongly convex if and only if the Hessian matrix $\nabla^2 f(x) \succ 0$ is positive definite for all $x$. You can compute the Hessian $\nabla^2 f(x) = 2A^TA$. It implies $f$ is strongly convex if $\text{Null}(A) = \{0\}$. So $A$ must be injective.