Can the transpose of cropped block-Toeplitz matrix be represented as a cropped 2D convolution?

104 Views Asked by At

Suppose we have the following matrices defined over the field of complex numbers ($\Bbb C$):

  • a square input matrix $\mathbf{U}$ with dimensions $n \times n$

  • a symmetric convolution kernel $\mathbf{H}$ with dimensions $k \times k$.

  • a square output matrix of convolution $\mathbf{V} = \mathbf{H} * \mathbf{U}$ with dimensions $(n+k-1) \times (n+k-1)$.

It is known that there is an equivalence between the 2D convolution and matrix-vector multiplication with the block-Toeplitz matrix. More specifically, there exists a block-Toeplitz matrix $\mathbf{T}(\mathbf{H})$ satisfying the relationship

$$ \texttt{vec}(\mathbf{V}) = \mathbf{T}(\mathbf{H}) \texttt{vec}(\mathbf{U}) = \texttt{vec}(\mathbf{H}*\mathbf{U}) $$

where $\texttt{vec}(\mathbf{U}),\texttt{vec}(\mathbf{V})$ are the vectorized forms of the input and output matrices.

Next, lets suppose we crop the output of the convolution to have the same dimensions as the input. The crop operation can be represented as matrix multiplication with a binary matrix $\mathbf{C}$ having dimensions $n^2 \times (n+k-1)^2$ such that

$$ \texttt{vec}(\mathbf{V}_{c}) = \mathbf{C}\mathbf{T}(\mathbf{H})\texttt{vec}(\mathbf{U}) = \texttt{vec}(\texttt{crop}(\mathbf{H}*\mathbf{U})) $$

Finally we arrive at the question:

Can the matrix-vector operation involving the transpose of the Cropped Toeplitz matrix $(\mathbf{C}\mathbf{T})^{T}$ be represented as a cropped convolution? Mathematically, can we say that

$$ (\mathbf{C}\mathbf{T})^{T} \texttt{vec}(\mathbf{U}) = \texttt{vec}(\texttt{crop}(\mathbf{H' * \mathbf{U}})) $$

for some new kernel $\mathbf{H}'$?


Motivation

This question stems from the implementation of a physics-based diffractive neural network. If the relationship above holds, I think it would immensely speed up backpropagation and reduce the space complexity.

1

There are 1 best solutions below

3
On

Suppose that the matrix $\bf U$ is $n \times n$ and that the matrix $\bf H$ is $m \times m$. Thus, the matrix ${\bf V} := {\bf H} \ast {\bf U}$ produced via $2$-dimensional convolution is $(m + n - 1) \times (m + n - 1)$. There is a matrix-valued function

$${\bf T} : {\Bbb R}^{m \times m} \to {\Bbb R}^{(m + n - 1)^2 \times n^2}$$

such that

$$ \operatorname{vec} ({\bf Y}) = {\bf T} ({\bf H}) \operatorname{vec} ({\bf U}) $$

where $\operatorname{vec}$ denotes the vectorization operator. Transposing, we could write $ {\bf T}^\top ({\bf H}) \operatorname{vec} ({\bf U}) $, which is utter nonsense because the dimensions do not match. Please refine your question.


Example

Let $m = n = 2$. Hence, $m + n - 1 = 3$. Note that the $9 \times 4$ matrix

$$ {\bf T} ({\bf H}) = \left[\begin{array}{cc|cc}h_{22} & & & \\ h_{12} & h_{22} & & \\ & h_{12} & & \\ \hline h_{21} & & h_{22} & \\ h_{11} & h_{21} & h_{12} & h_{22} \\ & h_{11} & & h_{12} \\ \hline & & h_{21} & \\ & & h_{11} & h_{21} \\ & & & h_{11} \end{array}\right] $$

is block-Toeplitz rather than plain vanilla Toeplitz. Again, please refine your question.