Iterative polynomial approximation algorithms for inverse graph filters
Cheng Cheng, Qiyu Sun, Cong Zheng · 2025
Read Iterative polynomial approximation algorithms for inverse graph filters by Cheng Cheng, Qiyu Sun, Cong Zheng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14341.txt.
Introduction
Cheng Cheng, Qiyu Sun, and Cong Zheng present 2025 methods to run the inverse of a graph filter by repeated polynomial steps. Graph filters shape signals that live on a network, and their inverse is needed for tasks like undoing blur. A famed family of polynomials, named in the text, can mimic smooth functions with error that falls at an exponential rate.
The new methods build on those polynomial fits and run in a spread-out way across the network. Each node needs only small storage and compute, and talks just to its direct neighbours. That suits swarms of small agents with weak hardware. The methods close in on the true inverse at an exponential rate. In sim tests they beat both a direct polynomial fit and a standard descent method on speed.
Catalog record
| CREATOR | Cheng Cheng, Qiyu Sun, Cong Zheng |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-14341
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Iterative polynomial approximation algorithms for inverse graph filters Cheng Cheng, Qiyu Sun, Cong Zheng Abstract Chebyshev interpolation polynomials exhibit the exponential approximation property to analytic functions on a cube. Based on the Chebyshev interpolation polynomial approximation, we propose iterative polynomial approximation algorithms to implement the inverse filter with a polynomial graph filter of commutative graph shifts in a distributed manner. The proposed algorithms exhibit exponential convergence properties, and they can be implemented on distributed networks in which agents are equipped with a data processing subsystem for limited data storage and computation power, and with a one-hop communication subsystem for direct data exchange only with their adjacent agents. Our simulations show that the proposed polynomial approximation algorithms may converge faster than the Chebyshev polynomial approximation algorithm and the conventional gradient descent algorithm do. Cheng is with the School of Mathematics, Sun Yat-sen University, Guangzhou, 510275; and Sun and Zheng are with the Department of Mathematics, University of Central Florida, Orlando, Florida 32816. Emails: [email protected]; Cheng is with the Department of Mathematics [email protected]. Keywords: Graph inverse filter, polynomial approximation algorithm, distributed implementation, graph signal processing. I Introduction Graphs are widely used to model the complicated topological structure of networks, such as (wireless) sensor networks, smart grids and social networks [ 1 , 10 , 13 , 25 , 26 , 27 , 30 , 32 ] . Many data sets on a network can be represented by signals {\bf x}=(x_{i})_{i\in V} residing on the graph {\mathcal{G}}=(V,E) , where x_{i} represents the real/complex/vector-valued data at the vertex/agent i\in V , a vertex in V may represent an agent of the network, and an edge in E between vertices could indicate that the corresponding agents have a peer-to-peer communication link between them. Graph signal processing paves an innovative way to extract valuable insights from datasets residing on the complicated networks, [ 7 , 8 , 22 , 23 , 36 ] . The filtering procedure for signals on a network is a linear transformation {\bf x}\longmapsto{\bf y}={\bf H}{\bf x},\vskip-3.99994pt (I.1) which maps a graph signal {\bf x} to another graph signal {\bf y}={\bf H}{\bf x} , and {\bf H}=(H(i,j))_{i,j\in V} is known as a graph filter . An graph shift is an elementary graph filter, and we say that a matrix {\bf S}=(S(i,j))_{i,j\in V} on the graph {\mathcal{G}}=(V,E) if S(i,j)\neq 0 only if either j=i or (i,j)\in E . In [ 13 ] , the notion of multiple commutative graph shifts {\bf S}_{1},\dots,{\bf S}_{d} are introduced, {\bf S}_{k}{\bf S}_{k^{\prime}}={\bf S}_{k^{\prime}}{\bf S}_{k},\ 1\leq k,k^{\prime}\leq d, (I.2) and some multiple commutative graph shifts on circulant/Cayley graphs and on Cartesian product graphs are constructed with physical interpretation. An important property for commutative graph shifts {\mathbf{S}}_{1},\ldots,{\mathbf{S}}_{d} is that they can be upper-triangularized simultaneously, \widehat{\bf S}_{k}={\bf U}^{\rm H}{\bf S}_{k}{\bf U},\ 1\leq k\leq d, (I.3) where {\bf U} is a unitary matrix and \widehat{\bf S}_{k}=(\widehat{S}_{k}(i,j))_{1\leq i,j\leq N},1\leq k\leq d , are upper triangular matrices. As \widehat{S}_{k}(i,i),1\leq i\leq N , are eigenvalues of {\bf S}_{k},1\leq k\leq d , we call the set \Lambda=\big\{\boldsymbol{\lambda}_{i}=\big(\widehat{S}_{1}(i,i),...,\widehat{S}_{d}(i,i)\big),1\leq i\leq N\big\} (I.4) as the joint spectrum of {\bf S}_{1},\ldots,{\bf S}_{d} [ 13 ] . For the case that graph shifts {\bf S}_{1},\ldots,{\bf S}_{d} are symmetric, all \widehat{S}_{k}(i,i),1\leq i\leq N,1\leq k\leq d are real-valued and the joint spectrum of graph shifts {\bf S}_{1},\ldots,{\bf S}_{d} is contained in some cube, \Lambda\subset[{\boldsymbol{\mu}},{\boldsymbol{\nu}}]:=[\mu_{1},\nu_{1}]\times\cdots\times[\mu_{d},\nu_{d}]\subset{\mathbb{R}}^{d}, (I.5) where for each 1\leq k\leq d , [\mu_{k},\nu_{k}] is the (minimal) interval to contain the spectrum of the graph shift {\bf S}_{k} . A popular family of graph filters is polynomial filters of commutative graph shifts {\bf S}_{1},\dots,{\bf S}_{d} , {\bf H}=h({\bf S}_{1},\ldots,{\bf S}_{d})=\sum_{l_{1}=0}^{L_{1}}\cdots\sum_{l_{d}=0}^{L_{d}}h_{l_{1},\dots,l_{d}}{\bf S}_{1}^{l_{1}}\cdots{\bf S}_{d}^{l_{d}},\vskip-6.00006pt (I.6) where h is a multivariate polynomial in variables t_{1},\cdots,t_{d} , h(t_{1},\ldots,t_{d})=\sum_{l_{1}=0}^{L_{1}}\cdots\sum_{l_{d}=0}^{L_{d}}h_{l_{1},\dots,l_{d}}t_{1}^{l_{1}}\ldots t_{d}^{l_{d}} [ 6 , 9 , 13 , 16 , 18 , 21 , 28 , 31 , 34 ] . The consideration of polynomial filters of multiple graph shifts is mainly motivated by signal processing of time-varying data sets on a sensor network over a period of time, which carry different correlation characteristics for spatial-temporal directions. Inverse filtering procedure associated with a polynomial filter of graph shifts is a versatile tool, offering a wide applications across denoising, signal reconstruction, graph semi-supervised learning and many other applications [ 2 , 3 , 5 , 6 , 9 , 16 , 17 , 21 , 24 , 29 , 31 ] . Its importance lies in its ability to recover original signals from observed data, enabling a deeper understanding of underlying network structures and dynamics. In this paper, we consider distributed implementation of inverse filtering procedure on simple graphs (i.e., unweighted undirected graphs containing no loops or multiple edges) of large order N\geq 1 . Given a polynomial filter {\bf H} of graph shifts, one of the main challenges in the corresponding inverse filtering procedure {\bf y}\longmapsto{\bf x}={\bf H}^{-1}{\bf y} (I.7) is on its distributed implementation, as the inverse filter {\bf H}^{-1} is usually not a polynomial filter of small degree even if {\bf H} is. The first two authors of this paper proposed the following exponentially convergent quasi-Newton method with arbitrary initial {\bf x}^{(0)} , {\bf e}^{(m)}={\bf H}{\bf x}^{(m-1)}-{\bf y}\ \ {\rm and}\ \ {\bf x}^{(m)}={\bf x}^{(m-1)}-{\bf G}{\bf e}^{(m)},\ m\geq 1 (I.8) to fulfill the inverse filtering procedure, where the polynomial approximation filter {\bf G} to the inverse {\bf H}^{-1} is so chosen that the spectral radius of {\bf I}-{\bf G}{\bf H} is strictly less than 1 [ 5 , 6 , 13 ] . An important problem is how to select the polynomial approximation filter {\bf G} appropriately for the fast convergence of the quasi-Newton method ( I.8 ). The above problem has been well studied when {\bf H} is a polynomial filter of the graph Laplacian (and a single graph shift in general) [ 3 , 6 , 15 , 16 , 29 , 31 ] . For a polynomial filter {\bf H} of multiple graph shifts, optimal/Chebyshev polynomial approximation filters are introduced in [ 13 ] . In Section II , we show the exponential approximation property of Chebyshev interpolation polynomials to analytic functions on a cube, and then we introduce the Chebyshev interpolation polynomial filter to approximate the inverse filter {\bf H}^{-1} and the corresponding quasi-Newton method algorithm ( III.2 ) to implement the inverse filtering procedure ( I.7 ). In Section III , we show the corresponding Chebyshev interpolation polynomial algorithm is of exponential convergence and can be applied to implement the inverse filtering procedure ( I.7 ) associated with a polynomial filter on distributed networks, see Theorem III.1 and Algorithms III.1 . Numerical experiments in Section IV indicate that the proposed Chebyshev interpolation polynomial approximation algorithm have better performance than Chebyshev polynomial approximation algorithm (CPA), the gradient descent algorithm with optimal step size (OGDA) and the autoregressive moving-average model (ARMA) do [ 3 , 13 , 15 , 16 , 17 , 29 , 31 , 34 ] . Notation: Bold lower cases and capitals are used to represent the column vectors and matrices respectively. Define \|{\bf x}\|_{2}=(\sum_{i\in V}|x_{i}|^{2})^{1/2} and \|{\bf x}\|_{\infty}=\sup_{i\in V}\{|x_{i}|\} for a graph signal {\bf x}=(x_{i})_{i\in V} and \|{\bf A}\|_{2}=\sup_{\|{\bf x}\|_{2}=1}\|{\bf A}{\bf x}\|_{2} for a graph filter {\bf A} . Denote the transpose, the Hermitian and Frobenius norm of a