# Dual norm of a truncated and ordered (decreasing order) $\ell_1$-norm

I do not understand yet how the following dual-norm of a truncated and ordered (in decreasing fashion) $\ell_1$-norm $\lVert \mathbf{x}\rVert_{[k]}$ on $\mathbf{x} \in \mathbb{C}^n$ is:

$$\lVert \mathbf{x}\rVert^*_{[k]}= \max\left\{\frac{1}{k} \| \mathbf{x} \|_1,\lVert \mathbf{x}\rVert_{\infty}\right\}$$

The truncated $\ell_1$-norm is defined as the sum of the $k$ largest magnitudes of the entries in $\mathbf{x}$ vector, i.e., $\lVert \mathbf{x}\rVert_{[k]}=\lvert x_{i_1}\rvert+.....+\lvert x_{i_k}\rvert$ in which $\lvert x_{i_1}\rvert\geq\lvert x_{i_2}\rvert\geq.....\geq\lvert x_{i_n}\rvert$.

Thank you

• I've never heard this referred to as the "truncated $\ell_1$ norm." Interesting. It has a logic to it. Commented Apr 21, 2018 at 14:28
• Thank you for your suggestion. Sure, I can change the definition of a dual norm as you have suggested. Commented Apr 21, 2018 at 14:36
• Sorry I deleted my other comment---I was having trouble getting LaTeX to work. Your definition is fine, I just think it might help you find a proof to use a different one. Commented Apr 21, 2018 at 14:41
• No problems. Is the following definition of a dual norm be useful? $\left\| \mathbf{y} \right\|^*_{[k]} = \max_{\left\| \mathbf{z} \right\| \leq1} {\rm Re} \ \left\{ \mathbf{z}^{\rm H} \mathbf{y} \right\}$ Commented Apr 21, 2018 at 14:53
• I tend to use $\le 1$ but yes! Commented Apr 21, 2018 at 14:54

I accidentally derived the dual norm of your dual norm. Let us first derive some conjugate functions: \begin{align} f(x) &= \max\left\{g(x),h(x)\right\} \\ g(x) &= \frac{1}{k} \| x \|_1 \\ h(x) &= \lVert x\rVert_{\infty} \\ g^*(y) &= 0 \text{ if } k \| y \|_\infty \leq 1 \;(\infty \text{ otherwise}) \\ h^*(y) &= 0 \text{ if } \| y \|_1 \leq 1 \;(\infty \text{ otherwise}) \\ \end{align} Using the well-known rule for the conjugate of $\max\{g,h\}$, we get: \begin{align} f^*(y) &= \inf_{v,z} \{ (z_1g)^*(v) + (z_2h)^*(y-v) \mid z_1+z_2 = 1, z\geq 0 \}\\ &= 0 \text{ if } \exists v,z : k \| v \|_\infty \leq z_1, \; \| y-v \|_1 \leq z_2, \; z_1+z_2 = 1, z\geq 0 \\ &= 0 \text{ if } \exists v : k \| v \|_\infty +\| y-v \|_1 \leq 1 \;(\infty \text{ otherwise}) \end{align} Using that the convex conjugate of a norm is the indicator of the unit ball for the dual norm, the dual norm of the dual norm is $$||y||^{**} = \inf_v \{ k \| v \|_\infty +\| (y-v) \|_1 \}.$$ This does not equal the norm you started with. Either the truncated L1-norm is not a real norm, or I made a mistake. Maybe you could do the same analysis for the norm itself, or check the above for a possible mistake.

• Are you sure it's not equal? Commented Apr 21, 2018 at 19:55
• Convince yourself that this optimization problem has an optimal value of $\|x\|_{[k]}$: $$\begin{array}{ll} \text{maximize}_v & v^T x \\ \text{subject to} & \| v \|_1 \leq k \\ & \| v \|_\infty \leq 1 \\ \end{array}$$ Take the dual of this with respect to $v$ and I'm reasonably sure you'll get your answer, or something very close to it. Commented Apr 21, 2018 at 20:03
• @MichaelGrant that is also how you can derive conditional value at risk. Found the error in my numerical verification. Commented Apr 21, 2018 at 21:41
• Yes! And it's not just that the primal model isn't jointly convex; it's also that with graph implementations, you need convex functions to be described by minimizations and concave functions by maximizations. Commented Apr 21, 2018 at 21:42
• @user550103 you can take the dual of Michael's problem using the Lagrangian or by first writing it as a linear optimization problem. Try both approaches, it takes practice. Commented Apr 22, 2018 at 12:17

The shortest proof I can think of is the following:

