5
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.