Computational Complexity and Separability

Complexity of N_N_M*M

In some cases, filter is separable, meaning you can get the square kernel H by convolving a single column vector by some row vector:

So we do two convolutions but each is W_N_N. So this is userful if W is big enough such that 2_W_N_N << W_W_N_N.

Used to be very important. Still, if W-31, save a factor of 15.