Let $A \in \mathbb{R}^{M\times N}$ and $z \in \mathbb{R}^M$. Consider $f : x \mapsto \Vert Ax -z \Vert$.
I have that $f$ is convex: $\Vert . \Vert$ is convex, and $x \mapsto Ax - z$ is affine. I am wondering if $f$ can be strictly convex, and if so, under which conditions.
Clearly if $A$ is not injective, $f$ is constant on $\ker A$ hence not strictly convex. If $z$ is in $\text {Im }\,A$, I can also show that $f$ is not strictly convex. However, I cannot deal with the general case: any suggestion?
I suppose that $\|\cdot\|$ denotes the Euclidean norm.
If $ker(A)=\{0\}$ and $z\not\in Im(A)$ then the function is actually strictly convex. First, we decompose $z$ orthogonally into $$ z = Ax_0 - z_0 $$ with $z_0 \in (Im(A))^\perp \setminus\{0\}$. Then it holds $$ \|Ax-z\|^2 = \|A(x-x_0)-z_0\|^2 = \|A(x-x_0)\|^2 + \|z_0\|^2, $$ and hence $$ f(x) = \sqrt{\|A(x-x_0)\|^2 + \|z_0\|^2}. $$ Let us test strict convexity with positive definiteness of the Hessian. The derivatives in directions $v$ and $(v,w)$ are $$ f'(x)v = \frac1{f(x)} v^TA^TA(x-x_0) $$ and $$ f''(x)(v,w) = \frac1{f(x)} v^TA^TAw - \frac1{f(x)^3} (v^TA^TA(x-x_0)) \cdot(w^TA^TA(x-x_0)). $$ This implies for $v\ne0$ and hence $Av\ne0$ $$ f''(x)(v,v) =\frac1{f(x)} \left(\|Av\|^2 -\frac{ (v^TA^TA(x-x_0)) ^2 }{f(x)^2}\right) \ge\frac{\|Av\|^2}{f(x)} \left(1 -\frac{ \|A(x-x_0)\| ^2 }{f(x)^2}\right) >0. $$ Hence the Hessian of $f$ is positive definite everywhere, implying the strict convexity in the missing case $ker(A)=\{0\}$ and $z\not\in Im(A)$.