PaperlayerView exact revision on arXiv

Source-linked AI summary

Nomographic Functions: Efficient Computation in Clustered Gaussian Sensor Networks

Mario Goldenbaum, Holger Boche, Sławomir Stańczak

arXiv:1310.7123v2cs.ITmath.IT

TL;DR

The paper addresses reliable function computation in clustered Gaussian sensor networks without first reconstructing individual readings. It combines pre/post-processing with nested lattice coding to protect sums of pre-processed readings. Nomographic functions can be computed faster than with separation, while arbitrary continuous functions require successive computations at reduced rates.

  • Problem

    In clustered Gaussian sensor networks, fusion centers need reliable function values rather than reconstructed individual sensor readings, but channel noise and interference complicate sum-based computation.

    Source: §I · p. 1, 1) Nomographic Functions · p. 9

  • Method

    The scheme pre-processes sensor readings, protects their sum with nested lattice codes, and applies post-processing; arbitrary continuous targets are handled through successive nomographic computations.

    Source: §I · p. 1, §VI · p. 10

  • Results

    Nomographic functions with continuous pre- and post-processing can be computed significantly faster than with separation, while arbitrary continuous functions incur a rate reduction by a factor of 2N + 1.

    Source: C. Discussion of the Results · p. 10

  • Takeaways & Limitations

    The approach extends computation from nomographic functions to every continuous function through successive steps, with lower decoding complexity and less coordination burden among its stated advantages.

    Source: §VI · p. 10

    Computing arbitrary continuous functions requires successive nomographic computations, reducing achievable computation rates.

    Source: §VI · p. 10

Abstract

from arXiv · show

In this paper, a clustered wireless sensor network is considered that is modeled as a set of coupled Gaussian multiple-access channels. The objective of the network is not to reconstruct individual sensor readings at designated fusion centers but rather to reliably compute some functions thereof. Our particular attention is on real-valued functions that can be represented as a post-processed sum of pre-processed sensor readings. Such functions are called nomographic functions and their special structure permits the utilization of the interference property of the Gaussian multiple-access channel to reliably compute many linear and nonlinear functions at significantly higher rates than those achievable with standard schemes that combat interference. Motivated by this observation, a computation scheme is proposed that combines a suitable data pre- and post-processing strategy with a nested lattice code designed to protect the sum of pre-processed sensor readings against the channel noise. After analyzing its computation rate performance, it is shown that at the cost of a reduced rate, the scheme can be extended to compute every continuous function of the sensor readings in a finite succession of steps, where in each step a different nomographic function is computed. This demonstrates the fundamental role of nomographic representations.

I. INTRODUCTION

The paper targets reliable function computation at fusion centers rather than reconstruction of individual sensor readings. It proposes a digital approach that uses pre/post-processing and lattice coding to protect sums over clustered Gaussian channels.

A. Related Work and Paper Organization

  • Interference-aware computation can outperform separation for linear functions, while pre/post-processing can match nonlinear functions to channel superposition, with nomographic functions characterized in.Separation reconstructs readings individually before computing the function.Source: §I · p. 1

I. INTRODUCTION

  • The digital scheme quantizes pre-processed readings and uses nested lattice codes to protect their sum against Gaussian noise before post-processing at the fusion center.It is presented for reliable computation of nomographic functions in clustered Gaussian sensor networks.Source: §I · p. 1
  • For nomographic functions, the proposed approach achieves rates unavailable to separation-based methods and can extend to every continuous function by computing multiple nomographic functions successively.The introduction also identifies universality, lower decoding complexity, reduced coordination burden, and support for maximum decoding error probabilities as scheme properties.Source: §I · p. 2

II. NETWORK MODEL & PROBLEM STATEMENT

  • The paper seeks to compute each cluster’s desired continuous function at its fusion center, despite shared nodes and Gaussian noise corrupting channel sums.Its response combines adapted pre/post-processing, lattice coding for noise protection, and universality to address inter-cluster interference.Source: §II · pp. 2–3

