Projecting a vector to another to detect the sparse values of such vector

Question

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

Answer 1

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