Convolution

From NARS2000
Revision as of 12:44, 22 November 2013 by WikiSysop (talk | contribs) (Created page with "<table border="1" cellpadding="5" cellspacing="0" rules="none" summary=""> <tr> <td> <table border="0" cellpadding="5" cellspacing="0" summary=""> <tr> <td val...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search
Z←L f⍡g R returns the convolution (moving window inner product) of L vs. R.
L and R are vectors; scalars are promoted to one-element vectors.
f and g are functions.
Z is a vector whose shape is (⍴L)+(⍴R)-1.

The result is obtained by dragging the reverse of the shorter argument through all positions of the longer argument (as in a moving window) and performing an f.g inner product between the two, including leading and trailing prefixes. For example,

      L←1 3 2 1 ⋄ R←2 1 ⋄ L+⍡×R

2 1 2   1 2     1 2       1    multiply the rows together
1 3 2 1     1 3 2 1     1 3 2 1     1 3 2 1     1 3 2 1

2 1 6   3 4     2 2       1    add the products

      L+⍡×R
2 7 7 4 1

Interestingly, this algorithm solves a diverse set of problems such as weighted moving average (used to remove pixelization from a digital image), polynomial multiplication, and overlapping string searching.

Polynomial multiplication is illustrated in the above example using the functions + and ×. Overlapping string searching uses the functions and = as in

      L←'abababc' ⋄ R←'aba'
      (0⌈¯1+(⍴L)⌊⍴R)↓L∧⍡=⌽R
1 0 1 0 0 0 0

where we need to drop leading elements of the convolution result to remove the leading prefix comparisons.