On the Measurement Matrix Used for Compressing Sensing
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 &amp; \mathbf{x}_2 &amp; \ldots &amp; \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
&amp; \mathbf F^H \newline
&amp;&amp; \ddots \newline
&amp;&amp;&amp; \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 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; \ldots\newline
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; \ldots\newline
\vdots\newline
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp;\ldots\newline
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; \ldots\newline
\vdots\newline
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; \ldots\newline
\vdots\newline
&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp;&amp; \ldots &amp; 0 &amp; 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.