スパースモデリングに関しては今日から出来るスパースモデリングを参考にしました.

文中で省略されている証明について以下で簡単に補足していますので,必要であれば適宜参照していただると幸いです.

1. 1変数の場合

$\lambda >0$, $y\in R$を固定する.
このとき以下の最適化問題を解く. $$\begin{array}{cccc}& \underset{x\in R}{\text{minimize}}& & \{|x|+\frac{1}{2\lambda }(y-x{)}^2\}\end{array}$$ (解法) $$\begin{array}{cccc}& \underset{x\in R}{\text{minimize}}& & \{|x|+\frac{1}{2\lambda }(y-x{)}^2\}\\ =& \underset{}{\text{min}}& & \{\underset{x\ge 0}{\text{minimize}}\{|x|+\frac{1}{2\lambda }(y-x{)}^2\},\underset{x\le 0}{\text{minimize}}\{|x|+\frac{1}{2\lambda }(y-x{)}^2\}\}\end{array}$$ であるので,$x\ge 0,x\le 0$の2つに分けて考える.
$x\ge 0$のとき

$$|x|+\frac{1}{2\lambda }(y-x{)}^2=x+\frac{1}{2\lambda }(y-x{)}^2=\frac{1}{2\lambda }(x-(y-\lambda ){)}^2+y-\frac{\lambda }{2}$$ ここで, $\frac{1}{2\lambda }(x-(y-x){)}^2\ge 0$であり, $y-\frac{\lambda }{2}$が定数であることに注意すると,
(i) $y-\lambda \ge 0$のとき
$x=y-\lambda$で最小値 $y-\frac{\lambda }{2}$をとる.
(ii) $y-\lambda <0$のとき $$\begin{array}{cc}0\le x_1\le x_2& \Rightarrow 0\le x_1-(y-\lambda )\le x_2-(y-\lambda )\\ & \Rightarrow \frac{1}{2\lambda }{(x_1-(y-\lambda \left)\right)}^2\le \frac{1}{2\lambda }{(x_2-(y-\lambda \left)\right)}^2\end{array}$$ より$x=0$のとき最小値$\frac{1}{2\lambda }(y-x{)}^2+y-\frac{\lambda }{2}$をとる.
同様に,一方,$x\le 0$のとき $$|x|+\frac{1}{2\lambda }(y-x{)}^2=-x+\frac{1}{2\lambda }(y-x{)}^2=\frac{1}{2\lambda }(x-(y+\lambda ){)}^2-y-\frac{\lambda }{2}$$ として上記と同様に求める.

2. 多変数の場合

$\lambda >0$, $y\in R^N$を固定する.
このとき以下の最適化問題を解く. $$\begin{array}{cccc}& \underset{x\in R^N}{\text{minimize}}& & \{|x{|}_1+\frac{1}{2\lambda }||y-x|{|}_2^2\}\end{array}$$ (解法)

$$\begin{array}{cc}||x|{|}_1+\frac{1}{2\lambda }||y-x|{|}_2^2& =\sum _{i=1}^N|x_i|+\frac{1}{2\lambda }\sum _{i=1}^N(y_i-x_i{)}^2\\ & =\sum _{i=1}^N|x_i|+\frac{1}{2\lambda }(y_i-x_i{)}^2\end{array}$$ である.ここで, $$\begin{array}{cccc}& \underset{x\in R^N}{\text{minimize}}& & \sum _{i=1}^N|x_i|+\frac{1}{2\lambda }(y_i-x_i{)}^2=\sum _{i=1}^N\underset{x_i\in R}{\text{minimize}}\{|x_i|+\frac{1}{2\lambda }(y_i-x_i{)}^2\}\end{array}$$ であることを示す.
この等式の左側を(左辺),右側を(右辺)と以後表記する.

1変数の例から任意の$i\in \{1,\dots ,N\}$に対して,
$|x_i|+\frac{1}{2\lambda }(y_i-x_i{)}^2$が最小値を取るような$x_i^{\ast }$が存在する.
そこで,$x^{\ast }=(x_1^{\ast },\dots ,x_N^{\ast }{)}^T$とする.
このとき,任意の$x=(x_1,\dots ,x_N{)}^T\in R^N$に対して,$x^{\ast }$の定義より, $$|x_i^{\ast }|+\frac{1}{2\lambda }(y_i-x_i^{\ast }{)}^2\le |x_i|+\frac{1}{2\lambda }(y_i-x_i{)}^2(\forall i\in \{1,\dots ,N\left\}\right)$$ であるので, $$\text{(right)}=\sum _{i=1}^N|x_i^{\ast }|+\frac{1}{2\lambda }(y_i-x_i^{\ast }{)}^2\le \sum _{i=1}^N|x_i|+\frac{1}{2\lambda }(y_i-x_i{)}^2$$ これが任意の$x=(x_1,\dots ,x_N{)}^T\in R^N$に成り立つので,
左辺は$x=x^{\ast }$のとき最小値${\sum }_{i=1}^N|x_i^{\ast }|+\frac{1}{2\lambda }(y_i-x_i^{\ast }{)}^2$をとる.(最小値をとる$x$が存在することが示せた)
また,(右辺)$\le$(左辺)が成立することがわかる.

逆に, $$\begin{array}{cc}& \underset{x\in R^N}{\text{minimize}}\sum _{i=1}^N|x_i|+\frac{1}{2\lambda }(y_i-x_i{)}^2\\ \le & \sum _{i=1}^N|x_i^{\ast }|+\frac{1}{2\lambda }(y_i-x_i^{\ast }{)}^2\\ =& \sum _{i=1}^N\underset{x_i\in R}{\text{minimize}}(|x_i|+\frac{1}{2\lambda }(y_i-x_i{)}^2)=\text{(right)}\end{array}$$ よって,(左辺)$\le$(右辺)

