5
$\begingroup$

Let $C$ be a (nonempty) convex compact subset of $\mathbb R^n$.

General question: Under what conditions on $C$ does the support function

$$\sigma_C(x) := \sup_{y \in C}x^Ty $$ define a norm on $\mathbb R^n$ ?

Specific question: For a real $n$-by-$n$ matrix $W = (w^j_i)$ , define $$C_W := \{y \in \mathbb R^n \text{ s.t } \sum_{i=1}^nw^j_i y_i^2 \le 1,\;\forall j\}. $$ Under what conditions on $W$ does the $\sigma_{C_W}$ define a norm on $\mathbb R^n$ ?

Observations:

  • In case $w^j_k \in \{0, 1\}$ and $\sum_{i=1}^n w^j_i > 0$ for all $k$ and $j$ (i.e $W$ is the adjacency matrix of a directed graph with no isolated nodes), then $\|.\|_W$ is indeed a norm called the overlapping group-norm (see Lemmas 1 & 2 of this manuscript), where the groups are taken to be the adjacency lists of $W$, i.e $g_i := \{j | w^j_i = 1\}$. I'd like to extend this to a general (nonnegatively) weighted directed graph.
$\endgroup$

1 Answer 1

6
$\begingroup$

General question: If $C$ is a subset of $\Bbb R^n$, then $\sigma_C$ is a norm if and only if $C$ is compact, convex, symmetric about the origin and has non-empty interior.

Proof: We know that $\|\cdot\|$ is a norm on $\Bbb R^n$ if and only if there exists a set $C$ with the properties listed above and such that $\|x\|=\gamma_C(x)$ where $\gamma_C(x)=\inf\{t>0\colon x/t \in C\}$. Note that $C$ is the unit ball of $\|\cdot\|$. Now, the dual norm of $\|\cdot\|$ is given by $\|x\|_*=\sigma_C(x)$. In particular, $\gamma_C$ is a norm if and only if $\sigma_C$ is a norm. More details can be found here and in the book on convex optimization of Boyd and Vandenberghe.

Specific question: $\sigma_{C_W}$ is a norm if and only if for every $i$, there exists $j$ such that $w_i^j>0$.

Proof: Note that if $\|\cdot\|_p$ denotes the usual $p$-norm, then $C_W$ is the unit ball of $$\|x\| = \big\|\|x\|_{w^1,2},\ldots,\|x\|_{w^n,2}\big\|_{\infty},$$ where $\|y\|_{w^j,2}$ is the weighted $2$-norm with (nonnegative) weights $w_1^j,\ldots,w_{n}^j$. From the previous observation, we know that $\sigma_{C_W}$ is a norm if and only if $\|\cdot\|$ is a norm. Clearly, $\|\cdot\|$ is nonnegative, (positively) homogeneous and satisfies the triangle inequality. Finally, you need to ensure that $\|x\|=0$ if and only if $x=0$. One direction is obvious. For the other direction, note that if $\|\cdot\|$ is a norm, then $\|e_i\|>0$ for every $i$, where $e_1,\ldots,e_n$ is the canonical basis of $\Bbb R^n$ so that for every $i$, there exists $j$ such that $0<\|e_i\|_{w^j,2}^2=w^j_i$.

$\endgroup$

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.