PaperlayerView exact revision on arXiv

Source-linked AI summary

Occupancy-Domain Over-the-Air Computation

Seyed Mohammad Azimi-Abarghouyi

arXiv:2609.11289v1cs.ITmath.IT

TL;DR

Coherent AirComp requires channel knowledge and energy-based non-coherent methods remain affected by fading, motivating an aggregate observable without channel weights. The paper develops Bernoulli occupancy and quota-based balanced occupancy computation; under ideal detection, the latter’s leading-order error does not exceed Bernoulli activation’s at any load.

  • Problem

    Energy superposition is linear only in expectation over fading, so within a coherence block realized channel gains remain random weights in the estimate.

    Source: §I · p. 1

  • Method

    The paper encodes the sum in binary resource-element occupancy, then introduces balanced occupancy computation with data-dependent quotas of random burst placements.

    Source: §IX · pp. 11–12

  • Results

    Under ideal detection, balanced occupancy computation’s leading-order error does not exceed Bernoulli activation’s at any load.

    Source: §IX · p. 12

  • Takeaways & Limitations

    Occupancy computation requires neither instantaneous nor statistical channel knowledge at the devices or server.

    Source: §IX · p. 11

    The scale-integrated bound assumes α=0 and a gain distribution fixed in advance, so it does not cover a two-phase scheme that first estimates S coarsely.

    Source: C. A lower bound for non-adaptive… · p. 5

Abstract

from arXiv · show

Over-the-air computation (AirComp) aggregates distributed data through the wireless multiple-access channel, but coherent implementations require channel state information (CSI), phase alignment, and power control, whereas non-coherent energy methods remain affected by fading. Signal superposition at the receive antenna is linear but requires coherence, and energy superposition is linear only in expectation over fading. We introduce occupancy-domain computation (ODC), whose observable is neither a received amplitude nor an energy: the sum is carried by the silence of the shared resources. With exponential Bernoulli activation, the individual silence probabilities multiply, and the server recovers the sum from the idle fraction using binary activity decisions alone, so that once an activation is detected the amplitude that produced it does not enter the estimate. We characterize the maximum-likelihood estimator, optimal load, and a scale-integrated Fisher-information bound for non-adaptive operation over unknown dynamic ranges. We then introduce balanced occupancy computation (BOC), where each device forms a data-dependent quota of random burst placements. This removes the random placement-count fluctuation of Bernoulli activation; under ideal detection, the leading-order asymptotic root-mean-square error of BOC is no larger than that of Bernoulli ODC at any load and approaches $1/\sqrt{2M}$, where $M$ is the number of resource elements, as the number of devices becomes small relative to $M$. We further analyze unknown-scale operation, finite-frame deviations, and heterogeneous detection misses. Simulations validate the theory and compare ODC/BOC with affine non-coherent energy aggregation and REED.

I. INTRODUCTION

Occupancy-domain computation replaces amplitude or energy aggregation with binary busy/idle observations, encoding the sum in resource-element silence without channel knowledge. Balanced occupancy computation fixes each device’s placement-draw quota, removing random-count fluctuation from Bernoulli activation.

I. INTRODUCTION

  • Coherent AirComp needs instantaneous CSI, while energy-based non-coherent aggregation remains affected by realized fading weights within a coherence block.The paper’s central alternative is to recover the sum from binary occupancy rather than a real- or complex-valued signal statistic.Source: §I · p. 1
  • Unlike prior occupancy uses for cardinality estimation, this work applies randomization at the encoder so occupancy depends on device values.The paper contrasts this with prior methods that apply randomization to data already held by the estimator.Source: §I · p. 2

A. Contributions

  • With exponential Bernoulli activation, independent silence probabilities multiply and their logarithm recovers the sum, without channel quantities in the encoder or estimator.Once a burst is detected, its amplitude does not enter the occupancy statistic.Source: §I · pp. 1–2, A. Contributions · p. 2, B. The occupancy identity · p. 3
  • Balanced occupancy computation fixes placement-draw quotas up to rounding, and its leading-order error does not exceed Bernoulli activation’s at any load.The paper also proposes a two-phase probe for unknown scale, a reference-group correction for heterogeneous misses, and comparisons with affine energy aggregation and REED.Source: A. Contributions · p. 2

