# Dual Norm For Sum of 2-Norms

What is the dual of a norm that is the sum of two-norms? Specifically, say we have the following norm for $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}_i \in \mathbb{R}^{m \times n}$

$\|\mathbf{x}\| = \displaystyle{ \sum_{i=0}^{k} \|\mathbf{A}_i \cdot \mathbf{x} \|_2}$.

How would you then find

$\|\mathbf{y}\|_* = \underset{\mathbf{x}}{\mathrm{max}} \left\{ \mathbf{y}^T \mathbf{x} \;\; \mathrm{s.t.} \;\; \|\mathbf{x}\| \leq 1\right\}$?

I've tried solving for the convex conjugate looking for hints, but was unable to come up with anything meaningful.

Also, if anyone has recommendations for packages that I could use (preferably matlab-based) to solve the above numerically for systems as small as $10^3$ and as large as $10^6$, I'd greatly appreciate it. CVX, of which I am admittedly a novice and a hack, will not maximize convex functions.

Edit: So using the advice in the below comments, I end up with an eigen equation for the critical point $\mathbf{x}_*$:

$\displaystyle{ \sum_{i=0}^{k} {\|\mathbf{A}_i \mathbf{x}_* \|_2 } } \cdot \mathbf{y} = \displaystyle{ \sum_{i=0}^{k} { {\mathbf{A}_i^T \mathbf{A_i} } \over{ \|\mathbf{A}_i \cdot \mathbf{x}_* \|_2 } } } \mathbf{x}_* \mathbf{x}_*^{T} \cdot \mathbf{y}$

The only other idea I have had is that we know that $\|y\|_*$ is the function such that $\underset{\mathbf{x}}{\sup} \{ \mathbf{y}^T \mathbf{x} - \|\mathbf{x}\|\}$ is zero whenever $\|y\|_* \leq 1$ and is $\infty$ otherwise. I have not been able to use this in any meaningful way however.

-
Note that $\|y||_* = \max_{x} \{ |y^T\cdot x|/\|x\|\}$. So just solve for the critical points of $x \mapsto |y^T\cdot x|/\|x\|$ and substitute the answer back into the formula. – Deane Yang Jul 2 '12 at 19:22
You need some conditions on your A matrices, presumably, to ensure one has a norm and not just a seminorm – Yemon Choi Jul 2 '12 at 23:23
A rule of thumb that may be useful: the dual of a norm defined in terms of sums of other norms is usually given by taking the maximum of the duals of those constituent norms – Yemon Choi Jul 2 '12 at 23:24
@Yemon: How is that accurate? Let $||x||$ be the standard $L_2$-norm, then $n||x||+m||x||=(n+m)||x||$, but their duals are $(1/n)||x||$, $(1/m)||x||$, and $(1/n+m)||x||$ respectively. That operation is not the maximum. – Will Sawin Jul 3 '12 at 1:45
The definition of "dual norm" used in this question isn't at all standard. The standard definition is that $\| y \|_{*}=\sup \left\{ y^{T}x | \| x \| \leq 1 \right\}$ – Brian Borchers Jul 3 '12 at 2:10

Here is an answer. This is certainly the right answer theoretically (and almost a tautology, but I do not think much more can be said in general). I am really not sure it will be helpful numerically, sorry.

So the dual norm is given by $$\|y\|_* = \inf \{\max_{i=1}^k \|y_i\|_2, y_i \in \mathbf R^m, \sum_i A_i y_i=y\}.$$

A justification is the following: If $X$ is $\mathbf R^n$ with the norm you defined, $X$ is isometrically a subspace of $\ell^1_k(\ell^2_m)$ via the embedding $i:x \mapsto (A_i x)_{i=1}^k$. Here I adopt the classical notation $\ell^1_k(\ell^2_m)$ for the space of sequences $(x_1,\dots,x_k)$ with $x_i \in \mathbf R^m$, with the norm $\sum_i \|x_i\|_2$.

Now consider the adjoint $i^*:\ell^1_k(\ell^2_m)^* \to X^*$. There are two things to say. The first one is that $\ell^1_k(\ell^2_m)^* \simeq \ell^\infty_k(\ell^2_m)^*$, and that with this identification $i^*((y_i)_{i=1}^k)=\sum A_i y_i$.

The second is that $i^*$ is a "metric quotient map", which means that $i^*$ has norm $1$ and that any element in $X^*$ has an antecedent of the same norm in $\ell^1_k(\ell^2_m)^*$. This fact holds if $i:X \to Y$ is any isometry between Banach spaces, and is just the Hahn-Banach theorem (any linear functional $X \to \mathbf R$ can be extended to a linear functional $Y \to \mathbf R$ with the same norm).

-

I agree that I don't see any closed form formula for the dual norm. According to my calculations (to be treated skeptically), the dual norm $\|y\|_*$ of $y \ne 0$ is the unique positive real number such that $$y = \|y\|_* \sum_i \frac{A^t_iA_ix}{|A_ix|}$$ for some $x \ne 0$.

-
Is this equivalent to what I put in the edit to my question? – AnonSubmitter85 Jul 4 '12 at 1:33
I believe it is. – Deane Yang Jul 4 '12 at 9:07