For a project I need to do convolution and i use gpu for calculations. Sometimes I have to deal with kernel sizes of 50x50 and this size of kernel is sufficiently large that it chokes the gpu. (not enough memory svailable by the gpu) I need to find a way to break the kernel into smaller sizes (8x8 or similar) and do the convolution this way (i.e. piece by piece and later stitch together) so that I can realize gpu enhancements. What is the best way to break these kernels into smaller pieces? (I have no prior knowledge of kernel size so the solution must be something I can deal with in run time. )
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Yes, you can split them up. Convolution is a linear process, which means that superposition holds. Thus, you can break up any convolution kernel $k$ into multiple parts ($k_1, k_2, ... k_N$) such that $k = \sum k_i$.
For example, if you had a convolution kernel that looked like [1 2 3 4] (granted this is a silly kernel, but does fine for purposes of illustration), you could break it up into the following kernels, [1 2 0 0] and [0 0 3 4]. Now, you could simply do the convolutions like normal and then add the results together. The sum would be equal to the convolution product of the original kernel.
Doing that would be inefficient, though, both in terms of computations and memory. Instead, you could simply drop the 0's at the ends of the "sub-kernels", and do the convolutions using [1 2] and [3 4]. The one tricky part to this is that you have to offset the results before adding them together to get the correct answer.
The convolution operation is associative.
$(S ** g) ** h = S ** ( g ** h ) $
This means that if you find two kernels $g,h$ such that $g**h = k$, (where $k$ is your kernel), you can split your kernel into several parts, and apply each one individually. Each of the kernels can be smaller in size. The most known example of such kernels are Gaussian kernels.
Sometimes, it is even possible to split the kernel into two parts, such that each works only on one dimension. This quality is also possessed by Gaussian kernels.
To sum up, check if your kernel can be represented as convolution of two smaller kernels. This can be found out by checking the rank of the matrix. If it is equal to 1, it is separable. (That is because all of the rows are linear combinations of the first row).