1
$\begingroup$

I'm dealing with convolution among some large functions. Say f1 and f2.

The values f1(i) and f2(j) are so large that I should store them in the log scale. Say the log of f1 and f2 are lf1 and lf2.

Since every value should be store in the log scale, my task is to compute:

log( convolution(f1,f2) ).

For simplicity, assume length(lf1)==length(lf2) and computing only for the top length(lf1) elements.

Then, without FFT, the task can be done by the log-sum-exp trick: (In Matlab)

lf=zeros(length(lf1),1); %result
for i = 1:length(lf1)
    v=zeros(i,1);
    for j = 1:i+1
        v(j)=lf1(i)+lf2(j-i);
    max_v=max(v);
    lf(i)=max_v + log(sum( exp(v-max_v) ) ); %log-sum-exp trick

However, for FFT convolution ( something like ifft(fft(f1).*fft(f2)) ), the log-sum-exp trick seems hard to implement.

Is there any way out? Thanks!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.