HomeResearchSignal Processing over GraphsGeneralized Graph Signal Sampling and Reconstruction

Generalized Graph Signal Sampling and Reconstruction

1 Introduction

The research area of graph-based signal processing is developing fast to process signal and information  in irregular domains. An $N$-vertex undirected graph is represented by $\mathcal{G}(\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ is the vertex set and $\mathcal{E}$ is the edge set. A graph signal is a mapping from vertex set $\mathcal{V}$ to $\mathbb{R}$, which can also be written as a vector form ${\bf f}\in\mathbb{R}^N$. The eigenvectors $\{{\bf u}_k\}_{1\le k\le N}$ of the Laplacian of graph $\mathcal{G}$ are regarded as the Fourier basis of the frequency-domain, and the eigenvalues $0=\lambda_1<\lambda_2\le\cdots\le\lambda_N$ are regarded as frequencies. The expansion coefficients of a graph signal ${\bf f}$ in terms of $\{{\bf u}_k\}_{1\le k\le N}$ are the coefficients of the graph Fourier transform. Similar to Nyquist sampling theorem in time-domain, a smooth graph signal ${\bf f}$ may be uniquely determined by its decimation $\{f(u)\}_{u\in \mathcal{S}}$, where $\mathcal{S}\subseteq \mathcal{V}$ is the sampled vertex set. A natural description of the smoothness of ${\bf f}$ is being bandlimited. The subspace of $\omega$-bandlimited signals on $\mathcal{G}$ is called Paley-Wiener space, and denoted as $PW_{\omega}(\mathcal{G})\triangleq\text{span}\{{\bf u}_i|\lambda_i\le\omega\}$.

In sensor networks with clustering structure, the cluster head collects and combines data from nodes within the cluster, which is a natural local measurement. If the cluster head only transmits a linear combination of the signals, the graph signal reconstruction problem is estimating a smooth graph signal from local measurements. In this paper, we first generalize the sampling scheme for graph signals from decimation to local measurement. Based on this scheme, an algorithm named iterative local measurement reconstruction (ILMR) is proposed to reconstruct the original signal from limited measurements. It is proved that a bandlimited signal can be exactly reconstructed from its local measurements if certain conditions are satisfied. In noise scenario, the performance of ILMR is analyzed, and the optimal local weights are discussed. The proposed sampling scheme has several advantages. First, it will benefit in the situation where local measurements are easier to obtain than the samples of specific vertices. Second, the proposed local measurement and reconstruction is more robust against noise. This work has been published in the paper Generalized Graph Signal Sampling and Reconstruction, in 2015 IEEE Global Conference on Signal and Information Processing (GlobalSIP'15) and received the Best Paper Award.

2 Local Measurement: A Generalized Sampling Scheme

In the generalized sampling scheme proposed in this work, the vertices in $\mathcal{G}$ are partitioned into disjoint clusters, which are named as \emph{centerless local sets}. All the vertices in each centerless local set contribute to produce a measurement, and there is no specific sampling vertex.

Definition 1 (centerless local sets): For a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, assume that $\mathcal{V}$ is divided into disjoint local sets $\{\mathcal{N}_i\}_{i\in\mathcal{I}}$, where $\mathcal I$ denotes the index set. Each subgraph $\mathcal{G}_{\mathcal{N}_i}$, which denotes the subgraph of $\mathcal{G}$ restricted to $\mathcal{N}_i$, is connected.  Besides, $\{\mathcal{N}_i\}_{i\in \mathcal{I}}$ should satisfy $\bigcup_{i\in \mathcal{I}} \mathcal{N}_i=\mathcal{V}$ and $\mathcal{N}_i\cap \mathcal{N}_j=\emptyset$ for $\forall i, j\in\mathcal{I}, ~ i\neq j$.

For each centerless local set, a \emph{local weight} is defined to balance the contribution of all vertices in this set.

Definition 2 (local weight): A local weight ${\varphi}_i\in \mathbb{R}^N$ associated with a centerless local set $\mathcal{N}_i$ satisfies

$$\varphi_i(v)\begin{cases}\ge 0, v\in \mathcal{N}_i\\= 0, v\notin \mathcal{N}_i\end{cases}\text{ and }\sum_{v\in \mathcal{N}_i}\varphi_i(v)=1.$$

Finally, local measurement is defined by linearly combining the signals associated with the vertices in each centerless local set using the corresponding local weight, which is illustrated in Fig. 1.

Definition 3 (local measurement): For given centerless local sets and the associated local weights $\{(\mathcal{N}_i,{\varphi}_i)\}_{i\in \mathcal{I}}$, a set of local measurements for a graph signal $\bf f$ is $\{f_{{\varphi}_i}\}_{i\in \mathcal{I}}$, where

$$f_{{\varphi}_i}\triangleq\langle {\mathbf f}, {\varphi}_i\rangle=\sum_{v\in \mathcal{N}_i}f(v)\varphi_i(v).$$

 

Figure 1: An illustration of traditional sampling (decimation) scheme versus generalized sampling (local measurement) scheme. For each centerless local set, a local measurement is produced by a linear combination of signals associated with vertices within this set.

3 ILMR: Reconstruct Bandlimited Signals from Local Measurements

We will show that a bandlimited graph signal ${\mathbf f}\in PW_{\omega}(\mathcal{G})$ can be exactly reconstructed from its local measurements $\{f_{{\varphi}_i}\}_{i\in\mathcal{I}}$ under certain conditions. A reconstruction algorithm named iterative local measurement reconstruction (ILMR) is proposed to reconstruct graph signals from local measurements.

Proposition 1: For given centerless local sets and the associated weights $\{(\mathcal{N}_i, {\varphi}_i)\}_{i\in\mathcal{I}}$, $\forall {\mathbf f}\in PW_{\omega}(\mathcal{G})$, where $\omega<1/C_{\rm max}^2$, ${\mathbf f}$ can be reconstructed from its local measurements $\{f_{{\varphi}_i}\}_{i\in \mathcal{I}}$ through ILMR,

$${\mathbf f}^{(k+1)}={\mathbf f}^{(k)}+{\mathcal P}_{\omega}\left(\sum_{i\in \mathcal{I}}(f_{{\varphi}_i}-\langle {\mathbf f}^{(k)}, {\varphi}_i\rangle){\delta}_{\mathcal{N}_i}\right),$$

with the error at the $k$th iteration satisfying

$$\|{\mathbf f}^{(k)}-{\mathbf f}\|\le \gamma^{k}\|{\mathbf f}^{(0)}-{\bf f}\|,$$

where $\gamma =C_{\rm max}\sqrt{\omega}$ and $C_{\rm max}$ is determined by the division of centerless local sets.

It shows that if $\{{\varphi}_i\}_{i\in \mathcal{I}}$ are known ${\mathbf f}$ can be uniquely reconstructed by its local measurements $\{f_{{\varphi}_i}\}_{i\in \mathcal{I}}$. In each iteration of ILMR, the new increment is obtained by assigning the estimate error $(f_{{\varphi}_i}-\langle {\mathbf f}^{(k)}, {\varphi}_i\rangle)$ to all vertices in the associated centerless local sets, and then projecting it onto $PW_{\omega}(\mathcal{G})$. The procedures of ILMR in each iteration are illustrated in Fig. 2.

 

Figure 2: The procedures of ILMR.

For potential applications, if the local measurements come from the result of some repeatable physical operations, $\{{\varphi}_i\}_{i\in \mathcal{I}}$ is even not necessarily known when conducting ILMR. In detail, if $\{{\varphi}_i\}_{i\in\mathcal{I}}$ is unknown but fixed, i.e., the local measurement operation in Fig. \ref{algorithm} is a black box, $\langle {\mathbf f}^{(k)}, {\varphi}_i\rangle$ can also be obtained by conducting the physical operations in each iteration.

4 Noise Analysis

Suppose the observed signal associated with each vertex is corrupted by independent zero-mean Gaussian noise. The corrupted signal is denoted as $\tilde{\bf f}={\bf f+n}$, where ${\bf n}$ denotes the noise and $n(v)\sim\mathcal{N}(0,\sigma^2(v))$. The corrupted local measurements $\{\langle \tilde{\mathbf f}, {\varphi}_i\rangle\}_{i\in\mathcal{I}}$ is utilized to produce the temporary estimate $\tilde{\bf f}^{(k)}$ in ILMR.

Proposition 2: For given centerless local sets and the associated weights $\{(\mathcal{N}_i, {\varphi}_i)\}_{i\in\mathcal{I}}$, the original signal ${\mathbf f}\in PW_{\omega}(\mathcal{G})$, assuming the noise associated with vertex $v$ follows independent Gaussian distribution $\mathcal{N}(0,\sigma^2(v))$, if $\omega$ is less than $1/C_{\rm max}^2$, the expected reconstruction error of ILMR in the $k$th iteration satisfies

$${\rm E}\left\{\|\tilde{\bf f}^{(k)}-{\bf f}\|\right\} \le\frac{1}{1-\gamma}\sqrt{\frac{2}{\pi}}\sum_{i\in\mathcal{I}}\sqrt{|\mathcal{N}_i|}\sigma_i +\mathcal{O}\left(\gamma^{k+1}\right),$$

where $\sigma_i$ is the variance of the zero-mean Gaussian equivalent noise $n_i$ of $\mathcal{N}_i$,

$$\sigma_i^2=\sum_{v\in\mathcal{N}_i}\sigma^2(v)\varphi_i^2(v).$$

For given division of centerless local sets, the optimal choice of local weights to minimize the reconstruction error can be derived as follows.

Corollary 1: For given $\{\mathcal{N}_i\}_{i\in\mathcal{I}}$, if the noises associated with the vertices are independent and follow zero-mean Gaussian distributions $n(v)\sim\mathcal{N}(0,\sigma^2(v))$, then the optimal local weights $\{{\varphi}_i\}_{i\in\mathcal{I}}$ are

$$\varphi_i(v)=\displaystyle{\frac{(\sigma^2(v))^{-1}}{\sum_{v\in\mathcal{N}_i}(\sigma^2(v))^{-1}}}\delta_{\mathcal{N}_i}(v).$$

Specifically, we consider the case in which the noise variances are the same for all the vertices, i.e., $\sigma(v)=\sigma$ for any $v\in\mathcal{V}$.

Proposition 3: For given centerless local sets $\{\mathcal{N}_i\}_{i\in\mathcal{I}}$ and the associated weights $\varphi_i(v)=1/|\mathcal{N}_i|$ for $v\in\mathcal{N}_i$, the original signal ${\mathbf f}\in PW_{\omega}(\mathcal{G})$, assuming the noise associated with each vertex follows \emph{i.i.d} Gaussian distribution $\mathcal{N}(0,\sigma^2)$, if $\omega$ is less than $1/C_{\rm max}^2$, the expected reconstruction error of ILMR in the $k$th iteration satisfies

$${\rm E}\left\{\|\tilde{\bf f}^{(k)}-{\bf f}\|\right\}\le\frac{|\mathcal{I}|\sigma}{1-\gamma}\sqrt{\frac{2}{\pi}}+\mathcal{O}\left(\gamma^{k+1}\right).$$

5 Numerical Results

The convergence of ILMR in the noise-free scenario is verified. The Minnesota road graph, which has $2640$ vertices and $6604$ edges, is used in the experiments. The graph is divided into $709$ and $358$ centerless local sets for $N_{\rm max}$ equals $4$ and $8$, respectively. Fig. \ref{exp1} illustrates the convergence curves for different local weights. The convergence is accelerated if the graph is divided into more sets, which will bring more measurements and a higher sampling rate. It also shows reconstruction with uniform weight converges slightly faster than that with random weight, and both converge much faster than Kronecker delta weight case. In other words, local measurement help the reconstruction by combining the signals on different vertices properly.

 

Figure 3: The convergence behavior of ILMR for various division of centerless local sets and different local weights.

6 Download the paper

X. Wang, J. Chen, and Y. Gu, Generalized Graph Signal Sampling and Reconstruction, IEEE Global Conference on Signal and Information Processing (GlobalSIP), Orlando, Florida, USA, December 14-16, 2015. [Best Paper Award]

X. Wang, J. Chen, and Y. Gu, Local Measurement and Reconstruction for Noisy Graph Signals, submitted for possible publication.

7 Contact the authors 

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