# Composition of interpolation and decimation matrices

I understand that interpolation is a linear transformation of a signal vector that combines interleaving the elements of the input vector with zeros followed by a filtering operation to remove any newly introduced signal components.

Call the matrix that does this interpolation $$U$$. It is $$M\times{N}$$ matrix that maps a $$N$$-element input vector onto a longer $$M$$-element output vector with $$M>N$$.

A similar matrix for decimation, $$V$$, can be formed. A $$P\times{M}$$ matrix with $$P that maps an $$M$$-element input vector onto a shorter $$P$$-element output vector.

The composition of these interpolation and decimation matrices $$VU$$ has dimension $$P\times{N}$$.

How do I construct this $$P\times{N}$$ matrix explicitly, without needing to multiply these separate $$U$$ and $$V$$ matrices?

The advantage in avoiding the intermediate $$M$$-dimensional space is because, if I want to resample a $$127$$-length vector to a $$128$$-length vector, I have $$N=127$$, $$P=128$$, but $$M=127\times128 = 16256$$, which would require a huge amount of extra computation.

• ah, you're trying to do rational resampling. Fret not, rational resamplers use polyphase "magic" to work at the lower rate, so that you don't have to upsample by 127·128 first. – Marcus Müller Jan 18 '20 at 11:32
• @MarcusMüller can the "magic" be explained as an optimization of the matrix composition? I have tried to simplify the matrix multiplications involved, but it becomes quite complicated. – user827822 Jan 18 '20 at 20:01