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

I. INTRODUCTION

• The receiver must estimate the desired function from a noisy superposition, making preservation of task-relevant information the central encoder-and-decoder challenge.Each transmitter maps its local observation through an encoder to a complex symbol in one channel use.Source: §I · p. 2
• For empirical variance with K ≥4, exact computation requires both real dimensions of the complex aggregate.A single real aggregate with continuous processing cannot represent every continuous multivariate function.Source: §I · p. 2
• For continuous inputs and functions of two additive statistics, exact noiseless recovery can force a common affine encoder structure, reducing design to finitely many complex coefficients.The encoders are subject to pointwise peak-power constraints, and the computation uses a single complex channel use.Source: §I · p. 3
• The paper extends ChannelComp’s distance-based principle to continuous domains by maximizing received-signal separation relative to differences in the desired function value.The resulting robustness design is an exact convex program, and a decoder attains the minimum uniform noise-amplification constant.Source: §I · p. 3

A. Contributions

• For K ≥4 and the receiver postprocessing class specified in Theorem 1, exact noiseless computation forces every continuous encoder collection into a common affine structure preserving both statistics.The characterization requires neither continuity nor differentiability of the decoder.Source: A. Contributions · p. 3
• Robustness maximization over the characterized coefficients is an exact convex semi-infinite program, with no relaxation gap and global optimality over continuous peak-feasible encoders.A decoder attains the smallest uniform noise-amplification constant; the paper also gives closed-form quadratic and quartic designs and numerically certifies a near-optimal exponential design.Source: A. Contributions · p. 3
• Under mild regularity conditions, Proposition 3 characterizes the minimum leading average-MSE coefficient for a fixed encoder, and Theorem 3’s decoder attains it across regular moment distributions.Theorem 4 establishes the corresponding minimax limit for worst-case MSE and optimizes it over the identifiable encoder family.Source: A. Contributions · pp. 3–4
• Uniform robustness controls error for every input and noise realization, whereas average Gaussian MSE weights local sensitivity by the input distribution, creating a design tradeoff.Prior-aware tuning can reduce average MSE at the expense of uniform robustness.Source: A. Contributions · p. 4

B. Related Work

• Analog over-the-air schemes extend additive processing to nonlinear nomographic functions, while general continuous functions often require multiple aggregates, approximation, or multiple subcarriers.Examples include successive aggregation stages, monotone postprocessing, and learned vector representations.Source: B. Related Work · p. 4
• For finite alphabets, digital and algebraic approaches compute symmetric functions or distinguish target outputs through received sums, including ChannelComp.Other approaches recover histograms or use interactive and one-bit aggregation.Source: B. Related Work · p. 4
• This work instead treats continuous real-valued inputs and functions of two additive statistics, such as empirical variance, under peak constraints in one complex channel use.Exact recovery can force a common finite-dimensional encoder family, reducing the continuous encoder design problem.Source: B. Related Work · p. 4
• The paper adapts ChannelComp’s distance-based design principle [7] to continuous domains, maximizing received-signal separation relative to changes in the desired function value to control noisy estimation error.Source: B. Related Work · p. 5

C. Paper Organization

• After defining the model and desired functions, the paper develops encoder characterization and robust design, proves decoding guarantees including Gaussian limits, presents examples and numerical evaluations, and concludes.Technical proofs are deferred to the appendices.Source: C. Paper Organization · p. 5

D. Notation

• A complex symbol is represented by its in-phase and quadrature components as a real vector.The notation also uses bold symbols for real vectors.Source: D. Notation · p. 5
• For C1(I), derivatives extend continuously and finitely to both endpoints, where they are one-sided.Source: D. Notation · p. 5
• The text defines conventions for Euclidean and Frobenius norms and for real symmetric and positive-semidefinite matrices.The spectral matrix norm is included among the uses of ∥·∥2.Source: D. Notation · p. 5

II. SYSTEM MODEL

