I have an issue when implementing compressive sensing to recover sparse vector. Assume I have sparse vector $x$ of length, for example, $(256,1)$. $x = [x_1,x_2,.....x_{256}]$. This vector is transformed into time domain using Fourier matrix, $X = iFFT(x)$, and then convoluted with a channel $h$ resulting $y = X*h$, where * denotes the convolution operation. Let's make $H$ denote the toeplitz matrix of vector $h$ correspondent to $y = XH$

$case-1: $ Let's describe the above process as below:

$1). $ $X = F'x$ , where $F$ is Fourier matrix transformation obtained in matlab by F = dftmtx(256). and then $F'$ is the inverse Fourier matrix. This $X$ is correspondent to X = ifft(x).

$2).$ The signal $y = HX$ can be expressed in function of $x$ as $y = HF'x$. The use of compressive sensing here is straightforward by putting $y = Ax$ where $A= HF'$ is the measurement matrix. Therefore, sparse vector $x$ can be recovered using any algorithm such as OMP, MP or any other.

$case-2: $ Assume that we transformed the vector $x$ into time domain using $iFFT$ operation, but his time in vector of $32$. It means that we take every $32$ elements of $x$ and then perform $iFFT$ for it. This process can be performed in matlab as, X1 = reshape(x,32,[]); X_2 = reshape(ifft(x),[],1); This $X_2$ is equivalent into the $X$ mentioned in case_1 but with Fourier transformation of vector $32$

$1)$ Similarly to above manipulation, $X_2 = F'_{32} x$, where $F'_{32}$ can be expressed as below :

enter image description here

where $X_2$ here is correspondent into $X$ in the case_1, and $F'_{32}$ is inverse Fourier matrix of size $32$ obtained in matlab as dftmtx(32)' .

$2)$ The signal $y$ can be expressed similarly to case_1 as $y = HX_2 = HF'_{32} x$. BUT, performing compressive sensing into this case, $y = A_2x$ where $A_2 = HF'_{32}$ doesn't recover the vector $x$.

My question, theoretically, any compressive sensing algorithm such as OMP, MP should be able to recover $x$ in both case since measurement matrices are known and then should be straightforward, but in case $2$ where measurement matrix $A_2$, the CS doesn't work? A small residual error happens when performing that in matlab, so is there mathematical expression for that error? Is it possible to overcome that issue ?

EDIT: Here is the method how to create the $A_1$ and $A_2$ in matlab

F = dftmtx(256)/256;     %%Fourier matrix 
X = F*x;                 %%x is sparse vector of length(256,1) and X time domain of x
h = randn(32,1);         %%channel 
H = toeplitz([h(1) zeros(1,255) ], [h.' zeros(1,255) ]).'  %%toeplitx matrix
y = H*X;                 %%recieved signale 

A1 = H*F;               %measurement matrix 
x_hat = omp(A1,y,q)    %estimated x, and q is the number of sparse 

%%% creating A2 
F2 = kron(eye(8), dftmtx(32)/32);   %Fourier matrix 
X2 = F2*x;                % ifft of reshaped x 
y2 = H*X2; 

A2 = H*F2; 
x_hat = omp(A2,y2,q)    %estimated x, and q is the number of sparse 

where omp is copressive sensing OMP algorithm. In case of building the measurement matrix using $A_1$, x_hat can be recovered well but when using the $A_2$, a small error occurs, it means that estimated signal can't be demodulated and have BER = 0 compared with original x

Here you can get the complete code Here Thank you

  • $\begingroup$ When I put $y=X_2 = F'_{32}x$ , then put the measurement matrix $A_2 = F'_{32}$ it's ok. but when I multiply with matrix $H$, Compressive sensing can't recover vector $x$. $h$ is random vector generated in matlab by h = randn(32,1); and H = toeplitz([h(1) zeros(1,256-1) ], [h.' 256-1) ]).'; That's really strange ! $\endgroup$
    – Gze
    Commented Mar 21, 2020 at 5:41
  • 1
    $\begingroup$ @DSPNovice sorry for that error, I modified it, it's y2, it's not y. $\endgroup$
    – Gze
    Commented Mar 24, 2020 at 15:10
  • 1
    $\begingroup$ That helps, but we're not quite there yet: Your code does not work: F2 is 256x256 so you cannot multiply F2 with reshape(x,32,8), which is 32x8. Also, you haven't indicated the value of q you are using (or how to generate x really). If you ditch the reshape, it seems both versions work for me for the example I tested (q=3). $\endgroup$
    – Florian
    Commented Mar 24, 2020 at 17:28
  • 1
    $\begingroup$ Since Hermitian is conjugate transpose, can you try conj()' instead of conj() if that makes a difference $\endgroup$
    – DSP Novice
    Commented Mar 25, 2020 at 10:42
  • 1
    $\begingroup$ No I cannot since your link had already expired 1 hour after you posted it. I'll have to check if I'm allowed to share this code. $\endgroup$
    – Florian
    Commented Mar 25, 2020 at 17:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.