List of algorithms for analysis formulation

We consider TV-like problem of the form
&space;+&space;g(D&space;x))

where $f,g$ are convex, lsc, closed, $A$ is a linear operator, $D$ is represents a finite difference operator, either in 1D or 2D
We let $\ell(x) = f(Ax - y)$.

Depending on $f,g,A$ several algorithms can be implemented and below is a subset of them.

# Data fidelity loss and metric on D x

Huber:

- Smooth
- prox-easy but $f \circ A$ is not prox-easy except if $A$ is diagonalizable in Fourier

L1:

- Nonsmooth
- prox-easy but $f \circ A$ is not prox-easy

L1-L2:

- Only make sense for 2D
- Nonsmooth
- prox-easy but $f \circ A$ is not prox-easy

MSE:

- Smooth
- prox-easy but $f \circ A$ is not prox-easy except if $A$ is diagonalizable in Fourier

Note: Huber and L1 can be used either as a data fidelity metric, or as a way to measure the gradient ($\|\cdot\|^{2}$ can also be used for $g$ but then it $Γ$-converges towards the Sobovel energy).

# Solvers

## Direct methods

- $A = \operatorname{Id}$ or orthogonal design, $D$ is whatever finite diff.
- $f$ is the MSE
- $g$ is the $\ell^{1}$-norm

- [ ] Graph-cut based (Boykov, Veksler, and Zabih 2001) or (Kolmogorov and Zabin 2004) (note: this is the fastest way)
- Alternative discretization (maybe not relevant)

## Forward-Backward on the dual

- $A = \operatorname{Id}$ or orthogonal design, $D$ is whatever finite diff.
- $f$ is such that $f^{\star}$ is $L$-smooth with closed-form gradient.
- $g$ is prox-easy.

The starting point is to consider the dual problem of the primal problem reads
&space;-&space;g^{\star}(\theta)&space;.)

Variants:

- [ ] Vanilla
- [ ] Momentum (Heavy-ball (Polyak 1964), ADAM …)
- [ ] Accelerated (Nesterov , FISTA (Beck and Teboulle 2009), …)
- [ ] Extrapolation (Celer (Massias, Gramfort, and Salmon 2018))
- [ ] Mirror descent (Bregman-prox) see (Ben-Tal and Nemirovski 1987) for a review (I am not a specialist)

# Proximal-dual hybrid gradient

The starting point is two possible saddle point problems equivalent \eqref{eq:tv-gen}

&space;+&space;\ell(x)&space;.)

if $\ell$ is prox-easy or

&space;+&space;f(\zeta+y))
if $g$ is prox-easy but $\ell$ is not prox-easy.

- [ ] Alternating Direction Method of Multipliers (ADMM) (Eckstein 1989) or (Gabay and Mercier 1976) a.k.a Douglas–Rachford (Lions and Mercier 1979) (there is a paper of Douglas–Rachford but harder to read in the modern language) on the dual.
- [ ] Arrow, Hurwicz (not convergent in theory in general but efficient) (book of 1958)
- [ ] PDHG (Esser 2009) or (Pock et al. 2010) ($1/k$)
- [x] PDHG with over-relaxation a.k.a Chambolle-Pock (Chambolle and Pock 2011) ($1/k^{2}$)
- [x] #14

Variants:

- [ ] Acceleration of PDHG: FISTA-like for strongly convex case (Chambolle and Pock 2011)
- [ ] Preconditionning of PDHG: (Chambolle and Pock 2011) for a diagonal preconditionning easy to implement
- [ ] Accelerated ADMM

The issue provides a broad TV-denoising formulation and checklist of algorithms but names no files or tests. Start by inspecting the repository's solver and benchmark entry points, then compare the checked PDHG items with the current implementation and issue #14. Done requires a maintainer-defined subset and validation criteria.

Written by the indexing model from the issue text.