Hi, Convolution in time domain is equal to multiplication in Frequency domain. I am using convolution in neural network. As many papers says that converting image and weight matrix in frequency domain, multiply and inverse the result will take less process time comparable to convolution in Time domain. But the process time is increased instead of decreasing in my program. I have given the detail here how I implemented the algorithm, please give me suggestion and let me know where I did mistake. Comparison between FFT and Convolution For an example, take an image size 16X16 Weight matrix size of 5X5 Output image of convolution is 11X11 One convolve takes 5X5 =25 multiplication and addition For whole image 11X11X25 = 3025 operation ------------------------------------------------------------ FFT I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D FFT Reference http://local.wasp.uwa.edu.au/~pbourke/other/dft/index.html For each row 16X4=64 operation is required (16 log 16) 1D row wise FFT takes 16X64=1024 operation 1D Col wise FFT takes 1024 operation Totally 2048 operation is needed to convert 16X16 spatial image to frequency image We have to do this operation for weight matrix and inverse transform also So 2048 *3 =6144 operation is required along with 64 complex Multiplication So Totally 6206 operation is required in FFT --------------------------------------------------------------- As I discussed above convolution in time domain takes 3025 operation and FFT takes 6206 operations. Please let me know what is the problem. I like to know how to improve the code Regards Saravanan
Comparison between FFT and Convolution
Started by ●September 23, 2008
Reply by ●September 23, 20082008-09-23
On Sep 23, 1:10�pm, saravanan <saravananr...@gmail.com> wrote:> Hi, > Convolution in time domain is equal to multiplication in Frequency > domain. I am using convolution in neural network. As many papers says > that converting image and weight matrix in frequency domain, multiply > and inverse the result will take less process time comparable to > convolution in Time domain.this is true for FIR filters that have a long impulse response. if the length of the two sequences that you are convolving is short enough (which depends on how the fast convolution code is coded) it will be more efficient to do it the old fashioned way.> But the process time is increased instead > of decreasing in my program. �I have given the detail here how I > implemented the algorithm, please give me suggestion and let me know > where I did mistake.for each row and column, you are convolving a 5 sample sequence against a 16 sample sequence? i would be quite surprized if doing that in the frequency domain would be faster or better for any reason.> > Comparison between FFT and Convolution > > For an example, take an image size � � �16X16 > Weight matrix size of � � � � � � � � � 5X5 > > Output image of convolution is � � � �11X11 > > One convolve takes 5X5 =25 multiplication and additionthat nearly haves to be cheaper in the time domain.> For whole image 11X11X25 = �3025 operation > ------------------------------------------------------------ > > FFT > I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D > FFT > Referencehttp://local.wasp.uwa.edu.au/~pbourke/other/dft/index.html > > For each row 16X4=64 operation is required (16 log 16) > 1D row wise FFT takes 16X64=1024 operation > 1D Col wise FFT takes 1024 operation > Totally 2048 operation is needed to convert 16X16 spatial image to > frequency image > We have to do this operation for weight matrix and inverse transform > also > So 2048 *3 =6144 operation is required along with 64 complex > Multiplication > So Totally �6206 operation is required in FFT > --------------------------------------------------------------- >i dunno, it seems to me that you answered your own question. i never learn this lesson to read to the bottom of the post before hitting reply. r b-j
Reply by ●September 23, 20082008-09-23
On Sep 23, 2:35�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> On Sep 23, 1:10�pm, saravanan <saravananr...@gmail.com> wrote: > > > Hi, > > Convolution in time domain is equal to multiplication in Frequency > > domain. I am using convolution in neural network. As many papers says > > that converting image and weight matrix in frequency domain, multiply > > and inverse the result will take less process time comparable to > > convolution in Time domain. > > this is true for FIR filters that have a long impulse response. �if > the length of the two sequences that you are convolving is short > enough (which depends on how the fast convolution code is coded) it > will be more efficient to do it the old fashioned way. > > > But the process time is increased instead > > of decreasing in my program. �I have given the detail here how I > > implemented the algorithm, please give me suggestion and let me know > > where I did mistake. > > for each row and column, you are convolving a 5 sample sequence > against a 16 sample sequence? �i would be quite surprized if doing > that in the frequency domain would be faster or better for any reason. > > > > > Comparison between FFT and Convolution > > > For an example, take an image size � � �16X16 > > Weight matrix size of � � � � � � � � � 5X5 > > > Output image of convolution is � � � �11X11 > > > One convolve takes 5X5 =25 multiplication and addition > > that nearly haves to be cheaper in the time domain. > > > > > > > For whole image 11X11X25 = �3025 operation > > ------------------------------------------------------------ > > > FFT > > I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D > > FFT > > Referencehttp://local.wasp.uwa.edu.au/~pbourke/other/dft/index.html > > > For each row 16X4=64 operation is required (16 log 16) > > 1D row wise FFT takes 16X64=1024 operation > > 1D Col wise FFT takes 1024 operation > > Totally 2048 operation is needed to convert 16X16 spatial image to > > frequency image > > We have to do this operation for weight matrix and inverse transform > > also > > So 2048 *3 =6144 operation is required along with 64 complex > > Multiplication > > So Totally �6206 operation is required in FFT > > --------------------------------------------------------------- > > i dunno, it seems to me that you answered your own question. �i never > learn this lesson to read to the bottom of the post before hitting > reply. > > r b-j- Hide quoted text - > > - Show quoted text -Well, to start with, you've got an apples and oranges comparison. The convolution via FFT is 16x16, but the output of your 'conventional' convolution is 11x11? That's definitely not right. And they are both incorrect if you're trying to do a linear convolution. With a 16x16 image and a 5x5 kernel, you need at least a 20x20 output to get a linear convolution. You might want to take a look at S. Smith's book: http://www.dspguide.com/ch24/6.htm http://www.dspguide.com/ch24/7.htm Scroll down to the bottom of the second link above to see the comparison between conventional and FFT based convolution in terms of processing time. And, as r b-j has pointed out (and, as shown in the second link above), for very small kernels, the conventional way can in fact be faster than convolution via FFT. But if the kernel is even remotely large, then the FFT way is definitely faster. Where the crossover occurs depends on the size of the kernel, and whether or not you're applying any tricks to the FFT processing.
Reply by ●September 24, 20082008-09-24
On Sep 24, 12:37�am, kevinjmc...@netscape.net wrote:> On Sep 23, 2:35�pm, robert bristow-johnson <r...@audioimagination.com> > wrote: > > > > > > > On Sep 23, 1:10�pm, saravanan <saravananr...@gmail.com> wrote: > > > > Hi, > > > Convolution in time domain is equal to multiplication in Frequency > > > domain. I am using convolution in neural network. As many papers says > > > that converting image and weight matrix in frequency domain, multiply > > > and inverse the result will take less process time comparable to > > > convolution in Time domain. > > > this is true for FIR filters that have a long impulse response. �if > > the length of the two sequences that you are convolving is short > > enough (which depends on how the fast convolution code is coded) it > > will be more efficient to do it the old fashioned way. > > > > But the process time is increased instead > > > of decreasing in my program. �I have given the detail here how I > > > implemented the algorithm, please give me suggestion and let me know > > > where I did mistake. > > > for each row and column, you are convolving a 5 sample sequence > > against a 16 sample sequence? �i would be quite surprized if doing > > that in the frequency domain would be faster or better for any reason. > > > > Comparison between FFT and Convolution > > > > For an example, take an image size � � �16X16 > > > Weight matrix size of � � � � � � � � � 5X5 > > > > Output image of convolution is � � � �11X11 > > > > One convolve takes 5X5 =25 multiplication and addition > > > that nearly haves to be cheaper in the time domain. > > > > For whole image 11X11X25 = �3025 operation > > > ------------------------------------------------------------ > > > > FFT > > > I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D > > > FFT > > > Referencehttp://local.wasp.uwa.edu.au/~pbourke/other/dft/index.html > > > > For each row 16X4=64 operation is required (16 log 16) > > > 1D row wise FFT takes 16X64=1024 operation > > > 1D Col wise FFT takes 1024 operation > > > Totally 2048 operation is needed to convert 16X16 spatial image to > > > frequency image > > > We have to do this operation for weight matrix and inverse transform > > > also > > > So 2048 *3 =6144 operation is required along with 64 complex > > > Multiplication > > > So Totally �6206 operation is required in FFT > > > --------------------------------------------------------------- > > > i dunno, it seems to me that you answered your own question. �i never > > learn this lesson to read to the bottom of the post before hitting > > reply. > > > r b-j- Hide quoted text - > > > - Show quoted text - > > Well, to start with, you've got an apples and oranges comparison. �The > convolution via FFT is 16x16, but the output of your 'conventional' > convolution is 11x11? �That's definitely not right. �And they are both > incorrect if you're trying to do a linear convolution. With a 16x16 > image and a 5x5 kernel, you need at least a 20x20 output to get a > linear convolution. > > You might want to take a look at S. Smith's book: > > http://www.dspguide.com/ch24/6.htm > > http://www.dspguide.com/ch24/7.htm > > Scroll down to the bottom of the second link above to see the > comparison between conventional and FFT based convolution in terms of > processing time. > > And, as r b-j has pointed out (and, as shown in the second link > above), for very small kernels, the conventional way can in fact be > faster than convolution via FFT. �But if the kernel is even remotely > large, then the FFT way is definitely faster. > > Where the crossover occurs depends on the size of the kernel, and > whether or not you're applying any tricks to the FFT processing.- Hide quoted text - > > - Show quoted text -yes , exactly when the kerenel is small convolution is faster, if the size increases FFT will be faster. I agreed the same above. Thanks Naresh