🔢 mathematics

Rate-Reliability Tradeoff for Deterministic Identification over Gaussian Channels

This paper presents the first analysis of the rate-reliability tradeoff for deterministic identification over general linear Gaussian channels, demonstrating that the established theoretical insights and practical relevance from discrete-output cases extend to continuous-output systems.

Original authors: Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Needle in a Haystack" Problem

Imagine you are at a massive music festival with millions of people.

The Old Way (Shannon Transmission): You want to tell your friend, "I am wearing a red hat." To do this, you have to send a long, detailed message describing your hat, your location, and your face. If the crowd is noisy (the channel is "Gaussian" or full of static), you might need to repeat the message many times to make sure they understand. The amount of information you can send grows linearly with time. If you double the time, you double the info.
The New Way (Identification): Your friend doesn't care about your hat. They just want to know: "Are you the person I'm looking for?" They have a specific person in mind. You don't need to describe yourself; you just need to prove you are that specific person.

Surprisingly, with this "Identification" method, you can check for billions of specific people in the same amount of time it takes to describe one person in the old way. It's like finding a needle in a haystack, but you can check for a million different needles simultaneously.

The Catch: The "Deterministic" Rule

In the best version of this new method, you can use a little bit of randomness (like rolling a die) to make your message harder to guess, which helps you find even more needles. But in the real world, many systems (like sensors or emergency beacons) can't roll dice; they have to be deterministic. They must follow a strict, pre-set rule every single time.

The big question this paper asks is: If we can't use randomness, and the signal is noisy (like a Gaussian channel), how many people can we still identify, and how reliable is the answer?

The Tradeoff: Speed vs. Accuracy

The authors discovered a fascinating "speed vs. accuracy" tradeoff. Think of it like a security guard at a club.

1. The "Super Strict" Guard (Exponential Reliability)

Imagine the guard is so strict that they will never let a stranger in (0% false alarms) and they will never miss the VIP (0% missed VIPs). To achieve this perfect, "exponential" reliability in a noisy environment:

The guard has to check IDs very slowly.
The Result: You can only identify a linear number of people. If you have 10 minutes, you can check 10 people. If you have 100 minutes, you check 100. The "super speed" advantage of identification disappears. You are back to the old, slow way.

2. The "Relaxed" Guard (Sub-Exponential Reliability)

Now, imagine the guard is willing to make a tiny, almost impossible-to-notice mistake. Maybe they let in 1 person in a billion who isn't the VIP, or they miss the VIP once in a billion tries.

The Result: Suddenly, the speed explodes! You can now identify a super-linear number of people. If you have 10 minutes, you might check millions of people.
The Analogy: It's like the guard stops checking every single detail and just looks for a "vibe." If the vibe is close enough, they let them in. Because they are willing to accept a tiny bit of uncertainty, they can process the crowd incredibly fast.

The "Gaussian" Noise (The Weather)

The paper focuses on Gaussian Channels. In real life, this is like trying to shout a message across a windy field. The wind (noise) distorts your voice.

The authors proved that even with this wind, the "Relaxed Guard" strategy works.
They found a mathematical "sweet spot." If you demand perfect accuracy, you lose the speed advantage. If you accept near-perfect accuracy (errors that vanish very slowly), you get the massive speed advantage.

The "Magic" of the Math

The researchers used some heavy math (involving "volumetric arguments" and "packing spheres") to prove this.

The Sphere Analogy: Imagine every possible message is a ball in a giant room. To make sure the guard doesn't get confused, the balls (messages) must be far apart from each other.
The Tradeoff: If you demand the balls be perfectly far apart (high reliability), you can only fit a few balls in the room. If you allow the balls to be slightly closer together (lower reliability), you can pack millions of them in.
The paper calculates exactly how much you can pack based on how much "noise" (wind) is in the room and how strict the guard needs to be.

Why Does This Matter?

This isn't just about math; it's about the future of the internet and sensors.

