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
    Commented Oct 14, 2022 at 14:40
  • $\begingroup$ @cheyp : Thank you for your comment. This is now fixed. $\endgroup$ Commented 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
    Commented 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
    Commented 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$ Commented 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
    Commented Oct 14, 2022 at 14:02
  • 1
    $\begingroup$ @dohmatob : You are right. This is now fixed. $\endgroup$ Commented Oct 14, 2022 at 14:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .