Search code examples
arraysmatlabmultiplicationconvolutionsliding-window

Efficient way to calculate the "product" of a discrete convolution


I'm looking for an elegant way to compute the "product" of a discrete convolution, instead of the sum.

Here is the formula of a discrete convolution:

enter image description here

In this case we can use: conv(x,y)

Now I would like to implement those operations

enter image description here

Of course I can use a loop, but I'm looking for a trick in order to linearize this operation.

EXAMPLE:

f = [2 4 3 9 7 1]
g = [3 2 1]

dist = length(g)-1;

for ii = 1:length(f)-dist
    x(ii) = prod(f(ii:ii+dist).*g)
end

x =

144    648   1134    378

Solution

  • Another solution partly inspired by Dev-iL answer to relatively the same question

    exp(sum(log(g))+conv(log(f),[1 1 1],'valid'))
    

    or

    exp(sum(log(g))+movsum(log(f),numel(g),'Endpoints', 'discard'))
    

    since exp(sum(log(x))) = prod(x)

    But here instead of one vector we have two vectors f and g.

    The desired formula can be reformulated as:

    enter image description here

    Timing in octave:

    f= rand(1,1000000);
    g= rand(1,100);
    
    disp('----------EXP(LOG)------')
    tic
        exp(sum(log(g))+conv(log(f),ones(1,numel(g))));
    toc
    
    disp('----------BSXFUN------')
    tic
        ind = bsxfun(@plus, 0:numel(f)-numel(g), (1:numel(g)).');
        x = prod(bsxfun(@times, f(ind), g(:)),1);
    toc
    disp('----------HANKEL------')
    tic
        prod(g)*prod(hankel(f(1:numel(g)), f(numel(g):end)));
    toc
    
    disp('----------CUMPROD-----')
    tic
        pf = cumprod(f);
        x = prod(g)*pf(numel(g):end)./[1 pf(1:(end-numel(g)))];
    toc
    

    Result:

    ----------EXP(LOG)------%rahnema1
    Elapsed time is 0.211445 seconds.
    ----------BSXFUN--------%Luis Mendo
    Elapsed time is 1.94182 seconds.
    ----------HANKEL--------%gnovice
    Elapsed time is 1.46593 seconds.
    ----------CUMPROD-------%gnovice
    Elapsed time is 0.00748992 seconds.