Exercises

$\mathbf{x}^{(t+1)} = \mathrm{soft}_{\lambda/L}\bigl(\mathbf{x}^{(t)} + L^{-1}\mathbf{A}^{H}(\mathbf{y}-\mathbf{A}\mathbf{x}^{(t)})\bigr)$, with $L\geq\lambda_{\max}(\mathbf{A}^{H}\mathbf{A})$.

$k_{\text{ISTA}}\approx k_{\text{FISTA}}^2 = 10{,}000$.

$\mathbf{x}^{+}=(\mathbf{A}^{H}\mathbf{A}+\rho I)^{-1}(\mathbf{A}^{H}\mathbf{y}+\rho(\mathbf{z}-\mathbf{u}))$, $\mathbf{z}^{+}=\mathrm{soft}_{\lambda/\rho}(\mathbf{x}^{+}+\mathbf{u})$, $\mathbf{u}^{+}=\mathbf{u}+\mathbf{x}^{+}-\mathbf{z}^{+}$.

(1) Compute $\mathbf{c}=\mathbf{A}^{H}\mathbf{r}^{(t)}$; (2) add $i^\star=\arg\max|c_i|$ to the support; (3) solve least-squares on the active set; (4) update residual $\mathbf{r}^{(t+1)}=\mathbf{y}-\mathbf{A}\hat{\mathbf{x}}$.

The posterior is a mixture over all $2^N$ supports. Entries of the posterior mean are weighted averages across supports; the weight on "$x_i=0$" supports shrinks but does not make $\mathbb{E}[x_i\mid\mathbf{y}]$ exactly zero unless the posterior collapses.

Let $f(\mathbf{x})=\tfrac{1}{2}\|\mathbf{y}-\mathbf{A}\mathbf{x}\|_2^2$. Lipschitz gradient with $L$ gives $f(\mathbf{x}^{+})\leq f(\mathbf{x})-\tfrac{1}{2L}\|\nabla f(\mathbf{x})\|_2^2$ for a full gradient step.

$\|\mathrm{prox}_{\lambda/L\,\|\cdot\|_1}(\mathbf{u})-\mathrm{prox}_{\lambda/L\,\|\cdot\|_1}(\mathbf{v})\|_2\leq\|\mathbf{u}-\mathbf{v}\|_2$.

The composite iteration decreases $F(\mathbf{x})=f(\mathbf{x})+\lambda\|\mathbf{x}\|_1$ at rate $O(1/k)$.

$(\mathbf{A}^{H}\mathbf{A}+\rho I_N)^{-1} = \rho^{-1}I_N - \rho^{-1}\mathbf{A}^{H}(\rho I_M+\mathbf{A}\mathbf{A}^{H})^{-1}\mathbf{A}\cdot\rho^{-1}$.

One $M\times M$ Cholesky factorization ($O(M^3)$) shared across iterations; per-iteration cost becomes $O(MN)$.

At each iteration, the correlation of the residual with any in-support atom dominates the correlation with any out-of-support atom, provided the coherence is small.

The worst-case correlation gap is $1-(2s-1)\mu>0$, i.e.\ $\mu<1/(2s-1)$. This ensures OMP never selects a wrong atom and exits after exactly $s$ iterations.

$\mathrm{hard}_\tau(x) = x\cdot\mathbb{1}\{|x|>\tau\}$. Discontinuous; equivalent to proximal of $\lambda\|\cdot\|_0$ which is nonconvex.

Lipschitz-continuous, monotone, equals $\mathrm{prox}_{\lambda\|\cdot\|_1}$ which is convex.

Hard thresholding algorithms (IHT) lack global convergence guarantees; soft thresholding algorithms (ISTA) converge globally.

For each group $g$, $\mathrm{prox}_{\lambda\|\cdot\|_{2,1}}(\mathbf{v})_g = \max(1-\lambda/\|\mathbf{v}_g\|_2, 0)\cdot\mathbf{v}_g$.

$V^{(t)}=\rho^{-1}\|\mathbf{u}^{(t)}-\mathbf{u}^\star\|_2^2+\rho\|\mathbf{z}^{(t)}-\mathbf{z}^\star\|_2^2$ is nonincreasing and bounded below.

$V^{(t)}-V^{(t+1)}\geq\rho\|\mathbf{r}^{(t+1)}\|_2^2+\rho\|\mathbf{s}^{(t+1)}\|_2^2$ where $\mathbf{r}, \mathbf{s}$ are primal/dual residuals. Summability forces $\|\mathbf{r}^{(t)}\|_2,\|\mathbf{s}^{(t)}\|_2\to 0$.

Compute posterior $p(\mathbf{x}\mid\mathbf{y},\boldsymbol{\gamma})$: Gaussian with mean $\boldsymbol{\mu}$, covariance $\boldsymbol{\Sigma}$.

Maximize $\mathbb{E}[\log p(\mathbf{x}\mid\boldsymbol{\gamma})]$ in $\gamma_i$: $\partial/\partial\gamma_i[-\tfrac{1}{2}\log\gamma_i - \tfrac{1}{2\gamma_i}\mathbb{E}[x_i^2]]=0$ gives $\hat{\gamma}_i=\mathbb{E}[x_i^2]=\mu_i^2+\Sigma_{ii}$.

Define $V_k = \tfrac{2}{L}(t_k^2)(F(\mathbf{x}^{(k)})-F^\star) + \|t_k\mathbf{x}^{(k)}-(t_k-1)\mathbf{x}^{(k-1)}-\mathbf{x}^\star\|_2^2$ with $t_k\sim k/2$.

Using the descent lemma $F(\mathbf{x}^{(k+1)})\leq F(\mathbf{y})+\tfrac{L}{2}\|\mathbf{x}^{(k+1)}-\mathbf{y}\|_2^2+\nabla f(\mathbf{y})^T(\mathbf{x}^{(k+1)}-\mathbf{y})$ at the momentum point $\mathbf{y}$, one shows $V_{k+1}\leq V_k$.

$V_k\leq V_0$ gives $F(\mathbf{x}^{(k)})-F^\star \leq \tfrac{2L}{t_k^2}V_0 = O(1/k^2)$.

Correlate residual with columns; select top $2s$. RIP guarantees signal components dominate noise.

Merge with current support ($\leq 3s$ atoms); solve least-squares restricted to this support.

Keep top $s$ magnitudes. Using $\delta_{4s}$-RIP, the error contracts by a factor $<1$ per iteration, giving geometric convergence to an $O(\|\mathbf{w}\|_2)$-neighborhood.

$\mathcal{L}(\boldsymbol{\gamma})=-\log\det(\mathbf{C})-\mathbf{y}^H\mathbf{C}^{-1}\mathbf{y}$ with $\mathbf{C}=\sigma^2I_M+\mathbf{A}\Gamma\mathbf{A}^{H}$, $\Gamma=\mathrm{diag}(\boldsymbol{\gamma})$.

$\mathbf{C}$ is $M\times M$; adding a nonzero $\gamma_i>0$ adds at most rank $1$. Once rank $M$ is reached, further positive $\gamma_i$ give no improvement to $\mathcal{L}$.

Wipf-Rao (2004) show the unconstrained maxima lie on faces of the positive orthant with at most $M$ positive coordinates.