Rate–distortion limits of binary linear encoders

For iid Bernoulli(p) bits, 0<p≤1/2, determine the distortion achievable by a full-row-rank k×n binary linear encoder H. The target converse is k/n≥h(p)(1−D(H)/p), where h is binary entropy and D(H) is optimal bitwise-MAP distortion.

Why it matters and what counts as progress

Why it matters: It determines the distortion cost of using a binary linear encoder on a biased source, rather than allowing arbitrary nonlinear encoding.

What counts as progress: A converse matching achievable linear-encoder distortion for every Bernoulli bias, beyond the unbiased source case.

How the problem developed

1978 · Open problem [1]
J. L. Massey Asked whether the best lossy rate for linear encoding a Bernoulli source is attained by time-sharing between lossless linear compression and estimating the rest by zero.
1978 · Partial result [1]
T. C. Ancheta Established the time-sharing bound for the unbiased Bernoulli source p = 1/2; the nonuniform case remained open.
24 Aug 2026 · Reported claim [1]
Yihong Wu and GPT-5.6 Sol The paper proves the time-sharing expression is optimal for every 0 < p < 1/2, extending Ancheta’s result and answering Massey’s question in the stated binary linear-encoder model.

AI contribution

Entropy of Bernoulli Measures Conditioned on Affine Subspaces and a Problem of Ancheta--Massey

Yihong Wu

For iid Bernoulli(p) bits with 0<p≤1/2 and a full-row-rank k×n binary linear encoder H, its optimal bitwise-MAP distortion D(H) obeys k/n≥h(p)(1−D(H)/p). A nonasymptotic entropy bound for every affine subspace drives the converse.

AI involvementAI-centered

ImportanceNotable

Technical verificationReported

Human understandingFull