Shane Chu

Convolutions

The textbook definition of (linear) convolution is as follows: a convolution of two vectors $\bm f\in\mathbb R^n$ and $\bm x\in\mathbb R^m$ is a vector $\bm f * \bm x\in\mathbb R^{n+m-1}$, where

i.e., the $k$-th entry of the vector $\bm f * \bm x$ is the sum of all product $\bm f[i]\bm x[j]$ such that the indices $i,j$ satisfy the condition $i+j=k+1$.

This definition doesn't show convolution is related to applcations (it's more useful for proof exercises). Ok, what is an intuitive way to think about convolution?

Note that convolution is a linear operation, for which we can write it down as a matrix-vector multiplication. To make things concrete, suppose $\bm f=(f_1,f_2,f_3)^\top$ and $\bm x=(x_1,x_2,x_3,x_4)^\top$, then we can write

which is the same as what's going on in equation (1).

What's interesting from this perspective is when the vector $\bm x$ is sparse, i.e. $\bm x$ has mostly zero entries. Let's say $\bm x=(0,1,0,0)^\top$. Substitute this to the above, we have that

What does this say? If we think about that $\bm f * \bm x$ as some kind of signal, then this is saying that $\bm f$ as a feature is presented in the span from the 2nd to the 4th entries.

We can leverage this intuition to think about applications related to bioinformatics. If the signal is a DNA string, and the feature represents a motif, e.g., it could be a k-mer, or a position frequency matrix, etc., then we have something meaningful: the sparse vector $\bm x$ indicates where the motif $\bm f$ is presented in the DNA string. Moreover, the non-zero entry in $\bm x$ doesn't need to be $1$. It could be an arbitrary value signifying the strength of the presense of $\bm f$ in the DNA string.

The description above is just an analogy. To develop this idea further, we look at a classic problem in signal processing: convolutional dictionary learning.