PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Least Mean Squares Estimation of Graph Signals

Paolo Di Lorenzo, Sergio Barbarossa, Paolo Banelli, Stefania Sardellitti

arXiv:1602.05703v3cs.LGcs.SYeess.SY

TL;DR

Recovering and tracking band-limited graph signals from partial observations requires suitable sampling strategies. The paper develops adaptive LMS estimation and sampling, including support tracking when bandwidth is unknown; numerical results illustrate the analysis and a sample-complexity versus mean-square-performance tradeoff.

  • Problem

    Graph sampling aims to recover band-limited or approximately band-limited signals from a subset of samples, but recovery can be ill-conditioned depending on sample locations.

    Source: §I · p. 1

  • Method

    The paper uses adaptive LMS estimation from partial noisy observations and, when bandwidth is unknown, estimates frequency support online while adapting the sampling strategy.

    Source: §I · p. 2, §III · p. 3, §IV · p. 9

  • Results

    Numerical results confirm the analysis: Max-Det outperforms Min-MSD at low sample counts, while Min-MSD outperforms the other strategies when |S| exceeds |F|=10.

    Source: §I · p. 2, E. Numerical Results · p. 8

  • Takeaways & Limitations

    The cartography application illustrates a tradeoff between the number of samples used for processing and mean-square performance.

    Source: §I · p. 2, §VI · p. 13

    The Lasso thresholding approach introduces bias that can deteriorate performance when the graph signal is not sufficiently sparse, such as at large bandwidth.

    Source: §IV · p. 9

Abstract

from arXiv · show

The aim of this paper is to propose a least mean squares (LMS) strategy for adaptive estimation of signals defined over graphs. Assuming the graph signal to be band-limited, over a known bandwidth, the method enables reconstruction, with guaranteed performance in terms of mean-square error, and tracking from a limited number of observations over a subset of vertices. A detailed mean square analysis provides the performance of the proposed method, and leads to several insights for designing useful sampling strategies for graph signals. Numerical results validate our theoretical findings, and illustrate the performance of the proposed method. Furthermore, to cope with the case where the bandwidth is not known beforehand, we propose a method that performs a sparse online estimation of the signal support in the (graph) frequency domain, which enables online adaptation of the graph sampling strategy. Finally, we apply the proposed method to build the power spatial density cartography of a given operational region in a cognitive network environment.

I. INTRODUCTION

Graph sampling seeks to recover band-limited graph signals from partial observations, but sample placement can make recovery ill-conditioned. This paper develops adaptive LMS estimation and sampling strategies, including an approach for unknown bandwidth and a cognitive-network cartography application.

I. INTRODUCTION

  • Sample placement matters because graph-signal recovery from a given number of observations can become ill-conditioned.The paper motivates strategies that optimize the sampling set.Source: §I · p. 1
  • The paper proposes adaptive LMS strategies that reconstruct and track band-limited graph signals from limited observations, with sampling sets that may vary over time.A mean-square analysis connects sampling strategy to reconstruction, stability, and error performance.Source: §I · p. 2
  • For unknown bandwidth, an LMS method estimates and tracks frequency support while adapting the graph sampling strategy.The paper also illustrates tracking on time-varying graph signals.Source: §I · p. 2
  • In cognitive-network power cartography, the signal is smooth but not perfectly band-limited, so partial-sample recovery is affected by aliasing.The paper reports a tradeoff between sample-count complexity and mean-square performance.Source: §I · p. 2

II. GRAPH SIGNAL PROCESSING TOOLS

The paper represents graph signals through graph-frequency components and uses their support to describe bandwidth. It also defines vertex and frequency localization and states when a signal can be perfectly localized in both domains.

