1
$\begingroup$

Assuming we have sparse vector of length $N$ such as $X = [0,1,0,-1,0,1,1,0]$ which has some non-zeros values. The vector $x = iFFT(X)$ is convoluted with another vector $h$ resluting $y = h*x$. Suppose that $h$ and $y$ are known, is it possible to recover the sparse vector $X$ using such methods of sparse vector estimation, such as compressive sensing or any other method?

$NP$: I have suggested to take $FFT$ for $y$ resulting $Y = FFT(y) = HoX$, where $o$ is the element-wise multiplication between $H$ and $X$. Then based on $Y$ I think it's easier to recover sparse vector $X$. But the issue when using element-wise division, I can't get the position of each non-zeros element in $X$. On the other hand, I don't know how to implement compressive sensing to recover $X$.

Thank you in advance

Improve this question
$\endgroup$
  • $\begingroup$ Are you sure this is really what you want? If you have $Y = X \circ H$ then you can simply recover $X = Y \oslash H$ (where $\oslash$ means entry-wise division). It should not be necessary with sparse recovery methods. $\endgroup$ – Thomas Arildsen Mar 6 '20 at 9:32
  • $\begingroup$ @ThomasArildsen , Thank you for your feedback. I wanted just to simplify the question. However, the exact issue I'm working on it is: $y = h*x$ , where * is convolution operation, and $x = iFFT(X)$ where $X$ is sparse. So I need to recover sparse vector $X$ based on $y$ and $h$. $\endgroup$ – Gze Mar 6 '20 at 9:57
  • $\begingroup$ In the question,I modified the equations to make the question clearer, I said, if $y=h*x$ and $x=iFFT(X)$, where X is sparse vector, so to recover $X$, I first took the $FFT(y) = FFT(h*x) = HoX$, where $o$ denotes the element wise multiplication. I'm not 100% sure if that manipulation is correct or not. thanks again for your feedback. $\endgroup$ – Gze Mar 6 '20 at 10:02
  • $\begingroup$ @ThomasArildsen I modified the question as I explained. If needed to upload also the code I have done, I will. $\endgroup$ – Gze Mar 6 '20 at 10:29
  • $\begingroup$ @ThomasArildsen Could you please check this question and let me if at least is possible to build that sensing matrix or no ? dsp.stackexchange.com/questions/64450/… . Thanks again $\endgroup$ – Gze Mar 9 '20 at 6:32
1
$\begingroup$

When you have the described convolution measurement, you can indeed recover your $X$ using sparse recovery methods. Some examples are, as you suggest, OMP, MP, or for example subspace pursuit (SP), compressive sampling matching pursuit (CoSaMP), iterative hard thresholding (IHT), a plethora of other variants of greedy recovery methods, as well as basis pursuit (BP), basis pursuit denoising (BPDN), and approximate message passing (AMP).
The key to this is the measurement matrix. Have a look at the random demodulator architecture to see how they construct their measurement matrix ($\mathbf M$) [1]. This is very similar to what you want.
Your IFFT is modelled by their $\mathbf F$; in their case the transform is just DFT instead of IDFT, but that does not change the principle. Your measurement matrix (lets us call it $\mathbf H$) is a little bit different than [1]'s $\mathbf M$.
Assume that we can express your convolution as discrete convolution. I would model you measurement matrix as: $$\mathbf H = \begin{bmatrix} \mathbf h & 0 & & \ldots && 0\\ 0 & \mathbf h & 0 & \ldots && 0\\ \vdots\\ 0 & & \ldots && 0 & \mathbf h \end{bmatrix}$$ This is a convolution matrix. The non-zeros parts $\mathbf h$ of each row of $\mathbf H$ is the vector you convolve $x$ by (where I would call it vector $\mathbf x$). The non-zero parts of $\mathbf H$ generally overlap across the columns.
See for example MATLAB's convmtx for a practical example of construction of $\mathbf H$. You may want to sub-sample the rows of $\mathbf H$ (i.e. only keep every $m$th row), corresponding to a lower sample-rate of your sequence $y$ than your original sequence $x$.

Improve this answer
$\endgroup$
  • $\begingroup$ Yes .. Exactly, The measurement matrix is the issue which I couldn't solve. I don't know how to build it. I have checked that paper before, but as you see in my case, I perform convolution between channel and the $iFFT$ of my sparse signal. it's not direct convolution between the sparse signal and another. That's what confused me more. $\endgroup$ – Gze Mar 6 '20 at 10:50
  • $\begingroup$ Your IFFT is modelled by the matrix $\mathbf F$ in [1]. Your measurement matrix is $\mathbf M$ in [1]. Looking more closely at it now, it occurs to me that the random demodulator is not exactly what you want, but the structure is very similar. I am going to update my answer. $\endgroup$ – Thomas Arildsen Mar 6 '20 at 11:02
  • $\begingroup$ I will print that paper out and read it line by line to understand everything in it. At the same time, awaiting for your answer update. I will check that paper and update you what I got. $\endgroup$ – Gze Mar 6 '20 at 11:04
  • $\begingroup$ Thank you for the details. I will check it and let you know. $\endgroup$ – Gze Mar 6 '20 at 11:30
  • $\begingroup$ Hi Thomas, I built the code as I added in the question, but again, I couldn't understand how to build the measurement matrix. when I try to build as you described by $hF^h$ where $F^H$ is the inverse Fourier transform, I get an error. Could you please help me in that line of building the measurement matrix in the code? Thank you. $\endgroup$ – Gze Mar 6 '20 at 16:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.