III. NOMOGRAPHIC FUNCTIONS

Nomographic functions are suited to distributed computation because their inner sums match channel superposition. The section relates their scope to continuous-function representations and explains how the network applies pre- and post-processing.

III. NOMOGRAPHIC FUNCTIONS

  • A structural match between a function and channel superposition is needed to benefit from signal interactions; nomographic functions provide such a class.This match motivates using channel superposition for network computation.Source: §III · p. 3
  • Without continuity restrictions, every function is nomographic, but continuous pre- and post-processing restricts the class to a nowhere-dense subset of continuous functions.The section denotes the unrestricted class by N(E^N) and the continuous-processing class by N0(E^N).Source: §III · p. 3
  • Every continuous multivariate function can be represented using at most 2N + 1 continuous nomographic functions, and that number cannot be reduced.The component post-processing functions may depend on the target function, whereas the pre-processing functions do not.Source: §III · p. 3
  • Each node uses pre-processing functions independent of the desired function, while each fusion center adds constants, applies its post-processing functions, and sums intermediate results.This independence means pre-processing need not be updated when desired functions change, a property termed universality.Source: §III · pp. 3–4

IV. RELIABLE COMPUTATION OF NOMOGRAPHIC FUNCTIONS OVER THE GAUSSIAN MAC

The section motivates reliable computation of nomographic functions by the match between their inner sums and Gaussian-channel superposition. It defines computation codes and focuses first on a single cluster before extending to multiple clusters.

IV. RELIABLE COMPUTATION OF NOMOGRAPHIC FUNCTIONS OVER THE GAUSSIAN MAC

  • Nomographic functions’ inner sums match the Gaussian multiple-access channel’s superposition, motivating reliable coding to handle additive noise.The section introduces computation codes as a formal framework for this task.Source: §IV · p. 4
  • An (f, T, n) computation code maps T sensor readings per node to n channel inputs and decodes n outputs into T estimates of the desired function values.Its performance is expressed as achievable function values per channel use within a fixed accuracy.Source: §IV · p. 4
  • The proposed code is first developed for a fixed continuous nomographic function in a single cluster, with the multiple-cluster extension deferred to a later subsection.The encoders and decoder are decomposed into components to respect the function’s nomographic structure.Source: §IV · p. 4

A. Data Pre- and Post-Processing

The section turns pre-processed sensor readings into finite messages and has the fusion center recover an approximation of the desired function from sums computed over the channel. The quantization precision and modulo-sum range govern the approximation and the processing path.

A. Data Pre- and Post-Processing

  • Finite channel capacity makes quantization of the real-valued pre-processed readings necessary before transmission.Their ranges are compact intervals, and the union of those ranges is bounded in absolute value by πmax.Source: A. Data Pre- and Post-Processing · p. 4
  • Each node forms a length-b binary representation of its quantized pre-processed reading and uses a source encoder to form a length-k message over Zp.The same quantizer is used at each node; p is assumed prime.Source: A. Data Pre- and Post-Processing · pp. 4–5
  • The modulo-p sum can provide the needed inner sum when p is sufficiently large to avoid wraparound.The fusion center first needs a reliable estimate of each inner sum.Source: A. Data Pre- and Post-Processing · p. 5
  • The fusion center recovers the desired function by decomposing the modulo-p sum into binary-representation sums, inverse-quantizing the digits, and applying ψ.This produces an approximation of the desired function.Source: A. Data Pre- and Post-Processing · p. 5
  • The quantization parameter b affects accuracy, and its relationship to a specified ε is given in Lemma 3.Shifting the pre-processed values by πmax makes them nonnegative without loss of generality.Source: A. Data Pre- and Post-Processing · pp. 4–5

B. Nested Lattice Coding

Nested lattice codes provide structure for protecting the modulo sum against Gaussian noise. Their linearity preserves sums modulo the shaping lattice, while the lattice properties support channel coding and shaping.

