Dual Norm For Sum of 2-Norms - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:13:50Z http://mathoverflow.net/feeds/question/101168 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101168/dual-norm-for-sum-of-2-norms Dual Norm For Sum of 2-Norms AnonSubmitter85 2012-07-02T18:22:38Z 2012-07-04T07:02:45Z <p>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}$</p> <p><code>$\|\mathbf{x}\| = \displaystyle{ \sum_{i=0}^{k} \|\mathbf{A}_i \cdot \mathbf{x} \|_2}$</code>.</p> <p>How would you then find</p> <p><code>$\|\mathbf{y}\|_* = \underset{\mathbf{x}}{\mathrm{max}} \left\{ \mathbf{y}^T \mathbf{x} \;\; \mathrm{s.t.} \;\; \|\mathbf{x}\| \leq 1\right\}$</code>?</p> <p>I've tried solving for the convex conjugate looking for hints, but was unable to come up with anything meaningful.</p> <p>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.</p> <p>Edit: So using the advice in the below comments, I end up with an eigen equation for the critical point $\mathbf{x}_*$:</p> <p><code>$\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}$</code></p> <p>The only other idea I have had is that we know that <code>$\|y\|_*$</code> is the function such that <code>$\underset{\mathbf{x}}{\sup} \{ \mathbf{y}^T \mathbf{x} - \|\mathbf{x}\|\}$</code> is zero whenever <code>$\|y\|_* \leq 1$</code> and is $\infty$ otherwise. I have not been able to use this in any meaningful way however.</p> http://mathoverflow.net/questions/101168/dual-norm-for-sum-of-2-norms/101244#101244 Answer by Deane Yang for Dual Norm For Sum of 2-Norms Deane Yang 2012-07-03T17:34:17Z 2012-07-03T17:34:17Z <p>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$.</p> http://mathoverflow.net/questions/101168/dual-norm-for-sum-of-2-norms/101291#101291 Answer by Mikael de la Salle for Dual Norm For Sum of 2-Norms Mikael de la Salle 2012-07-04T07:02:45Z 2012-07-04T07:02:45Z <p>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. </p> <p>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\}.$$</p> <p>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$.</p> <p>Now consider the adjoint $i^*:\ell^1_k(\ell^2_m)^* \to X^*$. There are two things to say. The first one is that <code>$\ell^1_k(\ell^2_m)^* \simeq \ell^\infty_k(\ell^2_m)^*$</code>, and that with this identification <code>$i^*((y_i)_{i=1}^k)=\sum A_i y_i$</code>.</p> <p>The second is that <code>$i^*$</code> is a "metric quotient map", which means that <code>$i^*$</code> 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 <code>$X \to \mathbf R$</code> can be extended to a linear functional $Y \to \mathbf R$ with the same norm). </p>