ISTA algorithm : Iterative Shrinkage‑Thresholding Algorithm

Set $x\in\mathbb{R}^n\quad y\in\mathbb{R}^n\quad n\ll m\quad y=\phi x$

Given $y$ and $\phi$, we want to get $x$, if we use the LASSO regression model $$\mathrm{argmin}\ \|y-\phi x\|_2^2+\lambda\|x\|_1$$

We can use iteration $$x^{k+1}=\mathrm{prox}_{\beta\lambda\|\cdot\|_1}\left(x^{k}-2\beta\phi^T(\phi x^{k}-y)\right)$$ to solve it

That is the ISTA algorithm, to derive this expression, we need to introduce the following concepts

Definition. Let $\varphi:\mathbb{R}^n\rightarrow\mathbb{R}\cup\{+\infty\}$ be proper. The subdifferential of $\varphi$ at $x\in\mathbb{R}^n$ is defined by $$\partial\varphi(x):=\left\{y\in\mathbb{R}^n:\ \varphi(z)\ge\varphi(x)+y^T(z-x),\ \forall z\in\mathbb{R}^n\right\}$$

Prop 1. Let $\varphi$ be a real‑value convex function on $\mathbb{R}^n$. If $\varphi$ is differentiable at $x$ then $\partial\varphi(x)=\nabla\varphi(x)$

Proof. $\varphi$ is convex so for any $x,y\in\mathbb{R}^n$ $$\forall \lambda\in(0,1)$$ $$f(\lambda x+(1-\lambda)y)\le(1-\lambda)(f(x))+\lambda f(y)$$ $$f(x+\lambda(y-x))\le(1-\lambda)(f(x))+\lambda f(y)$$

So $$\frac{f(x+\lambda(y-x))-(f(x))}{\lambda}\le f(y)-(f(x))$$

$$\nabla (f(x))\cdot(y-x)\le f(y)-(f(x))$$ $$f(y)\ge\nabla (f(x))\cdot(y-x)+(f(x))$$

So $\nabla\varphi(x)\in\partial\varphi(x)$

If $p\in\partial\varphi(x)$ $$\forall z\in\mathbb{R}^n\quad \varphi(z)\ge\varphi(x)+p\cdot(z-x)$$

$h$ is a unit vector, let $(z=x+th)$

$$\varphi(x+th)\ge\varphi(x)+t\cdot p\cdot h$$

$$\frac{\varphi(x+th)-\varphi(x)}{t}\ge p\cdot h$$

So $$\lim_{t\to0}\frac{\varphi(x+th)-\varphi(x)}{t}\ge p\cdot h$$

$$\nabla\varphi(x)\cdot h=D_h\varphi(x)=\lim_{t\to0}\frac{\varphi(x+th)-\varphi(x)}{t}\ge p\cdot h$$

$$(\nabla\varphi(x)-p)\cdot h=0\quad \text{for any }h$$

So $\nabla\varphi(x)=p$

So $\partial\varphi(x)\supset\nabla\varphi(x)$

Theorem 1. Let $\varphi$ be a real‑valued convex function on $\mathbb{R}^n$. Then $$x^*\in\mathrm{Argmin}\ \varphi \iff 0\in\partial\varphi(x^*)$$

Proof. $$ \begin{aligned} x^*\in\mathrm{Argmin}\ \varphi &\iff \varphi(x^*)\le\varphi(z)\quad \forall z\in\mathbb{R}^n\\ 0\cdot(z-x^*)+\varphi(x^*)&\le\varphi(z)\\ &\iff 0\in\partial\varphi(x^*) \end{aligned} $$

Definition. Let $\varphi\in\Gamma_0(\mathbb{R}^n)$. The prox(imity operator) of $\varphi$ at $x$ is $$\mathrm{prox}_\varphi(x):=\underset{u\in\mathbb{R}^n}{\mathrm{argmin}}\ \frac12\|u-x\|_2^2+\varphi(u)$$