A. System model

  • The system assumes unknown channel coefficients, no pilots or reciprocity, slot-level alignment, and thresholded busy/idle decisions for each resource element.The receiver uses the energy only to make a binary decision; it does not form an estimate of the received sample itself.Source: A. System model · p. 2

B. The occupancy identity

  • The occupancy identity holds for every finite device count, with no channel coefficients or separate dependence on the number of devices.It therefore permits an unknown, time-varying device population when the aggregate is the quantity of interest.Source: B. The occupancy identity · pp. 2–3

III. BERNOULLI ACTIVATION AND ITS SCALE LIMITATION

Bernoulli activation estimates the aggregate from the idle-resource count, which is sufficient for the sum and yields an asymptotically efficient estimator. Its best fixed-scale operating point is a load of 1.5936, while multi-gain operation addresses a range of aggregates.

A. Encoding, decoding and error expression

  • The idle count N0 is sufficient for S, and the clipped nonnegative maximum-likelihood estimator is asymptotically efficient at fixed positive load.As M grows, the estimator attains the occupancy model’s Cramér–Rao bound.Source: A. Encoding, decoding and error… · p. 3
  • λ*=1.5936 uniquely minimizes the asymptotic relative RMSE, and the corresponding idle fraction is 0.20 when α=0.The optimum gain depends on the aggregate itself; loads 0.8 and 3.2 increase error by 11% and 22%, respectively.Source: A. Encoding, decoding and error… · pp. 3–4
  • Occupancy-estimation error decreases without bound as M increases, unlike the block-fading energy schemes’ error floor from realized channel gains.The stated fading-floor contrast applies to energy-superposition schemes under block fading.Source: A. Encoding, decoding and error… · p. 4

B. Multi-gain frames

Multi-gain frames spread activation gains over a deployment range, using jointly sufficient idle counts and a constrained likelihood estimate. For non-adaptive independent-gain designs, a scale-integrated Fisher-information bound limits worst-case accuracy, and guarded geometric spacing approaches that bound.

B. Multi-gain frames

  • Equal-size gain groups with two guard groups cover [Smin,Smax], and their independent idle counts are jointly sufficient for S.The design uses geometrically spaced gains to span the deployment range.Source: B. Multi-gain frames · p. 4
  • The constrained multi-gain log-likelihood is concave, giving a unique interior MLE when it has a root and endpoint estimates otherwise.Bisection finds the root when the derivative changes sign over the allowed range.Source: B. Multi-gain frames · p. 4

C. A lower bound for non-adaptive designs

  • For a non-adaptive Bernoulli design with α = 0, every regular estimator unbiased for ln S has worst-case relative RMSE over the range at least π^-1 sqrt(6 ln D/M).A geometrically spaced multi-gain design with equal allocation approaches that bound when Q ln β = ln D + o(ln D), away from finite-range edge effects.Source: C. A lower bound for non-adaptive… · p. 4
  • The bound assumes α=0 and gains fixed in advance, so it is the most favorable false-alarm case and does not cover a two-phase scheme that first estimates S coarsely.It concerns uniform accuracy across a range, not peak accuracy at one operating point.Source: C. A lower bound for non-adaptive… · pp. 4–5
  • For D=10^3, the guarded geometric design’s coefficient is 2.049, about 14% above the non-adaptive lower bound.The factor 1.884 relative to the calibrated optimum is the cost of this particular guarded design, not a universal lower bound.Source: C. A lower bound for non-adaptive… · p. 5

IV. BALANCED OCCUPANCY COMPUTATION

Balanced occupancy computation replaces independent per-resource coin flips with data-dependent quotas and random placement draws. The resulting occupancy identity is exact, and the server estimates the aggregate from the idle-resource count.

