2
$\begingroup$

$\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 KM, \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.

$\endgroup$
2
  • $\begingroup$ A small typo: $L$ instead of $K$ in the third equation. $\endgroup$
    – cheyp
    Oct 14, 2022 at 14:40
  • $\begingroup$ @cheyp : Thank you for your comment. This is now fixed. $\endgroup$ Oct 14, 2022 at 14:44

1 Answer 1

2
$\begingroup$

$\newcommand\ka\kappa\renewcommand{\R}{\mathbb R}\newcommand{\de}{\delta}\newcommand\ep\varepsilon$Take any nonzero $a=(a_1,\dots,a_n)\in\R^n$. We have
\begin{equation*} K=\inf_{x\in\R^n}\ka(x),\quad \ka(x):=\ka_a(x):=(\|a-x\|_2+t\|x\|_1). \tag{1}\label{1} \end{equation*}

Since the norms $\|\cdot\|_p$ are orthant-symmetric, without loss of generality (wlog) $a_i\ge0$ for all $i\in[n]:=|[1,\dots,n\}$. Since the function $\ka$ is continuous and $\ka(x)\to\infty$ as $\|x\|_2\to\infty$, the infimum in \eqref{1} is attained at some $x=(x_1,\dots,x_n)\in\R^n$.

In what follows, (unless specified otherwise) let $x$ be such a minimizer.

If now $x_j<0$ for some $j\in[n]$ then, recalling that $a_i\ge0$ for all $i\in[n]$ and replacing the $j$th coordinate of $x$ by $-x_j$, we get another minimizer of $\ka$. So, wlog $x_j\ge0$ for all $j\in[n]$. Let \begin{equation*} J:=\{j\in[n]\colon x_j>0\}. \end{equation*} Then, differentiating the function $\ka$ at the minimizer $x$, we get
\begin{equation*} a_j-x_j=ct\quad\text{for all}\quad j\in J, \end{equation*} with $x_j=0$ for $j\notin J$, where \begin{equation*} c:=\|a-x\|_2=\sqrt{kc^2t^2+\sum_{j\notin J}a_j^2}, \end{equation*} whence \begin{equation*} c=\sqrt{\frac{\sum_{j\notin J}a_j^2}{1-kt^2}}, \end{equation*} where \begin{equation*} k:=|J|, \end{equation*} the cardinality of $J$; here it is assumed that $k<1/t^2$.

Thus, letting \begin{equation*} A_1:=\sum_{j\in J}a_j,\quad A_2:=\sum_{j\notin J}a_j,\quad B_1:=\sqrt{\sum_{j\in J}a_j^2},\quad B_2:=\sqrt{\sum_{j\notin J}a_j^2}, \end{equation*} after some algebra we get \begin{equation*} K=\sqrt{1-kt^2}B_2+tA_1,\quad M=\min(\sqrt{B_1^2+B_2^2},tA_1+tA_2). \end{equation*}

Take now any real $\ep\in(0,1)$ and consider the case when \begin{equation*} t\le\frac{1-\ep}{\sqrt n}; \tag{2}\label{2} \end{equation*} note that then $k\le n\le(1-\ep)^2/t^2$, so that the condition $k<1/t^2$ is satisfied. Suppose now that $K<<M$; we write $A<<B$ or, equivalently, $B>>A$ if $A=o(B)$, and we write $A\ll B$ or, equivalently, $B\gg A$ if $A=O(B)$. Then \begin{equation*} tA_1\le K<< M\le tA_1+tA_2, \end{equation*} so that $tA_1<<tA_2$ and $tA_1+tA_2\ll tA_2$. Also, $A_2\le B_2\sqrt{n-k}\le B_2\sqrt n$ and hence $tA_2\le\frac{1-\ep}{\sqrt n}B_2\sqrt n\le B_2$. So, \begin{equation*} M\le tA_1+tA_2\ll tA_2\ll B_2. \end{equation*} On the other hand, \eqref{2} implies that $kt^2\le nt^2\le(1-\ep)^2$ and hence $1-kt^2\ge1-(1-\ep)^2>0$, so that \begin{equation*} K\gg B_2+tA_1\ge B_2. \end{equation*} We conclude that, in the case \eqref{2}, the assumption $K<<M$ leads to $K\gg M$. Thus, \begin{equation*} t\le\frac{1-\ep}{\sqrt n}\implies K\gg M. \tag{3}\label{3} \end{equation*}

