Lower bound on observations needed for symbol recovery in random linear codes
A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding
Information Theory
Summary
The paper finds a minimum number of random linear measurements needed to reliably recover a single piece of information from certain types of data encodings. The authors show this minimum is about π/4 times the size of the data, regardless of some technical details like the type of field or decoding method. They extend prior results that were limited to simpler codes and decoding methods. Their work gives an exact expected number of measurements in some special cases, with known constructions that meet this limit.
What this means in practice
- •For coding theory engineers: Know the fundamental measurement limits when designing linear codes for efficient symbol recovery.
- •For signal processing teams: Avoid designing measurement schemes that claim recovery with fewer observations than the established π/4 lower bound.
A theory result. No direct application yet.
Authors
Daniella Bar-Lev, Ohad Elishco, Ryan Gabrys
Abstract
We study the expected number of random linear observations required to recover a prescribed information symbol. For ensembles with uniformly random supports, independently sampled nonzero coefficients, and uniformly bounded column weights, we prove that the asymptotic normalized expected recovery time is at least $π/4$ under optimal decoding. The result holds over finite or infinite fields and extends the lower bound previously established for binary fully symmetric codes under peeling decoding. For singleton - pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit, independently of the field and coefficient distribution. The minimum within this family is approximately $0.793933445$, which explicit constructions attain asymptotically over every fixed finite field.