Convex envelope of norm 0

In class, we showed that the convex envelope of the norm 0 on vectors, defined as the number of nonzero coordinates, is the norm 1 on the unitary ball for norm 1 and $\infty$.

We also tried to prove that it is the same if we take the unitary ball in norm 2, but we failed, and we now think it is false.

Do you know the solution for norm 2 or in general any p norm?

Edit: A convex envelope of a function $f(x)$ on a domain $D$ is a convex function $g(x)$ defined on $D$ such that $g(x)\le f(x)$ for all $x\in D$ and for every other convex function such that $h(x)\le f(x)$, then $h(x)\le g(x)\le f(x)$.

• I'm not sure I understand your question completely but the convex relaxation of any $p$-norm with $0\le p<1$ is the $1$-norm, after that all $p$-norms are convex so I'm not sure I see the point of your question? – tibL Sep 11 '16 at 13:35
• It all depends where you perform such relaxation: the relaxation of norm 0 on all the space $\mathbb R^n$ is the constant fuction zero. – Exodd Sep 11 '16 at 19:44
• Please tell your instructor not to use the term "0-norm". The cardinality function is not a norm. (Stepping off my soapbox now.) The original use of the term made it clear that it is an abuse of notation, but now people throw it around like it's no big deal. – Michael Grant Sep 13 '16 at 1:29
• Furthermore: it is not quite the case that the convex envelope of the cardinality function is the 1-norm. Rather, the convex envelope of the this function is:$$f(x) = \begin{cases} \mathop{\textrm{card}}(x) & \|x\|_\infty \leq 1 \\ +\infty & \text{otherwise} \end{cases}$$ – Michael Grant Sep 13 '16 at 1:31
• How can an envelope of a limited function be infinite? – Exodd Sep 13 '16 at 8:42

As long as $p>1$ and $n>1,$ and neither are infinite, the answer is definitely no.

Consider this notation: $$f_q^p(x) = \begin{cases} ||x||_q & x \in B_p \\ +\infty &\text{else} \end{cases},$$ where $B_p = \{x \in \mathbb{R}^n \mid ||x||_p \le 1\}.$ Also define the epigraph $$\text{epi} (f) = \{(x, y) \in \mathbb{R}^{n+1} \mid y \ge f(x)\}.$$ Then, what I will prove, which is equivalent to your statement about convex envelopes, is that, for all $p >1$ and $n \in \mathbb{N}\setminus\{1\},$ $$\text{epi} (f_1^p) \not = \text{conv}( \text{epi} (f_0^p) ).$$

proof: Note that $(n^{-1/p} \mathbb{1}, n^{(p-1)/p}) \in \text{epi}(f_1^p).$ Now, note that $f_0^p(n^{-1/p} \mathbb{1}) = n > n^{(p-1)/p}$ for all $p, n > 1.$ Thus, $(n^{-1/p} \mathbb{1}, n^{(p-1)/p}) \not\in \text{epi}(f_0^p).$

So the question is, is $(n^{-1/p} \mathbb{1}, n^{(p-1)/p})$ a member of $\text{conv}( \text{epi} (f_0^p) )?$ The answer again is no. To see why, note that $n^{-1/p} \mathbb{1}$ is an extreme point of $B_p$, thus is cannot be written as a convex combination of other points in $B_p$. Therefore, it is hopeless to look for a collection of points in $\text{conv}( \text{epi} (f_0^p) )$ who's convex combination is equal to $(n^{-1/p} \mathbb{1}, n^{(p-1)/p})$.

• Is it true in general that the convex envelope of a function must coincide with the function on the extreme points of the (convex) domain? – Exodd Oct 6 '16 at 16:15
• @Exodd No: The original function may be discontinuous at some (possibly extreme) point, and the convex envelope must be continuous everywhere, and they definitely can't agree at such a point. But this does not invalidate my claim. The last sentence in my proof can be proved by the separation principle: find a plane that separates the convex set $\text{conv}(\text{epi}(f_0^p))$ from the point $(n^{-1/p} \mathbb{1}, n^{(p-1)/p}).$ I can add this to the proof but I need to think about what the affine equation would be. – Charles F Oct 7 '16 at 15:16
• the convex envelope of a discontinuous convex function is the same function.. – Exodd Oct 7 '16 at 15:29
• @Exodd a "discontinuous convex function" is a contradiction of terms; confer [math.stackexchange.com/questions/258511/… answer). – Charles F Oct 13 '16 at 14:48
• On a closed domain, a convex function can be discontinuous: take $f:[0,1]\to R$ such that f[0,1)=0, f(0)=1. – Exodd Oct 14 '16 at 20:09