Toeplitz Matrix - Discrete Convolution

Discrete Convolution

The convolution operation can be constructed as a matrix multiplication, where one of the inputs is converted into a Toeplitz matrix. For example, the convolution of and can be formulated as:

y = h \ast x = \begin{bmatrix} h_1 & 0 & \ldots & 0 & 0 \\ h_2 & h_1 & \ldots & \vdots & \vdots \\ h_3 & h_2 & \ldots & 0 & 0 \\ \vdots & h_3 & \ldots & h_1 & 0 \\ h_{m-1} & \vdots & \ldots & h_2 & h_1 \\ h_m & h_{m-1} & \vdots & \vdots & h_2 \\ 0 & h_m & \ldots & h_{m-2} & \vdots \\ 0 & 0 & \ldots & h_{m-1} & h_{m-2} \\ \vdots & \vdots & \vdots & h_m & h_{m-1} \\ 0 & 0 & 0 & \ldots & h_m \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end{bmatrix}
y^T = \begin{bmatrix} h_1 & h_2 & h_3 & \ldots & h_{m-1} & h_m \end{bmatrix} \begin{bmatrix} x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & 0& \ldots & 0 \\ 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & \ldots & 0 \\ 0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots & \vdots & \ldots & 0 \\ 0 & \ldots & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_n & \vdots \\ 0 & \ldots & 0 & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_n \end{bmatrix}.

This approach can be extended to compute autocorrelation, cross-correlation, moving average etc.

Read more about this topic:  Toeplitz Matrix

Famous quotes containing the word discrete:

    “We have good reason to believe that memories of early childhood do not persist in consciousness because of the absence or fragmentary character of language covering this period. Words serve as fixatives for mental images. . . . Even at the end of the second year of life when word tags exist for a number of objects in the child’s life, these words are discrete and do not yet bind together the parts of an experience or organize them in a way that can produce a coherent memory.”
    —Selma H. Fraiberg (20th century)