PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling of graph signals with successive local aggregations

Antonio G. Marques, Santiago Segarra, Geert Leus, Alejandro Ribeiro

arXiv:1504.04687v2cs.SIcs.IT

TL;DR

The paper addresses how to sample graph signals when existing approaches observe values at multiple nodes. It proposes successive local graph-shift aggregations at a single node, analyzes recovery under several settings, and shows equivalence to classical sampling on directed cycles while preserving a useful Vandermonde structure more generally.

  • Problem

    Existing graph-signal sampling largely observes signal values at a subset of nodes, motivating a single-node approach that uses graph structure for recovery.

  • Method

    The paper samples successive applications of a graph-shift operator at one node, using local neighbor exchanges and exploiting the resulting Vandermonde sampling structure.

  • Results

    The method is equivalent to classical sampling on directed cycles and provides conditions for perfect reconstruction on more general graphs.

  • Takeaways & Limitations

    A K-bandlimited graph signal can be reconstructed at one node from its own value and K −1 exchanges with neighbors when the stated recovery conditions hold.

Abstract

from arXiv · show

A new scheme to sample signals defined in the nodes of a graph is proposed. The underlying assumption is that such signals admit a sparse representation in a frequency domain related to the structure of the graph, which is captured by the so-called graph-shift operator. Most of the works that have looked at this problem have focused on using the value of the signal observed at a subset of nodes to recover the signal in the entire graph. Differently, the sampling scheme proposed here uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the information gathered by the neighbors of the node. When the graph corresponds to a directed cycle (which is the support of time-varying signals), our method is equivalent to the classical sampling in the time domain. When the graph is more general, we show that the Vandermonde structure of the sampling matrix, which is critical to guarantee recovery when sampling time-varying signals, is preserved. Sampling and interpolation are analyzed first in the absence of noise and then noise is considered. We then study the recovery of the sampled signal when the specific set of frequencies that is active is not known. Moreover, we present a more general sampling scheme, under which, either our aggregation approach or the alternative approach of sampling a graph signal by observing the value of the signal at a subset of nodes can be both viewed as particular cases. The last part of the paper presents numerical experiments that illustrate the results developed through both synthetic graph signals and a real-world graph of the economy of the United States.

I. INTRODUCTION

The paper extends graph-signal sampling beyond observing values at selected nodes by using successive graph-shift aggregations at one node. It connects this scheme to classical sampling while addressing recovery, noise, unknown frequency support, and broader sampling formulations.

  • I. INTRODUCTION: Graph signals are assumed to have sparse representations in a graph-structure-related frequency domain.
  • I. INTRODUCTION: The proposed method samples at a single node through successive graph-shift applications, using locally exchanged neighbor information.
  • I. INTRODUCTION: The paper analyzes noiseless recovery, noisy reconstruction, unknown frequency support, and a generalized scheme containing selection and aggregation sampling as special cases.
  • II. SAMPLING OF GRAPH SIGNALS: The graph-shift operator is a locally computable linear transformation whose sparsity pattern captures graph structure.
  • II. SAMPLING OF GRAPH SIGNALS: Successive aggregation produces samples that node i can determine locally from information within progressively larger neighborhoods.

A. Example: Sampling in the time domain

On a directed cycle, selection sampling and aggregation sampling both reduce to conventional time-domain sampling. Aggregation differs on general graphs because it moves the signal through the graph and incorporates the chosen shift operator.

  • A. Example: Sampling in the time domain: A directed cycle represents the discrete time domain, with each node connected cyclically to the next.
  • A. Example: Sampling in the time domain: With K/N = 1/2, the uniform selection matrix selects the odd-indexed signal values.
  • A. Example: Sampling in the time domain: Using S = Adc, successive shifts rotate the signal so aggregation at one node collects the same elements as selection sampling.
  • A. Example: Sampling in the time domain: For the cycle graph, selection and aggregation sampling are equivalent and reduce to conventional sampling.
  • A. Example: Sampling in the time domain: On general graphs, selection samples fixed nodes while aggregation samples a shifted signal at one fixed node, making aggregation dependent on graph structure.
  • A. Example: Sampling in the time domain: Graph-frequency sparsity is expressed through a subset of eigenvectors of the graph-shift operator, paralleling classical bandlimitedness.

B. Selection sampling of bandlimited graph signals

