What is n-dimensional DFT as a linear transformation matrix look like? How it can be expressed as a matrix multiplication?

Question

In the above picture, the Discrete Fourier Transform, for the case of 1-dimension is expressed as a matrix multiplication of the 1-D vector of length $N$ with a DFT matrix of dimension $N\times N$. I want a similar thing for a general case of n-dimensional DFT. That is, let $x$ be an n-dimensional object, say $N_1\times N_2\times...\times N_n$. I want to take a n-dimensional DFT of this object, by expressing as a product with a DFT matrix as in the case of 1-dimension example in the above figure. What kind of object would the DFT matrix (if i can call it a matrix) be? That defintely not a matrix product but something generalized to handle higher dimensions. Please provide me some theory and directions, or if it already exists, please point me to a reference.

PS : I don't know anything about Tensors, so Ia m not sure if tensors would help.

Answer 1

The DFT is separable so can be applied per dimension (e.g. apply on rows first, the on columns). The most natural way is indeed to write it as a tensor product: if $D_k$ is the DFT on $\mathbb{C}^{d_k}$ then $D_1\otimes \ldots \otimes D_n$ is the DFT on $\mathbb{C}^{d_1}\otimes \ldots \otimes \mathbb{C}^{d_n}$. Of course, being linear, this can always be written as a matrix after choosing some basis. As an example consider $\mathbb{C}^{2}\otimes \mathbb{C}^2$ with basis $$\{e_1\otimes e_1, e_2 \otimes e_1, e_1 \otimes e_2, \ e_2\otimes e_2 \}$$ Then in this basis $$ D\otimes D = (D\otimes {\bf1})({\bf1} \otimes D) = \begin{pmatrix} D&0\\ 0 & D \end{pmatrix} \begin{pmatrix} d_{11} \cdot {\bf 1}&d_{12}\cdot {\bf 1}\\ d_{21}\cdot {\bf 1}& d_{22}\cdot {\bf 1}\end{pmatrix} $$ where each entry in the last matrix is a diagonal $2\times 2$ matrix and $d_{jk}$ are the entries of $D$.

Answer 2

Addition of tensors is entrywise. Tensors aren't (generally) used to represent linear transformations, and therefore don't have "inverses" in the sense of matrices. (The "inverse matrix" is the matrix which represents the inverse linear transformation. Matrix multiplication is only important inasmuch as it represents the composition of linear functions.)

A good introduction to tensors is Kolda, Bader, 2006, which can currently be found for free here. The "tensor product" described here is called "outer product" in Kolda, Bader. The "tensor product" in the answer above is called the Kronecker product here and in Kolda, Bader. The Kronecker product "tensor product" represents a vectorized form of the outer product "tensor product".

Specifically, given vectors $v_1, \dots, v_N$, and matrices $M_1, \dots, M_N$, then the outer product:

$$ (M_1 v_1) \circ (M_2v_2)\circ \cdots \circ (M_N v_N) $$

(using the "outer product" notation from Kolda, Bader) is an "order $N$ tensor", or a "tensor of order $N$" (using the terminology of Kolda, Bader), i.e. an "$N$-dimensional (multiway) array", an array where each entry has $N$ indices. If $\operatorname{vec}_{\operatorname{col}}$ denotes the colexicographical vectorization of a tensor (which is what is used implicitly throughout Kolda, Bader and in many other sources -- in the case of an order $2$ tensor, i.e. a matrix, colexicographical vectorization is the same as column-major vectorization) then one has that:

$$ \operatorname{vec}_{\operatorname{col}} ( (M_1 v_1) \circ (M_2v_2)\circ \cdots \circ (M_N v_N) ) = (M_N \otimes M_{N-1} \otimes \cdots \otimes M_1) \operatorname{vec}_{\operatorname{col}}(v_1 \circ v_2 \circ \cdots \circ v_N)\,, $$

where $\otimes$ represents the Kronecker product of matrices, so the multiplication on the right hand side of the above equation is standard matrix-vector multiplication.

