Certified basis-pursuit denoising by primal-dual hybrid gradient

Inputs are integers $m,n\ge 1$, a matrix $A\in {\mathbb{R}}^{m\times n}$ in the standard finite coordinate bases, a vector $y\in {\mathbb{R}}^m$, a radius $ϵ\ge 0$, positive real step sizes $\alpha ,\beta$, an initial primal-dual state $x^0\in {\mathbb{R}}^n$, $p^0\in {\mathbb{R}}^m$, a nonnegative integer sweep cap $N$, positive integer proximal-call caps $C_f,C_{g^{\ast }}$, and deterministic finite solver programs with Boolean certificate checkers for the two proximal calls. Each solver/checker record must be complete and well-formed. Admissible solver/checker pairs satisfy the soundness condition that an accepted output is an exact minimizer of its stated proximal subproblem; this is an input assumption, not a finite proof search performed by the procedure.

Set $f(x)=\mathrm{\parallel }x{\mathrm{\parallel }}_1$ and $g(u)=0$ when $\mathrm{\parallel }u-y{\mathrm{\parallel }}_2\le ϵ$, with $g(u)=+\mathrm{\infty }$ otherwise. Define the Fenchel conjugate by $g^{\ast }(p)={\sup }_{u\in {\mathbb{R}}^m}(⟨p,u⟩-g(u))$. For a proper closed convex function $q$ and $t>0$, ${\mathrm{prox}}_{tq}(v)$ denotes the unique minimizer of $q(w)+\mathrm{\parallel }w-v{\mathrm{\parallel }}_2^2\mathrm{/}(2t)$. Let $A^{\ast }$ be the Euclidean adjoint and let $\mathrm{\parallel }A{\mathrm{\parallel }}_2={\sup }_{\mathrm{\parallel }v{\mathrm{\parallel }}_2\le 1}\mathrm{\parallel }Av{\mathrm{\parallel }}_2$. The target is ${\min }_{z\in {\mathbb{R}}^n}\mathrm{\parallel }z{\mathrm{\parallel }}_1\text{subject to}\mathrm{\parallel }Az-y{\mathrm{\parallel }}_2\le ϵ\mathrm{.}$

Return invalid-input if dimensions or vectors do not match, if $ϵ<0$, if $N$ is not a nonnegative integer, if either proximal cap is not a positive integer, if either step size is nonpositive, if either solver/checker record is missing or malformed, or if the exact strict check $\alpha \beta \mathrm{\parallel }A{\mathrm{\parallel }}_2^2<1$ fails. For admissible inputs initialize ${\bar{x}}^0=x^0$ and perform the exact primal-dual hybrid-gradient recurrence for at most $N$ sweeps: $p^{k+1}={\mathrm{prox}}_{\beta g^{\ast }}(p^k+\beta A{\bar{x}}^k),x^{k+1}={\mathrm{prox}}_{\alpha f}(x^k-\alpha A^{\ast }{p}^{k+1}),{\bar{x}}^{k+1}=2x^{k+1}-x^k\mathrm{.}$ Use the supplied solver/checker pairs and caps for the corresponding proximal calls. Propagate any invalid-input, prox-call-failed, or prox-cap-exhausted status and the state returned by the primal-dual procedure. If all $N$ sweeps complete, let $(x,p)$ be the final primal-dual state and perform these exact tests in order:

• If $p\mathrm{\ne }0$, $A^{\ast }p=0$, and $\mathrm{\mid }⟨p,y⟩\mathrm{\mid }>ϵ\mathrm{\parallel }p{\mathrm{\parallel }}_2$, return infeasible.
• Otherwise, if $\mathrm{\parallel }Ax-y{\mathrm{\parallel }}_2\le ϵ$, $\mathrm{\parallel }{A}^{\ast }p{\mathrm{\parallel }}_{\mathrm{\infty }}\le 1$, and $\mathrm{\parallel }x{\mathrm{\parallel }}_1=-⟨p,y⟩-ϵ\mathrm{\parallel }p{\mathrm{\parallel }}_2$, return success with $x$.
• If neither certificate passes, return budget-exhausted with the final state.

For $N=0$, test the initial state. The certificate tests use exact real comparisons. The procedure makes no guarantee that a finite run finds a certificate and makes no convergence or finite-termination claim.

Primal-dual hybrid-gradient recurrence, proximal-call interface, caps, and statuses

Exact primal optimality and infeasibility certificates

Proper, closed, and convex BPDN objectives

Existence of a minimizer when the residual ball is nonempty

Induced Euclidean operator norm

Proximal mapping as a global minimizer

Existence and uniqueness of proximal minimizers

Euclidean adjoint

Finite-dimensional norms

Chambolle and Pock, A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging, §§2–3.1

Foucart and Rauhut, A Mathematical Introduction to Compressive Sensing, §4.3