Prop 2. Let $\varphi\in\Gamma_0(\mathbb{R}^n)$. Then $$y\in\partial\varphi(x)\iff x=\mathrm{prox}_\varphi(x+y)$$

Proof. $\forall x,y\in\mathbb{R}^n$

let $\tilde{\varphi}(u)=\frac12\|u-(x+y)\|_2^2+\varphi(u)$ $$\partial\tilde{\varphi}(u)=(u-(x+y))+\partial\varphi(u)$$

$$ \begin{aligned} x=\mathrm{prox}_\varphi(x+y)&\iff x=\underset{u\in\mathbb{R}^n}{\mathrm{argmin}}\ \frac12\|u-(x+y)\|_2^2+\varphi(u)\\ &=\underset{u\in\mathbb{R}^n}{\mathrm{argmin}}\ \tilde{\varphi}(u)\\ &\iff 0\in\partial\tilde{\varphi}(x)\quad (\text{Thm1.})\\ &\iff 0\in -y+\partial\varphi(x)\\ &\iff y\in\partial\varphi(x) \end{aligned} $$

Theorem 2. Let $\varphi\in\Gamma_0(\mathbb{R}^n)$. Then $x^*\in\mathrm{Argmin}\ \varphi \iff x^*=\mathrm{prox}_\varphi(x^*)$

Proof. $x^*\in\mathrm{Argmin}\ \varphi \iff 0\in\partial\varphi(x^*)\quad (\text{Thm1.})$ $$\iff x^*=\mathrm{prox}_\varphi(x^*)\quad (\text{prop2.})$$

Definition. $T$ is $L$-Lipschitz continuous if $\forall x,y\in\mathbb{R}^n$ $$\|Tx-Ty\|\le L\|x-y\|$$

Definition. $T$ is nonexpansive if $\forall x,y\in\mathbb{R}^n$ $$\|Tx-Ty\|\le\|x-y\|$$

Definition. $T$ is $\alpha-$averaged nonexpansive if $\exists$ a nonexpansive operator $N$ s.t. $T=(1-\alpha)I+\alpha N\quad \alpha\in(0,1)$

Prop 3. If $T$ is average nonexpansive then $T$ is nonexpansive

Proof. Since $T$ is $\alpha$-average nonexpansive so $\exists$ nonexpansive $N$ s.t. $T=(1-\alpha)I+\alpha N$

$$ \begin{aligned} \|Tx-Ty\|_2^2&=\|(1-\alpha)(x-y)+\alpha Nx-\alpha Ny\|_2^2\\ &=(1-\alpha)^2\|x-y\|_2^2+\alpha^2\|Nx-Ny\|_2^2+2\alpha(1-\alpha)(x-y)\cdot(Nx-Ny)\\ &\le(1-\alpha)^2\|x-y\|_2^2+\alpha^2\|x-y\|_2^2+2\alpha(1-\alpha)\|x-y\|\cdot\|Nx-Ny\|\\ &\le(1-\alpha)^2\|x-y\|_2^2+\alpha^2\|x-y\|_2^2+(2\alpha-2\alpha^2)\|x-y\|_2^2\\ &=\left((1+\alpha^2-2\alpha+\alpha^2+2\alpha-2\alpha^2)\right)\|x-y\|_2^2\\ &=\|x-y\|_2^2 \end{aligned} $$

So $T$ is nonexpansive

Prop 4. $T$ is $\alpha-$averaged nonexpansive $\ \alpha<1$ iff $$\forall x,y\in\mathbb{R}^n\quad \|Tx-Ty\|_2^2\le\|x-y\|_2^2-\frac{1-\alpha}{\alpha}\left\|(I-T)x-(I-T)y\right\|_2^2$$

$$N=\frac1\alpha(T-(1-\alpha)I)\quad T=(1-\alpha)I+\alpha N\quad I-T=\alpha(I-N)$$

$$\|Tx-Ty\|_2^2\le\|x-y\|_2^2-\frac{1-\alpha}{\alpha}\left\|(I-T)x-(I-T)y\right\|_2^2$$

