Estimados expertos en optimización,
Pido disculpas por preguntar probablemente la relación bien conocida entre la optimización basada en pérdida de Huber y la optimización basada en $\ell_1$. Sin embargo, estoy atascado con una prueba basada en 'principios básicos' (sin usar sobreenvoltura de Moreau, por ejemplo, aquí) para mostrar que son equivalentes.
Formulación del problema
El vector de observación es \begin{align*} \mathbf{y} &= \mathbf{A}\mathbf{x} + \mathbf{z} + \mathbf{\epsilon} \\ \begin{bmatrix} y_1 \\ \vdots \\ y_N \end{bmatrix} &= \begin{bmatrix} \mathbf{a}_1^T\mathbf{x} + z_1 + \epsilon_1 \\ \vdots \\ \mathbf{a}_N^T\mathbf{x} + z_N + \epsilon_N \end{bmatrix} \end{align*} donde
- $\mathbf{A} = \begin{bmatrix} \mathbf{a}_1^T \\ \vdots \\ \mathbf{a}_N^T \end{bmatrix} \in \mathbb{R}^{N \times M}$ es una matriz conocida
- $\mathbf{x} \in \mathbb{R}^{M \times 1}$ es un vector desconocido
- $\mathbf{z} = \begin{bmatrix} z_1 \\ \vdots \\ z_N \end{bmatrix} \in \mathbb{R}^{N \times 1}$ también es desconocido pero escaso en la naturaleza, por ejemplo, se puede ver como un valor atípico
- $\mathbf{\epsilon} \in \mathbb{R}^{N \times 1}$ es un ruido de medición con distribución gaussiana estándar con media cero y varianza unitaria normal, es decir, $\mathcal{N}(0,1)$.
Necesitamos demostrar que los dos problemas de optimización siguientes P$1$ y P$2$ son equivalentes.
P$1$: \begin{align*} \text{minimizar}_{\mathbf{x},\mathbf{z}} \quad & \lVert \mathbf{y} - \mathbf{A}\mathbf{x} - \mathbf{z} \rVert_2^2 + \lambda\lVert \mathbf{z} \rVert_1 \end{align*}
y
P$2$: \begin{align*} \text{minimizar}_{\mathbf{x}} \quad & \sum_{i=1}^{N} \mathcal{H} \left( y_i - \mathbf{a}_i^T\mathbf{x} \right), \end{align*} donde la función Huber $\mathcal{H}(u)$ se define como $$\mathcal{H}(u) = \begin{cases} |u|^2 & |u| \leq \frac{\lambda}{2} \\ \lambda |u| - \frac{\lambda^2}{4} & |u| > \frac{\lambda}{2} \end{cases} . $$
Mi intento parcial siguiendo la sugerencia en la respuesta a continuación
Intentamos convertir el problema P$1$ en una forma equivalente insertando la solución óptima de $\mathbf{z}$, es decir,
\begin{align*} \text{minimizar}_{\mathbf{x},\mathbf{z}} \quad & \lVert \mathbf{y} - \mathbf{A}\mathbf{x} - \mathbf{z} \rVert_2^2 + \lambda\lVert \mathbf{z} \rVert_1 \\ \equiv \\ \text{minimizar}_{\mathbf{x}} \left\{ \text{minimizar}_{\mathbf{z}} \right. \quad & \left. \lVert \mathbf{y} - \mathbf{A}\mathbf{x} - \mathbf{z} \rVert_2^2 + \lambda\lVert \mathbf{z} \rVert_1 \right\} \end{align*}
Derivando respecto a $\mathbf{z}$, \begin{align} 0 & \in \frac{\partial}{\partial \mathbf{z}} \left( \lVert \mathbf{y} - \mathbf{A}\mathbf{x} - \mathbf{z} \rVert_2^2 + \lambda\lVert \mathbf{z} \rVert_1 \right) \\ \Leftrightarrow & -2 \left( \mathbf{y} - \mathbf{A}\mathbf{x} - \mathbf{z} \right) + \lambda \partial \lVert \mathbf{z} \rVert_1 = 0 \\ \Leftrightarrow & \quad \left( \mathbf{y} - \mathbf{A}\mathbf{x} - \mathbf{z} \right) = \lambda \mathbf{v} \ . \end{align} para algún $ \mathbf{v} \in \partial \lVert \mathbf{z} \rVert_1 $ siguiendo apuntes de conferencia de Ryan Tibshirani (diapositivas #18-20), es decir, \begin{align} v_i \in \begin{cases} 1 & \text{si } z_i > 0 \\ -1 & \text{si } z_i < 0 \\ [-1,1] & \text{si } z_i = 0 \\ \end{cases}. \end{align} Entonces, la optimización de subgradiente dice: \begin{align} \begin{cases} \left( y_i - \mathbf{a}_i^T\mathbf{x} - z_i \right) = \lambda \ {\rm sign}\left(z_i\right) & \text{si } z_i \neq 0 \\ \left| y_i - \mathbf{a}_i^T\mathbf{x} - z_i\right| \leq \lambda & \text{si } z_i = 0 \end{cases} \end{align} Además, siguiendo notas de Ryan Tibsharani, la solución debería ser 'umbral suave' $$\mathbf{z} = S_{\lambda}\left( \mathbf{y} - \mathbf{A}\mathbf{x} \right),$$ donde \begin{align} S_{\lambda}\left( y_i - \mathbf{a}_i^T\mathbf{x} \right) = \begin{cases} \left( y_i - \mathbf{a}_i^T\mathbf{x} - \lambda \right) & \text{si } \left(y_i - \mathbf{a}_i^T\mathbf{x}\right) > \lambda \\ 0 & \text{si } -\lambda \leq \left(y_i - \mathbf{a}_i^T\mathbf{x}\right) \leq \lambda \\ \left( y_i - \mathbf{a}_i^T\mathbf{x} + \lambda \right) & \text{si } \left( y_i - \mathbf{a}_i^T\mathbf{x}\right) < -\lambda \\ \end{cases} . \end{align}
Ahora, pasamos al problema de optimización P$1$ de tal manera que \begin{align*} \text{minimizar}_{\mathbf{x}} \left\{ \text{minimizar}_{\mathbf{z}} \right. \quad & \left. \lVert \mathbf{y} - \mathbf{A}\mathbf{x} - \mathbf{z} \rVert_2^2 + \lambda\lVert \mathbf{z} \rVert_1 \right\} \\ \equiv \end{align*}
\begin{align*} \text{minimizar}_{\mathbf{x}} \quad & \lVert \mathbf{y} - \mathbf{A}\mathbf{x} - S_{\lambda}\left( \mathbf{y} - \mathbf{A}\mathbf{x} \right) \rVert_2^2 + \lambda\lVert S_{\lambda}\left( \mathbf{y} - \mathbf{A}\mathbf{x} \right) \rVert_1 \end{align*}
- si $\lvert\left(y_i - \mathbf{a}_i^T\mathbf{x}\right)\rvert \leq \lambda$, entonces Así, $\left[S_{\lambda}\left( y_i - \mathbf{a}_i^T\mathbf{x} \right)\right] = 0$.
el objetivo sería $$\text{minimizar}_{\mathbf{x}} \sum_i \lvert y_i - \mathbf{a}_i^T\mathbf{x} \rvert^2, $$ que es fácil de ver que coincide con la función de penalización de Huber para esta condición. ¿De acuerdo?
- si $\lvert\left(y_i - \mathbf{a}_i^T\mathbf{x}\right)\rvert \geq \lambda$, entonces $\left( y_i - \mathbf{a}_i^T\mathbf{x} \mp \lambda \right)$.
el objetivo sería $$\text{minimizar}_{\mathbf{x}} \sum_i \lambda^2 + \lambda \lvert \left( y_i - \mathbf{a}_i^T\mathbf{x} \mp \lambda \right) \rvert, $$ que casi coincide con la función de Huber, pero no estoy seguro de cómo interpretar la última parte, es decir, $\lvert \left( y_i - \mathbf{a}_i^T\mathbf{x} \mp \lambda \right) \rvert$. ¡Por favor sugiera!