B. Nested Lattice Coding

  • Nested lattice codes are used to protect the modulo sum against Gaussian noise, and their key structural property is closure of sums modulo the shaping lattice.A sum of lattice codewords modulo the shaping lattice is itself a codeword.Source: 1) Basic Facts and Definitions · pp. 5–6
  • A shaping lattice Λs nested in a coding lattice Λc defines the two Voronoi regions Vs and Vc shown for the hexagonal-lattice example.The shaping and coding lattices are identified by their respective fundamental Voronoi regions.Source: 1) Basic Facts and Definitions · p. 6, Figure 3 · p. 6
  • The cited lattice sequence is simultaneously good for AWGN channel coding and shaping, while the coding-lattice sequence is good for AWGN channel coding.The passage defines channel goodness through vanishing probability of noise outside the Voronoi region under the stated volume condition, and shaping goodness through normalized second moment.Source: 1) Basic Facts and Definitions · p. 6

2) Channel Encoding:

The channel encoder uses a shared nested lattice code to protect the modulo sum, with its shaping lattice scaled to meet the transmit power constraint.

2) Channel Encoding:

  • Each sensor uses the same n-dimensional nested lattice code to protect the modulo-p sum against Gaussian receiver noise.The code is based on a nested lattice pair.Source: 2) Channel Encoding · p. 6
  • Scaling the shaping lattice so its second moment equals P makes each codeword meet the average power constraint.The encoder maps each message wi to a length-n lattice codeword.Source: 2) Channel Encoding · p. 6
  • The passage states that the resulting message rate is measured in bits per channel use and refers to its expression as (24).Source: 2) Channel Encoding · p. 6

3) Channel Decoding:

The fusion center decodes the modulo sum using nearest-neighbor lattice decoding, and the analysis relates decoding error and quantization precision to achievable computation rates.

3) Channel Decoding:

  • Nearest-neighbor decoding quantizes the receive vector to the coding lattice, reduces it to the shaping lattice, and inverts the channel encoder.The resulting lattice point is a valid codeword; the received sum is treated as a single codeword corrupted by Gaussian noise.Source: 3) Channel Decoding · pp. 6–7

4) Decoding Error Probability:

  • The decoding-error bound is effectively a maximum error probability, which must be small for every codeword because no sensor-reading distribution is assumed.The passages attribute the bound's independence from the correct sum to coding-lattice symmetry.Source: 4) Decoding Error Probability · p. 7

V. ACHIEVABLE COMPUTATION RATES

  • With a sufficiently large quantizer parameter b, the desired functions can be uniformly approximated to arbitrary precision ε.Source: §V · p. 7
  • The smallest bit count b0 needed for accuracy ε can depend on the number of nodes, a dependence shared by schemes that quantize multivariate-function arguments.Source: §V · p. 7

A. The Single Cluster Case

For a single Gaussian multiple-access cluster, Theorem 5 gives an achievable computation rate for nomographic functions. The section compares rates across arithmetic mean, geometric mean, and Euclidean norm examples and against separation-based computation.

1) Nomographic Functions:

  • For any f ∈ N0(E^N) and desired accuracy ε > 0, Theorem 5 states that there is an achievable computation rate for f and ε, with b0(f, ε) specified as in Lemma 3.Source: 1) Nomographic Functions · p. 7
  • At P/σ²_Z = 15 dB, the arithmetic mean is computed about 1.3 times faster than the geometric mean and 2 times faster than the Euclidean norm.Figure 4 plots the achievable rates for these examples with N = 5 and ε = 10^-3.Source: 1) Nomographic Functions · p. 8, Figure 4 · p. 8
  • The scheme computes many linear and nonlinear functions at rates significantly higher than every rate achievable with separation-based computation.The separation approach decodes all quantized sensor readings individually before computing the function.Source: 1) Nomographic Functions · p. 8
  • As P/σ²_Z approaches infinity, the achievable-rate expression approaches the normalized single-user AWGN capacity; attainability of that bound at finite P/σ²_Z is unknown.The finite-power question is stated as unresolved.Source: 1) Nomographic Functions · p. 8
  • The logarithmic denominator term in the rate expressions penalizes avoiding wraparounds in the modulo-p sum.The remark identifies this term as the cost of avoiding wraparounds.Source: 1) Nomographic Functions · p. 8

