Linear source coding compresses a random source vector by applying a linear transformation, while allowing an arbitrary decoding map. For a binary source
, an encoder has the form 
with a binary 
matrix 
, and the rate is 
. In lossy coding, distortion can be measured by the
expected fraction of incorrectly reconstructed bits.
For independent Bernoulli bits with parameter 
and allowed distortion 
, the optimal asymptotic rate for linear
encoding is
 |
where 
is binary information entropy and 
denotes the base-2 logarithm. This rate is achieved by compressing
a fraction 
of the source losslessly and estimating the remaining bits by zero.
The unrestricted rate-distortion function is 
, which is smaller at interior distortions.
Thus linearity imposes a genuine cost even though linear encoders suffice for asymptotically
lossless compression.
Wu (2026) proved the optimality of the linear rate for all 
, answering the question of Massey and extending
Ancheta's 
result, both documented in that paper. GPT-5.6 Sol discovered the proof
in an author-guided process, and Wu simplified and checked it. Independent external
review had not been reported as of Sep. 7, 2026.