A. Quota encoding

  • Each device draws a data-dependent quota of resource-element indices uniformly with replacement, then activates each distinct selected element.Randomized rounding makes the quota conditionally unbiased, with variance at most 1/4; repeated draws to one element require only one burst.Source: A. Quota encoding · p. 5
  • Fixing the placement-draw count up to quota rounding removes the random burst-count fluctuation of Bernoulli activation, which carries no information about the aggregate.The quota design makes occupancy indicators exchangeable but not independent because they share the pool of placement draws.Source: A. Quota encoding · p. 5

B. Exact identity and estimator

  • Conditioned on the quotas, the idle-resource count supports an exact occupancy identity for every finite K under ideal detection, independent of received amplitudes and phases.The total number of placement draws N has expectation aS and variance no greater than K/4.Source: B. Exact identity and estimator · p. 5
  • The server estimates S by counting idle resource elements and inverting their probability, with N0 sufficient for the total placement count N.The one-frame procedure thresholds each resource element, counts idle elements, and applies the estimator.Source: B. Exact identity and estimator · p. 5

C. Error expression and operating point

Under ideal detection, quota encoding removes Bernoulli activation-count variability and has no larger leading-order asymptotic RMSE at any load. Its operating point and finite-load advantage depend on the load and value profile, while overlap collisions remain a source of error.

C. Error expression and operating point

  • BOC’s operating load satisfies λ⋆ = λ0(1 + O(λ0)), with λ0 = (2K/M)^(1/3).Quota encoding removes the Bernoulli activation-count term, but overlap collisions remain; quota rounding is small in the stated example.Source: C. Error expression and operating point · pp. 5–6
  • BOC’s RMSE reduction versus Bernoulli activation is 1.76× as K/M → 0, 1.53× at K/M = 0.1, and 1.32× at K/M ≃ 1.The corresponding reductions in channel uses are 3.09×, 2.34×, and 1.75×; the asymptotic constants are an upper envelope.Source: C. Error expression and operating point · p. 6
  • At their respective optimal loads, the Bernoulli-to-BOC activity-budget ratio grows as (M/K)^(1/3), while BOC bounds each device’s activity in advance.A hard cap on nk can clip large values and bias the aggregate, a regime not analyzed here.Source: C. Error expression and operating point · p. 6
  • At every load λ > 0, BOC’s leading-order asymptotic RMSE is no larger than Bernoulli ODC’s, with a strict leading-coefficient reduction when S > 0.The comparison is at equal load and under Theorem 3’s assumptions.Source: C. Error expression and operating point · p. 6
  • BOC retains a strictly smaller leading-order error coefficient than Bernoulli activation, but the gap shrinks as max_k ax_k → 0 and decreases smoothly beyond K/M around 1.The stated validity range is K/M = O(1); when max_k ax_k ≤ 1, the quota reduces to linear Bernoulli activation.Source: C. Error expression and operating point · p. 6

D. A non-asymptotic guarantee

For ideal detection, the paper gives a finite-frame deviation bound for occupancy counting that accounts for both burst-placement randomness and quota rounding. The bound holds for every M and K, but is looser than the asymptotic expression.

D. A non-asymptotic guarantee

  • For ideal detection, the conditional deviation probability obeys P{|N0 − Mq| ≥ t | N} ≤ 2e^(−2t^2/N), where q = (1 − 1/M)^N.The theorem also gives a high-probability bound when tδ < Mq, ensuring N0 > 0.Source: D. A non-asymptotic guarantee · p. 6
  • The finite-frame bound’s two terms correspond to burst-placement randomness and quota rounding, matching the two terms in the asymptotic expression.Source: D. A non-asymptotic guarantee · p. 6
  • The bound is looser than the asymptotic expression, giving about 4.3/√M for a Gaussian 95% interval, but it holds for every M and K.The stated looseness is the usual cost of a bounded-difference argument.Source: D. A non-asymptotic guarantee · p. 6