• Each transmitter observes a real input in I and applies its own continuous encoder to send one complex symbol.The encoder collection may also be shared across transmitters.Source: §II · p. 5
• The pointwise constraint bounds each encoder’s symbol power by P for every possible local observation, independently of the input distribution.The bound applies to every transmitter.Source: §II · p. 5
• Transmissions are synchronized and phase-aligned with unit effective channel gains; in the Gaussian setting, the additive noise is circularly symmetric complex Gaussian.Channel compensation, when used, must be compatible with the peak-power constraint.Source: §II · p. 6
• The receiver applies a decoder to the received signal, using the encoders and desired function to process its in-phase and quadrature components.Source: §II · p. 6

A. Desired Functions

• Two continuous local preprocessing functions define aggregate statistics by averaging their outputs across transmitters, and two receiver functions postprocess those statistics.Source: A. Desired Functions · p. 6
• The paper calls the two aggregate statistics moments and writes the desired function in moment coordinates as f(m) = ψ1(m1) + ψ2(m2).The attainable moment set consists of moment vectors generated by admissible input vectors and need not be convex or two-dimensional.Source: A. Desired Functions · pp. 6–7
• For empirical variance with K ≥ 4, both real dimensions are necessary: continuous real-valued encoders cannot compute it exactly, even if encoders differ across nodes.Source: A. Desired Functions · p. 7

B. Identifiability and the Robustness Criterion

• Identifiability requires equal noiseless received aggregates to imply equal desired function values, making the exact noiseless decoder well defined on the aggregate set.Source: B. Identifiability and the Robustness… · p. 7
• The robustness score measures received-aggregate separation relative to desired-value differences; a smaller admissible L means greater separation and limits noise amplification.The encoder design minimizes the smallest admissible L subject to the peak-power constraint.Source: B. Identifiability and the Robustness… · p. 8
• A positive robustness score guarantees identifiability and is equivalent to a finite separation bound; its inverse square root is the minimum uniform noise-amplification constant for a decoder exact on noiseless aggregates.Source: B. Identifiability and the Robustness… · p. 8

• The design proceeds from characterizing encoders that permit identifiable computation to optimizing their coefficients under the peak-power constraint.Source: §III · p. 8

A. Encoder Characterization

• For K ≥4, if both receiver postprocessing functions are nonconstant and at least one is nonaffine, identifiable computation holds if and only if the encoders have the common affine form in (7).Each postprocessing function must be affine throughout its domain or nonaffine on every open subinterval; the theorem also assumes the local preprocessing functions are linearly independent with 1.Source: A. Encoder Characterization · pp. 8–9
• The form E_k(s) = c_k + uϕ1,k(s) + vϕ2,k(s), with u and v linearly independent over R, preserves both prescribed moments in the noiseless aggregate.The aggregate sums the local encoders, yielding the two moments in the independent complex directions u and v.Source: A. Encoder Characterization · p. 9
• Exact recovery of the requested scalar postprocessed sum nevertheless requires every admissible continuous encoder collection to yield an aggregate from which both moments are recoverable.This result requires neither differentiable encoders, decoder regularity, nor invertible local preprocessing functions.Source: A. Encoder Characterization · p. 9
• When receiver postprocessing functions have both affine and nonaffine regions, optimization within (7) remains valid, but global optimality over all continuous encoders needs a separate necessity argument.Smoothness alone does not guarantee the encoder characterization; a C∞ example permits exact computation outside (7).Source: A. Encoder Characterization · p. 9

B. Optimal Design

• Theorem 2 removes the rank constraints without a relaxation gap, yielding a program with 3K + 4 real decision variables that needs no convex moment set or differentiable receiver postprocessing.The constraints remain semi-infinite in general; they reduce to finitely many conditions for the polynomial examples, but this is not guaranteed generally.Source: B. Optimal Design · pp. 10–11

IV. DECODING

