Pith. sign in

REVIEW 2 major objections 5 minor 17 references

The Performance of Compression-Based Denoisers

T0 review · 2 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that a good lossy compressor, when its distortion measure is matched to the observation channel and set to the conditional-entropy level, asymptotically outputs independent posterior samples, making its denoising loss exac

desk verdict Genuine advance: exact loss characterization for compression-based denoising over general DMCs, but the main theorem's rank hypothesis is mis-stated and needs a correction. read the letter →

arxiv 2512.14539 v2 pith:VAXY5DJR submitted 2025-12-16 cs.IT math.IT

Dan Song , Ayfer Özgür , Tsachy Weissman This is my paper
classification cs.ITmath.IT MSC 94A3494A15
keywords compression-baseddenoisingrate-distortiontheoryposteriorsamplingconditionalindependencediscretememorylesschannelsstationaryergodicsourcesdouble-sidedmixingempiricaldistributions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper shows that lossy compression of a noisy observation is itself a denoising operation, for any stationary ergodic source passed through any discrete memoryless channel. The key is to choose the compressor's distortion measure as the negative log-likelihood of the channel, ρ(z,y)=-log p_{Z|X}(z|y), and to operate at the distortion level H(Z|X), the conditional entropy of the observation given the source. Under a double-sided mixing condition on the source–observation pair, the reconstruction produced by a good compressor behaves asymptotically like an independent draw from the posterior of the source given the observation. The denoising loss for any loss function therefore converges to the expected loss of two independent posterior samples, an exact expression that improves on earlier upper bounds for additive-noise channels.

What carries the argument

The engine is the pair (ρ, D) with ρ(z,y)=-log p_{Z|X}(z|y) and D=H(Z|X). For this choice, the rate-distortion function takes the closed form R(Z^k,H(Z|X))=(1/k) I(Z^k;X^k), achieved uniquely by the law (Z^k,Y^k) =_d (Z^k,X^k) when the channel matrix has full row rank. This yields the marginal result that the empirical (Z^k,Y^k) distribution converges to the posterior. The second ingredient is the double-sided mixing coefficient δ_k, which measures how far the finite-window posterior is from the infinite-window posterior; Lemma 1 bounds the total-variation discrepancy of the empirical conditional of X0 given (Z^k,Y^k) from the true posterior by |X|δ_k. Vanishing of δ_k turns the marginal pos

What would settle it

Take a stationary but non-mixing source, e.g., the deterministic alternating sequence X_i=(i mod 2), observed through a binary symmetric channel. Because the posterior P(X0|Z^k) does not stabilize with k, δ_k does not vanish. If one constructs a good code for ρ(z,y)=-log p_{Z|X}(z|y) at D=H(Z|X), the empirical conditional distribution Q^{(n)}_{X0|Z^k,Y^k} should not converge to P_{X0|Z^k}, and the limit in Theorem 5 should differ from E_Z[E_{U,V∼P_{X0|Z}}^2 Λ]. Computing that limit would locate the precise boundary of the theorem's validity.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 5: for finite alphabets, a double-sided mixing pair (X,Z), an invertible channel matrix P_{Z|X}, and a bounded loss Λ, any sequence of good lossy codes for Z under the channel-matched distortion at level H(Z|X) satisfies lim_{n→∞} E[Λ^n(X^n,Y^n(Z^n))] = E_Z[E_{U,V∼(P_{X0|Z})^2} Λ(U,V)]. In words, compression samples from the posterior exactly, and the two random variables — the clean symbol and its reconstruction — are asymptotically conditionally independent given the observation. This both generalizes the framework beyond additive noise and replaces a worst-case-coupling upper bound with an exact formula; for squared error, the formula is 2 Var(X0|Z), a

Load-bearing premise

The load-bearing premise is that the source and observation pair is double-sided mixing, δ_k→0, which is not implied by stationarity or ergodicity; the paper establishes it only for Markov sources with strictly positive channel transition probabilities, and the exact loss limit collapses without it.

Editorial extensions

