Re: Why aren't these convolution results equal to each other?

[Mike Miller]

On Tue, Apr 19, 2016 at 10:39:42 +0200, Max Görner wrote:
> Dear list,
> 
> I struggle with some deviations of results derived on different ways.
> I would like to discuss these with you. I'm using Octave 4.0.0 on Ubuntu
> 15.10.
> 
> The first problem concerns different ways to do 1D convolution. Please
> see the following listing:
> 
>     kernel = normpdf (1:100, 50, 10);
>     M = randn(1, 199);
>     m1 = convn(M, kernel, 'valid');
>     m2 = conv(M, kernel, 'valid');
>     m3 = conv2(1, kernel, M, 'valid');
>     disp([isequal(m1, m2), isequal(m1, m3), isequal(m2, m3)]);
> 
> Here m1 == m3 (i.e. convn == conv2), but m1 != m2 and m2 != m3. On
> Matlab R2015b it's only m1 == m2. I suspected that m1 == m2 == m3.

There is an open bug report about the precision of results from
convn(..., "valid"), please see https://savannah.gnu.org/bugs/?39314 for
more information.

NB: conv calls the function filter, and then trims the result if the
"valid" keyword is given. conv2 and convn both perform a different
multiplication if the "valid" keyword is given.

> The second problem concerns different ways to do 2D convolution. Please
> see the following listing:
> 
>     kernel = normpdf(1:100, 50.5, 10);
>     M = randn(199);
>     m1 = conv2(abs(kernel), 1, conv2(1, kernel, M, 'valid'), 'valid');
>     m2 = conv2(1, kernel, conv2(abs(kernel), 1, M, 'valid'), 'valid');
>     m3 = conv2(abs(kernel), kernel, M, 'valid');
>     disp([isequal(m1, m2), isequal(m1, m3), isequal(m2, m3)]);
> 
> Here m1 != m2 and m1 != m3 and m2 != m3. On Matlab R2015b it is m2 ==
> m3. I suspected, that exactly one of m1 or m2 equals m3, since either
> the vertical or the horizontal convolution should take place first.

Just to clarify, so we know what we're talking about when you say they
are not equal,

  >> max (abs (m1(:) - m2(:)))
  ans =    1.1102e-16
  >> max (abs (m1(:) - m3(:)))
  ans =    5.2736e-16
  >> max (abs (m2(:) - m3(:)))
  ans =    4.9960e-16

Are your results similar?

> So now I'm a bit irritated, since I suspected bit equality in some of
> the results above but got small deviations. I hesitate to blame floating
> point arithmetics for thoose deviations.
> 
> Could someone explain why these results are different and why this has
> to be that way or why it is acceptable?

I don't think it's at all hard to believe that each of your examples may
produce slightly different results.

Your m3 convolution above is actually identical to

  >> m4 = conv2 (M, kernel' * kernel, "valid");
  >> isequal (m3, m4)
  ans =  1

on my system, so maybe that helps demonstrate why it is not equal to
either of m1 or m2.

-- 
mike