Universal Sampling Rate Distortion

I. INTRODUCTION

• The problem uses spatial sampling of k-subsets of m sources followed by joint compression to reconstruct a predesignated source subset within a distortion level.Source: §I · p. 1
• The work extends prior sampling rate-distortion analysis for known joint pmfs and relates to applications including in-network computation and dynamic thermal management.Related literature includes universal coding, compressed sensing, temporal sampling, and spatial sampling of random fields.Source: §I · pp. 1–2
• Unlike most prior settings, the paper studies spatial rather than temporal sampling and restricts universality to an unknown pmf within a finite family.It considers average distortion in Bayesian settings and peak distortion in nonBayesian settings.Source: §I · p. 2
• Universal sampling rate distortion jointly captures tradeoffs among sampling, unknown-pmf approximation, lossy compression rate, and reconstruction distortion.The target is robust performance without exact knowledge of the sources’ joint pmf.Source: §I · pp. 1–2
• Independent random sampling can learn all k-marginals and improve universal performance, while memoryless random sampling can learn the entire joint pmf from the sampling sequence.The memoryless sampler may choose sets based on instantaneous source realizations.Source: §I · p. 2
• The achievability proofs introduce schemes that combine source-distribution learning with lossy compression, including deterministic realization-dependent sampling to reduce code complexity.Source: §I · p. 2

II. PRELIMINARIES

• The source consists of i.i.d. repetitions of a discrete memoryless multiple source whose pmf belongs to a finite full-support family, with Bayesian and nonBayesian uncertainty settings.The Bayesian model specifies a known parameter prior, whereas the nonBayesian model treats the parameter as an unknown constant.Source: §II · pp. 2–3
• A k-random sampler causally chooses k-sized source subsets and outputs both the selected sets and sampled source sequences without knowing the underlying pmf.Source: §II · p. 3
• The three sampler classes are memoryless-random, independent-random, and fixed-set, obtained by progressively restricting dependence on source realizations and sampling history.Source: §II · p. 3
• The decoder reconstructs a fixed recovery subset of source components from a compressed representation of the sampler output under a finite single-letter distortion measure.Source: §II · p. 3
• A universal block code consists of a sampler, encoder, and decoder, with rate 1/n log J and decoder access to the sampling sequence under the stated formulation.For independent-random sampling, the paper later notes that explicit decoder knowledge of the sampling sequence is unnecessary.Source: §II · p. 3
• The universal sampling rate-distortion function is the infimum achievable rate at distortion level ∆, with separate functions for fixed-set, independent-random, and memoryless-random samplers.Expected distortion is used in the Bayesian setting, while peak distortion is used in the nonBayesian setting; expected-distortion USRDf is no larger than peak-distortion USRDf.Source: §II · pp. 3–4

• The USRDf is characterized for k-FS, k-IRS, and k-MRS in both Bayesian and nonBayesian settings, with each successive sampler offering a better estimate of θ.The k-IRS characterization remains achievable with an uninformed decoder, while k-MRS achievability uses instantaneous source realizations.Source: §III · pp. 4, 9
• For k-FS, the Bayesian USRDf is a minmax over ambiguity atoms and distortion allocations, whereas the nonBayesian USRDf maximizes atomwise quantities and is no smaller.Ambiguity atoms group source parameters inducing identical sampled-component marginals.Source: §III · pp. 4–5
• Fixed-set sampling can benefit from observing components outside the recovery set: in Example 3, R_{3}(∆) ≤ R_{1}(∆), strictly for suitable ∆.The example uses X_3 = X_1 ⊕ X_2 while recovering sources 1 and 2.Source: §III · pp. 7–8
• A k-IRS refines the ambiguity partition and can strictly outperform the best k-FS through improved θ estimation and time-sharing across fixed-set samplers.Examples 4 and 5 show strict superiority; k-IRS can estimate both sampled-component marginals, whereas k-FS estimates only one.Source: §III · pp. 9–10
• For k-MRS, instantaneous source-dependent sampling distinguishes all pmfs, and the USRDf is characterized using an auxiliary time-sharing variable U with |U| ≤ 2|Θ| + 1.Conditionally deterministic samplers attain the extrema and are optimal throughout the feasible distortion interval.Source: §III · pp. 10–11
• The k-MRS characterization is equivalently attained by deterministic samplers based on mappings from source realizations and U to sampling sets, for both Bayesian and nonBayesian criteria.The achievability proof selects a minimizing deterministic mapping w.Source: §III · p. 11
• The characterization includes the entropy difference τ∈Θ h(pτ) −h(∆) for 0 ≤∆≤max τ∈Θ pτ.Source: §III · p. 11
• Rm(∆) < Rı(∆) in both the Bayesian and nonBayesian settings.Source: §III · p. 12
• The right-sides of (13), (14), (21), (22), (27), and (29) are finite-valued, decreasing, convex, and continuous for ∆min ≤∆≤∆max.Source: §III · p. 12

Proof strategy

• The proofs successively address fixed-set sampling, k-IRS, and k-MRS by estimating the relevant source parameter and choosing a corresponding rate-distortion code.Finite parameter families allow the estimate to be conveyed to the decoder rate-free; Bayesian schemes average distortion thresholds, while nonBayesian schemes enforce a worst-case distortion bound.Source: A. Achievability proofs · p. 12

Fixed-set sampling

• For fixed-set sampling, maximum-likelihood parameter learning selects a fixed-set sampling rate-distortion code whose rate and expected distortion approach the target characterization.The construction sends the parameter estimate and the selected code index, with the estimation error becoming negligible for sufficiently large blocklength.Source: A. Achievability proofs · pp. 13–14