3. ベイズの定理

観測行列を$A\in R^{m\times n}$,原情報を$x\in R^n$, 出力情報を$y\in R^m$とする.
出力情報は入力情報を観測行列によって変換したものに,ノイズが加えられて得られるとする. $$y=Ax+{\rho }_{0}n$$ ここで${\rho }_0>0,n\in R^m$とする.

観測情報$A$と原情報$x$,観測情報$A$と原情報$y$は互いに独立であるから,
$P(A\cap x)=P\left(A\right)\cap P\left(x\right)$,
$P(A\cap y)=P\left(A\right)\cap P\left(y\right)$ が成立することに注意すると, $$P(x|A,y)P\left(A\right)P\left(y\right)=P(y|A,x)P\left(A\right)P\left(x\right)$$ が成立する.
(Proof) $$\text{(left)}=\frac{P(x\cap A\cap y)}{P(A\cap y)}P\left(A\right)P\left(y\right)=\frac{P(y\cap A\cap x)}{P(A\cap x)}P\left(A\right)P\left(x\right)\frac{P(A\cap x)}{P(A\cap y)}\frac{P\left(y\right)}{P\left(x\right)}=\text{(right)}$$ ゆえに, $$P(x|A,y)=\frac{P(y|A,x)P\left(x\right)}{P\left(y\right)}$$ が成立.

4. メジャライザー最小化

$$\begin{array}{cc}|x-y{|}_2^2& =\sum _{i=1}^n(x_i-y_i{)}^2\\ & =\sum _{i=1}^n{(x_i-(y_i-\frac{1}{L}\nabla g\left(y{)}_i\right)-\frac{1}{L}\nabla g\left(y{)}_i\right)}^2\\ & =\sum _{i=1}^n{(x_i-(y_i-\frac{1}{L}\nabla g\left(y{)}_i\right))}^2-\frac{2}{L}\nabla g(y{)}_i(x_i-(y_i-\frac{1}{L}\nabla g\left(y{)}_i\right))+\frac{1}{L^2}(\nabla g(y{)}_i{)}^2\\ & ={|x-(y-\frac{1}{L}\nabla g\left(y\right)\left)\right|}_2^2-\frac{2}{L}\nabla g\left(y{)}^T\right(x-y)-\frac{1}{L^2}|\nabla g(y){|}_2^2\end{array}$$

初めに以下を示す $$g\left(x\right)\le q_L(x,y)$$ (Proof)
$\nabla g\left(x\right)$はリプシッツ定数$L$の連続関数だから,シュワルツの不等式より $${\left(\nabla g\right(x)-\nabla g(x\left)\right)}^T(x-y)\le \parallel \nabla g\left(x\right)-\nabla g\left(x\right){\parallel }_2\parallel x-y{\parallel }_2\le L\parallel x-y{\parallel }_2^2$$ $h:R^n\to R$を $h\left(x\right)=\frac{1}{2}L\parallel x{\parallel }_2^2-g\left(x\right)$と定めると,
$\nabla h\left(x\right)=Lx-\nabla g\left(x\right)$であり,上式より
$${\left(\nabla h\right(x)-\nabla h(y\left)\right)}^T(x-y)\ge 0$$ である. $h\in C^1$級であるので,$h$は凸関数.ゆえに, $$\begin{array}{cc}& h\left(x\right)\ge h\left(y\right)+{\left(\nabla h\right(y\left)\right)}^T(x-y)\\ \iff & g\left(x\right)\le q_L(x,y)\end{array}$$ 証明のための予備知識
URL>Theorem1,2,URL > Proposition1.3

次に以下を示す.

$g\left(x\right)=|y-Ax{|}_2^2$とすると,
$$\nabla g\left(x\right)=-\frac{1}{\lambda }{A}^T(y-Ax)$$ (Proof) $${\left(\nabla g\right(x\left)\right)}_i=\frac{\partial g\left(x\right)}{\partial x_i}=\frac{1}{2\lambda }\frac{\partial }{\partial x_i}\sum _{j=1}^m{(y_i-\sum _{i=1}^n{a}_{ji}{x}_i)}^2=-\frac{1}{\lambda }\sum _{j=1}^m{a}_{ji}(y_i-\sum _{i=1}^n{a}_{ji}{x}_i)$$ 一方, $${(-\frac{1}{\lambda }{A}^T(y-Ax\left)\right)}_i=-\frac{1}{\lambda }\sum _{j=1}^m{a}_{ji}(y_j-\sum _{i=1}^n{a}_{ji}{x}_i)$$ 次にリプシッツ定数$L$は

$L=\frac{1}{\lambda }|A^{T}A{|}_2$

となることを示す.

(Proof) $$|\nabla g\left(x_1\right)-\nabla g\left(x_2\right)|=\frac{1}{\lambda }|A^{T}A(x_2-x_1){|}_2\le \frac{1}{\lambda }|A^{T}A{|}_2|x_1-x_2{|}_2$$ ここで,任意の行列$A\in R^{n,n}$に対し, $$|A{|}_2:=ma{x}_{|x{|}_2=1}|Ax{|}_2$$ と定義する.
有限次元ベクトル空間上のノルムが1となる部分集合はコンパクト,
有限次元線形写像やノルムの連続性を用いることで右辺の集合は最大値を持つことが示される.
また, $|A{|}_2=ma{x}_{|x{|}_2=1}|Ax{|}_2$は$x$が$A$の最大の固有値${\mu }_0$に対応する固有ベクトルを持つとき最大になり,その値は$\sqrt{{\mu }_0}$