# Residual error when setting measurement matrix in compresssive sensing

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

• 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 !
– Gze
Mar 21 '20 at 5:41
• @DSPNovice sorry for that error, I modified it, it's y2, it's not y.
– Gze
Mar 24 '20 at 15:10
• 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). Mar 24 '20 at 17:28
• Since Hermitian is conjugate transpose, can you try conj()' instead of conj() if that makes a difference Mar 25 '20 at 10:42