II. GRAPH SIGNAL PROCESSING TOOLS

  • For an undirected graph, the Laplacian is symmetric positive semidefinite, and its eigenvectors are suited to representing clusters.The eigenvectors minimize the graph total-variation norm described in the passage.Source: §II · p. 2
  • A graph signal can have a compact representation when its graph-frequency vector is sparse or approximately sparse, as with signals smooth within clusters.The signal may vary across clusters, while its nonzero spectral coefficients correspond to the clusters.Source: §II · p. 2
  • The paper follows a Laplacian-based Graph Fourier Transform for undirected graphs and defines bandwidth as the size of the nonzero frequency support.The theory could be extended to directed graphs with minor modifications.Source: §II · p. 2
  • The Paley-Wiener space comprises signals whose GFT is supported on a frequency set, while vertex and frequency projectors express localization on their respective subsets.A signal is perfectly localized in both domains if and only if BDB (or DBD) has eigenvalue one.Source: §II · p. 3

III. LMS ESTIMATION OF GRAPH SIGNALS

The proposed graph LMS method estimates a band-limited signal from noisy, streaming observations on a selected vertex subset. Its recursion uses instantaneous data and alternates vertex- and frequency-domain projections.

III. LMS ESTIMATION OF GRAPH SIGNALS

  • The observation model uses noisy partial samples of a signal assumed to be band-limited to a known frequency set.The sampling operator selects the observed vertices, allowing the designer to reduce computational and memory burden while retaining theoretical performance guarantees.Source: §III · p. 3
  • With a sufficiently small step size, LMS converges in the mean to the true signal and has bounded mean-square error, while sampling-set choice affects reconstruction and stability.The optimal estimate minimizes mean-squared error subject to the frequency-band limitation.Source: §III · p. 3
  • The graph LMS recursion uses instantaneous observations rather than requiring signal statistics that may be unavailable or time-varying.It alternates orthogonal projections onto the sampled vertex set and the known frequency set.Source: §III · p. 4

A. Reconstruction Properties

Unique reconstruction of any band-limited signal from samples on a vertex set holds exactly when the stated sampling condition is satisfied. A sufficient sample count alone does not ensure recovery; graph topology and sample placement also matter.

A. Reconstruction Properties

  • Unique recovery requires that no nonzero signal be both band-limited to F and perfectly localized on the sampled set S.The theorem states this as a necessary and sufficient condition for reconstruction from samples in S.Source: A. Reconstruction Properties · p. 4
  • If the stated sufficient condition holds, I − BDB is invertible and the signal can be recovered from the corresponding expression.The theorem's condition excludes a nontrivial signal that vanishes on the selected samples.Source: A. Reconstruction Properties · p. 4
  • Having |S| ≥ |F| is necessary but not sufficient, because DB may lose rank or become ill-conditioned depending on graph topology and sample placement.Thus, sampling locations affect the reconstruction algorithm's performance.Source: A. Reconstruction Properties · p. 4

B. Mean-Square Analysis

The mean-square analysis tracks the LMS error in the graph-frequency domain and gives conditions for stability and finite steady-state error. It also yields a step-size bound for sufficiently small stepsizes.

B. Mean-Square Analysis

  • The error recursion can be transformed to graph-frequency coordinates and restricted to the signal’s band-limited support for mean-square analysis.The transformed error on that support is equivalent to the vertex-domain error from a mean-square perspective.Source: B. Mean-Square Analysis · p. 4

F DUF

  • For bounded initial conditions, the LMS strategy converges in mean-square error when the sampling operator and step-size satisfy the stated reconstruction and stability conditions.Stability requires the sampling matrix to have full rank and the step-size to satisfy the bound in (23).Source: F DUF · p. 5
  • When the recursion matrix Q is stable, the weighted squared error converges to a finite steady-state value.The initial-condition term vanishes asymptotically, while the remaining matrix geometric series converges.Source: F DUF · p. 5
  • For sufficiently small step-sizes, the upper bound on the steady-state error is at most µc/ν when 0 < µ < ν/δ^2.Here δ and ν are the maximum and minimum eigenvalues, respectively, of U_F^H D U_F.Source: F DUF · p. 5

C. Steady-State Performance

