HomeResearchSignal Processing over GraphsA Distributed Tracking Algorithm for Reconstruction of Graph Signals

A Distributed Tracking Algorithm for Reconstruction of Graph Signals

1 Introduction

Signal processing on graph is naturally related to distributed systems. For large-scale systems in lack of a central controller, e.g., sensor networks, distributed estimation and tracking is an important topic. In many practical distributed systems, a central processor is lacking and the majority of nodes have severely limited data processing power. Moreover, the node-to-node transmission delay is non-negligible in large-scale networks, i.e., a given node cannot communicate globally with all other nodes to obtain instant fresh data. These difficulties with large distributed systems pose a new and practical challenge to graph-based signal processing: how to reconstruct graph signals distributively and efficiently? This is the motivation of the present paper, in which we propose a distributed algorithmic solution and answer the prior question to a reasonable extent.

In this work, we focus on the distributed recovery problem of graph-based time-varying signal. We propose a distributed algorithm, namely the {\it distributed least square reconstruction} (DLSR), to adaptively reconstruct the missing values of a graph signal by allowing neighboring nodes to communicate with one another and make local updates. Due to the transmission delay caused by node-to-node communication, some out-of-band energy inevitably occurs during the distributed signal reconstruction process. The DLSR algorithm uses a decay factor to dampen this out-of-band energy and achieves {\it perfect reconstruction} of the unknown graph signal. Theoretical convergence proof and error bounds of DLSR is given in our analysis. This work has been published at IEEE Journal of Selected Topics on Signal Processing 9(4): 728-740, 2015 in the paper A Distributed Tracking Algorithm for Reconstruction of Graph Signals by Xiaohan Wang, Mengdi Wang, and Yuantao Gu.

2 Problem Setting

We consider the distributed reconstruction of a time-varying low-frequency signal defined over graph by sampling at a small portion of nodes. The problem could be described in the scenario of wireless sensor network (WSN). For a given WSN, there are unknown function $f_*^{(t)}(v)$ associating with node $v$ at time $t$. Suppose that the function is slowly varying over both the time domain and the space domain. A snapshot of such function could be modeled as an unknown time-varying low-frequency signal ${\bf f}_*^{(t)}\in PW_{\omega}(\mathcal{G})$ located over a graph.

Suppose that the WSN is a hybrid network and only a small subset of nodes in $\mathcal{S}$ are equipped with sensors. As a result, one can measure the signal entries on support $\mathcal{S}$ as $\{f_*^{(t)}(u)\}_{u\in\mathcal{S}}$ at time $t$. Our purpose is to distributivedly estimate the function values at all nodes $\{f_*^{(t)}(v)\}_{v\in\mathcal{V}}$, by using historical measurements at selected nodes $\{f_*^{(\tau)}(u)\}_{u\in\mathcal{S}, \tau\le t}$. See Fig. 1 for a demonstration of the raised problem.

 

Figure 1: An example of graph signal reconstruction over wireless sensor network.

When the signal is time-invariant, the problem reduces to bandlimited graph signal reconstruction, where the nodes with and without sensors correspond to sampled and missing data. In the distributed setting, it is impossible for every node to obtain the instant estimation errors $\{f_*(u)-f^{(k)}(u)\}_{u\in\mathcal{S}}$.

In what follows, we proposed an algorithm called distributed least square reconstruction (DLSR). By letting each node conducting the iteration locally at each time instant, DLSR can adaptively reconstruct the missing entries of a slowly time-varying graph signal.

3 Algorithm Description

The basic idea of DLSR is to spread the current estimation errors associated with the representative nodes (which are equipped with sensors) to all other nodes over the connected network. Every node iteratively updates its own estimation based on its received messages.

The driver of the proposed algorithm is on those nodes with sensors, which calculates the error between the measurement $f_*^{(k)}(u)$ and the temporary estimation $f^{(k)}(u)$ in the $k$th iteration by

$$         \epsilon^{(k)}(u) = f_*^{(k)}(u) - f^{(k)}(u), \quad\forall u\in\mathcal{S}.$$