• Theorem 3 constructs a decoder attaining the minimum uniform noise-amplification constant for any attainable moment set.Its deterministic error bound holds for every noise realization, and zero noise gives exact recovery.Source: §IV · pp. 12–13
• For known noise radius rn, the minimum worst-case absolute error is ωE(2rn)/2, attained by outputting the midpoint of function values consistent with the observation and noise bound.This is a fixed-encoder guarantee for continuous desired functions.Source: §IV · p. 14

A. Gaussian Estimation Limits

• Under the stated assumptions, both high-SNR asymptotic coefficients are attainable with encoders and decoders independent of noise power.The minimax result requires MK = int MK; linear independence of the local preprocessing functions alone does not imply this condition.Source: A. Gaussian Estimation Limits · pp. 15–16
• For a fixed encoder and a regular moment distribution, the Theorem 3 decoder attains the minimum leading average-Gaussian-MSE coefficient without depending on that distribution.The Gaussian coefficient uses local sensitivity, whereas robustness uses all attainable moment vectors, so the criteria can favor different designs.Source: A. Gaussian Estimation Limits · pp. 16–17

V. EXPLICIT DESIGNS AND PERFORMANCE EVALUATION

• For strictly convex or strictly concave preprocessing and postprocessing, the robustness score for the stated encoder family depends on ψ′ only through its endpoint values.The section derives robustness-optimal quadratic and quartic encoders and numerically certifies an exponential design.Source: §V · p. 17

A. Optimal Quadratic and Quartic Encoders

• For K ≥ 4, Proposition 4 identifies shared encoders maximizing robustness for the quadratic and quartic statistics under the stated conditions on ψ.The results apply when ψ is even, continuously differentiable, and strictly convex or strictly concave.Source: A. Optimal Quadratic and Quartic… · p. 18
• The quadratic and quartic designs have robustness scores K^2P/5 and 4K^2P/85, respectively.The reported scores are for the variance and fourth-order Jensen gap, respectively.Source: A. Optimal Quadratic and Quartic… · p. 18

B. Certified Exponential Design

• For the exponential target, encoder coefficients are computed numerically because the symmetry used for the polynomial designs is unavailable.A finite design grid alone cannot guarantee peak-power feasibility between its points or certify proximity to the optimal robustness score.Source: B. Certified Exponential Design · p. 20
• The exponential design uses rational primal and dual certificates, with verification-grid refinement used to assess the certified relative optimality gap.The repaired encoder need not touch the peak-power boundary.Source: B. Certified Exponential Design · pp. 20–21

C. MSE under a Robustness Requirement

• For variance V, the study optimizes b within an encoder family shared by all transmitters, with the peak-power constraint satisfied for every 1 ≤ b < 2.Source: C. MSE under a Robustness Requirement · p. 21
• For uniform inputs, 90% robustness retention reduces the high-SNR MSE coefficient by 17.68% at K = 4 and 29.07% at K = 16, with uniform noise-amplification constant LE increasing by 5.41%.Without a retention requirement, the selected designs retain 83.91% and 60.91% of maximum robustness at K = 4 and K = 16; for endpoint-Beta inputs at K = 4, the 90% requirement is inactive because the unconstrained design retains 91.67%.Source: C. MSE under a Robustness Requirement · pp. 22–23

D. Finite-SNR Performance

• Across 72 tested combinations, robustness-optimal encoders reduce MSE by 6.12%–22.92% versus baselines, while prior-aware tuning adds 5.69%–72.01% reduction and can substantially lower robustness.For the fourth-order Jensen gap with uniform inputs and K = 16, normalized robustness falls from 0.05853 to 0.007273 under prior-aware tuning.Source: D. Finite-SNR Performance · p. 24, Table III · p. 24, Figure 6 · p. 25
• At 30 dB, endpoint-Beta inputs with K = 4 remain 3.49%–7.19% below their limiting MSE ratios, so the asymptotic coefficient alone does not capture performance at that SNR.Prior-aware tuning nevertheless yields substantial MSE reductions across moderate and high SNRs.Source: D. Finite-SNR Performance · p. 25