Consider finally the case when, for some real $\ep>0$,
\begin{equation*} 1>>t\ge\frac{1+\ep}{\sqrt n}. \tag{4}\label{4} \end{equation*} For all $j\in[n]$, let then \begin{equation*} a_j:=1(j\le m)+b\,1(j>m),\quad x_j:=1(j\le m)(1-tC), \end{equation*} where \begin{equation*} m:=\Big\lceil\frac1{t^2}\Big\rceil-1,\quad C:=b\sqrt{\frac{n-m}{1-mt^2}}, \end{equation*} and a real $b$ varies with $n$ and $t$ so that \begin{equation*} \frac{tm}{\sqrt n}<<b<<\frac m{\sqrt n}. \tag{5}\label{5} \end{equation*} Note that $m>>1$, \begin{equation*} n-m\gg n \tag{6}\label{6} \end{equation*} by \eqref{4}, \begin{equation*} 1-mt^2\le t^2, \tag{7}\label{7} \end{equation*} and \begin{equation*} b>>\frac{tm}{\sqrt n}\ge(1+\ep)\frac mn\ge\frac mn \tag{8}\label{8} \end{equation*} by \eqref{5} and \eqref{4}. Next,
\begin{equation*} K\le\ka_a(x)=K_1+K_2,\quad M=\min(M_1,M_2), \tag{9}\label{9} \end{equation*} where \begin{equation*} K_1:=\sqrt{1-mt^2}\, b\sqrt{n-m},\quad K_2:=tm, \end{equation*} \begin{equation*} M_1:=\sqrt{m+(n-m)b^2},\quad M_2:=tm+t(n-m)b. \end{equation*} Further, \begin{equation*} K_1\le tb\sqrt{n-m}<<b\sqrt{n-m}\le M_1 \tag{10}\label{10} \end{equation*} by \eqref{7} and \eqref{4}; \begin{equation*} K_2<< b\sqrt n\ll \sqrt{(n-m)b^2}\le M_1 \tag{11}\label{11} \end{equation*} by \eqref{5} and \eqref{6}; \begin{equation*} K_1\le tb\sqrt{n-m}<<t(n-m)b\le M_2 \tag{12}\label{12} \end{equation*} by \eqref{7} and \eqref{6}; \begin{equation*} K_2=tm<< tbn\ll tb(n-m)\le M_2 \tag{13}\label{13} \end{equation*} by \eqref{8} and \eqref{6}.

It follows from \eqref{9}--\eqref{13} that $K<<M$ in the case \eqref{4}.

Summarizing, for all $t=t_n>0$ we have \begin{equation} \inf_{a\in\R^n\setminus\{0\}}R_{n,t_n}(a)\to0\quad\text{if}\quad 1>>t_n\ge\frac{1+\ep}{\sqrt n} \end{equation} and \begin{equation} \inf_{a\in\R^n\setminus\{0\}}R_{n,t_n}(a)\asymp1 \quad\text{if}\quad 0<t_n\le\frac{1-\ep}{\sqrt n} \quad\text{or}\quad t_n\gg1. \end{equation}

$\endgroup$
10
  • $\begingroup$ This is really interesting and insightful. Thanks. $\endgroup$
    – dohmatob
    Oct 14, 2022 at 6:20
  • $\begingroup$ Just a small comment, but the function $x \mapsto \|x-a\|_2 + t\|x\|_1$ is no strictly convex. One can directly see this in the case $t=0$; indeed, the $\ell_2$-norm is not strictly convex math.stackexchange.com/a/1356847/168758. $\endgroup$
    – dohmatob
    Oct 14, 2022 at 12:14
  • $\begingroup$ @dohmatob : Thank you for your appreciation. As for the strict convexity, I meant it as a norm property (see e.g. arxiv.org/abs/1012.5595), which is now clarified. $\endgroup$ Oct 14, 2022 at 13:22
  • $\begingroup$ Thanks for that paper which seems interesting in its own right. Still, $\kappa_a$ doesnt have a unique minimizer. For example, when $n=1$, $t = 1$, and $a \in (0,\infty)$, the minimizers of $\kappa_a$ are the entire interval $[0,a]$. Maybe I missed something in the second paragraph of this post ? $\endgroup$
    – dohmatob
    Oct 14, 2022 at 14:02
  • 1
    $\begingroup$ @dohmatob : You are right. This is now fixed. $\endgroup$ Oct 14, 2022 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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