Independent random sampling

• For k-IRS, an initial phase estimates θ2 by repeatedly sampling every candidate set, followed by a phase that time-shares those sets according to the optimizing distribution.The resulting rate is bounded by the IRS mutual-information expression plus ε′, while the distortion guarantee holds for sufficiently large estimation and coding blocks.Source: A. Achievability proofs · pp. 14, 16

Memoryless random sampling

• For k-MRS, a deterministic sampler first estimates θ, after which deterministic sampling rules indexed by U are concatenated to realize the optimizing time-sharing distribution.The construction uses conditional point-mass samplers and achieves the stated rate and expected distortion as the preliminary and coding blocks grow.Source: A. Achievability proofs · pp. 16–18
• The k-MRS achievability construction uses typical sampling-set frequencies and fixed-set codes for each sampled set, yielding the target rate expression up to ε′.The sampling sequence is typical with probability approaching one, and the resulting rate is expressed as a weighted sum of conditional mutual informations.Source: A. Achievability proofs · pp. 17–18

Unified converse

• A unified converse begins with k-MRS and derives the k-IRS and fixed-set results by restricting the sampler’s dependence on the source.The proof uses the same lemma under progressively weaker sampling models, with the corresponding parameter representation changed for each model.Source: B. Converse proof · pp. 18–20

Converse lemma

• Lemma 7 converts conditional mutual-independence assumptions into the single-letter constraints needed for the converse bounds.The lemma applies to finite-valued variables whose per-time pairs are conditionally mutually independent given the parameter.Source: B. Converse proof · pp. 18–19

Auxiliary variable

• Carathéodory’s theorem represents the relevant convex-hull point using an auxiliary variable U with support size at most 2|Θ| + 1.This finite-support representation supplies the auxiliary-variable form used in the k-MRS converse.Source: B. Converse proof · p. 20

Independent and fixed-set sampling

• For k-IRS, the converse establishes R ≥ R̄(∆) for ∆ ≥ ∆min, completing the lower bound for that sampling mechanism.The fixed-set converse follows analogously after replacing the random-sampling parameterization with a fixed sampled set.Source: B. Converse proof · pp. 20–21

NonBayesian converse

• In the nonBayesian setting, the converse proofs remove the outer minimizations over distortion thresholds while retaining the same successive weakening from k-MRS to k-IRS and fixed-set sampling.The resulting arguments use appropriate conditional probability mass functions for each fixed parameter value.Source: B. Converse proof · p. 21

V. DISCUSSION

• Finite pmf families enable uniform estimator consistency and rate-free conveyance of source-distribution estimates to the decoder.Extensions to countable or uncountable families remain open.Source: §V · p. 21
• For memoryless random sampling, decoder knowledge of the sampling sequence implicitly conveys source realizations and lets it replicate the encoder’s distribution estimate.Without access to the sampling sequence, the corresponding universal sampling rate distortion function remains unanswered.Source: §V · p. 21
• The achievability schemes for independent and memoryless random sampling estimate the distribution from both the sampled sequence and sampled source values.These schemes exploit spatial freedom in choosing the sampling sequence.Source: §V · p. 21
• The choice of sampling sequence raises open questions about how dependence on source realizations affects estimation and how sampler output can implicitly embed source realizations.These questions are presented as independently relevant to statistical learning theory.Source: §V · p. 21

A. Proof of (52) and (53)

• The concatenated code’s rate is evaluated by combining the component codes indexed by u ∈ U.The supplied passage introduces the rate calculation for the concatenated construction but does not include its completed expression.Source: A. Proof of (52) and (53) · p. 22
• The rate and distortion conclusions are asserted for all sufficiently large n, with ε′ chosen appropriately.The proof derives the final bound through an intermediate inequality and type-based estimates.Source: A. Proof of (52) and (53) · p. 23
• The proof bounds the expected distortion of the concatenated code after defining the decoder output Y^n′.The distortion argument uses the component-code construction and subsequent inequalities.Source: A. Proof of (52) and (53) · p. 23

B. Proof of Proposition 4

• The inner maximum and minimum can be interchanged in the displayed optimization, supporting the epigraph formulation.The proof then treats r(∆) analogously.Source: B. Proof of Proposition 4 · p. 24
• Convexity in ∆ permits q(∆) and r(∆) to be expressed through their Lagrangian forms.The proof invokes convexity before defining the corresponding Lagrangian functions Gq and Gr.Source: B. Proof of Proposition 4 · pp. 24–25
• The proof identifies the relevant distortion contribution through an expectation conditioned on S=s, X_S=x_s, U=u, and θ=τ.The resulting term is treated as a function of s, x_M, and u.Source: B. Proof of Proposition 4 · p. 24
• The proof represents q(∆) and r(∆) as maxima of their respective Lagrangians minus α∆.The representation applies for the relevant distortion interval and nonnegative multiplier and family-weight variables.Source: B. Proof of Proposition 4 · p. 25

C. Proof of Lemma 5

• The right-hand sides of the relevant expressions are finite-valued and nonincreasing in ∆.Their finiteness follows from finiteness of the underlying quantities A(δ,τ1).Source: C. Proof of Lemma 5 · p. 25
• Continuity holds for ∆ > ∆min and at ∆min by the cited continuity argument, with analogous properties applying to the other expressions.The proof explicitly invokes a standard continuity result at the minimum distortion.Source: C. Proof of Lemma 5 · p. 25
• Convexity of the right-hand side is proved by selecting maximizers at two distortion levels and combining the corresponding minimizing distortions.The argument considers ∆1 < ∆2 and a convex combination parameter 0 < α < 1.Source: C. Proof of Lemma 5 · p. 25