Let \(F_N\) be a \(N\times N\) Fourier matrix , \(m=2s\le N\) and \(A\) be the first \(m\) rows of \(F\). Then, there is an algorithm which gives \(x\) for arbitrary \(y\in \mathbb{C}^m\) with effort of order \(N\). [1]
Proof
Suppose \(x\) is \(s\)-sparse . Let \(\hat{x}(0), \ldots , \hat{x}(2s-1)\) given by
\[ \hat{x}(j)=\sum_{k\in \mathbb{Z}_N} x(k)e_j(-k). \]We define
\[ p(t)= \frac{1}{N} \prod_{k\in S} \Bigl(1-\e^{-2\pi i\frac{k}{N}} \e^{2\pi i\frac{t}{N}}\Bigr). \]Then, \(p(t)=0\) if and only if \(t\in S\). Identify \(S\) with the polynomial of \(p\). Since \(\supp x\subseteq S\) we have \(p(t)x(t)=0\) for all \(t\). This implies \(\hat{p}\ast \hat{x}=\hat{px}=0\) due to the convolutional theorem . To be more precise, that is
\[ \hat{p}\ast\hat{x}(j)=\sum_{k\in \mathbb{Z}_N} \hat{p}(k)\hat{x}(j-k)=0 \]for all \(j\).
To be continued…
References Link to heading
- I. Veselic. Class Lecture, Topic:
Compressive Sensing.
Technische Universität Dortmund, 2017.