$$\iff \left\|(1-\alpha)(x-y)+\alpha(Nx-Ny)\right\|_2^2\le\|x-y\|_2^2-\frac{1-\alpha}{\alpha}\left\|\alpha\left[(I-N)x-(I-N)y\right]\right\|_2^2$$

$$ \begin{aligned} (1-\alpha)^2\|x-y\|_2^2+\alpha^2\|Nx-Ny\|_2^2+2\alpha(1-\alpha)(x-y)(Nx-Ny)&\\ \le\|x-y\|_2^2-\alpha(1-\alpha)\|x-y-(Nx-Ny)\|_2^2&\\ \le\|x-y\|_2^2-\alpha(1-\alpha)\|x-y\|_2^2-\alpha(1-\alpha)\|Nx-Ny\|_2^2+2\alpha(1-\alpha)(x-y)\cdot(Nx-Ny)& \end{aligned} $$

$$\iff \left(1+\alpha^2-2\alpha-1+\alpha-\alpha^2\right)\|x-y\|_2^2\le\left(-\alpha+\alpha^2-\alpha^2\right)\|Nx-Ny\|_2^2$$

$$\iff \|Nx-Ny\|_2^2\le\|x-y\|_2^2$$

$N$ is nonexpansive $\iff T$ is $\alpha-$averaged nonexpansive

Lemma 1. Let $T$ be nonexpansive operator s.t. $\mathrm{Fix}(T)\neq\emptyset$

For $\forall$ initial vector $x^{0}\quad x^{k+1}=Tx^{k}$ get Picard sequence $\{x^{k}\}_{k\in\mathbb{N}}\in\mathbb{R}^n$. It satisfies that $\lim\limits_{k\to\infty}\|Tx^{k}-x^{k}\|=0$, then $\{x^{k}\}$ converge to a fixed point of $T$

Proof. $\forall$ fixed point $\hat{x}$ of $T$

$$ \begin{aligned} \|x^{k+1}-\hat{x}\|&=\|Tx^{k}-T\hat{x}\|\\ &=\|Tx^{k}-T\hat{x}\|\le\|x^{k}-\hat{x}\| \end{aligned} $$

So the sequence $\{\|x^{k}-\hat{x}\|\}_{k\in\mathbb{N}}$ is monotonically decreasing

Since $\{\|x^{k}-\hat{x}\|\}_{k\in\mathbb{N}}$ has a lower bound so $\lim\limits_{k\to\infty}\|x^{k}-\hat{x}\|$ exist

Also $\|x^{k}-\hat{x}\|\le\|x^{0}-\hat{x}\|$ so the sequence is bounded so $\exists$ a subsequence $\{x^{k_j}\}$ converge to some $x^*$

$$\lim_{j\to\infty}\|Tx^*-Tx^{k_j}\|\le\lim_{j\to\infty}\|x^*-x^{k_j}\|=0\quad (\text{Since }T\text{ nonexpansive})$$

So $\lim\limits_{j\to\infty}Tx^*=\lim\limits_{j\to\infty}Tx^{k_j}=Tx^*$

$$Tx^*-x^*=\lim_{j\to\infty}Tx^{k_j}-x^{k_j}=0$$

So $Tx^*=x^*$ so $x^*$ is fixed point $x^*\in\mathrm{Fix}(T)$

Since $\lim\limits_{k\to\infty}\|x^{k}-\hat{x}\|$ exist for $\forall \hat{x}\in\mathrm{Fix}(T)$

So $\lim\limits_{k\to\infty}\|x^{k}-x^*\|$ exist and $\lim\limits_{j\to\infty}\|x^{k_j}-x^*\|=0$

So $\lim\limits_{k\to\infty}\|x^{k}-x^*\|=0$

Theorem 3. Let $T$ be average nonexpansive operator and $\mathrm{Fix}(T)\neq\emptyset\quad x^{0}\in\mathbb{R}^n$ $x^{k+1}=Tx^{k}$ get $\{x^{k}\}_{k\in\mathbb{N}}$. Then $\{x^{k}\}_{k\in\mathbb{N}}$ converge to a fixed point of $T$

