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$$


$$ \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.

  • 3
    $\begingroup$ 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. $\endgroup$
    – cardinal
    Dec 18, 2013 at 17:25
  • $\begingroup$ @cardinal: It seems to answer my quetions. Thanks! $\endgroup$
    – Roy
    Dec 18, 2013 at 18:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.