Selection sampling observes a subset of graph nodes and recovers a bandlimited signal through its active frequency coefficients. Perfect recovery requires an invertible sampled basis matrix, unlike the automatically invertible Vandermonde structure available for classical time signals.

  • Selection sampling: Selection sampling forms samples as Cx and recovers a K-bandlimited signal by inverting CVK before reconstructing x = VKbxK.The sampled basis rows must be linearly independent.
  • Aggregation sampling: Aggregation sampling observes sequentially shifted signals at one node, with shifts computed through local information exchange among neighboring nodes.The graph-shift operator participates in both sampling and recovery.
  • Aggregation sampling: The shifted observation at node i has the form yi = Ψdiag(υi)bx, where Ψ is Vandermonde and υi contains frequency-basis values at that node.This representation relates local shifted observations to the sparse frequency coefficients.
  • Recovery conditions: Perfect aggregation recovery requires invertible CΨi; with the stated sampling setup, this follows from distinct first K eigenvalues and nonzero first K entries of υi.The Vandermonde factor supplies full rank, while the diagonal node-dependent factor must also be invertible.
  • Recovery conditions: Only the first K entries of the shifted signal are needed for recovery, rather than the entire vector yi.Once bxK is recovered, the original signal follows as x = VKbxK.

D. Discussion

The discussion interprets aggregation sampling as local recovery of bandlimited graph signals. Its feasibility depends on graph spectral structure, node participation in active frequencies, and knowledge of the relevant graph basis.

  • Local recovery: A K-bandlimited signal can be reconstructed at one node from its own value and K−1 exchanges with neighbors.These observations involve nodes within a neighborhood of radius K−1.
  • Local recovery: For a 1-bandlimited signal, the value at one node alone suffices when that node has a nonzero value in the active frequency basis.For a 2-bandlimited signal, the node value and one neighboring exchange suffice under Proposition 1.
  • Implementation: Local implementation requires nodes to know VK and the first K eigenvalues of the graph-shift operator.This knowledge represents the graph structure supporting the signal.
  • Interpolator structure: The interpolator factors into graph-basis, sampling-pattern, and node-frequency terms, revealing which structures determine recovery.The factorization also supports closed-form computation through diagonal and Vandermonde inverses.
  • Sampling patterns: Sampling patterns remain invertible for several regularly spaced choices when the relevant eigenvalues are distinct, including the classical uniform-spacing counterpart.Offset patterns additionally require the active frequencies to be nonzero.

IV. SAMPLING AND INTERPOLATION IN THE PRESENCE OF NOISE

With noisy shifted observations, the paper estimates the bandlimited signal using BLUE under a general covariance model. Error covariance quantifies estimator quality, while the sampling design and noise structure affect recovery performance.

  • Noise model: Noisy aggregation observations are modeled as zi = yi + wi, with zero-mean noise independent of the graph signal and having covariance R(i)w.The interpolation analysis allows colored noise.
  • BLUE interpolation: The BLUE estimator recovers the active frequency coefficients when the required inverse exists and coincides with the Gaussian MVU estimator.In the Gaussian case, it attains the Cramér–Rao lower bound and its inverse covariance is the Fisher information matrix.
  • BLUE interpolation: More observation rows improve estimation, while exact K-row selection reduces the general estimator to the corresponding simplified form.The stated reduction assumes the inverse exists.
  • Performance assessment: The covariance depends on the noise model, graph frequencies, observation node, and selected observations.These factors determine the error behavior of the estimator.
  • Performance assessment: Error metrics based on covariance include trace, largest eigenvalue, and inverse trace of the inverse covariance.Trace minimization corresponds to minimizing mean square error.
  • Performance assessment: The frequency-estimator covariance is used for metrics e3 and e4 because the time-estimator covariance is singular.The covariance matrices therefore support different assessment choices.

B. Noise models

The paper considers several graph-domain noise models and derives their covariance consequences. Even white noise can become correlated after graph processing, with correlation shaped by the graph and sampling design.

  • Noise models: For white noise in the observed signal, the covariance is R(i)w = σ2I, with σ2 denoting noise power.The corresponding K×K covariance is obtained for the selected observations.
  • Noise models: White noise in the original signal yields covariance shaped by Ψ, the eigenvector matrix V, and the node-dependent eigenvalue factors υi.For a normal shift, V is unitary and the expression simplifies using |diag(υi)|2.
  • Noise models: The resulting noise is correlated, and its correlation depends on graph eigenvalues and eigenvectors, the observation node, and the observation-selection scheme.Thus noise color after processing is tied to both graph structure and sampling choices.
  • Noise models: White noise in the active frequency coefficients propagates through the observation model as wi = Ψdiag(υi)EKbwK.This provides another covariance model for noisy aggregation observations.
  • Noise models: Noise originating in a graph-process input or before low-pass graph filtering can produce structured observation noise.Diffusion processes and prior low-pass graph filtering are cited as examples.

