PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling Rate Distortion

Vinay Praneeth Boda, Prakash Narayan

arXiv:1607.04143v1cs.ITmath.IT

TL;DR

When only k of m sources are sampled at each time, the challenge is to compress them while reconstructing all m sources within a distortion level. The paper formulates sampling rate distortion and characterizes several sampling strategies, including a decoder-knowledge invariance for independent random sampling and conditional point-mass optimality for an upper bound with an uninformed decoder.

  • Problem

    The paper asks how to causally sample k of m discrete memoryless sources to minimize compression rate for a specified reconstruction distortion.

    Source: §I · p. 1

  • Method

    The paper formulates sampling rate distortion and characterizes fixed-set, independent-random, and memoryless-random sampling strategies, including decoder-informed and uninformed cases.

    Source: §III · p. 4, §V · pp. 19–20

  • Results

    For independent random sampling, the SRDf is unchanged by decoder knowledge; for an uninformed-decoder memoryless sampler, the SRDf upper bound admits conditional point-mass optimality.

    Source: §I · pp. 2–3

  • Takeaways & Limitations

    The framework characterizes tradeoffs among sampling strategy, optimal encoding rate, and reconstruction distortion.

    Source: §V · p. 19

    For memoryless random sampling with an uninformed decoder, the upper bound's tightness is unknown, and whether time-sharing is needed for convexification remains open.

    Source: §V · p. 20

Abstract

from arXiv · show

Consider a discrete memoryless multiple source with $m$ components of which $k \leq m$ possibly different sources are sampled at each time instant and jointly compressed in order to reconstruct all the $m$ sources under a given distortion criterion. A new notion of sampling rate distortion function is introduced, and is characterized first for the case of fixed-set sampling. Next, for independent random sampling performed without knowledge of the source outputs, it is shown that the sampling rate distortion function is the same regardless of whether or not the decoder is informed of the sequence of sampled sets. Furthermore, memoryless random sampling is considered with the sampler depending on the source outputs and with an informed decoder. It is shown that deterministic sampling, characterized by a conditional point-mass, is optimal and suffices to achieve the sampling rate distortion function. For memoryless random sampling with an uninformed decoder, an upper bound for the sampling rate distortion function is seen to possess a similar property of conditional point-mass optimality. It is shown by example that memoryless sampling with an informed decoder can outperform strictly any independent random sampler, and that memoryless sampling can do strictly better with an informed decoder than without.

I. Introduction

The paper introduces a sampling rate-distortion formulation for jointly sampling and compressing multiple sources to reconstruct all of them under a distortion constraint. It characterizes fixed-set and random-sampling regimes, including how sampler structure and decoder knowledge affect performance.

I. Introduction

  • The new sampling rate-distortion function combines source sampling with lossy compression to reconstruct all sources, in a centralized setting without a sparsity assumption.The sampler may depend on observed source values.Source: §I · p. 2
  • For a fixed sampling set, the sampling rate-distortion function is characterized; under probability-of-error distortion, coding the sampled sources followed by maximum a posteriori estimation suffices.The characterization builds on remote source-receiver rate-distortion work.Source: §I · p. 2
  • For independent random sampling, the sampling rate-distortion function is unchanged by whether the decoder knows the sampled-set sequence, a property that does not generally extend to causal samplers.Sampling is independent of source outputs and in time, but need not be identically distributed over time.Source: §I · p. 2
  • With an informed decoder, an output-dependent memoryless sampler is optimally characterized by a conditional point-mass and can strictly outperform any independent random sampler.The point-mass structure reduces the search space for an optimal sampler.Source: §I · p. 2
  • With an uninformed decoder, an upper bound on the sampling rate-distortion function also has an optimal conditional point-mass sampler.This result concerns an upper bound for memoryless random sampling.Source: §I · p. 3

II. Preliminaries

The preliminaries formalize sampling-rate distortion coding for a finite-alphabet, full-support discrete memoryless multiple source, defining k-sample selection, reconstruction, and informed versus uninformed decoding.

