Conditions reveal fixed form of encoders for noise-resistant data sums

It Takes Two Moments: Rigidity and Limits of Continuous Encoders for Over-the-Air Computation

Information Theory

Summary

Combining data sent from multiple sources over a shared wireless channel is tricky because signals can mix in complicated ways and noise can cause errors. The authors studied how to design continuous encoders—ways of transforming data before sending—that guarantee perfect results when multiple devices send information simultaneously. They found that when you have four or more devices, these encoders must follow a specific, simple structure, turning a complex design problem into choosing just a few numbers. They also developed methods to measure how well these encoders resist noise and derive the best encoders for functions like finding variance in data, along with how noisy the results can get in practice.

What this means in practice

  • For wireless system designers: Create encoding schemes for multiple transmitters that guarantee exact function computation despite noise in wireless sensor networks.
  • For signal processing engineers: Implement robust decoders that minimize noise amplification when computing functions like variance from combined wireless signals.

Authors

Saeed Razavikia

Abstract

We study over-the-air computation of functions, such as empirical variance, formed by combining two separately postprocessed sums of locally transformed observations. We consider continuous encoders subject to pointwise peak-power constraints over a single use of a complex multiple-access channel. With four or more transmitters, we identify conditions under which exact noiseless recovery forces every continuous encoder collection into a common affine structure that preserves both sums, reducing infinite-dimensional encoder design to selecting a finite set of coefficients. To quantify resilience against channel noise, we introduce a robustness score that measures the separation of noiseless received aggregates relative to variations in the desired function value. Within this characterized encoder family, we formulate robustness maximization as an exact convex semi-infinite program, eliminating rank constraints without a relaxation gap, and construct a decoder that attains the minimum uniform noise-amplification constant. For several function classes, including empirical variance, we derive closed-form robustness-optimal encoders and scores. Under mild regularity conditions, we also establish sharp limits on the Gaussian mean squared error at high signal-to-noise ratios and show how using the input distribution reduces average error at the expense of uniform robustness.
View PDFOpen arXiv