Compressed sensing: Optimization in $L_1$ norm and total variation with fourier coefficients

I'm reading the article Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information (Candes, Romberg and Tao, 2004).

In this article they are talking about recovering the function $f$ whose fourier coefficients are known on some domain $\Omega$, by solving the following optimization problems:

$$\min ||g||_{TV} \space\space\space \text{s.t.} \space\space\space\hat{g}(w)=\hat{f}(w),w \in \Omega$$

and

$$\min ||g||_{L_1} \space\space\space \text{s.t.} \space\space\space\hat{g}(w)=\hat{f}(w),w \in \Omega$$

Can someone please give me a reference that suggests how to actually solve these optimization problems (that combines both $g$ and $\hat{g}$)?

A relevant R package would also be nice.

• Have you looked at their own software package, $\ell_1$-magic? It may not be the most efficient implementation or algorithm, though. Note also that the fourier coefficients and the original function are related by a linear transformation, which can be approximated discretely by a DFT, making linear programming packages a viable solution. Dec 18, 2013 at 17:25
• @cardinal: It seems to answer my quetions. Thanks!
– Roy
Dec 18, 2013 at 18:14