V. SELECTING THE GAIN WITHOUT SCALE KNOWLEDGE

The paper describes gain selection without prior scale knowledge and models detection misses as thinning of activations. Gain probing can limit mismatch costs, while the erasure analysis identifies bias and assumptions that constrain the model.

V. SELECTING THE GAIN WITHOUT SCALE KNOWLEDGE

  • A two-phase design probes for S with guarded multi-gain Bernoulli activation, then uses the remaining REs for computation at a selected gain.The probe can use a few percent of the frame, and a beacon broadcasts the gain without per-device feedback, instantaneous CSI, or device identification.Source: §V · pp. 6–7
  • At K/M = 0.1, a gain mismatch by factors r = 2 and r = 1/2 increases RMSE by 6.6% and 8.7%, respectively.An alternative bisection probe takes O(log log D) stages, but is preferable only when downlink latency is small.Source: §V · pp. 6–7

A. The erasure model and its validity

  • The erasure model treats each activation as effective with probability 1 − εk, independently across REs, bursts, and devices; missed bursts are indistinguishable from non-transmission.The independent-burst assumption requires enough coherence dimensions for scattered REs to fade independently.Source: A. The erasure model and its validity · p. 7
  • Misses bias both uncorrected encoders, and BOC also incurs an explicit binomial-thinning variance term.The ideal-detection error expression is recovered as miss probabilities vanish.Source: A. The erasure model and its validity · p. 7
  • With one faded dimension per logical RE, co-activating devices’ miss events are correlated; more dimensions reduce mismatch with independent erasures but increase RMSE by √Ns for a fixed physical channel-use budget.A delay beyond the guard interval can mark a neighboring RE and bias the count.Source: A. The erasure model and its validity · p. 7

B. Pre-compensation for Bernoulli activation

Bernoulli pre-compensation can restore the ideal occupancy identity when estimated miss probabilities are accurate, but clipping and joint detection can leave bias. Quota self-normalization estimates the mean without SNR knowledge, with resource and reference-quota trade-offs.

B. Pre-compensation for Bernoulli activation

  • Bernoulli pre-compensation restores the ideal occupancy identity under the independent-erasure model when the estimated miss probability equals the true miss probability.The required estimate can come from long-term link statistics, without instantaneous CSI.Source: B. Pre-compensation for Bernoulli… · p. 7
  • If the pre-compensation probability exceeds one, clipping leaves residual bias; joint detection can also make pre-compensation over-correct.The method is most appropriate for moderate misses and operating points where the required probability remains well below one.Source: B. Pre-compensation for Bernoulli… · p. 7

C. Self-normalization for quota encoding

  • Quota self-normalization estimates the mean without SNR knowledge for arbitrary heterogeneous miss probabilities; with i.i.d. misses independent of values, its estimate is consistent as K → ∞.Recovering the sum from the mean requires K to be known.Source: C. Self-normalization for quota encoding · p. 8
  • Under ideal detection, splitting the frame equally between data and reference groups doubles RMSE relative to using all M REs for one BOC estimate.For ideal detection the smallest nonzero reference quota, n0 = 1, is optimal; with misses, an interior optimum can arise because collision and thinning terms move in opposite directions.Source: C. Self-normalization for quota encoding · p. 8
  • In the stated example, the selected reference quota is n0 = 2 at mean miss probability 0.15 and n0 = 4 at 0.30.With nonzero misses, the optimal split can shift because thinning terms depend on the two group sizes.Source: C. Self-normalization for quota encoding · p. 8

VII. EXTENSIONS

The extensions let occupancy compute nonnegative nomographic transforms and handle signed or vector-valued aggregation, with distinct resource costs and development limits.

