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

Improve this question
$\endgroup$
2
  • 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

0

Reset to default

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.