If this is right

  • For mean-squared-error loss, the compression-based denoiser achieves exactly 2 Var(X0|Z), a factor-of-two improvement over the prior worst-case bound of 4 Var(X0|Z).
  • For Hamming loss on a binary source through a BSC, the achieved loss is E_Z[2α(1−α)] with α=P(X0=1|Z), which never exceeds the old bound 2φ(α) and coincides with the Bayes envelope at α=0, 1/2, and 1.
  • The framework applies to arbitrary discrete memoryless channels, including erasure channels, and to sources with memory such as Markov chains, as long as the channel matrix has full row rank.
  • Because the distortion measure depends only on the channel, the same compressor design works for any downstream loss function; the result thus supplies a universal recipe for posterior sampling via rate-distortion coding.
  • In the scalar Gaussian case, the scheme achieves the rate-distortion-perception optimal tradeoff, linking compression-based denoising to perception-constrained coding.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exact loss formula depends on conditional independence; if double-sided mixing fails, the empirical conditional may not converge to the posterior, so the formula would break down even though the marginal posterior result might survive — a boundary worth probing with non-mixing sources like periodic or deterministic signals.
  • The factor-of-two gap relative to the Bayes-optimal MSE suggests a natural test: if one runs two independent good codes and averages their outputs, the variance term should halve, potentially approaching the Bayes envelope; the paper leaves this multi-code averaging unexplored.
  • The rate-distortion-perception optimality shown for Gaussian sources hints that the compression-based denoiser might be optimal in the perfect-perception sense for a broader class of sources; a general proof would require extending Proposition 3 beyond the Gaussian case.
  • Since the distortion measure is exactly the channel's log-likelihood, one could implement the scheme in practice by using any standard lossy codec on a transformed representation of the observations; experiments on real data, which the paper lists as future work, could verify whether the asymptotic formula estimates finite-block performance.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. This paper studies compression-based denoising for a stationary ergodic source X^n observed through a known discrete memoryless channel P_{Z|X}. The authors propose to compress Z^n with a lossy code designed for the channel-matched distortion ρ(z,y) = -log p_{Z|X}(z|y) at distortion level H(Z|X). Using a prior result of Weissman–Ordentlich on the empirical distribution of good rate-distortion codes, they show (Theorem 4/Corollary 2) that the empirical (Z^k,Y^k) distribution of a good code asymptotically coincides with (Z^k,X^k), so the reconstruction is a posterior sample. The main contribution (Theorem 5) adds a double-sided mixing condition on (X,Z) and a rank condition on the channel matrix, and proves the stronger statement that, in the joint empirical distribution, X_0 and Y_0 are asymptotically conditionally independent given Z^k, yielding the exact loss lim_n E[Λ^n(X^n,Y^n)] = E_Z E_{U,V∼P_{X_0|Z}^2}[Λ(U,V)]. Examples give a factor-of-two MSE improvement over the earlier bound and Hamming-loss evaluations. A comparison with indirect rate–distortion and rate–distortion–perception shows the scheme is generally not equivalent to indirect rate–distortion but can achieve the perfect-perception curve in the scalar Gaussian case.

Significance. If the main theorem is correct, this is a meaningful advance: it replaces the worst-case-coupling upper bound of [7] with an exact characterization for general DMCs, and the conditional-independence structure is a genuine strengthening. The derivation is transparent and rests on standard rate-distortion theory plus the independent prior result of Weissman–Ordentlich; no ad-hoc parameters are introduced. The erasure-channel example and the Gaussian rate-distortion-perception comparison illustrate the applicability and limitations. The main proof (Theorem 5) is essentially correct under the full-row-rank condition, and the claimed factor-of-two MSE improvement over [7] follows from the independence of two posterior samples.

