# Looking for a function such that

Let $$M\in\mathbb{R}^{n\times n}$$ and $$y\in\mathbb{R}^n$$. We define $$l:\,\mathbb{R}^n\to\mathbb{R}$$ by $$x\mapsto ||Mx-y||^2_2$$. Now I´m looking for a a function $$f:\,\mathbb{R}_{\geq 0}\to\mathbb{R}$$, which satisfies $$f(||x||_2)\leq l(x)$$. In addition $$f$$ should be monotone increasing with $$\lim_{\alpha\to\infty}\frac{f(\alpha)}{\alpha}=\infty$$. This looks very simple and maybe it is, but unfornately I couldn't find such a function.

Edit: We assume $$M\neq0$$. If it helps we can also assume that $$M$$ is a diagonal binary matrix.

Chris

• I updated my answer to reflect the edit. – user159517 Mar 17 at 14:01

Let $$M$$ be a diagonal binary matrix. There are two possible cases to consider
1. $$M$$ is singular
2. $$M$$ is the identity matrix.
First, lets assume that 1) holds. Let $$x_0 \in \text{ker} M$$ with $$\|x_0\| = 1$$. Let $$\alpha$$ be big enough such that $$f(\alpha) > \|y\|_2^2$$. Then for all $$c > \alpha$$, we find
$$f(\|cx_0\|_2) > l(cx_0).$$ So the statement is wrong.
In the case $$2)$$, where $$M$$ is the identity matrix, take $$g(\|x\|_2) := (\|x\|_2- (1+\|y\|_2))^{+}$$ where $$+$$ denotes the positive part. Whenever $$g$$ is nonzero, due to the reverse triangle inequality we have $$\|x-y\|_2 \geq 1$$ and $$g(\|x\|_2) \leq \|x\|_2 - \|y\|_2 \leq \|x-y\|_2.$$ Now for any $$p \in (1,2)$$, the function $$f(\|x\|_2) := g(\|x\|_2)^p$$ does the job.
• That's right. I did not think about that corner case. I assume that $M\neq 0$. I will edit the question. Thank you! – Chris S. Mar 17 at 12:48