Preliminaries

  • The source is an i.i.d. sequence of full-support discrete memoryless source vectors, with finite reproduction alphabets for every component.The source vector has pmf P_XM, and each reproduction alphabet Y_i corresponds to X_i.Source: §II · p. 3
  • A k-random sampler causally selects a random k-sized subset of components at each time and outputs the sampled sets and their source values.Its selection may depend on source observations through the current time and on previously selected sets.Source: §II · p. 3
  • The k-memoryless sampler selects according to the current source vector, while the k-independent sampler selects without dependence on source outputs or past sampled sets.These arise from successively restrictive choices of the sampler’s conditional pmf.Source: §II · p. 3
  • A block code maps the sampler output to a finite message and reconstructs the source sequence under an expected fidelity criterion defined by a single-letter distortion measure.The decoder produces a reproduction sequence in the product reproduction alphabet.Source: §II · p. 3
  • The sampling rate-distortion function is the infimum achievable rate at a distortion level; informed-decoder rates do not exceed uninformed-decoder rates, and both are nonincreasing in k.An informed decoder receives the sampled-set sequence S^n; the uninformed decoder does not.Source: §II · p. 4

III. Results

The results characterize fixed-set and independent-sampling SRDfs, and show that source-dependent sampling with an informed decoder admits optimal conditional point-mass samplers. Example 2 demonstrates strict advantages for informed k-MRS over both k-IRS and uninformed k-MRS.

Results

  • For fixed source distribution, the fixed-set SRDf is the standard rate-distortion function with a modified distortion measure; the fixed-set, k-IRS, and informed k-MRS SRDfs are finite, nonincreasing, convex, and continuous in distortion.The fixed-set characterization uses the sampled components as the source.Source: §III · pp. 4, 8
  • For k-IRS, the SRDf is unchanged by informing the decoder of sampled sets and is the lower convex envelope of fixed-set SRDfs; it can strictly beat the best fixed set for 0.5 < ∆ < 1.318.Strict improvement over the best fixed-set sampler can occur when no single fixed set is uniformly best across distortions.Source: §III · pp. 5–6
  • For informed k-MRS, conditional point-mass sampling suffices for every distortion level, with time-sharing yielding the lower convex envelope of its sampler-specific SRDfs.The time-sharing variable can take at most three values, and the optimal sampler may depend on distortion.Source: §III · pp. 7–8
  • For uninformed k-MRS, the paper gives an upper bound whose optimum is attained by a conditional point-mass sampler, but does not establish a converse or tightness in general.The obstacle is that convexity of the bound in distortion is unresolved; the optimal sampler need not match the informed-decoder optimum.Source: §III · p. 8
  • Allowing time-dependence in strong k-MRS or k-IRS sampling does not improve their respective SRDfs.The strong-sampler SRDfs equal the expressions for informed k-MRS and k-IRS, respectively.Source: §III · p. 8
  • Example 2 shows that informed k-MRS strictly beats k-IRS and, uniformly over feasible distortions, uninformed k-MRS.For the probability-of-error example, the chosen sampler maps source values one-to-one to the sampled set and sampled source; the bound for uninformed k-MRS is tight in this example.Source: §III · pp. 8–9

IV. Proofs · A. Achievability proofs

The achievability proofs build successively from fixed-set sampling to k-IRS and then k-MRS. They use predetermined sampling and concatenated codes for k-IRS, and a deterministic point-mass sampler for informed-decoder k-MRS.

A. Achievability proofs

  • The proof sequence uses fixed-set achievability as a building block for k-IRS and then k-MRS.The uninformed-decoder k-MRS proof rests on the preceding proofs.Source: A. Achievability proofs · pp. 9–10
  • The k-MRS informed-decoder proof establishes that the optimal sampler is deterministic, with PS|XM a conditional point-mass.This structure is then used in the achievability proof of Theorem 4.Source: A. Achievability proofs · p. 10
  • For k-MRS with an uninformed decoder, Theorem 6’s achievability proof rests on the preceding proofs.Source: A. Achievability proofs · p. 10
  • For fixed-set achievability, sampled-source codewords serve as sufficient statistics for MAP reconstruction of unsampled sources.The estimation error matches the reduction in the distortion threshold.Source: A. Achievability proofs · p. 12
  • The k-IRS achievability construction selects sampling sets a priori in proportions PS(A) and concatenates fixed-set codes for each set.This predetermined sequence does not require the decoder to be additionally informed of the sampled sets.Source: A. Achievability proofs · p. 12
  • Theorem 5’s proof establishes equality between q(∆) and r(∆), using their convexity to express them in terms of their Lagrangians.The equality proves the theorem.Source: A. Achievability proofs · p. 14

PU, PS|XMU, PYM|SXSU

The section establishes conditional point-mass optimality for the minimizing sampler and constructs achievability using fixed-set codes for conditional sources, combined by time-sharing.

