coerciveness of $\|Hx - y\|_2^2 + R(x)$ where $R$ convex

Question

Let $x \in \mathbb{R}^d$, $y \in \mathbb{R}^m$, $H \in \mathbb{R}^{m,d}$ and $R$ proper, convex and lower-semicontinuous. What do we require $H$ to fulfill in order for

$$x \mapsto \|Hx - y\|_2^2 + R(x)$$

to be coercive? If $H = I$, then this map is the proximal operator which, famously, indeed is coercive.

There was a similar question: Why does $f:\mathbb{R}^n\rightarrow\mathbb{R}\cup\{\infty\}$ closed, proper, convex imply that $f(x)+\|Ax-b\|^2$ attains a minimum?

More precisely, if let's say $H$ is invertible, does this imply that the function above is coercive?

Answer 1

This seems to be variation on the map $x \mapsto \|x - y\|_2^2 + R(x)$, which is vital in the definition of the prox operator. If you're abreast of this stuff, you'll know that the chain of logic involved begins with showing $\|x - y\|_2^2$ is supercoercive, not just coercive. A function $f$ is supercoercive if $$\lim_{\|x\| \to \infty} \frac{f(x)}{\|x\|} = \infty.$$ What's nice about supercoercive functions is that they're coercive, but also that they're stable under the addition of convex functions, i.e. $f + g$ is supercoercive if $f$ is supercoercive and $g$ is convex. Thus, $\|x - y\|_2^2 + R(x)$ is supercoercive and convex, thus coercive and convex, and hence has a unique minimum.

That's what we need here: we need $\|Hx - y\|_2^2$ to be supercoercive, which happens if and only if $H$ has full column rank. Essentially, I am claiming that the following are equivalent:

1. $H$ has full column rank,
2. $x \mapsto \|Hx - y\|^2_2$ is supercoercive,
3. $x \mapsto \|Hx - y\|^2_2 + R(x)$ is supercoercive for all proper, convex, lsc $R$,
4. $x \mapsto \|Hx - y\|^2_2 + R(x)$ is coercive for all proper, convex, lsc $R$.

Clearly, 2 implies 3 and 3 implies 4. If we assume 1, then $H^\top H$ and hence $\sqrt{H^\top H}$ are positive definite, and $$\|Hx\|_2^2 \ge \sigma^2 \|x\|^2$$ where $\sigma > 0$ is the least eigenvalue of $\sqrt{H^\top H}$. We therefore have, $$\lim_{\|x\|_2 \to \infty} \frac{\|Hx\|_2^2}{\|x\|_2} \ge \lim_{\|x\|_2 \to \infty} \sigma^2\|x\|_2 = \infty,$$ thus $\|Hx\|^2_2$ is supercoercive. We then have $$\|Hx - y\|^2_2 = (Hx - y)^\top(Hx - y) = \|Hx\|^2_2 - y^\top H x - x^\top H^\top y + \|y\|^2_2,$$ i.e. $\|Hx - y\|^2_2$ is just the sum of a supercoercive function $\|Hx\|_2^2$ and an affine function, and hence is supercoercive. Thus 1 implies 2.

To finally show that 4 implies 1, we assume the negation of 1. If $H$ does not have full column rank, then some non-zero $x_0 \in \Bbb{R}^d$ exists such that $Hx_0 = 0$. Then, taking $R(x) \equiv 0$, we get $$x \mapsto \|Hx - y\|^2_2 + R(x) = \|Hx - y\|^2_2$$ which is not coercive, as $x = \lambda x_0$ for $\lambda \to \infty$ yields $\|y\|_2^2$ constantly, which does not blow out to $\infty$. Thus we have the negation of 4, and all four conditions are equivalent.

One could get bogged down further in the weeds here. Could we adjust our assumptions on $R$ to compensate for a non-trivial nullspace of $H$? We would need $R$ to be coercive in the non-trivial directions in the nullspace of $H$. But let's not get into that here $-$ I think this answers the question satisfactorily.