1. Prove that $\|\cdot\|_{[k]}$ and $\|\cdot\|_{[k]}^*$ are norms (easy be definition).
2. Use the LP problem suggested by Michael Grant that $$\|x\|_{[k]}=\max\{x^Tz\colon \|z\|_1\le k,\,\|z\|_\infty\le 1\}$$ and since $\|z\|_1\le k$ $\Leftrightarrow$ $\frac{1}{k}\|z\|_1\le 1$ rewrite it as $$\|x\|_{[k]}=\max\{x^Tz\colon \|z\|_{[k]}^*\le 1\}.\tag{1}$$
3. The relation (1) means by definition that $\|\cdot\|_{[k]}$ is the dual of $\|\cdot\|_{[k]}^*$. Taking dual once again: the dual of $\|\cdot\|_{[k]}$ is the second dual of $\|\cdot\|_{[k]}^*$, which is the same as $\|\cdot\|_{[k]}^*$.

P.S. The last fact "the second dual norm is the norm itself" is a known result in finite dimensional spaces (even in reflexive Banach spaces). A proof normally uses separation theorems of convex sets (alternatively Hahn-Banach theorem). It can be found in e.g. Horn, Johnson, Matrix Analysis, Ch. 5, Sec. 5.5.

• I tend to agree with this proof without deep diving into details. Commented May 1, 2018 at 13:16

Based on the input from @LinAlg and MichaelGrant--to be reviewed.

The function $f(\mathbf{x}) = \lVert \mathbf{x} \rVert_{[k]}$ is equal to the optimal value of the following linear program (LP): \begin{align*} \text{maximize}_\mathbf{v} \quad &\mathbf{v}^{\rm T} \mathbf{x}\\ \text{subject to }\quad & \lVert \mathbf{v} \rVert_1 \leq k \\ & \lVert \mathbf{v} \rVert_\infty \leq 1 \\ \equiv \\ \text{minimize} \ \ \quad &-\mathbf{v}^{\rm T} \mathbf{x}\\ \text{subject to }\quad & \mathbf{1}^{\rm T} \mathbf{t} \leq k \ ; - \mathbf{t} \preceq \mathbf{v} \preceq \mathbf{t} \\ & - \mathbf{1} \preceq \mathbf{v} \preceq \mathbf{1} \\ \equiv \\ \text{minimize} \ \ \quad &-\mathbf{v}^{\rm T} \mathbf{x}\\ \text{subject to }\quad & \mathbf{1}^{\rm T} \mathbf{t} \leq k \\ & - \mathbf{t} \preceq \mathbf{v} \preceq \mathbf{t}\\ & \mathbf{t} \preceq \mathbf{1} \\ \equiv \\ \text{minimize} \ \ \quad &-\mathbf{v}^{\rm T} \mathbf{x} &\\ \text{subject to }\quad & \mathbf{1}^{\rm T} \mathbf{t} - k \leq 0 \\ & -\mathbf{v} - \mathbf{t} \preceq 0 \\ & \mathbf{v} - \mathbf{t} \preceq 0 \\ & \mathbf{t} - \mathbf{1} \preceq 0 \end{align*}

Then, forming the Lagrangian such that \begin{align*} L\left(\mathbf{v},\mathbf{t},\rho,\boldsymbol{\mu}_1,\boldsymbol{\mu}_2,\boldsymbol{\lambda} \right) &= -\mathbf{v}^{\rm T} \mathbf{x} +\rho \left( \mathbf{1}^{\rm T} \mathbf{t} - k \right) + \boldsymbol{\mu}_1^{\rm T} \left( -\mathbf{v} - \mathbf{t} \right) + \boldsymbol{\mu}_2^{\rm T} \left( \mathbf{v} - \mathbf{t} \right) + \boldsymbol{\lambda}^{\rm T}\left( \mathbf{t} - \mathbf{1} \right) \\ &= -\mathbf{v}^{\rm T} \mathbf{x} +\rho \left( \mathbf{1}^{\rm T} \mathbf{t} - k \right) - \mathbf{v}^{\rm T} \boldsymbol{\mu}_1 - \mathbf{t}^{\rm T} \boldsymbol{\mu}_1 + \mathbf{v}^{\rm T} \boldsymbol{\mu}_2 - \mathbf{t}^{\rm T} \boldsymbol{\mu}_2 + \mathbf{t}^{\rm T} \boldsymbol{\lambda} - \mathbf{1}^{\rm T} \boldsymbol{\lambda} \\ &= \mathbf{v}^{\rm T} \left( -\mathbf{x} -\boldsymbol{\mu}_1 + \boldsymbol{\mu}_2 \right) + \mathbf{t}^{\rm T} \left( \rho \mathbf{1} - \boldsymbol{\mu}_1 - \boldsymbol{\mu}_2 + \boldsymbol{\lambda} \right) + \left( - \rho k - \mathbf{1}^{\rm T} \boldsymbol{\lambda} \right) . \end{align*}