C. Selection of the sampling set

Sampling-node choice affects noisy interpolation quality, even though noiseless recovery can use any node satisfying the nonzero-eigenvector condition. The preferred node depends on active frequencies and the error criterion.

  • Any node can recover the graph signal when the entries of υi at active frequencies are non-zero.
  • Noise makes the error covariance matrix node-dependent, so sampling-node selection should target a small interpolation error.The best node can be found by evaluating N closed-form expressions involving matrix inversions.
  • For white noise in active frequency coefficients, estimator performance is independent of the sampling node for every stated error metric.
  • For the e4 metric, the optimal node has large |[υi]k| values at active frequencies, weighted by eigenvalue magnitude and the selection scheme.

2) Design of the sample-selection scheme:

The sample-selection scheme controls the tradeoff between reconstruction quality and noise, while structured selection matrices make optimization more manageable. Sampling-node and shift choices can be jointly optimized for local reconstruction.

  • The error covariance depends on the selection matrix, whose design trades sample quality against the corresponding noise and generally depends on the chosen error metric.
  • Admissible matrices in CK guarantee feasible recovery while greatly reducing the candidate space compared with all N choose K selection matrices.
  • For e3, the optimal shift origin is chosen by minimizing det bR(i), comparing consecutive structured selection matrices.
  • If shifts amplify active frequencies, the strategy applies the shift as many times as possible; if they attenuate them, it avoids applying the shift.
  • Selection schemes outside CK lead to binary optimization, whose approximate algorithms are left for future work.
  • Sampling-node selection and sampling shifts can be combined to obtain the best local reconstruction across graph nodes.
  • More than N columns may be added when shifting attenuates noise while amplifying the signal, benefiting the sampling procedure.

V. IDENTIFYING THE SUPPORT OF THE GRAPH SIGNAL

Known-support recovery extends beyond principal eigenvectors, whereas unknown-support recovery exploits the aggregation scheme’s Vandermonde sensing matrix. In the noiseless case, 2K observations can identify and reconstruct a K-sparse signal under stated conditions.

  • All recovery results remain valid for any known active frequency support when the corresponding eigenvector and canonical matrices replace the principal-frequency matrices.
  • Unknown-support sampling becomes a sparse reconstruction problem, with the aggregation scheme providing a useful Vandermonde sensing matrix.
  • For known support, selecting K suitable rows of Ψdiag(υi)EK gives a one-to-one invertible transformation; unknown support requires more samples.
  • 2K observations guarantee unique K-sparse recovery when the structured selection matrix, nonzero eigenvalues, distinct eigenvalues, and nonzero υi entries satisfy Proposition 2.
  • The identifiability proof relies on every 2K-column submatrix of the aggregation sensing matrix being full rank through its Vandermonde structure.
  • For a single active frequency, one sample cannot identify the frequency, but two samples reveal its eigenvalue ratio and enable full-signal reconstruction.
  • The l0 formulation is non-convex; replacing it with an l1 norm provides a straightforward convexification, but support guarantees require coherence or RIP analysis.

B. Noisy joint recovery and support identification

With unknown frequency support and noise, recovery uses a sparsity-regularized least-squares formulation that accounts for colored noise. Performance is sensitive to sensing-matrix conditioning and eigenvalue similarity.

  • Noisy unknown-support recovery estimates the sparse frequency coefficients through a least-squares optimization problem.
  • The objective weights observations by the inverse square root of the noise covariance to account for colored noise.
  • Replacing the l0 penalty with an l1 penalty yields a convexified formulation controlled by the parameter γ.
  • Poor conditioning of CΨdiag(υi), strongly influenced by similar eigenvalues, leads to bad recovery performance.

VI. SPACE-SHIFT SAMPLING OF GRAPH SIGNALS