The steady-state analysis uses a general weighted-error expression to derive performance metrics. Selecting the weighting appropriately yields the steady-state MSD, while a separate selection evaluates error at an individual vertex.

C. Steady-State Performance

  • Expression (30) yields performance metrics by selecting the free weighting parameter ϕ, including the steady-state mean square deviation.The steady-state MSD follows by choosing ϕ = (I − Q)^−1 vec(I).Source: C. Steady-State Performance · p. 5
  • A different weighting selection evaluates the mean square deviation for the signal value associated with a particular vertex.The passage introduces the k-th vertex as the target of this vertex-specific metric.Source: C. Steady-State Performance · pp. 5–6
  • The theoretical performance expressions are compared with numerical simulations to assess their validity.The comparison is reported at each graph vertex.Source: C. Steady-State Performance · p. 6

D. Sampling Strategies

The section develops greedy sampling strategies because exhaustive selection over vertex combinations becomes intractable. The criteria target minimum MSD or surrogates based on determinant and minimum eigenvalue.

D. Sampling Strategies

  • Min-MSD greedily adds samples that produce the largest reduction in MSD, using a pseudoinverse before the sample count reaches the bandwidth.The full search over sampling sets is intractable even for moderately sized graphs.Source: D. Sampling Strategies · p. 6
  • The sampling set should account for reconstruction, algorithm stability, and desired mean-square error, while also considering where—not only how many—vertices are sampled.The proposed greedy algorithms are sub-optimal approaches to the sampling-set selection problem.Source: D. Sampling Strategies · p. 6

F DUF

  • Max-Det greedily selects rows to maximize the pseudo-determinant of U_F^H D U_F, a surrogate for reducing MSD by moving its eigenvalues away from one.The selected rows are chosen to span a large-volume basis; the pseudo-determinant becomes the determinant when |S| ≥ |F|.Source: F DUF · p. 6
  • Max-λmin uses the same greedy sampling idea but maximizes the minimum nonzero eigenvalue of U_F^H D U_F as a surrogate criterion.The method is related to the batch reconstruction sampling method in.Source: F DUF · p. 7

E. Numerical Results

The simulations support the theoretical MSD expressions and show that sampling strategy and graph mismatch affect performance. Sample placement matters especially at low sample counts, while removing different graph links produces different levels of degradation.

E. Numerical Results

  • The theoretical MSD expressions match simulation results at each graph vertex.The simulations average squared error after convergence over 200 independent runs.Source: Figure 2 · p. 7, E. Numerical Results · p. 7
  • Increasing the number of samples improves the LMS learning rate when step-sizes are tuned to give the same steady-state MSD.The transient MSD comparison uses Max-Det sampling and averages results over 200 independent simulations.Source: E. Numerical Results · p. 7, Figure 3 · p. 8
  • At low sample counts, Max-Det outperforms Max-λmin and Min-MSD, while Min-MSD outperforms the alternatives once |S| exceeds |F| = 10.Random sampling performs poorly, especially with few samples; the Min-MSD advantage at larger counts reflects its use of graph topology and observation-noise distribution.Source: E. Numerical Results · pp. 7–8, Figure 4 · p. 8
  • Removing different links produces very different transient-MSD performance: Link 1 matches the ideal case, while Links 2–4 cause progressively greater losses.The authors relate the losses to how link removal changes the benchmark graph’s Laplacian eigenvectors.Source: Figure 5 · p. 8, E. Numerical Results · pp. 8–9

IV. LMS ESTIMATION WITH ADAPTIVE GRAPH SAMPLING

The adaptive method estimates an unknown, time-varying graph-frequency support from streaming observations and uses it to update the sampling strategy. In simulations, hard thresholding gives the best steady-state NMSD among the tested functions while matching the sample count to the signal bandwidth.