major comments (2)
  1. [III-B, Theorem 5 (Eq. 39); proof of Corollary 2 (Eq. 35); Example 3] The statement of Theorem 5 requires the channel matrix P_{Z|X} to be invertible, but the proof invokes Corollary 2 (Eq. (35)), whose hypothesis is only full row rank, and the proof of Theorem 4 also uses full row rank for uniqueness. Example 3 (Binary Symmetric Source with Erasures) uses an erasure channel with |X|=2 and |Z|=3; its 2×3 transition matrix has full row rank but is not square, hence not invertible. The theorem as written therefore does not cover the paper's own showcase, nor any DMC with unequal input/output alphabet sizes. The mathematical argument itself goes through under full row rank (this is exactly the condition that forces P_Y=P_X in the uniqueness step), so the fix is local but necessary: restate Theorem 5 with the full-row-rank condition, define the matrix orientation (rows indexed by inputs or outputs), and correct the alphabet declaration in Example 3.
  2. [Abstract / Section VI vs Definition 5 (Eqs. 36–37) and Proposition 1] The abstract, introduction, and conclusion claim the result for any stationary ergodic source, but Theorem 5 assumes (X,Z) are double-sided mixing, i.e. δ_k(X,Z)→0 in Definition 5. This condition is not implied by stationarity/ergodicity; the manuscript itself notes that processes with nonzero δ_k exist, and Proposition 1 establishes the condition only for Markov sources with strictly positive channel probabilities. Since Lemma 1 (Eq. (38)) and hence the exact limit in Eq. (39) collapse without δ_k→0, the advertised scope is broader than the proven statement. Please either prove the result under plain stationarity/ergodicity or amend the abstract, Section I, and Section VI to state the double-sided-mixing assumption.
minor comments (5)
  1. [Section IV, Example 3] The line 'Let X=Z=Y={0,1}' is inconsistent with the erasure channel; Z must include the erasure symbol ε, and indeed the text later uses Z_t≠ε. Please correct the alphabet declaration.
  2. [Section IV, Example 2] Please specify D∈(0,1/2) for the BSC(D) channel. At D=1/2 the channel matrix is singular and the rank/invertibility condition of Theorem 5 fails.
  3. [Section IV-A, Examples 4 and 5] These Gaussian examples use continuous alphabets and lie outside the finite-alphabet hypotheses of Theorems 4–5. State explicitly that they are informal infinite-alphabet analogues, or provide the needed extension.
  4. [Theorem 5 proof, Eqs. (45)–(46)] The error notation o_n(1), o_k(1), and o(1/n) is nonstandard and the order of limits is implicit. Since Corollary 2 is applied for fixed k before taking k→∞, please use explicit error bounds η(n,k) with lim_{k→∞} lim_{n→∞} η(n,k)=0, or otherwise clarify the double-limit argument.
  5. [Section IV-A, Proposition 3] The finite-alphabet necessity direction is described only as 'nearly identical' to Proposition 2 and not written out. Since Proposition 3 is used for the optimality claim in Example 5, please include the proof or explicitly state that only the sufficiency direction is needed for the paper's conclusions.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is a genuine derivation from rate-distortion theory plus a mixing estimate, not a restatement of its inputs.

full rationale

The derivation chain is self-contained in the relevant sense. Theorem 4 computes the rate-distortion function for rho(z,y) = -log p_{Z|X}(z|y) at D = H(Z|X) directly from the information inequality and verifies achievability by (Z^k,Y^k) = (Z^k,X^k); the posterior-sampling conclusion is not assumed in the definition of a good code but follows from equality conditions. Corollary 2 is an application of the prior theorem [7, Thm 3], which is a published, parameter-free result about empirical distributions of rate-constrained codes; its assumptions do not include the target loss characterization, so it is independent support rather than a circular premise. Lemma 1 bounds the failure of conditional independence by the double-sided mixing coefficient and is proved from the Markov chain and stationarity. Theorem 5 combines these ingredients; the final expression E_Z E_{U,V iid P_{X0|Z}}[Lambda(U,V)] is not built into the distortion measure or the definition of goodness, but emerges from the rate-distortion equality and the mixing estimate. There is no fitted parameter called a prediction, no renaming of a known result under new coordinates, and no load-bearing claim justified solely by self-citation. The cited distortion measure from [8] is attribution only, not evidence. The invertible-versus-full-row-rank mismatch noted for erasure channels is an internal-consistency/correctness issue, not circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted. The central claim is derived from the source/channel model and standard rate-distortion theorems; the only new mathematical object is the mixing coefficient δ_k, which is an assumption, not a fitted entity.