Proof. $T$ is $\alpha$-average nonexpansive so $T$ is nonexpansive (Prop3)

By prop4 $$\|Tx-Ty\|_2^2\le\|x-y\|_2^2-\frac{1-\alpha}{\alpha}\left\|(I-T)x-(I-T)y\right\|_2^2$$

Set $x=x^{k}\quad y=\hat{x}$ then $$\|x^{k+1}-\hat{x}\|_2^2\le\|x^{k}-\hat{x}\|_2^2-\frac{1-\alpha}{\alpha}\left\|x^{k}-x^{k+1}-(\hat{x}-\hat{x})\right\|_2^2$$

$$\|x^{k+1}-\hat{x}\|_2^2+\frac{1-\alpha}{\alpha}\|x^{k+1}-x^{k}\|_2^2\le\|x^{k}-\hat{x}\|_2^2$$

$$\frac{1-\alpha}{\alpha}\|x^{k+1}-x^{k}\|_2^2\le\|x^{k}-\hat{x}\|_2^2-\|x^{k+1}-\hat{x}\|_2^2$$

So $\frac{1-\alpha}{\alpha}\sum_{k=0}^K\|x^{k+1}-x^{k}\|_2^2\le\|x^{0}-\hat{x}\|_2^2-\|x^{K+1}-\hat{x}\|_2^2$ $$\le\|x^{0}-\hat{x}\|_2^2$$

So $\lim\limits_{k\to\infty}\|x^{k+1}-x^{k}\|_2^2=0$

So by lemma1. $\{x^{k}\}$ will converge to a fixed point of $T$

Lemma 2. Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be differentiable and convex $L$ be a positive real number. Then $\nabla f$ is $L$-Lipschitz continuous iff $$\forall x,y\in\mathbb{R}^n\quad \|\nabla f(x)-\nabla f(y)\|^2\le L\langle x-y,\nabla f(x)-\nabla f(y)\rangle$$

So we can get $$ \begin{aligned} &\left\|(I-(2/L)\nabla f)x-(I-(2/L)\nabla f)y\right\|_2^2\\ =&\left\|(x-y)-\frac{2}{L}(\nabla f(x)-\nabla f(y))\right\|_2^2\\ =&\|x-y\|_2^2+\frac{4}{L^2}\|\nabla f(x)-\nabla f(y)\|_2^2-\frac{4}{L}(x-y)\cdot(\nabla f(x)-\nabla f(y))\\ =&\|x-y\|_2^2+\frac{4}{L}\left(\frac{1}{L}\|\nabla f(x)-\nabla f(y)\|_2^2-(x-y)\cdot(\nabla f(x)-\nabla f(y))\right)\\ \le&\|x-y\|_2^2 \quad (\text{lemma 2.}) \end{aligned} $$

So $I-\frac{2}{L}\nabla f$ is nonexpansive and $$I-\alpha\nabla f=(1-\theta)I+\theta\left(I-\frac{2}{L}\nabla f\right),\quad \theta=\frac{\alpha L}{2}\in(0,1)$$

So $\frac{\alpha L}{2}<1$ $\alpha<\frac{2}{L}$ and then $I-\alpha\nabla f$ is average nonexpansive

Lemma 3. Let $T_1,T_2$ be $\theta_1-$ and $\theta_2-$averaged operators on $\mathbb{R}^n$ with $\theta_1,\theta_2\in(0,1)$. Then $T_1\circ T_2$ is $\theta-$averaged with $$\theta=\frac{\theta_1+\theta_2-2\theta_1\theta_2}{1-\theta_1\theta_2}$$

Definition. $T:\mathbb{R}^n\rightarrow\mathbb{R}^n$ be an operator. $T$ is firmly nonexpansive if $$\forall x,y\in\mathbb{R}^n\quad \|Tx-Ty\|^2\le \langle Tx-Ty,x-y\rangle$$

Prop 5. $T$ is firmly nonexpansive $\iff T$ is $\frac12-$averaged nonexpansive