Then the estimation errors at node $u$ ($u\in\mathcal{S}$) are transmitted to other nodes in the network. At the $k$th iteration, an arbitrary $v$ collects a set of delayed but most recent estimation errors,

$$         \{\epsilon^{(k-\tau(u,v))}(u)\}_{u\in\mathcal{S}}, \quad \forall v\in\mathcal{V}(\mathcal{G}),$$

where $\tau(u,v)$ denotes the transmission delay from node $u$ to node $v$. We denote the maximal transmission delay of the network by $\tau=\max_{u\in\mathcal{S}, v\in\mathcal{V}(\mathcal{G})}\tau(u,v)$. Utilizing the most recent estimation errors, node $v$ updates its local estimate by

\begin{align}&f^{(k+1)}(v)=(1-\mu_{k+1}\beta_{k+1})f^{(k)}(v)\nonumber\\&\quad+\mu_{k+1}\sum_{u\in\mathcal{S}}\epsilon^{(k-\tau(u,v))}(u)(\mathcal{P}_{\omega}{\delta}_u)(v),\quad \forall v\in\mathcal{V}(\mathcal{G})\end{align}

where $\mu_{k+1}$ and $\beta_{k+1}$ denote the stepsize and decay factor, respectively. $(\mathcal{P}_{\omega}{\delta}_u)(v)$ denotes the entry at $v$ of the lowpass component of ${\delta}_u$, which could be calculated and stored before the system starts.

4 Convergence Analysis

We will first study the convergence behavior of DLSR in a general situation that the bandlimited graph signal to be constructed varies slowly by time, and then specialize the result to a time-invariant case. In order to simplify the expression, we will fix stepsizes $\mu$ and $\beta$ to be constants in studying the time-varying case. Finally, we let the stepsizes be diminishing and show that DLSR achieves a perfect reconstruction of time-invariant signal.

By defining the in-band error and out-of-band error as, respectively,

\begin{align}e^{(k)}&=\left\|\mathcal{P}_{\omega}{\bf f}^{(k)}-\mathcal{P}_{\omega}\tilde{\bf f}_*^{(k)}\right\|,\nonumber\\e_+^{(k)}&=\left\|\mathcal{P}_{{\omega}_+}{\bf f}^{(k)}-\mathcal{P}_{{\omega}_+}\tilde{\bf f}_*^{(k)}\right\| =\left\|\mathcal{P}_{{\omega}_+}{\bf f}^{(k)}\right\|,\nonumber\end{align}

where $\mathcal{P}_{\omega_+}$ denotes the projection operator onto the high-frequency subspace, the following proposition gives inequalities that $\left\{e^{(k)}\right\}$ and $\{e_+^{(k)}\}$ satisfy. Further, it will be shown that if the signal varies slowly enough, by properly selecting the stepsize $\mu$, DLSR can track time-varying signals.

Proposition 1: Supposing the true signal satisfies

$$\left|f_*^{(k+1)}(u)-f_*^{(k)}(u)\right|\le\Delta, \quad\forall u\in\mathcal{V(G)}, k\ge1,$$

If $\Delta\le\min\left\{\Delta_{\text{max}},\beta B_{e_+}/(|\mathcal{S}|\tau)\right\}$ and

$$\mu_{\text{min}}\le\mu<\min{\left\{\mu_{\text{max}},\frac{1}{\beta+A},\frac{B_{\eta}}{C+|\mathcal{S}|^{\frac{3}{2}}\tau^2\Delta}\right\}},$$

the errors $\left\{e^{(k)}\right\}$ and $\{e_+^{(k)}\}$ satisfy

\begin{align}e_+^{(k+1)} & \le (1-\mu\beta)e_+^{(k)}+\mu^2C+M(\mu)\Delta,\nonumber\\e^{(k+1)} &\le (1-\mu\beta-\mu A)e^{(k)}+\mu\|{\bf T}\|e_+^{(k)}+\mu^2C+M(\mu)\Delta.\end{align}

In the above inequalities, $M(\mu)$, $\Delta_{\text{max}}$, $\mu_{\text{min}}$, $\mu_{\text{max}}$, $B_{\eta}$ and $C$ are constants determined by $|\mathcal{S}|$, $\tau$, $\mu$, $\beta$, $\Delta$ and $N$.

