L1-Normの劣微分

前にL1-Normの劣微分
について書いたが，間違っていたので修正．

[1]のPointwise maximumの項に書いてあるテクニックを使う．$\bm{x} \in \mathbb{R}^d$として，$\|\bm{x}\|_1$を以下のように表す（結構感動的）．

$\begin{aligned} f(\bm{x}) = \|\bm{x}\|_1 = \max\{\bm{s}^T \bm{x} \vert \bm{s} \in \{-1, 1\}^d\} \end{aligned}$

$\bm{x}$に対して，$\|\bm{x}\|_1 = \bm{s}^T \bm{x}$となったとする．この時，$\bm{s}$は以下のようになる．

$\begin{aligned} s_j = \left\{\begin{array}{ll} 1 & (x_j > 0) \\ -1 & (x_j < 0) \\ -1 \ \text{or} \ 1 & (x_j = 0) \end{array}\right. \end{aligned}$

$\bm{s}^T \bm{x}$のsubgradientを$\bm{g}$とすると，$\bm{g} \in \partial f(\bm{x})$である．最後に，$\bm{g} = \bm{s}$である．

参考:

1. https://see.stanford.edu/materials/lsocoee364b/01-subgradients_notes.pdf

Written with StackEdit.