A. Function class and signed data

  • The server computes Ψ(Σ_k g_k(x_k)) for nonnegative g_k, with accuracy governed by Theorem 1 or Theorem 3 for S_g=Σ_k g_k(x_k), covering the nomographic function class computable by analog AirComp,.Source: A. Function class and signed data · p. 8
  • Because each resource's occupancy is an OR, signed inputs use separate positive and negative RE groups and subtract their estimates.Source: A. Function class and signed data · p. 8
  • Vector aggregation is linear in dimension; random nonnegative weights can superimpose coordinates while preserving the exact identity and yielding a concave aggregate-vector likelihood, but this is not developed.Source: A. Function class and signed data · p. 8

B. Privacy

The numerical results show where balanced occupancy computation improves on Bernoulli activation, how scale uncertainty and detection misses affect estimation, and the scope of the privacy and federated-learning discussion.

B. Privacy

  • Occupancy encoding leaks less per observation than amplitude or energy schemes, but the intended anonymous-superposition setting is not a formal privacy guarantee.Adding calibrated randomization for differential privacy would add aggregation error, and the privacy–utility trade-off is not analyzed.Source: B. Privacy · p. 8

A. Theory, scale uncertainty, and population scaling

C. Federated learning

  • The proposed federated-SGD extension remains future work: it would clip gradients coordinate-wise, sketch them, and account for aggregation error in the SGD bound.The passage describes a prospective extension rather than an evaluated federated-learning result.Source: C. Federated learning · p. 9

VIII. NUMERICAL RESULTS

  • Numerical comparisons use relative RMSE, with ideal-detection experiments requiring no channel realization and detector experiments using Rayleigh fading independent across REs and devices.External baselines are non-coherent continuous-sum methods; both use statistical channel powers, unlike ODC and BOC.Source: §VIII · p. 9

A. Theory, scale uncertainty, and population scaling

  • Near their respective optima, Bernoulli activation reaches relative RMSE ≃1.24 at λ = 1.59, while BOC reaches about 0.81 at λ = 0.53.Quota encoding removes the activation-count term, shifting the optimum to a sparser frame; BOC’s advantage is greatest for K ≲ M, while the encoders converge as population approaches or exceeds frame length.Source: Figure 3 · p. 9, A. Theory, scale uncertainty, and… · pp. 9–10
  • At K/M ≃0.1, normalized RMSE improves from about 1.25 for Bernoulli activation to 0.81 for BOC, and at K/M ≃2 from 1.27 to 1.02.The simulations follow the predicted law across K/M from 0.02 to nearly 2.Source: A. Theory, scale uncertainty, and… · pp. 9–10, Figure 4 · p. 9

B. Imperfect activity detection

  • Under heterogeneous misses, uncorrected quota encoding is 14.5% low at mean miss rate 0.15 and 30% low at 0.30; self-normalization keeps residual bias within about ±1% without individual SNRs.Source: B. Imperfect activity detection · p. 10

C. Comparison with external aggregation baselines

The external comparisons find lower error for occupancy schemes than non-coherent energy baselines in the reported regimes, while calibration and detection affect the comparisons differently. The conclusions distinguish BOC’s accuracy and activity advantages from Bernoulli ODC’s simpler operation near frame-sized populations.

C. Comparison with external aggregation baselines

  • At 1024 physical channel uses, relative RMSE is 12.2% for affine NC-OAC, 4.42% for REED, 3.90% for Bernoulli ODC, and 2.55% for BOC.With ideal activity decisions, the comparison is at equal physical channel uses, not equal radiated energy; the energy baselines receive exact average channel powers.Source: C. Comparison with external… · p. 10
  • With detection at 20 dB, BOC relative RMSE is 1.78% versus REED’s 2.21% at 4096 physical channel uses; Bernoulli ODC remains above REED.Across 64, 256, 1024, and 4096 uses, BOC remains below REED; at this operating point only quota encoding yields an end-to-end margin over REED.Source: C. Comparison with external… · p. 10, Figure 8 · p. 11
  • Occupancy error falls with SNR to its logical-RE resolution floor; tuning Ns to the link budget balances detection reliability against fewer REs, while the affine NC-OAC gap grows and the REED gap saturates.The reported BOC-to-affine NC-OAC accuracy ratio grows from 4.5× at 20 dB to 6.6× at 36 dB; its ratio over REED is 1.2–1.8× from 20 to 36 dB.Source: C. Comparison with external… · p. 11
  • With 1–3 dB calibration error, BOC stays within 2.6–2.8% relative RMSE and Bernoulli ODC within 3.8–4.1%, while REED and affine NC-OAC errors rise.Calibration error leaves the occupancy curves unchanged; REED’s error rises from 3.11% to 4.14%, 6.45%, and 9.60% across the reported calibration settings.Source: Figure 9 · p. 11, C. Comparison with external… · p. 11

