Dual Convex Problem for a Problem including Total Variation

Question

For a convex problem including total variation, like $$ (1) \qquad \underset {\widehat{x}} {\text{minimize}} \hspace{0.3cm} \Vert \widehat{x} \Vert_{TV} \\ \qquad s.t. \hspace{0.3cm} y = F_n \widehat{x} $$ where $x$ is continuous-time signal which is a weighted superposition of spikes: $$ (2) \qquad x = \sum_j a_j \delta_{t_j} $$ and the minimization is carried out over the set of all finite complex measures x supported on [0,1] and $F_n$ is the linear map collecting the lowest $n=2f_c+1 $ frequency coefficients. In fact the constraint of the above problem is a matrix notation to relate the data $y$ and the object $x$ in the following equation: $$ (3) \qquad y(k) = \int_0^1 e^{-i2\pi kt}x dt = \sum_ja_je^{-i2\pi kt_j} \hspace{0.3cm} ,\hspace{1cm} k \in \mathbb{Z},|k|\leq f_c . $$ In this paper, the convex problem dual to (1) is introduced as $$ (4) \qquad \underset {c}{\text{maximize}} \hspace{0.2cm} Re \langle y,c \rangle \\ \qquad s.t. \qquad \Vert F_n^{^{*}}c \Vert \leq 1 ; $$ the constraint imposes that the modulus of the trigonometric polynomial $$ F_n^{^{*}}c(t) = \sum_{|k| \leq f_c }c_ke^{i2\pi kt} $$ be uniformly bounded by 1 over the interval [0,1]. And Finally, the form of the dual problem is: $$ (5) \qquad \qquad \qquad \qquad \underset {c}{\text{maximize}} \hspace{0.2cm} Re \langle y,c \rangle \\ \qquad \qquad s.t. \hspace{0.2cm} \left[ \begin{array}{cc} Q & c\\ c^* & 1 \end{array} \right] \succeq 0 , \quad \sum_{i=1}^{n-j}Q_{i,i+j}= \begin{cases} 1, & j=0 \\[2ex] 0, & j=1,...,n-1 \end{cases} $$ What's going on here? How the equation (4) is obtained from (1)?

Answer 1

Have a look at this paper especially section 3.1, where they explain this kind of reasoning.

There are a lot more explanations spread out through the literature. For example here as well.