Abstract
A shift-invariant system is a collection of functions $\{g_{m,n}\}$ of the form $g_{m,n}(k) = g_m(k-an)$. Such systems play an important role in time-frequency analysis and digital signal processing. A principal problem is to find a dual system $\gamma_{m,n}(k) = \gamma_m(k-an)$ such that each function $f$ can be written as $f = \sum \langle f, \gamma_{m,n} \rangle g_{m,n}$. The mathematical theory usually addresses this problem in infinite dimensions (typically in $L_2(\mathbb{R})$ or $\ell^2(\mathbb{Z})$), whereas numerical methods have to operate with a finite-dimensional model. Exploiting the link between the frame operator and Laurent operators with matrix-valued symbol, we apply the finite section method to show that the dual functions obtained by solving a finite-dimensional problem converge to the dual functions of the original infinite-dimensional problem in $\ell^2(\mathbb{Z})$. For compactly supported $g_{m,n}$ (FIR filter banks) we prove an exponential rate of convergence and derive explicit expressions for the involved constants. Further we investigate under which conditions one can replace the discrete model of the finite section method by the periodic discrete model, which is used in many numerical procedures. Again we provide explicit estimates for the speed of convergence. Some remarks on tight frames complete the paper.
Introduction
In digital signal processing and time-frequency analysis, signals are frequently represented using shift-invariant systems—collections of functions generated by shifting a set of prototype functions. To reconstruct a signal from these coefficients, one requires a dual system. While the mathematical foundation for these systems is established in infinite-dimensional spaces like $\ell^2(\mathbb{Z})$, practical numerical computation is restricted to finite-dimensional models.
This paper addresses a fundamental gap: if a dual function is calculated using a finite window of data, does that solution converge to the "true" dual function of the infinite system? Furthermore, the research seeks to quantify the window size required to achieve a specific level of numerical accuracy.
Methodology: The Finite Section Method
The author utilizes the finite section method, a classical approach for approximating solutions to infinite-dimensional operator equations. The study specifically focuses on Toeplitz-type systems, representing the frame operator of a shift-invariant system as a Laurent operator with a matrix-valued symbol.
To establish convergence rates, the paper integrates several technical components:
- Block Laurent Operators: These allow the frame operator to be analyzed through its symbol, facilitating the transition from infinite sequences to finite matrices.
- Matrix Decay Theory: The research employs the Demko-Moss-Smith theorem, which characterizes the exponential decay of entries in the inverse of a banded matrix. This is critical for understanding how errors propagate in truncated systems.
- Periodic Modeling: The paper compares the standard truncation approach (finite section) with the periodic model (circulant matrices). The latter is widely used in practice due to its compatibility with the Fast Fourier Transform (FFT).
Key Insights
Inherited Decay and FIR Filters
A significant finding is that the decay properties of the original prototype functions ($g_m$) are inherited by the dual functions ($\gamma_m$). For Finite Impulse Response (FIR) filter banks—where functions are compactly supported—the dual functions decay exponentially. This inheritance ensures that the finite-dimensional approximation is not only valid but converges to the infinite-dimensional truth exponentially fast.
Justification of the Periodic Model
Practitioners often prefer periodic boundary conditions for computational efficiency. This paper provides a theoretical justification for this preference, proving that the periodic model is "canonical." It preserves the underlying group structure and achieves the same exponential convergence rate as the finite section method.
Explicit Error Bounds
Moving beyond qualitative convergence, the paper derives explicit constants for convergence rates. This allows researchers to determine, a priori, the necessary window size $N$ to meet a target error tolerance $\delta$.
Principal Results
Convergence Proof
The paper formally demonstrates that the finite section method is applicable to shift-invariant frame operators. As the window size $N$ increases, the finite solutions are guaranteed to converge to the infinite-dimensional dual in $\ell^2(\mathbb{Z})$.
Exponential Rate Formula
For systems with compactly supported functions (support length $s$), the error between the true dual $\gamma_m$ and the $N$-th approximation $\gamma_m^{(N)}$ is bounded by: $$\|\gamma_m - \gamma_m^{(N)}\| \leq \sqrt{2} C \lambda^N (\lambda^s - \lambda^{s+1})^{-3}$$ where $\lambda$ is a constant determined by the condition of the frame. This explicit bound provides a rigorous metric for numerical reliability.
Equivalence of Models
The research establishes that the periodic (circulant) model converges to the true dual at a similar exponential rate, confirming that FFT-based numerical procedures are theoretically sound for approximating infinite-dimensional duals.
Limitations and Future Directions
While the results for compactly supported (FIR) filters are robust, the paper notes that constants for cases involving non-compact support (such as polynomial or general exponential decay) are not yet as explicit. Additionally, the study focuses on the canonical dual (the minimal $\ell^2$-norm solution). Future work may explore the convergence properties of other dual systems in redundant frames and the specific algorithmic complexity of the associated Toeplitz and circulant solvers.
Summary updated