Difference between revisions of "Convolution"

From NARS2000
Jump to navigationJump to search
 
Line 31: Line 31:
 
   <td><apll>2</apll></td>
 
   <td><apll>2</apll></td>
 
   <td><apll>1 2</apll></td>
 
   <td><apll>1 2</apll></td>
   <td><apll>&nbsp;&nbsp;1 2</apll></td>
+
   <td><apll> 1 2</apll></td>
   <td><apll>&nbsp;&nbsp;&nbsp;&nbsp;1 2</apll></td>
+
   <td><apll>   1 2</apll></td>
   <td><apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1</apll></td>
+
   <td><apll>     1</apll></td>
 
   <td>&nbsp;&nbsp;&nbsp;multiply the rows together</td>
 
   <td>&nbsp;&nbsp;&nbsp;multiply the rows together</td>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
   <td><apll>1 3 2 1&nbsp;&nbsp;&nbsp;&nbsp;</apll></td>
+
   <td><apll>1 3 2 1   </apll></td>
   <td><apll>1 3 2 1&nbsp;&nbsp;&nbsp;&nbsp;</apll></td>
+
   <td><apll>1 3 2 1   </apll></td>
   <td><apll>1 3 2 1&nbsp;&nbsp;&nbsp;&nbsp;</apll></td>
+
   <td><apll>1 3 2 1   </apll></td>
   <td><apll>1 3 2 1&nbsp;&nbsp;&nbsp;&nbsp;</apll></td>
+
   <td><apll>1 3 2 1   </apll></td>
 
   <td><apll>1 3 2 1</apll></td>
 
   <td><apll>1 3 2 1</apll></td>
 
</tr>
 
</tr>
Line 49: Line 49:
 
   <td><apll>2</apll></td>
 
   <td><apll>2</apll></td>
 
   <td><apll>1 6</apll></td>
 
   <td><apll>1 6</apll></td>
   <td><apll>&nbsp;&nbsp;3 4</apll></td>
+
   <td><apll> 3 4</apll></td>
   <td><apll>&nbsp;&nbsp;&nbsp;&nbsp;2 2</apll></td>
+
   <td><apll>   2 2</apll></td>
   <td><apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1</apll></td>
+
   <td><apll>     1</apll></td>
 
   <td>&nbsp;&nbsp;&nbsp;add the products</td>
 
   <td>&nbsp;&nbsp;&nbsp;add the products</td>
 
</tr>
 
</tr>
 
</table>
 
</table>
<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;L+⍡×R<br />
+
<apll>     L+⍡×R
 
2 7 7 4 1</apll>
 
2 7 7 4 1</apll>
  
Line 62: Line 62:
 
<p>Polynomial multiplication is illustrated in the above example using the functions <apll>+</apll> and <apll>×</apll>.  Overlapping string searching uses the functions <apll>∧</apll> and <apll>=</apll> as in</p>
 
<p>Polynomial multiplication is illustrated in the above example using the functions <apll>+</apll> and <apll>×</apll>.  Overlapping string searching uses the functions <apll>∧</apll> and <apll>=</apll> as in</p>
  
<apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;L←'abababc' ⋄ R←'aba'<br />
+
<apll><pre>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(0⌈¯1+(⍴L)⌊⍴R)↓L∧⍡=⌽R<br />
+
      L←'abababc' ⋄ R←'aba'
1 0 1 0 0 0 0</apll>
+
      (0⌈¯1+(⍴L)⌊⍴R)↓L∧⍡=⌽R
 +
1 0 1 0 0 0 0</pre></apll>
  
<p>where we need to drop leading elements of the convolution result to remove the leading prefix comparisons.</p>
+
where we need to drop leading elements of the convolution result to remove the leading prefix comparisons.

Latest revision as of 23:48, 15 April 2018

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.