The paper introduces a general space-shift sampling setup that selects observations from signals collected at different nodes and shifts. Its formulation contains local aggregation and selection sampling as special cases, while distributed implementation reveals rank and recoverability constraints.

  • General sampling formulation: The general setup samples a vectorized noisy graph signal by selecting K equations from N^2 available observations to estimate the active frequency coefficients.The selected coefficients determine the reconstructed graph signal, while the selection aims to minimize noise-induced error.
  • Special cases: Restricting observations to one node yields local aggregation sampling, whereas selecting observations at a fixed shift across nodes yields selection sampling.Thus, both schemes are particular cases of the more general formulation.
  • Distributed implementation: In distributed message passing, a sampling node accesses its own shifted samples and earlier shifted samples from incoming neighbors.For L1 shifts and N1 neighbors, the node accesses L1 + 1 self-samples and L1 samples from each neighbor.
  • Distributed implementation: The structured observation matrix has 1 + L1(1 + N1) rows, but its associated sampling matrix is not full row rank.All but the first samples at the sampling node are linear combinations of neighbor samples.
  • Recoverability constraint: The number of recoverable frequencies under this distributed pattern is at most 1 + L1N1.The bound follows from the linear dependence among observations collected at the sampling node.
  • Alternative structures: Other distributed arrangements, such as nonneighboring nodes forwarding samples to a fusion center, need not exhibit the same linear-combination dependence.The absence of shared neighborhoods can remove this particular dependency among samples.

VII. NUMERICAL EXPERIMENTS

The experiments evaluate noiseless and noisy recovery using synthetic graph signals and a U.S. economic-sector network. They demonstrate exact recovery in several bandlimited settings, while unknown-frequency recovery depends on the graph-shift operator and network conditions.

  • Experimental scope: The experiments cover noiseless synthetic recovery, noisy recovery on real economic data, and space-shift sampling on the economic network.The real-world graph represents exchanges among U.S. economic sectors.
  • Economic network: For the U.S. economic network, the shift operator is sparse across the 62 real sectors and highly connected through artificial sectors AV and FU.The network contains 64 nodes in total, including AV and FU.
  • Synthetic signals: A 20-node random graph is evaluated with S1 = A, S2 = I − A, and S3 = 0.5A^2, which share eigenvectors but have different eigenvalues.S3 preserves locality through a two-hop neighborhood despite having a different sparsity pattern.
  • Known frequency support: The synthetic signal has bandwidth K = 3, and three aggregated samples recover the whole signal for any of the three shift operators.Its graph-frequency representation contains three active components, despite the signal appearing seemingly random in the node domain.
  • Unknown frequency support: When the active frequencies are unknown, 2K = 6 samples guarantee identifiability, but relaxed recovery depends on the network, signal, node, and shift operator.For the illustrated signal, the norm-1 relaxation succeeds with S = A at node 4 but fails with S = I − A at node 5.
  • Economic network: The 2011 production signal is approximately bandlimited, and retaining four frequency coefficients gives reconstruction error 3.5×10^-3.The error is computed as the ratio between reconstruction-error energy and original-signal energy.
  • Noisy recovery: Noise experiments compare interpolation performance across nodes, while a separate experiment treats the full economic signal as a noisy version of its four-frequency reconstruction.The latter evaluates reconstruction from four samples.

1) White noise in the observed signal:

Aggregation sampling under white-noise models shows that reconstruction accuracy depends strongly on the sampling node and noise location, while theoretical and empirical errors agree closely. In the U.S. economic graph, aggregation sampling outperforms selection sampling, and successive shifts substantially reduce median error.

  • White-noise analysis: Theoretical reconstruction errors closely match empirical averages across 1,000 noisy realizations for observation noise and signal noise.This agreement is reported for both white noise added to observations and white noise added directly to the reconstructed signal.
  • White-noise analysis: Reconstruction quality is highly node dependent: artificial sectors AV and FU perform best, while nodes 34 and 31 perform worst under observation noise.Nodes 34 and 31 contain a component of order 10^-4, increasing noise sensitivity; AV and FU are closely related to other economic sectors.
  • White-noise analysis: Under signal noise, AV and FU again attain the best reconstructions, while sectors 34 and 31 have the highest errors; the best non-artificial sector reaches error 0.001.The reported error corresponds to Professional Services under the stated signal-noise model.
  • White-noise analysis: With noise added only to the four active frequencies, reconstruction error is node independent and an example reconstruction achieves error 0.01.The empirical errors averaged over 1,000 realizations validate the analysis predicting node-independent quality for this noise model.
  • Real-world signal: For the approximately bandwidth-4 economic signal, four-observation reconstruction errors span 5 orders of magnitude across sampling nodes, usually falling between 10^-3 and 10^-1.The signal’s four-frequency approximation has reconstruction error 3.5×10^-3 relative to the original signal energy.
  • Real-world signal: Aggregation sampling outperforms selection sampling on minimum and median reconstruction error, while successive shifts reduce median error from 4.2 with none to 0.03 after one shift.Aggregation observes one node after successive graph shifts; selection observes four different nodes, and broader space-shift strategies are also evaluated.
Loading 1504.04687v2…