IV. LMS ESTIMATION WITH ADAPTIVE GRAPH SAMPLING

  • The adaptive algorithm alternates sparse GFT estimation with sampling-operator selection, using the estimated support to choose a sampling strategy.It uses an online ISTA-style update with a thresholding function, then updates the sampling operator based on the estimated support.Source: §IV · p. 9
  • Lasso thresholding can degrade performance when the graph signal is not sufficiently sparse, whereas hard thresholding removes bias on large components.The paper also notes residual bias at large values for Garotte thresholding.Source: §IV · pp. 9–10

Numerical Results

  • Hard thresholding achieves the best steady-state NMSD at the same learning rate; Garotte is slightly worse, while Lasso can perform poorly by overestimating bandwidth.The comparison uses three thresholding functions; the reported sample-selection examples use hard thresholding.Source: Figure 6 · p. 10, Numerical Results · p. 11
  • Hard-thresholding sampling selects as many vertices as the current estimated bandwidth and provides good reconstruction in the illustrated adaptive sequence.The sampling examples are shown at iterations 80, 180, and 280.Source: Figure 8 · p. 10, Figure 9 · p. 10, Figure 10 · p. 10

V. APPLICATION TO POWER SPATIAL DENSITY ESTIMATION IN COGNITIVE NETWORKS

The section applies graph-LMS estimation to build and track power spatial density maps in a cognitive-network scenario using measurements from a subset of radio access points. Simulations show improved steady-state and tracking performance with more samples and bandwidth, at increased computational complexity.

V. APPLICATION TO POWER SPATIAL DENSITY ESTIMATION IN COGNITIVE NETWORKS

  • The cartography illustration depicts primary-user power distribution, access-point deployment, graph topology, and the resulting graph signal.Source: Figure 11 · p. 11
  • The numerical example randomly deploys 100 RAPs to map power from two active primary users emitting 1 Watt each, under free-space path loss; each energy detector estimates received signals from 100 samples with additive white Gaussian noise of variance σ².Source: §V · pp. 11–12
  • The steady-state NMSD improves as sample count and processing bandwidth increase, with a threshold-like change when the number of samples exceeds the bandwidth size.For fewer samples than frequencies, NMSD is large; above that threshold, it becomes lower and stable.Source: Figure 12 · p. 12, §V · p. 12
  • Although the cartography signal is smooth rather than perfectly band-limited, most of its energy lies at low frequencies, so enough observations and low frequencies can yield satisfactory reconstruction.Sampling such a signal inevitably introduces aliasing.Source: §V · p. 12
  • The proposed method tracks changes in primary-user activity, and its steady-state performance improves with more samples and processing bandwidth.The simulation switches between one active user, two active users, and then only the second user.Source: Figure 13 · p. 12, §V · p. 12
  • Higher bandwidth and the consequent larger sample count improve mean-square performance at the cost of greater computational complexity.The reported results describe a trade-off between the number of samples used and mean-square performance.Source: §V · p. 12

VI. CONCLUSIONS

The conclusions summarize graph-LMS strategies for reconstructing and tracking band-limited graph signals from properly sampled subsets of vertices. The analysis links sampling strategy to reconstruction, stability, and mean-square error, while the proposed methods and application illustrate a complexity–performance trade-off.

VI. CONCLUSIONS

  • Under a band-limited assumption, graph-LMS strategies reconstruct signals from limited observations sampled from a subset of vertices.Source: §VI · p. 12
  • Mean-square analysis connects sampling strategy with reconstruction capability, stability, and mean-square error, and yields sampling strategies for adaptive estimation.Source: §VI · p. 12
  • An LMS method with adaptive graph sampling estimates and tracks frequency-domain signal support while adapting the sampling strategy for time-varying scenarios.Source: §VI · p. 12
  • The proposed strategies illustrate a trade-off between computational complexity and mean-square performance.Source: §VI · pp. 12–13
  • The authors expect these tools to support proactive sensing in cyber-physical systems using data-driven sampling that checks only a limited number of nodes.Source: §VI · p. 13
Loading 1602.05703v3…