Norma dual de un truncado y ordenado (orden decreciente) $\ell_1$ -norma

Question

Todavía no entiendo cómo la siguiente norma dual de un truncado y ordenado (de forma decreciente) $\ell_1$ -norma $\lVert \mathbf{x}\rVert_{[k]}$ en $\mathbf{x} \in \mathbb{C}^n$ es:

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

El truncado $\ell_1$ -se define como la suma de las $k$ mayores magnitudes de las entradas en $\mathbf{x}$ vector, es decir, $\lVert \mathbf{x}\rVert_{[k]}=\lvert x_{i_1}\rvert+.....+\lvert x_{i_k}\rvert$ en el que $\lvert x_{i_1}\rvert\geq\lvert x_{i_2}\rvert\geq.....\geq\lvert x_{i_n}\rvert$ .

Gracias

Answer 1

Accidentalmente derivé la norma dual de tu norma dual. Derivemos primero algunas funciones conjugadas: $$ \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} $$ Utilizando la conocida regla del conjugado de $\max\{g,h\}$ obtenemos: $$\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}$$ Utilizando que el conjugado convexo de una norma es el indicador de la bola unitaria para la norma dual la norma dual de la norma dual es $$||y||^{**} = \inf_v \{ k \| v \|_\infty +\| (y-v) \|_1 \}.$$ Esto no es igual a la norma con la que empezaste. O bien la norma L1 truncada no es una norma real, o bien he cometido un error. Tal vez usted podría hacer el mismo análisis para la norma en sí, o comprobar lo anterior para un posible error.

Answer 2

La prueba más breve que se me ocurre es la siguiente:

1. Demostrar que $\|\cdot\|_{[k]}$ et $\|\cdot\|_{[k]}^*$ son normas (de fácil definición).
2. Utilice el problema de LP sugerido por Michael Grant que $$ \|x\|_{[k]}=\max\{x^Tz\colon \|z\|_1\le k,\,\|z\|_\infty\le 1\} $$ y como $\|z\|_1\le k$ $\Leftrightarrow$ $\frac{1}{k}\|z\|_1\le 1$ reescribirlo como $$ \|x\|_{[k]}=\max\{x^Tz\colon \|z\|_{[k]}^*\le 1\}.\tag{1} $$
3. La relación (1) significa por definición que $\|\cdot\|_{[k]}$ es el dual de $\|\cdot\|_{[k]}^*$ . Tomando el dual una vez más: el dual de $\|\cdot\|_{[k]}$ es el segundo dual de $\|\cdot\|_{[k]}^*$ que es lo mismo que $\|\cdot\|_{[k]}^*$ .

---

P.D. El último hecho "la segunda norma dual es la propia norma" es un resultado conocido en espacios de dimensión finita (incluso en espacios de Banach reflexivos). Para demostrarlo se suelen utilizar los teoremas de separación de conjuntos convexos (o el teorema de Hahn-Banach). Se puede encontrar en, por ejemplo, Horn, Johnson, Matrix Analysis, capítulo 5, sección 5.5.

Answer 3

Basado en las aportaciones de @LinAlg y MichaelGrant a revisar.

La función $f(\mathbf{x}) = \lVert \mathbf{x} \rVert_{[k]}$ es igual al valor óptimo del siguiente programa lineal (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*}

Entonces, formando el Lagrangiano tal que \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*}

Ahora, tomando la derivada de $L\left( \mathbf{v},\mathbf{t},\rho,\boldsymbol{\mu}_1,\boldsymbol{\mu}_2,\boldsymbol{\lambda}\right)$ con respecto a $\mathbf{v}$ et $\mathbf{t}$ de tal manera que la función dual sea \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} \derecha. \Fin

El problema de optimización dual sería \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*}

En la optimización, $\boldsymbol{\mu}_1 = \max \left\{0, -\mathbf{x} \right\}$ et $\boldsymbol{\mu}_2 = \max \left\{0, \mathbf{x} \right\}$ tal que $| \mathbf{x}| = \rho \mathbf{1} + \boldsymbol{\lambda}$ . Así, el problema de optimización anterior puede escribirse sucintamente como $$\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\}.$$

[a verificar] Para conectarlo con la doble función $f^*(\mathbf{x}) = \lVert \mathbf{x} \rVert_{[k]}^*$ , tenemos que verificarlo numéricamente.