Matlab code to reproduce the results of the paper
Trajectory of Alternating Direction Method of Multipliers and Adaptive Acceleration
Clarice Poon, Jingwei Liang, 2019
Consider the following constrained and composite optimisation problem $$ \min_{x \in \mathbb{R}^n , y\in \mathbb{R}^m } ~ R(x) + J(y) \quad \textrm{such~that} \quad Ax + By = b , $$ where the following basic assumptions are imposed
-
$R, J$ are proper convex and lower semi-continuous functions. -
$A : \mathbb{R}^n \to \mathbb{R}^p $ and
$B : \mathbb{R}^m \to \mathbb{R}^p$ are {injective} linear operators. -
$\mathrm{ri} ( \mathrm{dom}(R) \cap \mathrm{dom}(J) ) \neq \emptyset$ , and the set of minimizers is non-empty.
Augmented Lagrangian associated to (1) reads
$$
\mathcal{L}(x,y; \psi) = R(x) + J(y) + \langle{\psi, Ax+By-b}\rangle + \tfrac{\gamma}{2}|Ax+By-b|^2 .
$$
where
Consider the following constrained problem
$$
\min_{x \in \mathbb{R}^{n} } ~ R(x) \quad
\textrm{suchthat} \quad Kx = f .
$$
Denote the set that} \quad x - y = 0 ,
\end{aligned}
$$
Here
-
$\ell_{1}$ -norm$(m, n)=(512, 2048)$ , solution$x^\star$ is$128$ -sparse; -
$\ell_{1,2}$ -norm$(m, n)=(512, 2048)$ , solution$x^\star$ has$32$ non-zero blocks of size$4$ ; -
Nuclear norm
$(m, n)=(1448, 4096)$ , solution$x^\star$ has rank of$4$ .
Case |
Case |
Nuclear norm |
---|---|---|
The formulation of LASSO in the form of ADMM reads
$$
\begin{aligned}
\min_{x, y \in \mathbb{R}^{n}} ~ \mu |x|_1 + \tfrac{1}{2} |Ky - f|^2 \quad\textrm{suchthat}\quad x - y = 0 ,
\end{aligned}
$$
where $K \in \mathbb{R}^{m\times n} , m < n$ is a random Gaussian matrix.
covtype | ijcnn1 | phishing |
---|---|---|
The TV based image inpainting can be formulated as
$$
\min_{x\in\mathbb{R}^{n\times n}} ~ |\nabla x|{1} \quad \textrm{such~that} \quad \mathcal{P}{\mathcal{S}}(x) = f .
$$
Define $\Omega = {x \in \mathbb{R}^{n\times n} : \mathcal{P}{\mathcal{S}}(x) = f }$, then (2) becomes
$$
\min{x\in\mathbb{R}^{n\times n}, y\in\mathbb{R}^{2n\times n}} ~ |y|{1} + \iota{\Omega}(x) \quad \textrm{suchthat} \quad \nabla x - y = 0 ,
$$
which is special case of (1) with \iota_{\Omega}(x) + \tfrac{\gamma}{2} |\nabla x - \tfrac{1}{\gamma} ( {z}{k-1} - 2\psi{k-1} ) |^2 ,
$$
which does not admit closed form solution. In the implementation, finite-step FISTA is applied to roughly solve the above problem.
Angle |
Error |
PSNR |
---|---|---|
Image quality comparison at iteration step
Original image | ADMM, PSNR = 26.6935 | iADMM, PSNR = 26.3203 |
---|---|---|
Corrupted image | A3DMM, |
A3DMM, |
Copyright (c) 2019 Clarice Poon and Jingwei Liang