Minimal number of additions in convolution

Question

The Winnograd algorithm can be used to reduce the number of multiplications in convolution. Is there a known method of reducing the number of additions in convolution?

Answer 1

One method which attracted my attention recently is Discrete Time Random Sampling.

Which is an approximation method useful to reduce both multiplications and additions in filtering.

Filter and $N$-length signal by a $L$-length filter can be performed in $\mathcal{O}(LM)$ instead of $\mathcal{O}(LN)$. Where $M\ll N$. Which is done by picking samples at random in a way described in the paper.

See also Frequency-Shaped Randomized Sampling for a more sophisticated approach which allows you to shape the spectrum of the error.

Answer 2

This is an interesting question. I don't think anyone has studied it. A basic query of the IEEE library of the term "minimal additions" returns 3 results of which none were related to convolution. Additions are relatively simple to implement compared to multiplications. The first commercially available digital hardware multiplier that I'm aware of was the TRW 1010J chip. The TMS320 was revolutionary because it could do a multiply and add in one cycle. Historically multiplications were avoided if possible, so no one would have considered an algorithm that gave up additions for multiplications, and if you don't do either, you don't do much.

Today multiplication has an energy penalty relative to addition in low power applications, so the topic remains relevant.

There is one possible exception, a bitwise shift left is the same as multiplication by 2 but probably is about the same as an add. It would depend on the device.

Answer 3

The Fast Fourier Transform (FFT) algorithm, when used to compute a convolution, reduces both the number of multiplications needed and the number of additions needed to compute the convolution from $O(N^2)$ to $O(N \log N)$.

Not quite applicable to the problem being considered here, but about 40 years ago, I published a paper in IEEE Transactions on Computers (vol. C-27, March 1978) about what I called semi-fast Fourier transform algorithms for computing the finite-field Fourier transform over GF$(2^m)$. Use of this algorithm reduces the number of finite-field multiplications, but not the number of finiite-field additions.