assumptions (6)
  • domain assumption The source X is stationary and ergodic with finite alphabet, and the channel P_{Z|X} is memoryless and known.
    Section II.B; the entire setting and the definition of D=H(Z|X) rely on it.
  • ad hoc to paper The pair (X,Z) is double-sided mixing, i.e. δ_k→0 with δ_k defined in Eq. (36).
    Introduced in Definition 5; Lemma 1 and Theorem 5 require it. Not implied by stationarity/ergodicity, though Proposition 1 gives it for Markov X with positive channel entries.
  • domain assumption The channel matrix P_{Z|X} has full row rank / is invertible.
    Used in Theorem 4/Corollary 2 to guarantee uniqueness of the rate-distortion-achieving distribution and recover the posterior; fails for e.g. BSC(1/2).
  • domain assumption There exists a sequence of good lossy codes at (R(Z,D),D) in the sense of Definition 3.
    Theorem 5 is conditional on such codes; the paper does not construct them, relying on standard rate-distortion coding theorems.
  • standard math Standard prior results: rate-distortion achiever uniqueness, HMM exponential forgetting, martingale convergence of posteriors.
    Invoked in proofs of Theorem 4, Proposition 1, and in the martingale argument before Definition 5.
  • domain assumption The reconstruction alphabet Y equals X so that ρ(z,y)=-log p_{Z|X}(z|y) is defined for y∈Y.
    Needed for the distortion measure; implicit in the setting.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Performance of Compression-Based Denoisers." pith.science (2026). https://pith.science/paper/VAXY5DJR

@misc{pith2026251214539,
  author       = {Pith},
  title        = {Pith review of: The Performance of Compression-Based Denoisers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VAXY5DJR}},
  note         = {Machine review of arXiv:2512.14539}
}
read the original abstract

We consider a denoiser that reconstructs a stationary ergodic source by lossily compressing samples of the source observed through a memoryless noisy channel. Prior work on compression-based denoising has been limited to additive noise channels. We extend this framework to general discrete memoryless channels by deliberately choosing the distortion measure for the lossy compressor to match the channel conditional distribution. By bounding the deviation of the empirical joint distribution of the source, observation, and denoiser outputs from satisfying a Markov property, we give an exact characterization of the loss achieved by such a denoiser. Consequences of these results are explicitly demonstrated in special cases, including for MSE and Hamming loss. A comparison is made to an indirect rate-distortion perspective on the problem.

Figures

Figures reproduced from arXiv: 2512.14539 by the authors.