IX. CONCLUSIONS

  • ODC replaces amplitude or energy with binary busy/idle decisions, so fading affects it through detection success and it requires no channel knowledge.The conclusion contrasts this with coherent and energy-based aggregation, which use channel information.Source: §IX · p. 11
  • BOC fixes each device’s placement quota, removing uninformative placement-count randomness; it is more accurate and uses less transmit activity than Bernoulli ODC, which is simpler near frame-sized populations.The paper reports leading-order asymptotic dominance over Bernoulli activation at every load, plus finite-frame and finite-population deviation results.Source: §IX · pp. 11–12
  • Structured placement, multi-coordinate frames, the multi-cell case, and formal privacy guarantees remain open directions.Source: §IX · p. 12

APPENDIX A PROOF OF THEOREM 1

The appendices derive the Bernoulli estimator and its optimal load, an integrated information bound for unknown scale, and the balanced-placement error law.

APPENDIX A PROOF OF THEOREM 1

  • The idle count N0 yields the binomial MLE qhat = N0/M; the delta-method variance attains the per-frame Fisher-information bound.Clipping has exponentially small probability at fixed q in (0, 1), so it does not change the stated asymptotic second moment.Source: Appendix A · p. 12
  • The optimal load is the unique positive root of λe^λ = 2(e^λ−1), where r(λ⋆) = 1.24263.At λ = 0.8 and 3.2, √r is 1.3838 and 1.5159, increases of 11.4% and 22.0%.Source: Appendix A · p. 12

APPENDIX B PROOF OF THEOREM 2

  • Integrating information over log scale gives π^2/6 independently of the gain distribution; over a dynamic range D, the worst-case RMSE bound follows from π^2/(6 ln D).The bound uses the minimum information over the interval and the Cramér–Rao bound across M conditionally independent resource elements.Source: Appendix B · p. 12

APPENDIX C PROOF OF THEOREM 3

  • For balanced placement, pairwise idle-event dependence yields the asymptotic variance calculation; with misses, its variance term changes from e^λ−1−λ to e^λ/(1−α)−1−λ.The derivation conditions on the placement count and applies the delta method to the idle count.Source: Appendix C · p. 12

APPENDIX D PROOF OF THEOREM 4

The appendices bound finite-frame estimation deviations and analyze how heterogeneous detection misses alter the effective aggregate and quota-encoding error.

APPENDIX D PROOF OF THEOREM 4

  • Conditioned on N placements, changing one placement alters the idle count by at most one, enabling a McDiarmid bound around its mean Mq.The proof then bounds the estimator’s deviation from N on the event that the observed idle count is positive.Source: Appendix D · p. 12
  • The aggregate’s rounding error is a sum of independent zero-mean, range-one terms, so Hoeffding’s inequality and a union bound combine it with the idle-count bound.The resulting relative-error bound is stated in (18).Source: Appendix D · pp. 12–13

APPENDIX E PROOF OF LEMMA 3

  • For quota encoding, the miss analysis assumes max_k n_k = o(M); thinning placement draws approximates burst thinning when no device carries a non-vanishing fraction of the aggregate.The analysis treats a uniformly placed, independently thinned quota as uniformly placed and derives the error at the resulting effective load.Source: Appendix E · p. 13
Loading 2609.11289v1…