PU, PS|XMU, PYM|SXSU

  • The minimizing P_S|X_MU is a conditional point mass, and equality holds in (32).The minimization order can be changed without altering the expression.Source: PU, PS|XMU, PYM|SXSU · p. 14
  • Achievability follows by concatenating codes indexed by U, which time-share fixed-set sampling rate-distortion codes for the conditional sources.The proof groups times when each sampling set is selected and uses predetermined-length subsets of typical sampling sequences to accommodate fixed-rate codes.Source: PU, PS|XMU, PYM|SXSU · pp. 14–16
  • Theorem 6’s proof uses an i.i.d. sequence with joint pmf P_SX from (21) and a modified distortion measure.The passage says the details parallel Proposition 1’s achievability proof and are omitted.Source: PU, PS|XMU, PYM|SXSU · p. 16

B. Converse proofs

The converse proofs are unified to highlight their underlying ideas, and proceed from k-MRS through k-IRS to fixed-set sampling.

B. Converse proofs

  • The unified converse proof order follows weakening sampler power: k-MRS, k-IRS, then fixed-set sampling.The presentation begins with Lemma 8 and pertinent technical results before turning to Propositions 1 and 7.Source: B. Converse proofs · p. 16
  • Lemma 8 reduces the needed work to proving that the right-sides of (6), (11), and (15) are convex and continuous.They are already finite-valued and nonincreasing in ∆; convexity of the right-side of (6) on [∆min,A, ∆max] is described as a standard consequence of mutual-information convexity.Source: B. Converse proofs · p. 16

PXA, PYM|XA

This section proves converse bounds for memoryless random, independent random, and fixed-set sampling by reducing block codes to single-letter bounds. It also establishes continuity of the rate-distortion expressions over their distortion ranges.

PXA, PYM|XA

  • The right-sides of (11) and (15) are continuous for ∆ > ∆min, and continuity at ∆ = ∆min also holds for (6), (11), and (15).Continuity at the minimum distortion is supported by (, Lemma 7.2).Source: PXA, PYM|XA · p. 16
  • Proposition 7 effectively implies converse proofs for Theorem 4, Theorem 2, and Proposition 1; specifically, a converse is fashioned for RI ms(∆), while those for Ris(∆) and RA(∆) emerge along the way.Every point in the convex hull of C ⊂ R2 can be represented as a convex combination of at most three points in C, by Carathéodory’s theorem [9].Source: PXA, PYM|XA · pp. 18–19
  • For strong k-IRS codes, restricting the sampler to depend only on past sampled sets gives R ≥ R_i(∆) for ∆ ≥ ∆min.The resulting lower convex envelope equals the k-IRS sampling rate-distortion function, which is already convex in distortion.Source: PXA, PYM|XA · p. 19
  • For fixed-set sampling, convexity of R_A(∆) gives the converse bound R ≥ R_A(∆) for ∆ ≥ ∆min,A.This follows by replacing the sampling law with the indicator that the sampled set equals A.Source: PXA, PYM|XA · p. 19

V. Conclusion

The paper introduces a sampling rate-distortion framework for centralized sampling and lossy reconstruction of a discrete memoryless multiple source, examining fixed-set, independent-random, and memoryless-random sampling. It provides single-letter characterizations for these strategies except memoryless random sampling with an uninformed decoder, where it gives an upper bound.

V. Conclusion

  • The framework studies tradeoffs among sampling strategy, encoding rate, and reconstruction distortion when fixed-size component subsets are sampled and the full source is reconstructed.For independent and memoryless random sampling, the decoder may or may not know the sampling sequence.Source: §V · pp. 19–20
  • Single-letter characterizations are provided for the considered sampling strategies except memoryless random sampling with an uninformed decoder, for which an upper bound is given.Source: §V · p. 20
  • The memoryless-random, uninformed-decoder upper bound can be convexified by time-sharing to become tight, but whether time-sharing is necessary for convexification remains open.Source: §V · p. 20

Appendix

The appendix addresses the minimum of expression (34) with respect to an unspecified quantity.

Appendix

  • The appendix states that it shows the minimum of (34) with respect to an unspecified quantity.Source: Appendix · p. 21

PU, PS|XMU, PYM|SXSU

The supplied passages identify a conditional log-probability term and specify the distribution used for the preceding expectation.

PU, PS|XMU, PYM|SXSU

Related papers

Loading 1607.04143v1…