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 :
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
reshape(x,32,8)
, which is 32x8. Also, you haven't indicated the value ofq
you are using (or how to generatex
really). If you ditch the reshape, it seems both versions work for me for the example I tested (q=3
). $\endgroup$ – Florian Mar 24 '20 at 17:28