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

Improve this question
$\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
    Commented Jul 2, 2012 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
    Commented Jul 2, 2012 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
    Commented Jul 2, 2012 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
    Commented Jul 3, 2012 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$
    – Brian Borchers
    Commented Jul 3, 2012 at 2:10

2 Answers 2

Reset to default
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).

Improve this answer
$\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$.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .