Lower-bound for $\inf_{x \in \mathbb R^n} \|x-a\|_2 + r\|x\|_1$ as a function of fixed $a \in \mathbb R^n$ and $r \ge 0$.

41 Views Asked by At

Fix $a \in \mathbb R^n$ and $r \ge 0$, and define $c=c(a,r) := \inf_{x \in \mathbb R^n} \|x-a\|_2 + r\|x\|_1$.

Question. As a function of $a$ and $r$, what is a good lower-bound for $c$ ?

A trivial (and very bad) lower-bound:

Let $B_p^n(r) := \{x \in \mathbb R^n \mid \|x\|_p \le r\}$ be the $\ell_p$-ball of radius $r$ in $\mathbb R^n$. Note that $$ \begin{split} c &\ge \inf_{x \in \mathbb R^n} n^{-1/2}\|x-a\|_1 + r\|x\|_1 = \text{ support function of }B_\infty^n(\min(n^{-1/2},r))\\ &= \min(n^{-1/2},r)\|a\|_1 \end{split} $$

1

There are 1 best solutions below

0
On BEST ANSWER

Notice that evaluating the function in the infinmum with $x=a$ and $x=0$ leads easily to get that \begin{equation}\label{eq}\tag{1} c \leq \min(\|a\|_2,r\,\|a\|_1). \end{equation} But in the particular case when $a_1 = a_2 = ... = a_n$, then it holds $\|a\|_2 = |a_2|\,\sqrt{n}$ and $\|a\|_1 = |a_2|\,n$, so that $\|a\|_2 = \|a\|_1/\sqrt{n}$, and $c \leq \|a\|_1 \min(n^{-1/2},r)$. Combining with your bound, it proves that in this case, $$ c = \min(n^{-1/2},r)\,\|a\|_1. $$ This proves that your bound is sharp in the sense that there exist vectors $a\in\Bbb R^n$ such that the bound is reached. However, this is not very good when $a = (a_1,0,\dots,0)$ and $n$ is large for instance. Hence you can still get lower bounds in terms of other quantities. For instance, since $\|x\|_{1} \geq \|x\|_2$, it follows that for any $a,x\in\Bbb R^n$, $$ u(x) := \|x-a\|_2 + r \,\|x\|_1 \geq \|x-a\|_2 + r \,\|x\|_2 \geq \min(1,r)\,(\|x-a\|_2 + \,\|x\|_2) $$ so by the triangle inequality $ \|x-a\|_2 + r \,\|x\|_1 \geq \min(1,r)\,\|a\|_2$. Taking the infimum yields $$ c \geq \min(1,r)\,\|a\|_2 $$ which is more satisfactory for large dimensions. Again this is in general sharp, as follows by taking $a = (a_1,0,\dots,0)$ and from \eqref{eq}.