Figure 1
Figure 1. Setting considered in this work. The source [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Comparison of the Bayes envelope, compression based denoiser loss, and suboptimal upper bound for denoising a binary [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Performance of compression based denoiser in Example 3 for various switching probabilities [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Performance of compression based denoiser in Example 3 for various erasure probabilities [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 1 canonical work pages

  1. [7]

    The empirical distribution of rate-constrained source codes,

    T. Weissman and E. Ordentlich, “The empirical distribution of rate-constrained source codes,”IEEE Transactions on Information Theory, vol. 51, no. 11, pp. 3718–3733, Nov. 2005

    2005

  2. [1]

    Indirect rate distortion problems,

    H. Witsenhausen, “Indirect rate distortion problems,”IEEE Transactions on Information Theory, vol. 26, no. 5, pp. 518–521, Sep. 1980

    1980

  3. [2]

    Information transmission with additional noise,

    R. Dobrushin and B. Tsybakov, “Information transmission with additional noise,”IRE Transactions on Information Theory, vol. 8, no. 5, pp. 293–304, 1962

    1962

  4. [3]

    Filtering random noise from deterministic signals via data compression,

    B. Natarajan, “Filtering random noise from deterministic signals via data compression,”IEEE Transactions on Signal Processing, vol. 43, no. 11, pp. 2595–2605, Nov. 1995. [Online]. Available: https://ieeexplore.ieee.org/document/482110/

    1995

  5. [4]

    Occam filters for stochastic sources with application to digital images,

    B. Natarajan, K. Konstantinides, and C. Herley, “Occam filters for stochastic sources with application to digital images,”IEEE Transactions on Signal Processing, vol. 46, no. 5, pp. 1434–1438, May 1998. [Online]. Available: https://ieeexplore.ieee.org/document/ 668806/

    1998

  6. [5]

    MDL denoising,

    J. Rissanen, “MDL denoising,”IEEE Transactions on Information Theory, vol. 46, no. 7, pp. 2537–2543, 2000

    2000

  7. [6]

    The Kolmogorov Sampler,

    D. L. Donoho, “The Kolmogorov Sampler,” 2002, available Online https://purl.stanford.edu/nd499ds7502

    2002

  8. [8]

    Training Generative Models From Privatized Data via Entropic Optimal Transport,

    D. Reshetova, W.-N. Chen, and A. Özgür, “Training Generative Models From Privatized Data via Entropic Optimal Transport,”IEEE Journal on Selected Areas in Information Theory, vol. 5, pp. 221–235, 2024

    2024

Show all 17 references
  1. [9]

    Csiszár and J

    I. Csiszár and J. Körner,Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, 1981

    1981

  2. [10]

    R. G. Gallager,Information theory and reliable communication. Springer, 1968, vol. 588

    1968

  3. [11]

    Coding Theorems for a Discrete Source With a Fidelity Criterion-,

    C. E. Shannon, “Coding Theorems for a Discrete Source With a Fidelity Criterion-,”Institute of Radio Engineers International Convention Record, vol. 7, 1959

    1959

  4. [12]

    Indirect Rate-Distortion Function of a Binary i.i.d Source,

    A. Kipnis, S. Rini, and A. J. Goldsmith, “Indirect Rate-Distortion Function of a Binary i.i.d Source,” Jun. 2015, arXiv:1505.04875 [cs]. [Online]. Available: http://arxiv.org/abs/1505.04875

    2015 arXiv

  5. [13]

    The Rate-Distortion Risk in Estimation From Compressed Data,

    ——, “The Rate-Distortion Risk in Estimation From Compressed Data,”IEEE Transactions on Information Theory, vol. 67, no. 5, pp. 2910–2924, May 2021, conference Name: IEEE Transactions on Information Theory. [Online]. Available: https://ieeexplore.ieee.org/document/9387338/?arnu...

    2021

  6. [14]

    Information Compression in the AI Era: Recent Advances and Future Challenges,

    J. Chen, Y . Fang, A. Khisti, A. Ozgur, N. Shlezinger, and C. Tian, “Information Compression in the AI Era: Recent Advances and Future Challenges,” Jun. 2024, arXiv:2406.10036 [cs]. [Online]. Available: http://arxiv.org/abs/2406.10036

    2024 arXiv

  7. [15]

    Rethinking lossy compression: The rate-distortion-perception tradeoff,

    Y . Blau and T. Michaeli, “Rethinking lossy compression: The rate-distortion-perception tradeoff,” inInternational Conference on Machine Learning. PMLR, 2019, pp. 675–685

    2019

  8. [16]

    Exponential Forgetting and Geometric Ergodicity in Hidden Markov Models,

    F. Le Gland and L. Mevel, “Exponential Forgetting and Geometric Ergodicity in Hidden Markov Models,”Mathematics of Control, Signals and Systems, vol. 13, no. 1, pp. 63–93, Feb. 2000. [Online]. Available: https://doi.org/10.1007/PL00009861

    doi

  9. [17]

    Hidden Markov processes,

    Y . Ephraim and N. Merhav, “Hidden Markov processes,”IEEE Transactions on Information Theory, vol. 48, no. 6, pp. 1518–1569, 2002

    2002

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.