Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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
1  
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
show 2 more comments

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.