Now, taking the derivative of $L\left( \mathbf{v},\mathbf{t},\rho,\boldsymbol{\mu}_1,\boldsymbol{\mu}_2,\boldsymbol{\lambda}\right)$ with respect to $\mathbf{v}$ and $\mathbf{t}$ such that the dual function reads \begin{align*} g\left(\rho,\boldsymbol{\mu}_1,\boldsymbol{\mu}_2,\boldsymbol{\lambda}\right) &= \left\{ \begin{matrix} \left( - \rho k - \mathbf{1}^{\rm T} \boldsymbol{\lambda} \right) & & \left( -\mathbf{x} -\boldsymbol{\mu}_1 + \boldsymbol{\mu}_2 \right) = \mathbf{0} , \quad \rho \mathbf{1} - \boldsymbol{\mu}_1 - \boldsymbol{\mu}_2 + \boldsymbol{\lambda} = \mathbf{0} \\ -\infty & &\text{otherwise}. \end{matrix} \right. \end{align*}

The dual optimization problem would be \begin{align*} \text{maximize} \quad \ & - \rho k - \mathbf{1}^{\rm T} \boldsymbol{\lambda} \\ \text{subject to }\quad & -\boldsymbol{\mu}_1 + \boldsymbol{\mu}_2 = \mathbf{x} \\ & \boldsymbol{\mu}_1 + \boldsymbol{\mu}_2 = \rho \mathbf{1} + \boldsymbol{\lambda} \\ & \rho \geq 0 \\ & \boldsymbol{\mu}_1 \succeq 0 \ ; \ \boldsymbol{\mu}_2 \succeq 0\\ & \boldsymbol{\lambda} \succeq 0 . \\ & \equiv\\ \\ \text{minimize} \quad \ & \rho k + \mathbf{1}^{\rm T} \boldsymbol{\lambda} \\ \text{subject to }\quad & -\boldsymbol{\mu}_1 + \boldsymbol{\mu}_2 = \mathbf{x} \\ & \boldsymbol{\mu}_1 + \boldsymbol{\mu}_2 = \rho \mathbf{1} + \boldsymbol{\lambda} \\ & \rho \geq 0 \\ & \boldsymbol{\mu}_1 \succeq 0 \ ; \ \boldsymbol{\mu}_2 \succeq 0\\ & \boldsymbol{\lambda} \succeq 0 . \end{align*}

At the optimality, $\boldsymbol{\mu}_1 = \max \left\{0, -\mathbf{x} \right\}$ and $\boldsymbol{\mu}_2 = \max \left\{0, \mathbf{x} \right\}$ such that $| \mathbf{x}| = \rho \mathbf{1} + \boldsymbol{\lambda}$. Thus, the above optimization problem can succinctly be written as $$\min_{\rho \geq 0,\: \boldsymbol{\lambda} \succeq 0} \left\{ \rho k + \mathbf{1}^{\rm T} \boldsymbol{\lambda} \ : \ \left|\mathbf{x}\right| = \rho \mathbf{1} + \boldsymbol{\lambda} \right\}.$$

[to be verified] To connect it with the dual function $f^*(\mathbf{x}) = \lVert \mathbf{x} \rVert_{[k]}^*$, we need to verify numerically.

• @LinAlg: Thank you for your suggestion. I have tried to follow it and simplified (hopefully without any mistakes). On the other hand, for me, it is still a mystery (at least to me) how to relate it with your dual results yet :(. Commented Apr 30, 2018 at 20:10
• You have $\min_{\rho,\lambda \geq 0}\{ k\rho + \sum \lambda_i : |x_i|=\rho+\lambda_i\}$. I agree it's not that simple to relate this to the dual norm. Commented Apr 30, 2018 at 20:48
• Sorry, I might be bit slow. How did you obtain $\left|\mathbf{x}\right| = \rho \mathbf{1} + \boldsymbol{\lambda}$? From these two constraints (a) $-\boldsymbol{\mu}_1 + \boldsymbol{\mu}_2 = \mathbf{x}$ and (b) $\boldsymbol{\mu}_1 + \boldsymbol{\mu}_2 = \rho \mathbf{1} + \boldsymbol{\lambda}$? If yes, then how? Commented Apr 30, 2018 at 21:03
• Yes, from those constraints. They resemble a well known reformulation for absolute values. At optimlity, $\mu_1 = \max\{0,-x\}$ and $\mu_2 = \max\{0,x\}$. Let's remove some outdated comments to keep this thread readable. Commented Apr 30, 2018 at 22:07
• Thank you very much for the clarification. I guess then we need to compare numerically. Commented May 1, 2018 at 5:40