VI. CONCLUSIONS

• The framework characterizes when exact computation forces continuous encoders to preserve both statistics, makes robustness optimization an exact convex semi-infinite program, and provides a decoder attaining minimum uniform noise amplification.The conclusions also report that prior-aware tuning can substantially reduce average MSE at the expense of uniform robustness.Source: §VI · p. 26

A. Proof of Theorem 1

• The proof establishes necessity by locally recovering both partial moment sums, showing the aggregate depends only on those sums and establishing encoder differentiability, then deriving common coefficients across nodes.Sufficiency follows by inverting the resulting affine map.Source: A. Proof of Theorem 1 · p. 27
• For K ≥ 4, exact computation requires encoders with common moment coefficients u, v linearly independent over R, and this form also suffices.The encoded sums recover both moments, after which the receiver evaluates ψ1(m1) + ψ2(m2).Source: A. Proof of Theorem 1 · p. 31

1) Excluded Cases:

• When either ψ1 or ψ2 is constant, or both postprocessing functions are affine, simpler real encoders suffice, so the universal characterization fails.A constant f needs zero encoders; bounded preprocessing functions allow common nonzero scaling to meet any P > 0.Source: 1) Excluded Cases · p. 31

2) Counterexample with Smooth Postprocessing Functions:

• Smooth postprocessing can permit exact computation with an encoder outside the common affine form (7).The example recovers f(s) = m2 + ρ(m1 − 3/4) by preserving m2 and qav, even when qav differs from m1.Source: 2) Counterexample with Smooth… · pp. 31–32

3) Scope of the Encoder Characterization:

• For K ≥ 4, real-valued encoders cannot satisfy (7) when u and v are linearly independent; for K = 3, form (7) is sufficient, but its necessity is not established.The cited passage states that f is not Lipschitz on MK, so Theorems 1 and 2 give Λ⋆(P; f) = 0, although encoders of form (7) with linearly independent u, v permit exact noiseless computation.Source: 3) Scope of the Encoder Characterization · p. 32

B. Proof of Theorem 2

• The rank constraint can be removed without changing the optimal robustness value, and the optimum is attained; positive robustness is equivalent to Lipschitz continuity of f and forces the common affine encoder form.The Lipschitz equivalence is for f on MK, and the affine-form conclusion assumes Theorem 1’s conditions.Source: B. Proof of Theorem 2 · pp. 33–35

C. Proof of the Gradient Bounds

• When MK is compact, convex, and full-dimensional, the gradient bounds coincide; an example shows endpoint gradients can fail to capture the interior maximum.The example gives Λ(E; f) = 8, whereas endpoint gradients would predict 16.Source: C. Proof of the Gradient Bounds · pp. 35–36

A. Proof of Proposition 1

• For positive robustness, McShane extension yields a decoder with the minimum uniform noise-amplification constant, Λ(E; f)^-1/2.Any decoder satisfying the stated robustness guarantee must have Lipschitz constant at least this value.Source: A. Proof of Proposition 1 · p. 36

B. Proof of Theorem 3

• A stated construction attains LE when BC(G) = K^2/Λ(E; f).Source: B. Proof of Theorem 3 · p. 36

C. Proof of Proposition 2

• The minimax worst-case error under noise bounded by rn is ωE(2rn)/2, attained by decoding to the midpoint of consistent function values.The proof gives a matching lower bound for every decoder and a measurable midpoint decoder achieving the bound.Source: C. Proof of Proposition 2 · p. 37

PROOFS OF THE GAUSSIAN ESTIMATION LIMITS

• The Gaussian-estimation converse uses a weighted van Trees argument that requires no derivatives of the decoder.Source: Appendix C · p. 37

A. Proof of Theorem 4

