On the Measurement Matrix Used for Compressing Sensing

Question

Assume we have a matrix $x$ of size $(8,8)$ where each column is considered to be sparse with degree of sparsity equals to $4$. it means that every column can have $4$ zeros and $4$ non-zeros values distributed randomly. The matrix $x$ can be written as follows:

Inverse Fourier transformation $(iFFT)$ is performed for every column in the matrix $x$. It means the matrix $F$ representing the $FFT$ matrix of size $(8,8)$ is multiplied with every column in matrix $x$, So $X = F^Hx$, where $X$ is the $iFFT$ column-wise of matrix $x$. The resulted matrix $X$ is read in row-wise leading to have a new row $X'$ of size $(1,64)$.(I mean the matrix $X$-transposed is reshaped to have one column).

The vector $X'$ is convoluted with such channel $h$ resulting $y$, so $y = HX'$, where $H$ is the toeplitz matrix gotten based on the channel $h$.

My question is to recover the spare vectors in matric $x$ based on the resulted vector $y$ and matrix $H$, I'm using compressive sensing, i.e OMP algorithm. My question is how to build the measurement matrix in that way.

$NP$: The measurement matrix can't be built straightforward since we reshaped the matrix $X$ in row-wise way. If not, I think we can build it to be $HF^H$ as used in the paper Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals.

Thank you in advance.

Answer 1

It is indeed possible to formulate this setting in terms of matrix-vector products. First, let us re-formulate your $x$ (notice throughout that I use bold letters for vectors and matrices): $$x = \begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 & \ldots & \mathbf{x}_8\end{bmatrix}$$ where $\mathbf x_k$ is the $k$ column of $x$.
I define the vertically stacked vector $\mathbf z$: $$\mathbf z = \begin{bmatrix}\mathbf{x}_1 \newline \mathbf{x}_2\newline \vdots\newline \mathbf{x}_8\end{bmatrix}$$ Now we can perform your column-wise IDFT of $x$ as: $$\mathbf Z = \begin{bmatrix}\mathbf F^H \newline & \mathbf F^H \newline && \ddots \newline &&& \mathbf F^H\end{bmatrix} \mathbf z = (\mathbf I_8 \otimes \mathbf F) \mathbf z$$ $\mathbf Z$ is the column-stacked equivalent of your $X$. Reading $X$ row-wise corresponds to reading $\mathbf Z$ through a permutation: $$\mathbf Z' = \mathbf P \mathbf Z$$ where $$\mathbf P = \begin{bmatrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \ldots\newline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & \ldots\newline \vdots\newline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\ldots\newline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & \ldots\newline \vdots\newline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & \ldots\newline \vdots\newline &&&&&&&&&& \ldots & 0 & 1\end{bmatrix}_{(64 \times 64)}$$ I hope the pattern is understandable: the first 8 rows of $\mathbf P$ pick out the 1st, 9th, ... 57th entry of $\mathbf Z$, the next 8 rows of $\mathbf P$ pick out the 2nd, 10th, ... 58th entry. The last 8 rows of $\mathbf P$ pick out the 8th, 16th, ... 64th entry of $\mathbf Z$.
Now $\mathbf Z' = X'$ and we can write: $$y = H \mathbf P (\mathbf I_8 \otimes \mathbf F) \operatorname{stack}(x)$$ Notice how I mix your notation with mine, so sorry it looks a bit messy. The "stack" operator stacks your matrix $x$ column-wise into the vector $\mathbf Z$.

It is important to notice here that this is mostly a theoretical exercise to see that the problem can indeed be brought on a standard form, familiar in compressed sensing, that can be plugged into for example OMP. You do not necessarily have to implement it this way. You may be able to still use the operations the way you describe them, and in particular it is more computationally efficient to compute the column-wise IFFT of your $x$ rather than forming the actual DFT Kronecker product matrix $\mathbf I_8 \otimes \mathbf F$ that I describe. However, it may be easier to implement by explicitly using my formulas here.
To put it another way, if you have a sparse reconstruction algorithm that understands the general compressed sensing problem $\mathbf y = \mathbf A \mathbf x$, then you can form $\mathbf A = H \mathbf P (\mathbf I_8 \otimes \mathbf F)$ and $\mathbf x = \operatorname{stack}(x)$ and plug those into the reconstruction algorithm. Whether you we will be able to "deconstruct" $\mathbf A$ and retain a more computationally efficient structure depends on your reconstruction algorithm and its interface.