I'm trying to express the $N$-dimensional discrete Fourier transform (DFT) of an $N$-dimensional array as the product between a matrix and a vector.
If $N=2$ the problem is quite simple: given a $n\times m$ matrix $X$, since $DFT(X) = F_nXF_m^T = F_nXF_m$ (where $F_h$ is the $h \times h$ Fourier matrix) and since $vec(AXB)=(A^T \otimes B)vec(X)$, the desired matrix is $F_n\otimes F_m$ and the vector is $vec(X)$, so that
$$vec(DFT(X)) = (F_n \otimes F_m) vec(X)$$
What can be done if $N\geq 3$, especially if $N=3$?
EDIT: let me better specify the notation, by using MATLAB conventions. An $N$-dimensional array $X$ is a function from $\{1,\dots,n_1\} \times \{1, \dots, n_2\} \times \dots \times \{1, \dots, n_N\}$ to $\mathbb C$. In MATLAB notation, one can access its elements by $X(i_1, i_2, \dots, i_n)$ with suitable indices $i_j$.
The $N$-dimensional DFT of an $N$-dimensional array $X$ is exactly what MATLAB does by typing fftn(X). More details here.
Instead of calculating the $N$-dimensional DFT in $N$ steps by applying the 1-D DFT along each dimension, I would like to find a "one shot" matrix-vector product formulation of this operation. A procedure like
- Unwrap vector $X$ to a vectorized form;
- Multiply $X$ by a suitable matrix;
- Wrap back $X$ to an $N$ dimensional array form;
- The output is the same as
fftn(X).
This need comes from the study of a 3-D imaging problem where the 3-D image has to be reconstructed from an underdetermined set of measurements using a particular solving procedure. The matrix I'm trying to obtain with your help is (almost) the matrix I will use in the solving procedure.