Convolution - Revision history

Sudleyplace at 23:48, 15 April 2018

2018-04-15T23:48:29Z

← Older revision		Revision as of 19:48, 15 April 2018
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>~~  ~~1 2</apll></td>		<td><apll> 1 2</apll></td>
	<td><apll>~~    ~~1 2</apll></td>		<td><apll> 1 2</apll></td>
	<td><apll>~~      ~~1</apll></td>		<td><apll> 1</apll></td>
	<td>   multiply the rows together</td>		<td>   multiply the rows together</td>
	</tr>		</tr>
	<tr>		<tr>
	<td><apll>1 3 2 1~~    ~~</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>
	<td><apll>1 3 2 1~~    ~~</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>
	<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>~~  ~~3 4</apll></td>		<td><apll> 3 4</apll></td>
	<td><apll>~~    ~~2 2</apll></td>		<td><apll> 2 2</apll></td>
	<td><apll>~~      ~~1</apll></td>		<td><apll> 1</apll></td>
	<td>   add the products</td>		<td>   add the products</td>
	</tr>		</tr>
	</table>		</table>
	<apll>~~      ~~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>~~      ~~L←'abababc' ⋄ R←'aba'~~<br />~~		<apll><pre>
	~~      ~~(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.

WikiSysop at 23:20, 14 November 2015

2015-11-14T23:20:12Z

← Older revision		Revision as of 19:20, 14 November 2015
Line 7:		Line 7:
	<td></td>		<td></td>
	<td></td>		<td></td>
	<td>returns the convolution (moving window inner product) of <apll>L</apll> vs. <apll>R</apll>.</td>		<td>returns the [https://en.wikipedia.org/wiki/Convolution convolution] (moving window inner product) of <apll>L</apll> vs. <apll>R</apll>.</td>
	</tr>		</tr>
	</table>		</table>

WikiSysop: Created page with "

2013-11-22T16:44:36Z

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..."

New page
<table border="1" cellpadding="5" cellspacing="0" rules="none" summary="">
<tr>
<td>
<table border="0" cellpadding="5" cellspacing="0" summary="">
<tr>
<td valign="top"><apll>Z←L f⍡g R</apll></td>
<td></td>
<td></td>
<td>returns the convolution (moving window inner product) of <apll>L</apll> vs. <apll>R</apll>.</td>
</tr>
</table>
</td>
</tr>
<tr>
<td><apll>L</apll> and <apll>R</apll> are vectors; scalars are promoted to one-element vectors.</td>
</tr>
<tr>
<td><apll>f</apll> and <apll>g</apll> are functions.</td>
</tr>

<tr>
<td><apll>Z</apll> is a vector whose shape is <apll>(⍴L)+(⍴R)-1</apll>.
</tr>
</table>

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

<apll>      L←1 3 2 1 ⋄ R←2 1 ⋄ L+⍡×R</apll><br />
<table border="0" cellpadding="0" cellspacing="0" rules="none" summary="">
<tr>
<td><apll>2</apll></td>
<td><apll>1 2</apll></td>
<td><apll>  1 2</apll></td>
<td><apll>    1 2</apll></td>
<td><apll>      1</apll></td>
<td>   multiply the rows together</td>
</tr>
<tr>
<td><apll>1 3 2 1    </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>
<td><apll>1 3 2 1</apll></td>
</tr>
<tr>
<td colspan="5"><hr size="6" /></td>
</tr>
<tr>
<td><apll>2</apll></td>
<td><apll>1 6</apll></td>
<td><apll>  3 4</apll></td>
<td><apll>    2 2</apll></td>
<td><apll>      1</apll></td>
<td>   add the products</td>
</tr>
</table>
<apll>      L+⍡×R<br />
2 7 7 4 1</apll>

<p>Interestingly, this algorithm solves a diverse set of problems such as [https://en.wikipedia.org/wiki/Weighted_moving_average#Weighted_moving_average weighted moving average] (used to remove pixelization from a digital image), polynomial multiplication, and overlapping string searching.</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>      L←'abababc' ⋄ R←'aba'<br />
      (0⌈¯1+(⍴L)⌊⍴R)↓L∧⍡=⌽R<br />
1 0 1 0 0 0 0</apll>

<p>where we need to drop leading elements of the convolution result to remove the leading prefix comparisons.</p>