TL;DR
This paper introduces novel methods for designing Autoregressive Moving Average (ARMA) graph filters, which offer improved accuracy and efficiency compared to existing Finite Impulse Response (FIR) filters. The proposed techniques, inspired by Prony's method and an iterative approach, enable more precise modeling of graph signal frequencies, leading to better performance in applications like interpolation, compression, and prediction.
What Problem Does This Paper Address?
Graph signal processing (GSP) extends traditional signal processing to data residing on irregular graph structures. A key tool in GSP is the graph filter, which manipulates the "graph frequency" components of a signal, analogous to how filters work in the time or spatial domains. Existing graph filters, primarily Finite Impulse Response (FIR) filters, are designed as polynomials of the graph shift operator (like the graph Laplacian or adjacency matrix). While effective, FIR filters often require high orders to accurately match desired frequency responses, leading to computational complexity and limited approximation accuracy, especially for sharp transitions in the frequency domain. This paper addresses this limitation by proposing Autoregressive Moving Average (ARMA) graph filters, which use a rational function of the graph shift operator. This rational form offers more degrees of freedom, potentially achieving better accuracy with fewer coefficients. The challenge lies in efficiently designing these ARMA filters for both directed and undirected graphs, especially when the graph structure itself is not perfectly known (universal design).
Methods
The paper proposes two main strategies for designing ARMA graph filters:
- Prony's Method Inspired Approach: This method adapts Prony's classical technique for system identification. It involves minimizing a modified error between the desired and modeled frequency response. This approach is further refined using an orthogonal subspace projection to improve conditioning and potentially accuracy.
- Iterative Approach: This method directly minimizes the true error between the desired and modeled frequency response. It's formulated as a recursive update of filter coefficients, often initialized with the solution from the Prony-inspired method. This iterative refinement aims to achieve higher approximation accuracy.
Both methods are designed to work for both directed and undirected graphs. The paper also extends the "universal design" concept, where filters are designed without explicit knowledge of the graph frequencies, by gridding the relevant frequency domains (real line for undirected, complex plane for directed). A centralized implementation of ARMA graph filters is also presented, leveraging efficient linear system solvers like the conjugate gradient (CG) method.
Datasets
The paper evaluates its proposed methods using:
- Synthetic data: Used to test the approximation accuracy of filter designs against ideal low-pass frequency responses and for Erdős Rényi graphs.
- Real data:
- Molene temperature dataset: Used for graph signal interpolation, compression, and prediction tasks. The graph is constructed based on geographical proximity and data smoothness.
Key Insights and Ideas
- ARMA filters offer superior approximation accuracy: ARMA filters, with their rational frequency response, can achieve significantly lower approximation errors than FIR filters, especially for complex frequency responses or when using fewer coefficients.
- Prony's projection is more robust than Prony's LS: For graphs with closely spaced eigenvalues (like Erdős Rényi graphs), Prony's projection method (which aims to minimize the true error) performs better than the standard Prony's Least Squares (LS) method (which minimizes a modified error).
- Iterative refinement is crucial for high accuracy: The iterative approach, by directly minimizing the true error, can further improve the approximation accuracy achieved by Prony's methods, particularly for higher-order filters.
- Universal design is effective: Designing filters by gridding the frequency domain (without knowing the exact graph frequencies) is a viable strategy and yields good results, especially for undirected graphs.
- ARMA filters are memory-efficient for compression: For lossy data compression, ARMA filters can achieve significant memory savings (up to 50%) with minimal error increase compared to FIR filters.
- Directed vs. Undirected Graphs: Generally, ARMA filters show better performance on undirected graphs, likely due to fitting on the real line versus the complex plane.
Key Results
- Approximation Accuracy: ARMA filters consistently outperform FIR filters in approximating desired frequency responses, often by several orders of magnitude, especially for higher filter orders. For example, in synthetic tests, ARMA filters achieved significantly lower Root Normalized Mean Square Error (RNMSE) than FIR filters.
- Data Compression: On the Molene dataset, ARMA filters enabled up to 50% memory savings for lossy compression with very little error compared to FIR filters.
- Interpolation: ARMA filters showed performance comparable to an ideal graph filter for interpolating missing data in the Molene dataset, outperforming FIR filters.
- Linear Prediction: ARMA filters achieved significantly lower approximation errors in linear prediction tasks on the Molene dataset compared to FIR filters, even with fewer bits for quantization. For instance, using an ARMA filter with K=4 and 7 bits achieved an error of 10⁻², saving 62.5% in transmission costs compared to FIR filters.
Limitations and Future Work
- Conditioning Issues: For both FIR and ARMA filters, the Vandermonde matrix can become ill-conditioned, especially with increasing orders. While ARMA filters can use lower orders, potentially mitigating this, it remains a consideration.
- Convergence of Iterative Approach: The iterative approach does not always guarantee monotonic convergence. In such cases, the paper suggests selecting the best result achieved during the iterations.
- Stability Constraint: The paper notes that the non-convex stability constraint for ARMA filters is ignored during the design phase but can be checked afterward.
- Future Work: The paper suggests that stationarity of the signal over time could be exploited by fitting joint graph-temporal filters. Additionally, the potential for ARMA models to reconstruct graph power spectra from subsets of nodes is mentioned.
Summary updated