nucleation

LIT-1247: Strong Successive Refinability and Rate-Distortion-Complexity Tradeoff

1 min read

Properties4
StatusActive — read 2026-10-20 (NOTE-980) in full, from arXiv:1506.03407v2; worth reading for successive refinement at second order (source dispersion): a sufficient condition, Corollary 6, that a source refinable at (D₁, D₂) throughout a neighbourhood of its law is also refinable with both dispersion terms, so that discrete sources under Hamming distortion and the Gaussian under squared error lose nothing even at √n precision; and for layered codes, which use a growing number L_n of refinement stages to trade encoding complexity against rate, with every stage on the rate–distortion curve. Read it knowing that it says nothing about logarithmic loss or the information bottleneck, though NOTE-988 recalled it as the source of a log-loss result (that result is No and Weissman, ISIT 2015, and No, Entropy 2019, and concerns direct log-loss, not the bottleneck's remote one); that its sufficient condition asks for refinability in a whole neighbourhood of the source, not at the source alone; that the layered-code results cover only binary-Hamming and Gaussian-quadratic sources; and that the abstract's "O(n^{log n}) algorithm" is an encoding search over codebooks shown to exist, not constructed, with the bound holding as stated only when the rate is below one nat.
Version2
Tagsinformation-theory, mathematics
Cited as “paper” byNOTE-980 — No, Ingber and Weissman — Strong successive refinability

Graph View

No, A., Ingber, A. & Weissman, T. (2016). Strong Successive Refinability and Rate-Distortion-Complexity Tradeoff. IEEE Transactions on Information Theory 62(6): 3618–3635. doi:10.1109/TIT.2016.2549540. arXiv:1506.03407 (10 June 2015).

Read in full in NOTE-980, from the arXiv copy.

Why this is here

Registered as the source of a result the reading of Equitz and Cover (NOTE-988, LIT-1238) recalled: that every discrete source is successively refinable under logarithmic loss, the loss under which the information bottleneck is a rate–distortion problem. That would bear on the stochastic half of QUESTION-220. The reading found the attribution wrong. This paper is about second-order (dispersion) refinability and about layered codes, and it stays in the record for those. Its bearing on QUESTION-220 is indirect, and NOTE-980 says what the log-loss result would and would not imply.

Backlinks