In this paper, we consider the inverse graph filtering process when the original filter is a polynomial of some graph shift on a simple connected graph. The Chebyshev polynomial
approximation of high order has been widely used to approximate the inverse filter. In this paper, we propose an iterative Chebyshev polynomial approximation (ICPA) algorithm to implement the inverse filtering procedure, which is feasible to eliminate the
restoration error even using Chebyshev polynomial approximation of lower order. We also provide a detailed convergence analysis for the ICPA algorithm and a distributed implementation of the ICPA algorithm on a spatially distributed network.
Numerical results are included to demonstrate the satisfactory performance of the ICPA algorithm in graph signal denoising.
more »
« less
Polynomial control on stability, inversion and powers of matrices on simple graphs
Spatially distributed networks of large size arise in a variety of science and engineering problems, such as wireless sensor networks and smart power grids. Most of their features can be described by properties of their state-space matrices whose entries have indices in the vertex set of a graph. In this paper, we introduce novel algebras of Beurling type that contain matrices on a connected simple graph having polynomial off-diagonal decay, and we show that they are Banach subalgebras of the space of all bounded operators on the space of all p-summable sequences. The $\ell^p$-stability of state-space matrices is an essential hypothesis for the robustness of spatially distributed networks. In this paper, we establish the equivalence among -stabilities of matrices in Beurling algebras for different exponents $p$, with quantitative analysis for the lower stability bounds. Admission of norm-control inversion plays a crucial role in some engineering practice. In this paper, we prove that matrices in Beurling subalgebras of have norm-controlled inversion and we find a norm-controlled polynomial with close to optimal degree. Polynomial estimate to powers of matrices is important for numerical implementation of spatially distributed networks. In this paper, we apply our results on norm-controlled inversion to obtain a polynomial estimate to powers of matrices in Beurling algebras. The polynomial estimate is a noncommutative extension about convolution powers of a complex function and is applicable to estimate the probability of hopping from one agent to another agent in a stationary Markov chain on a spatially distributed network.
more »
« less
- Award ID(s):
- 1816313
- PAR ID:
- 10131404
- Date Published:
- Journal Name:
- Journal of functional analysis
- Volume:
- 276
- Issue:
- 1
- ISSN:
- 0022-1236
- Page Range / eLocation ID:
- 148-182
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A spatially distributed network contains a large amount of agents with limited sensing, data processing, and communication capabilities. Recent technological advances have opened up possibilities to deploy spatially distributed networks for signal sampling and reconstruction. In this paper, we introduce a graph structure for a distributed sampling and reconstruction system by coupling agents in a spatially distributed network with innovative positions of signals. A fundamental problem in sampling theory is the robustness of signal reconstruction in the presence of sampling noises. For a distributed sampling and reconstruction system, the robustness could be reduced to the stability of its sensing matrix. In this paper, we split a distributed sampling and reconstruction system into a family of overlapping smaller subsystems, and we show that the stability of the sensing matrix holds if and only if its quasi-restrictions to those subsystems have uniform stability. This new stability criterion could be pivotal for the design of a robust distributed sampling and reconstruction system against supplement, replacement and impairment of agents, as we only need to check the uniform stability of affected subsystems. In this paper, we also propose an exponentially convergent distributed algorithm for signal reconstruction, that provides a suboptimal approximation to the original signal in the presence of bounded sampling noises.more » « less
-
In this paper, we study stable coordination in multi- agent systems with directed interactions, and apply the results for distributed topology control. Our main contribution is to extend the well-known potential-based control framework orig- inally introduced for undirected networks to the case of net- works modeled by a directed graph. Regardless of the particular objective to be achieved, potential-based control for undirected graphs is intrinsically stable. Briefly, this can be explained by the positive semidefiniteness of the graph Laplacian induced by the symmetric nature of the interactions. Unfortunately, this energy finiteness guarantee no longer holds when a multi-agent system lacks symmetry in pairwise interactions. In this context, our contribution is twofold: i) we formalize stable coordination of multi-agent systems on directed graphs, demonstrating the graph structures that induce stability for a broad class of coordination objectives; and ii) we design a topology control mechanism based on a distributed eigenvalue estimation algorithm to enforce Lyapunov energy finiteness over the derived class of stable graphs. Simulation results demonstrate a multi-agent system on a directed graph performing topology control and collision avoidance, corroborating the theoretical findings.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/https://doi.org/10.1016/j.jfa.2018.09.014