Taking the limit superiors, one obtains

\begin{align}\limsup_{k\rightarrow\infty}e_+^{(k)}&\le\left(D+\frac{E}{\beta}\right)\mu+\frac{M(\mu)}{\beta\mu}\Delta,\nonumber\\\limsup_{k\rightarrow\infty}e^{(k)}&\le\left(1+\frac{\|{\bf T}\|}{\beta}\right) \left(\frac{D\beta+E}{\beta+A}\mu+\frac{M(\mu)}{(\beta+A)\mu}\Delta\right).\nonumber\end{align}

where $D$ and $E$ are constants. The above results imply that for a constant stepsize $\mu$, the out-of-band error $e_+^{(k)}$ will eventually get below a threshold that is determined by $\mu$ and $\Delta$. Similarly, $\mathcal{P}_{\omega}{\bf f}^{(k)}$ will converge to the neighborhood of $\mathcal{P}_{\omega}\tilde{\bf f}_*^{(k)}$, and the error is also controlled by $\mu$ and $\Delta$.

For the time-invariant case, Proposition 1 becomes the following corollary for $\Delta=0$.

Proposition 2: The total error for the time-invariant case satisfies

$$\limsup_{k\rightarrow\infty}\|{\bf f}^{(k)}-{\bf f}_*\|\le F\beta+G\frac{\mu}{\beta}+H\mu+J\beta\mu,$$

where $F$, $G$, $H$, and $J$ are constants.

According to Proposition 2, by discarding the higher order of a diminishing stepsize $\mu_k$, the best $\beta_k$ satisfies $\beta_k\sim O(\sqrt{\mu_k})$ to minimize the total error. Accordingly, the total error bound can be controlled by adjusting $\mu_k$ and $\beta_k$. In other words, the reconstruction error can be made {\it arbitrarily small}: DRSL achieves perfect reconstruction.

The following proposition gives the convergence analysis for a special choice of diminishing stepsize and decay factor. 

Proposition 3: For diminishing stepsize $\mu_k=\mu_1/\sqrt{k}$ and decay factor $\beta_k=\beta_1/\sqrt[4]{k}$, the total error satisfies the following inequality,

$$\|{\bf f}^{(k)}-{\bf f}_*\|\le K/\sqrt[4]{k},$$

where $K$ is a constant.

It means that the total estimation error decreases on the rate of $1/\sqrt[4]{k}$ and converges to zero eventually.

5 Numerical Results

Experiments are designed to confirm the theoretical analysis and test the performance of the proposed distributed algorithm. The graph is generated by $100$ randomly located nodes and the edges are generated by $4$-nearest neighbors of the nodes, and the weights are inversely proportional to the square of geometric distance. Among the $100$ nodes, $20$ of them are randomly selected as the sampling set. The bandlimited signal is generated by filtering the high-frequency components off. The transmission delay of each pair of nodes is simply regarded as the number of hops between them in the graph. The maximal transmission delay of this graph is $14$.

In this experiment, the tracking performance of DLSR is verified. The parameters are chosen as $\Delta=0.005, \mu=0.1$, and $\beta=10^{-3}$. The time-varying signal is generated by adding a random bandlimited increment whose largest absolute entry is $\Delta$ for each time step. The aiming signal and iterative results of four nodes are focused on, as illustrated in Fig. 2. The nodes associated with the upper two subfigures are in the sampling set, and the nodes in the lower two subfigures are not in the sampling set. All the nodes can track the aiming signal for not dramatic changes. The proposed algorithm can track the slowly varying graph signal along with time.

 

Figure 2: Time-varying aiming signal and iterative results of four nodes. The proposed algorithm can track the aiming signal over time.

6 Download the paper

X. Wang, M. Wang, and Y. Gu, A Distributed Tracking Algorithm for Reconstruction of Graph Signals, IEEE Journal of Selected Topics on Signal Processing, 9(4): 728-740, 2015.

7 Contact the authors 

For any question and comment about the code and the website, please contact Yuantao Gu and Xiaohan Wang.