Using the notation for mode-$n$ product found in Kolda and Bader, note that:

$$ (M_1 v_1) \circ (M_2v_2)\circ \cdots \circ (M_N v_N) = (v_1 \circ \cdots \circ v_N) \times_1 M_1 \cdots \times_N M_N \,,$$

so therefore we also have that the following identity is true:

$$ \operatorname{vec}_{\operatorname{col}}((v_1 \circ \cdots \circ v_N) \times_1 M_1 \cdots \times_N M_N) = (M_N \otimes \cdots \otimes M_1) \operatorname{vec}_{\operatorname{col}} (v_1 \circ \cdots \circ v_N) \,.$$

Comparing this with section 4 of Kolda, Bader, we see that this gives a formula for the vectorization of a so-called Tucker decomposition. This result is a special case of Proposition 3.7 from a technical report by Kolda.

The multidimensional DFT can be expressed as a Tucker decomposition (see section 4 of Kolda, Bader), where each of the factor matrices is the standard DFT matrix, and the core tensor is the original multidimensional array being transformed. A vectorized Tucker decomposition (i.e. you vectorize the core tensor, and vectorize the linear transformation representing the factor matrices) can be written via Kronecker products as explained above, although this isn't explained clearly in Kolda, Bader.

Specifically, the multidimensional DFT corresponds to applying the 1-dimensional DFT to every mode of the tensor, so if $F_n$ denotes the DFT matrix of the appropriate size, then the multidimensional DFT of the array (called an "elementary tensor" in Kolda, Bader because it is an outer product of vectors) $A= v_1 \circ \cdots \circ v_N$ is:

$$ (F_1 v_1) \circ (F_2 v_2) \circ \cdots \circ (F_N v_N) = (v_1 \circ \cdots \circ v_N) \times_1 F_1 \cdots \times_N F_N \,.$$

For a general tensor $A$, not necessarily an elementary tensor, this generalizes to (because of the universal property of the tensor product, but don't worry about that for now) the following formula for the multidimensional DFT of a general (not necessarily elementary) tensor $A$:

$$ A \times_1 F_1 \cdots \times_N F_N \,.$$

However, in the DFT literature, at least that which I've been able to find, people (for whatever reason) almost never actually work with tensors: instead they vectorize everything. (Again, I don't know why, and I don't think it's a good idea.) So they will define multidimensional DFT in terms of Kronecker products of matrices, since this is the vectorization of the correct formula, $A \times_1 F_1 \cdots \times_N F_N$ given above, specifically you'll see:

$$ (F_N \otimes F_{N-1} \otimes \cdots \otimes F_1) \operatorname{vec}_{\operatorname{col}} (A) \,. $$

Also note that, since one has that (vectors are considered as column vectors, matrices with one column, so their Kronecker product is defined, see section 2 of Kolda, Bader):

$$ \operatorname{vec}_{\operatorname{col}} (v_1 \circ \cdots \circ v_N) = v_1 \otimes \cdots \otimes v_N$$

it is also true that

$$\operatorname{vec}_{\operatorname{col}} ( (M_1 v_1) \circ (M_2v_2)\circ \cdots \circ (M_N v_N) ) = (M_N \otimes \cdots \otimes M_1) (v_1 \otimes \cdots \otimes v_N)$$

and that

$$\operatorname{vec}_{\operatorname{col}} ((v_1 \circ \cdots \circ v_N) \times_1 M_1 \cdots \times_N M_N) = (M_N \otimes \cdots \otimes M_1) (v_1 \otimes \cdots \otimes v_N) \,.$$

Again, most literature on the DFT will refer to the Kronecker product of matrices or of column vectors as "the tensor product", and so they often define the multidimensional DFT of "the tensor product of vectors" $v_1 \otimes \cdots \otimes v_N$ as being $(F_N \otimes \cdots \otimes F_1)(v_1 \otimes \cdots \otimes v_N)$.

Compare the answer to this related question: Vectorize 3D discrete Fourier transform