Skip to main content
4 of 5
added 5 characters in body
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

On the infimal convolution of two norms on $\mathbb R^n$

$\newcommand{\R}{\mathbb R}$For natural $n$, $a\in\R^n$, and real $t>0$, let
\begin{equation*} K:=K_{n,t}(a):=\inf_{x\in\R^n}(\|a-x\|_2+t\|x\|_1), \end{equation*} \begin{equation*} M:=M_{n,t}(a):=\min(\|a\|_2,t\|a\|_1), \end{equation*} and (for nonzero $a$) \begin{equation*} R:=R_{n,t}(a):=\frac LM, \end{equation*} where $\|x\|_p:=(\sum_1^n|x_i|^p)^{1/p}$ for $x=(x_1,\dots,x_n)\in\R^n$.

So, the function $K_{n,t}$ is a norm on $\R^n$, which is the infimal convolution of the norms $\|\cdot\|_2$ and $t\|\cdot\|_1$. The function $M_{n,t}$ is a norm only for $t\ge1$ (and then $M_{n,t}=\|\cdot\|_2$) and for $t\le1/\sqrt n$ (and then $M_{n,t}=t\|\cdot\|_1$).

Clearly, $K\le M$. It was previously asked whether, for each $t>0$,
\begin{equation*} \inf_{a\in\R^n\setminus\{0\}}R_{n,t}(a)\to0 \end{equation*} as $n\to\infty$.

It was then shown that this is not true for $t=1$ and also not true for any real $t>0$, because $$\frac KM\ge\min(1,t).$$

It was further asked if \begin{equation*} \inf_{a\in\R^n\setminus\{0\}}R_{n,t_n}(a)\to0 \end{equation*} as $n\to\infty$ assuming that $t_n\to0$.

A somewhat surprising answer to this question will be given below.

Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229