Given real numbers $y_i's$, consider the following convex optimization problem: $$ \min_{x_i's} \sum_{i=1}^N(y_i-x_i)^2 + \lambda\sum_{i=1}^{N-1}|x_{i+1}-x_{i}|. $$ The paper A Direct Algorithm for 1D Total Variation Denoising by Laurent Condat claims that this is equivalent to: $$ \min_{s_i's} \sum_{i=1}^N \sqrt{(1 + (s_i-s_{i-1})^2)} \\ \mbox{subject to}~~ s_0=0, s_N=\sum_{i=1}^Ny_i \\~\mbox{and}~ \left|s_k-\sum_{i=1}^ky_i\right|\leq \lambda, \forall k. $$ I did see the references therein, especially [Mammen, E; van de Geer, S.: Locally adaptive regression splines. Ann. Statist. 25 (1997), no. 1, 387–413], but following the proof was a bit hard. Would appreciate help in this regard.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Sorry for digging this up after 3 years, I just stumbled upon the exact same problem. This is by no means a complete answer, just a current state of my own work.
I'm sure you saw that Condat poses the Fenchel-Moreau-Rockafellar dual problem
$$ \min_{u\in\mathbb{R}^{N+1}} \sum_{k=1}^N |y_k - u_k + u_{k-1}|^2 \text{ s.t. } \forall k=1,\dots,N-1: |u_k|\leq \lambda \text{ and } u_0,u_N = 0 $$
The relation to the primal problem is given via $x_k = y_k - u_k + u_{k-1}$ for $k=1,\dots,N$. The claim is, that $s_k = \sum_{i=1}^kx_i$ is a solution to the Taut-String problem. If we denote by $r_k = \sum_{i=1}^ky_i$ the running sum of $y$, then $s_k = r_k-u_k$. By the Karush-Kuhn-Tucker conditions, we get further information, namely
$$ \begin{cases} |u_k|\leq\lambda & \text{if } x_k = x_{k+1}\\ u_k = -\lambda & x_k < x_{k+1}\\ u_k = \lambda & x_k > x_{k+1} \end{cases}. $$
This shows at least, that the $s$ defined as the running sum of $x$ is in the feasible set of the taut-string problem, as $s_0 = r_0 + u_0 = 0$, $s_N = r_N - u_N = r_N$ and $|r_k-s_k| = |u_k| \leq \lambda$. We get even more from this, since $s$ touches $r+\lambda$ or $r-\lambda$ when $x$ introduces a jump which is exactly the behavior of the taut-string solution.
Edit: This is more an addendum than an edit. Given is a solution $s$ of the taut-string problem. Then we know from above that the FMR-dual solution is given by $u_i = r_i - s_i$ and $u$ satisfies the KKT-conditions, hence it is the solution of the dual problem, meaning $x$ is the primal solution.