• Under the stated linear-independence and gradient-spanning conditions, the optimized Gaussian-risk bound is attained by an encoder with G ≻ 0.The proof also establishes fixed-encoder achievability and converse bounds; peak-feasible coefficients form a compact set, and singular limits are excluded.Source: A. Proof of Theorem 4 · pp. 38–39

B. Proof of Proposition 3

• For a regular moment distribution and encoder with positive-definite G, an exact globally Lipschitz decoder exists, and any fixed Lipschitz decoder exact on RE achieves Jπ(G).Source: B. Proof of Proposition 3 · pp. 39–40
• The proof establishes that the encoder achieves Jπ(G) and derives an asymptotic converse, including for singular limiting Gram matrices when Qπ ≻ 0.The variational supremum equals Eπ[w^T G^-1 w]; the singular-limit argument uses a direction in ker G with positive Qπ-variance.Source: B. Proof of Proposition 3 · pp. 40–41

C. Local Sensitivity and Global Robustness

• Under the same noise normalization, Equation (13)'s leading worst-case MSE coefficient 1/(2K^2) can be strictly smaller than 1/[2Λ(E; f)]; the passage states 1/[2Λ(E; f)] ≥ 2601/(4000K^2).Source: C. Local Sensitivity and Global… · p. 42

Appendix A-C gives |f(m) − f(m′)| ≤

• For f(m) = m2 − ψ(m1), the proof constructs admissible perturbations in direction G^-1w(m) to establish sharpness of the local sensitivity bound and its vanishing-distance claim.The argument uses strict monotonicity of ψ′ and takes m1 toward the maximizing endpoint.Source: Appendix A · p. 43

1) Quadratic Encoders:

• Theorem 1 and Section V reduce both cases to a shared encoder E, with Gram quantities A = |u|², B = |v|², and C = Re(uv).Source: B. Proof of Proposition 4 · p. 44

2) Quartic Encoders:

• The quartic-encoder optimization is globally solved by a candidate whose peak constraints are active at ξ = ρ and ξ = 1.The unique ρ lies in (0, 1/3); the proof establishes global optimality using the two active convex constraints.Source: 2) Quartic Encoders · pp. 44–45

C. Certified Design

• The certified grid design yields feasible encoders with robustness at least K2ρhλh, while its discretization error is O(h2).The result applies under the stated smoothness, linear-independence, and nonconstant-function assumptions; under Theorem 1’s assumptions it certifies the optimum over continuous peak-feasible encoders.Source: C. Certified Design · pp. 45–46

D. Verified Primal and Dual Bounds

• The verified primal and dual bounds bracket λ⋆, bound the absolute and relative optimality gaps, and do not guarantee arbitrarily small gaps from sampled moment pairs.For λlo > 0, the relative loss is at most (λup − λlo)/λup; numerical certification also requires primal and dual verification errors to decrease.Source: D. Verified Primal and Dual Bounds · pp. 47–48
• The supplied proof fragment combines Lemma 1 with (40) to derive an upper bound on λ⋆, but the bound is truncated in the excerpt.Source: D. Verified Primal and Dual Bounds · p. 48

E. Projection Decoder in the Examples

• The projection decoder clips the first estimated moment to [−1, 1], leaves the second unchanged, and attains the smallest uniform noise-amplification constant for the fixed encoder collection.Its constant is L_E = Λ(E; f)^−1/2.Source: E. Projection Decoder in the Examples · p. 48

F. Moment Set and Output Range

• For p ∈ {2, 4}, the polynomial examples have variance m2 − m1^p in [0, 1], so clipping either estimated function value to [0, 1] cannot increase absolute error.The bound follows from Jensen’s inequality and |s_k| ≤ 1.Source: F. Moment Set and Output Range · p. 48
• For the variance example with K = 4, fixing m1 gives attainable m2 values throughout the interval between its minimizing and maximizing boundaries.A maximizing input vector is a vertex with at most one coordinate in (−1, 1); the other three coordinates are ±1.Source: F. Moment Set and Output Range · pp. 48–49