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.

Thank you in advance,


  • $\begingroup$ I updated my answer to reflect the edit. $\endgroup$ – 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.

  • $\begingroup$ That's right. I did not think about that corner case. I assume that $M\neq 0$. I will edit the question. Thank you! $\endgroup$ – Chris S. Mar 17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.