Factorization of a Toeplitz-block Toeplitz matrix $A$ (Toeplitz Matrix with Toeplitz Blocks) as a product $A = Q^H D \, Q$ using a diagonal matrix $D$ We can write a complex toeplitz matrix $A$ of size $M \times M$ as
$$A = F^H_2 D F_2$$
Where $D$ is a diagonal matrix and $F_2$ contains the first $M$ columns of a
$2M \times 2M$ DFT matrix. For a circulant matrix $A$, $F_2$ is just the DFT matrix of size $M$ and the above factorization represents the diagonalization of the matrix.
A Block Toeplitz Matrix with Toeplitz Blocks (BTTB) is the $2$-D analog to a toeplitz matrix: This means that if we consider the blocks as elements, we obtain a toeplitz matrix. Moreover, each block is a toeplitz matrix on itself.
Is there a factorization for TBBT matrices analogous to the above factorization of toeplitz matricecs?
 A: Let's first consider the case of Block Circulant Matrices with Circulant Blocks (BCCB). These block matrices consist of circulant blocks. If we consider the blocks as elements, the BCCB matrix turns into a circulant one. Let's assume the blocks to have the dimension $n \times n$, and the BCCB matrix to have the dimension $mn \times mn$. In this case, the diagonalization of the BCCB matrix is: $$A = (F_m \otimes F_n)^H D \,(F_m \otimes F_n)$$
$F_j$ is the untiary DFT matrix of size $j\times j$.
Suppose $A$ is now a BTTB matrix of size $mn \times mn$, with blocks of size $n \times n$. Take $M$ as the the smallest power of two such
that $M \geq 2m−1$. Take $N$ as the smallest power of 2 such that $N \geq 2n − 1$. $A$ can be written in the following way: $$A = Q^H D \, Q$$
where $D$ is diagonal with size $MN \times MN$ and Q has size $MN \times mn$. 
The columns of $Q$ form a subset of the columns of $F_M \otimes F_N$. The selection of the columns is done the following way


*

*Consider the columns of $F_M \otimes F_N$ as $M$ blocks of $N$ columns.

*Consider only the first $m$ blocks (The relevant blocks)

*take only the first $n$ columns of each one of the relevant blocks


Example: for $m = 2$ and $n=4$, choose $M = 4$ and $N = 8$. From $F_4 \otimes F_8$ choose columns with indices from $\{1,2,3,4,9,10,11,12\}$
Note that the vector product of a BTTB matrix can be calculated using a two dimensional FFT thanks to the above factorization.