Proof. $$T=\frac12 I+\frac12 N$$ $$N=2\left(T-\frac12 I\right)=2T-I$$

$$ \begin{aligned} &\forall x,y\in\mathbb{R}^n\\ \|Nx-Ny\|_2^2&=\|2Tx-2Ty-(x-y)\|_2^2\\ &=4\|Tx-Ty\|_2^2+\|x-y\|_2^2-4(Tx-Ty)\cdot(x-y)\\ &\le4(Tx-Ty)\cdot(x-y)+\|x-y\|_2^2-4(Tx-Ty)\cdot(x-y)\\ &=\|x-y\|_2^2 \end{aligned} $$

Theorem 4. Let $\varphi\in\Gamma_0(\mathbb{R}^n)$. Then $\mathrm{prox}_\varphi$ is firmly nonexpansive

$\forall x,y\in\mathbb{R}^n$ let $u=\mathrm{prox}_\varphi(x)\quad v=\mathrm{prox}_\varphi(y)$

Via prop2. $$x-u\in\partial\varphi(u),\quad y-v\in\partial\varphi(v)$$ $$\iff \forall z\quad \varphi(z)\ge\varphi(u)+(z-u)\cdot(x-u) \quad ①$$ $$\varphi(z)\ge\varphi(v)+(z-v)\cdot(y-v) \quad ②$$

let $①\ z=v\quad ②\ z=u$ $$\varphi(v)\ge\varphi(u)+(v-u)\cdot(x-u) \quad ③$$ $$\varphi(u)\ge\varphi(v)+(u-v)\cdot(y-v) \quad ④$$

So $③+④\implies 0\ge(v-u)\cdot(x-u)-(v-u)\cdot(y-v)$ $$0\ge(v-u)\left[(x-u)-(y-v)\right]=(v-u)\cdot\left((x-y)+(v-u)\right)$$

So $$\|u-v\|_2^2\le(x-y)(u-v)$$ $$\left\|\mathrm{prox}_\varphi(x)-\mathrm{prox}_\varphi(y)\right\|_2^2\le\langle x-y,\mathrm{prox}_\varphi(x)-\mathrm{prox}_\varphi(y)\rangle$$

So $\mathrm{prox}_\varphi$ is firmly nonexpansive and $\frac12$ average nonexpansive

So for the model $$\mathrm{argmin}\ F(x)=\|y-\phi x\|_2^2+\lambda\|x\|_1=f(x)+g(x)$$

$f(x)=\|y-\phi x\|_2^2$ is differentiable, $g(x)=\lambda\|x\|_1$ is not differentiable, $F$ is convex

$$ \begin{aligned} \partial F(x)&=\nabla f(x)+\partial g(x)\\ &=2\phi^T(\phi x-y)+\partial g(x) \end{aligned} $$

$\mathrm{argmin}\ F(x)$ $$\iff 0\in\nabla f(x)+\partial g(x)$$ $$\iff -\beta\nabla f(x)\in\partial(\beta g)(x)$$ $$\iff x=\mathrm{prox}_{\beta g}\left(x-\beta\nabla f(x)\right)$$

Set $$x^{k+1}=\mathrm{prox}_{\beta g}\left(x^{k}-\beta\nabla f(x^{k})\right)=Tx^{k}=T_1\circ T_2(x^{k})$$

$T_1=\mathrm{prox}_{\beta g},\quad T_2=I-\beta\nabla f$

Since $\nabla f=2\phi^T(\phi x-y)$ and $g=\lambda\|\cdot\|_1$, the explicit update is $$x^{k+1}=\mathrm{prox}_{\beta\lambda\|\cdot\|_1}\left(x^{k}-2\beta\phi^T(\phi x^{k}-y)\right)$$

With $0<\beta<2/L$ and $L=2\|\phi^T\phi\|$, $T_1,T_2$ are average nonexpansive; by Lemma 3 $T_1\circ T_2$ is average nonexpansive

So $x^{k+1}=Tx^{k}\quad \{x^{k}\}_{k\in\mathbb{N}}$ will converge to a fixed point which is the global min point