The Internet of Things (IoT): Imagine millions of smart sensors in a city. They don't need to send a full report (temperature, humidity, pressure). They just need to signal: "I am Sensor #4592, and I have an emergency."
Efficiency: If we use the "Relaxed Guard" method, we can handle millions of these sensors without clogging the network.
The Warning: The paper warns us that if we try to make these systems 100% perfect (zero errors), we lose the efficiency. We have to accept a tiny, theoretical risk of a mistake to get the massive speed boost.

Summary

Old Way: Send a long letter. Slow, but reliable.
New Way (Identification): Send a "Are you me?" signal. Fast, but tricky.
The Discovery: If you use a strict, no-randomness system, you can only get the "Fast" speed if you are willing to accept a tiny, almost non-existent chance of error. If you demand perfection, you lose the speed.
The Takeaway: In a noisy world, perfection is the enemy of efficiency. To communicate with massive numbers of devices, we must be willing to let go of the need for absolute certainty.

1. Problem Statement

The paper addresses the Rate-Reliability Tradeoff in Deterministic Identification (DI) over General Linear Gaussian Channels.

Context: In the Shannon transmission paradigm, the number of transmittable messages $M$ scales linearly with block length $n$ ( $\log M \sim nR$ ). In contrast, the Identification (DI) paradigm allows the receiver to check if a specific message was sent rather than decoding the entire message. For randomized DI, the number of identifiable messages $N$ scales doubly exponentially ( $\log N \sim 2^{nR}$ ).
The Gap: While DI over discrete channels and specific continuous channels (like AWGN) has been studied, the rate-reliability tradeoff (how the achievable rate changes as the error probability vanishes at different speeds) for general linear Gaussian channels with continuous output had not been established.
Specific Question: Does the "linearithmic" scaling ( $\log N \sim n \log n$ ) observed in DI over Gaussian channels persist when errors vanish exponentially fast, or does it collapse to linear scaling ( $\log N \sim n$ )? The authors investigate this for both symmetric and asymmetric error regimes.

2. Methodology

The authors employ a combination of information-theoretic bounds, geometric packing arguments, and statistical distance measures to derive converse (upper) and achievability (lower) bounds.

Channel Model: The study focuses on the general linear Gaussian channel $Y^n = Ax^n + Z^n$ , where $A$ is a deterministic full-rank linear transformation and $Z^n$ is Gaussian noise with covariance $\Sigma$ . A power constraint $\|x^n\|^2 \leq nP$ is imposed.
Metric Analysis:
- The authors relate the Total Variation (TV) distance between output distributions to the Fidelity (Bhattacharyya coefficient).
- For Gaussian distributions, Fidelity has a closed-form expression dependent on the Mahalanobis distance between input codewords.
- This allows the translation of probabilistic error constraints into geometric constraints on the Euclidean distance between codewords in the input space.
Geometric Packing:
- Converse (Upper Bounds): The problem is reduced to a sphere-packing problem. If errors are small, codewords must be separated by a minimum distance $r$ . The authors bound the number of non-overlapping spheres of radius $r$ that can fit inside a larger sphere defined by the power constraint.
- Achievability (Lower Bounds): The authors construct explicit codes using distance decoding. Codewords are selected as a packing of spheres, and the decoder accepts a message if the received vector is within a specific distance of the expected output.
Error Regimes: The analysis covers:
1. Symmetric Regime: Both error probabilities ( $\lambda_1, \lambda_2$ ) vanish exponentially with the same exponent.
2. Asymmetric Regimes:
  - Stein Regime: One error is constant, the other vanishes exponentially.
  - Sanov Regime: One error vanishes exponentially, the other is constant.

3. Key Contributions

A. Converse Results (Upper Bounds)

The paper establishes that the linearithmic capacity of DI is fragile and depends heavily on the rate of error decay:

