Downsampling as a Matrix Operation

Module by: Ivan Selesnick

Note: Your browser may not currently support MathML. Chrome will attempt to display MathML, but it should not be considered correct. Safari will attempt to display MathML, but it should not be considered correct. Please install the required MathPlayer plugin to view MathML correctly.Firefox requires additional mathematics fonts to display MathML correctly.Firefox requires additional mathematics fonts to display MathML correctly. See our browser support page for additional details. You can always view the correct math in the PDF version.

(Show MathML examples)

If the two examples below are mathematically the same, your browser is correctly displaying MathML, and you can dismiss this message.

Example 1:	$\frac{\sqrt{\frac{1}{2}}}{\sqrt{{f(x+y)}^2}}\frac{\sqrt{1}}{2}\langle ℝ\rangle$	Example 2:		(Hide examples)

The downsampler is a linear system, but it is not time-invariant. (Figure 1)

Figure 1

yn=x 2 n y n x 2 n The downsampler can also be represented in matrix form. ⋮y0y1y2y3⋮=⋮⋮…1000000……0010000……0000100……0000001…⋮⋮⋮x0x1x2x3x4x5x6⋮ ⋮ y0 y1 y2 y3 ⋮ ⋮ ⋮ … 1 0000 00… … 0 0100 00… … 0 0001 00… … 0 0000 01… ⋮ ⋮ ⋮ x0 x1 x2 x3 x4 x5 x6 ⋮ where D=⋮⋮…1000000……0010000……0000100……0000001…⋮⋮ D ⋮ ⋮ … 1 0000 00… … 0 0100 00… … 0 0001 00… … 0 0000 01… ⋮ ⋮ .

We can write y=Dx y D x where DD is the infinite matrix having the form shown. Note that the matrix DD that represents downsampling is not a Toeplitz matrix -- it is not constant along the diagonals. As we know, the downsampling operation can not be represented as a convolution.

Let's see what the transpose of the downsampler is. We can do this by observing the form of the transpose of the matrix DD, which has the following form: DT=⋮⋮…1000……0000……0100……0000……0010……0000……0001…⋮⋮ D ⋮ ⋮ … 1 000 … … 0 0 00 … … 0 1 00 … … 0 0 00 … … 0 0 10 … … 0 0 00 … … 0 0 01 … ⋮ ⋮ The matrix DTD represents upsampling: z=DTy⇔zn=[↑2]yn ⇔ z D y z n [↑2] y n Note that DTD≠I D D I so therefore upsampling is not an orthogonal transformation. Indeed, when the matrix product DTD D D is computed, we find that DTD=⋮⋮…100000……000000……001000……000000……000010……000000……000001…⋮⋮ D D ⋮ ⋮ … 1 0000 0… … 0 0000 0… … 0 0100 0… … 0 0000 0… … 0 0001 0… … 0 0000 0… … 0 0000 1… ⋮ ⋮ So z=DTDx⇔zn=[↑2][↓2]xn=xnifn is even 0 ifn is odd ⇔ z D D x z n [↑2] [↓2] x n x n n is even 0 n is odd Equivalently, Zz=0.5Xz+X-z Z z 0.5 X z X z

Comments, questions, feedback, criticisms?

Send feedback

• E-mail the author of the module, Downsampling as a Matrix Operation

Footer

This work is licensed by Ivan Selesnick under a Creative Commons Attribution License (CC-BY 1.0), and is an Open Educational Resource.

Last edited by Charlet Reedstrom on Aug 13, 2005 11:11 am GMT-5.