Paper V: Polyphase coordinates on finite index sublattices

E3 Polyphase coordinates on finite index sublattices

On this page · Permalink · Source line 1756

Let \(L\leq{\mathbb Z}^d\) be a sublattice of finite index \(q\). Choose a set \(R\subset{\mathbb Z}^d\) containing one representative from every coset in \({\mathbb Z}^d/L\). Thus

\[ {\mathbb Z}^d=\bigsqcup_{r\in R}(r+L). \]

For \(x:{\mathbb Z}^d\to{\mathbb C}\), its channel at \(r\) is the sequence on \(L\)

\[ x_r(\ell)=x(r+\ell). \]

Permalink · Source line 1758

Definition E3.1: Lattice packet

For \(r\in R\), define the coordinate projector

\[ (P_rx)(n)={\mathbf 1}_{r+L}(n)x(n). \]

The family \((P_r)_{r\in R}\) is called the packet system associated with \(L\) and \(R\).

Permalink · Source line 1767 · Claim record · Lean coverage · Code · Worked examples

For finite \(p\), equip \(\bigoplus_{r\in R}\ell^p(L)\) with

\[ \|(u_r)\|^p=\sum_{r\in R}\|u_r\|_p^p. \]

For \(p=\infty\), use the maximum norm.

Permalink · Source line 1775

Theorem E3.2: Exact lattice polyphase decomposition

For every \(1\leq p\leq\infty\), the analysis map

\[ {\mathcal A}_L:\ell^p({\mathbb Z}^d)\longrightarrow\bigoplus_{r\in R}\ell^p(L), \qquad {\mathcal A}_Lx=(x_r)_{r\in R}, \]

is an isometric isomorphism. Its inverse is the interleaving map

\[ {\mathcal S}_L(u)(r+\ell)=u_r(\ell). \]

The projectors satisfy

\[ P_rP_s=\delta_{rs}P_r, \qquad \sum_{r\in R}P_r=I. \]

Read proof · Visual guide: Six image phases are six exact address classes · Read statement and proof side by side · Permalink · Source line 1781 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E3.2

Every address has a unique representation \(r+\ell\). For finite \(p\),

\[ \|x\|_p^p = \sum_{r\in R}\sum_{\ell\in L}|x(r+\ell)|^p = \sum_{r\in R}\|x_r\|_p^p. \]

The corresponding supremum identity is immediate when \(p=\infty\). Unique address representation proves that analysis and interleaving are inverse maps. The projector identities follow from the disjoint coset partition.

Back to statement · Read statement and proof side by side · Permalink · Source line 1800 · Claim record · Lean coverage · Code · Worked examples

Corollary E3.3: One dimensional residue coordinates

For \(L=N{\mathbb Z}\) and \(R=\{0,\ldots,N-1\}\),

\[ x_r(k)=x(Nk+r) \]

and

\[ \ell^p({\mathbb Z})\cong\bigoplus_{r=0}^{N-1}\ell^p({\mathbb Z}) \]

isometrically.

Read proof · Read statement and proof side by side · Permalink · Source line 1812 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary E3.3

Apply Theorem E3.2 to the standard residue representatives.

Back to statement · Read statement and proof side by side · Permalink · Source line 1824 · Claim record · Lean coverage · Code · Worked examples

Proposition E3.4: Translation covariance

Fix \(a\in{\mathbb Z}^d\). For every \(r\in R\), write uniquely

\[ r-a=r_a+\lambda_{a,r}, \qquad r_a\in R, \quad \lambda_{a,r}\in L. \]

Then

\[ ({\mathcal A}_LT_ax)_r(\ell) = x_{r_a}(\ell+\lambda_{a,r}). \]

Thus a fine translation permutes the lattice packets and applies an internal translation on \(L\).

Read proof · Read statement and proof side by side · Permalink · Source line 1828 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition E3.4

Evaluate at \(r+\ell\):

\[ (T_ax)(r+\ell) =x(r+\ell-a) =x(r_a+\ell+\lambda_{a,r}). \]

This is the stated channel formula.

Back to statement · Read statement and proof side by side · Permalink · Source line 1846 · Claim record · Lean coverage · Code · Worked examples

A signal and its four residue channels, which interleave exactly. — A signal and its four exact residue channels. Interleaving the channels returns the original samples without approximation.

E3.1 Refinement of sublattices

On this page · Permalink · Source line 1863

Let \(L'\leq L\leq{\mathbb Z}^d\), with both indices finite. Choose representative systems \(R\) for \({\mathbb Z}^d/L\) and \(R'\) for \({\mathbb Z}^d/L'\). For \(r\in R\), define

\[ \operatorname{Child}(r) = \{s\in R':s+L'\subset r+L\}. \]

Permalink · Source line 1865

Theorem E3.5: Exact lattice refinement

For every coarse packet,

\[ P_r^{L} = \sum_{s\in\operatorname{Child}(r)}P_s^{L'}. \]

The fine packets in the sum are pairwise disjoint. Refinement through several nested sublattices is transitive.

Read proof · Visual guide: Six image phases are six exact address classes · Read statement and proof side by side · Permalink · Source line 1872 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E3.5

The coset \(r+L\) is the disjoint union of the \(L'\) cosets contained in it. Multiplying by the corresponding indicator functions gives the projector identity. A nested partition of a coset is independent of whether the intermediate level is inserted, which proves transitivity.

Back to statement · Read statement and proof side by side · Permalink · Source line 1882 · Claim record · Lean coverage · Code · Worked examples

Example E3.6: Rectangular image phases

For

\[ L=M{\mathbb Z}\times N{\mathbb Z}\subset{\mathbb Z}^2, \]

one may take

\[ R=\{0,\ldots,M-1\}\times\{0,\ldots,N-1\}. \]

The analysis map separates an image into \(MN\) exact phases. Refining \((M,N)\) to \((M',N')\), where \(M\mid M'\) and \(N\mid N'\), splits every coarse phase into

\[ \frac{M'}M\frac{N'}N \]

fine phases.

Permalink · Source line 1886

Read and explore

Proofs and implementation

About this work

Other resources