Exponential Error Decay: If errors vanish exponentially fast (i.e., error exponents $E > 0$ $E > 0$ are constant), the achievable rate drops from linearithmic ( $n \log n$ $n lo g n$ ) to linear ( $n$ $n$ ).
- The rate is upper-bounded by $R \leq \frac{1}{2} \log \frac{C}{E}$ , where $C$ depends on channel parameters ( $P, \Sigma, A$ ).
- This holds even if only one of the two errors vanishes exponentially (asymmetric regimes).
Sub-Exponential Error Decay: If errors vanish slowly (exponents $E(n) = \Omega(1/n)$ $E (n) = Ω (1/ n)$ ), the linearithmic scaling ( $\log N \sim n \log n$ $lo g N \sim n lo g n$ ) is recovered.
- The capacity upper bound converges to $\dot{C}_{DI}(G) \leq 1/2$ , independent of channel parameters like power $P$ or noise covariance $\Sigma$ at the leading order.

B. Achievability Results (Lower Bounds)

The authors provide explicit code constructions that match the converse bounds:

Linear Codes: They construct deterministic codes with exponentially small errors that achieve linear rates, confirming the converse results for the exponential error regime.
Linearithmic Codes: They construct codes with sub-exponentially vanishing errors (polynomial decay) that achieve the linearithmic rate scaling.
Tradeoff Characterization: The construction explicitly demonstrates the tradeoff: as the error exponent increases (faster error decay), the achievable rate drops from $O(\log n)$ to $O(1)$ .

C. Structural Insights

Universality of Tradeoff: The results mirror those found for discrete-output channels, suggesting a universal behavior where linearithmic scaling requires errors to vanish slower than exponentially.
Parameter Independence: A striking finding is that in the linearithmic regime, the capacity is a universal constant ( $1/2$ ) independent of channel parameters ( $P, \Sigma$ ). In contrast, in the linear regime (exponential errors) and randomized identification, the capacity depends explicitly on these parameters.

4. Key Results Summary

Error Regime	Error Exponent Behavior	Achievable Rate Scaling	Dependence on Channel Parameters
Linearithmic	Sub-exponential ( $E(n) \to 0$ )	$\log N \sim n \log n$	None (Leading order is constant $1/2$ )
Linear	Exponential ( $E(n) = E > 0$ )	$\log N \sim n$	Yes (Depends on $P, \Sigma, A$ via $\nu_{max}$ )
Asymmetric	One error exponential	Linear	Yes

Theorem 2 & 3: Provide upper bounds showing that if $E_{min} > 0$ , the rate is $O(1)$ (linear scaling).
Theorem 4: Proves the existence of linear codes with exponentially small errors.
Theorem 6: Proves the existence of linearithmic codes with sub-exponential errors, achieving a capacity lower bound of $1/4$ (with potential to reach $1/2$ ).

5. Significance and Implications

Theoretical Advancement: This is the first analysis of the rate-reliability tradeoff for DI over general continuous-output channels. It bridges the gap between discrete and continuous channel theories.
Practical Relevance: Gaussian channels are the standard model for physical communication systems (wireless, optical, sensor networks). The results provide performance limits for event-triggered and goal-oriented communications (e.g., IoT, tactile internet) where identifying a specific event is more critical than transmitting a full data stream.
Design Guidelines: The paper clarifies that to achieve the super-linear efficiency of DI, systems must tolerate slower error decay (sub-exponential). If a system requires exponentially low error probabilities (high reliability), it must settle for linear scaling, losing the massive capacity advantage of identification.
Methodological Innovation: The paper demonstrates how to adapt volumetric packing arguments (typically used for discrete or specific continuous cases) to general linear Gaussian channels by leveraging the specific symmetries of Gaussian distributions to map statistical distances to Euclidean geometry.

In conclusion, the paper establishes that Deterministic Identification over Gaussian channels offers a massive capacity boost (linearithmic) only when the reliability requirement is relaxed to sub-exponential error decay. If high reliability (exponential error decay) is required, the system reverts to linear scaling, similar to traditional transmission, though with potentially higher rates than standard transmission.