Dual Norm For Sum of 2-Norms - MathOverflow

Dual Norm For Sum of 2-Norms

2012-07-02T18:22:38Z

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.

Answer by Deane Yang for Dual Norm For Sum of 2-Norms

2012-07-03T17:34:17Z

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$.

Answer by Mikael de la Salle for Dual Norm For Sum of 2-Norms

2012-07-04T07:02:45Z

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).