3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Deane Yang
    Jul 2 '12 at 19:22
  • $\begingroup$ You need some conditions on your A matrices, presumably, to ensure one has a norm and not just a seminorm $\endgroup$
    – Yemon Choi
    Jul 2 '12 at 23:23
  • $\begingroup$ 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 $\endgroup$
    – Yemon Choi
    Jul 2 '12 at 23:24
  • 1
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Jul 3 '12 at 1:45
  • 1
    $\begingroup$ 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\} $ $\endgroup$ Jul 3 '12 at 2:10
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Is this equivalent to what I put in the edit to my question? $\endgroup$ Jul 4 '12 at 1:33
  • $\begingroup$ I believe it is. $\endgroup$
    – Deane Yang
    Jul 4 '12 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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