2) Kolmogorov’s Superpositions:

Kolmogorov’s superpositions extend computation beyond the nowhere-dense class of continuous nomographic functions. In clustered networks, non-universal preprocessing can require time-division coordination, while the achievable rate is constrained by cluster overlap and power limits.

2) Kolmogorov’s Superpositions:

  • Every continuous function of N variables can be composed of 2N + 1 elements from N0(EN), although N0(EN) is nowhere dense among continuous functions.Theorem 6 gives an achievable computation rate for the resulting function at a desired accuracy ε.Source: 2) Kolmogorov’s Superpositions · p. 8
  • Theorem 6 provides an achievable computation rate for any continuous target function f at desired accuracy ε.The supplied passages state the rate result but do not provide its full expression.Source: 2) Kolmogorov’s Superpositions · p. 8

1) Nomographic Functions:

  • Overlapping clusters require time-division when adjacent fusion centers need different nomographic functions, because continuous preprocessing cannot be universal.The average computation rate is reduced by a factor of L; the clusters have equal rates, and more clever time-sharing cannot increase rates when all clusters overlap.Source: 1) Nomographic Functions · p. 9

2) Kolmogorov’s Superpositions:

Universal preprocessing lets clusters compute individual Kolmogorov superpositions without coordination, while computing arbitrary continuous functions requires successive nomographic computations and reduced rates. The discussion also identifies lower decoding complexity and an equal-channel-gain assumption as practical advantages and a scope boundary.

2) Kolmogorov’s Superpositions:

C. Discussion of the Results

  • For arbitrary continuous functions, computation rates scale down by 2N + 1; for individual nomographic functions in multiple clusters, they are reduced by L.Individual Kolmogorov superpositions can be computed at the Theorem 6 rate regardless of cluster coupling.Source: C. Discussion of the Results · p. 10, §VI · p. 10
  • Fusion centers compute only one-variable functions, which can be less demanding than computing the desired multivariate function from all raw readings.For continuous nomographic functions, decoding complexity is essentially that of a single-user lattice decoder and is |Cℓ|-fold less than separation-based decoding.Source: C. Discussion of the Results · p. 10

VI. CONCLUSION

  • For arbitrary continuous functions, successive nomographic computations may yield rates below standard multiple-access schemes, while offering lower decoding complexity and less coordination burden.The paper presents these as additional advantages for sensor-network applications.Source: §VI · p. 10
  • The proposed approach assumes unit channel gains; fading with overlapping clusters can produce differing gains that may harm computation rates.The paper leaves appropriate handling of this case to future work.Source: §VI · pp. 10–11

APPENDIX

The appendices establish the accuracy and rate claims by bounding quantization error and showing that lattice-based computation can achieve the stated rate with vanishing error probability.

A. Proof of Lemma 3

  • A sufficiently large b0 makes the quantization error smaller than ε across clusters and preprocessing components.The proof uses uniform continuity on compact ranges.Source: A. Proof of Lemma 3 · p. 11

B. Proof of Theorem 5

  • Theorem 5’s proof chooses τ to prevent message-sum wraparound and shows that estimation error vanishes exponentially at an admissible rate.The resulting function values are computed within accuracy ε with high probability.Source: B. Proof of Theorem 5 · pp. 11–12

C. Proof of Theorem 6

The proof obtains the rate for Kolmogorov superpositions by computing their nomographic components successively and bounding the total decoding error.

C. Proof of Theorem 6

  • Theorem 6 follows by computing the 2N + 1 nomographic components successively and summing their decoding error probabilities.Each component’s error probability vanishes exponentially when its rate satisfies (37).Source: C. Proof of Theorem 6 · p. 12
Loading 1310.7123v2…