LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pending

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Convexity, monotonicity, and continuity of finite rate-distortion

Statement

Let the source and reproduction alphabets be finite nonempty sets and let the distortion be finite-valued and nonnegative. The finite-alphabet information rate-distortion function $R (D)$ of Finite-alphabet information rate-distortion function is finite and nonincreasing on $[D_{\min}, \infty)$ , convex there, zero for $D \geq D_{c} : = \min_{\hat{x}} E d (X, \hat{x})$ , and right-continuous at every feasible distortion, including $D_{\min}$ .

Facts & Assumptions

Given: A finite source pmf, finite nonempty reproduction alphabet, and finite nonnegative distortion.

[F1]

Finite-alphabet information rate-distortion function: $R (D)$ minimizes finite mutual information over channels meeting the mean-distortion constraint and is $+ \infty$ when infeasible.

[F2]

Attainment of finite-alphabet rate-distortion minima: feasibility is equivalent to $D \geq D_{\min}$ , and every feasible minimum is attained on a finite channel simplex.

[F3]

Finite log-sum inequality with support and equality cases: the finite log-sum inequality applies to nonnegative finite arrays, with zero terms interpreted by continuity.

[F4]

Finite mutual information: mutual information is the finite joint-KL sum; it is finite for finite alphabets.

[F5]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite KL divergence is nonnegative.

[F6]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: closed bounded subsets of a finite-dimensional Euclidean space are compact.

Proof

1.1F1F2F5given

Feasibility at every $D \geq D_{\min}$ and attainment are given by [F2], so $R (D)$ is finite there; [F5] gives $R (D) \geq 0$ . If $D_{2} \geq D_{1}$ , every channel feasible at $D_{1}$ is feasible at $D_{2}$ , so the infimum cannot increase.

1.2F1F3F4givenalgebra

Fix $D_{0}, D_{1} \geq D_{\min}$ , $t \in [0, 1]$ , and channels $W_{0}, W_{1}$ feasible at those budgets. Set $W = t W_{0} + (1 - t) W_{1}$ ; its distortion is at most $t D_{0} + (1 - t) D_{1}$ . For each $(x, \hat{x})$ , apply [F3] to the two joint-mass terms $t p (x) W_{0} (\hat{x} ∣ x), (1 - t) p (x) W_{1} (\hat{x} ∣ x)$ and corresponding product-marginal terms $t p (x) q_{0} (\hat{x}), (1 - t) p (x) q_{1} (\hat{x})$ , then sum over $(x, \hat{x})$ . The resulting inequality is $I_{W} (X; \hat{X}) \leq t I_{W_{0}} (X; \hat{X}) + (1 - t) I_{W_{1}} (X; \hat{X})$ , in nats and therefore also in bits.

2.1F1F5step 1.1given

The constant channel outputting a minimizer of $E d (X, \hat{x})$ has distortion $D_{c}$ and zero mutual information. For $D \geq D_{c}$ , this channel is feasible, so [F5] gives $R (D) = 0$ .

2.2F1F2step 1.2algebra

Choose minimizing channels at $D_{0}, D_{1}$ by [F2] and use their mixture from step 1.2. The mixture is feasible at $t D_{0} + (1 - t) D_{1}$ and has rate at most $t R (D_{0}) + (1 - t) R (D_{1})$ ; taking the infimum proves convexity.

2.3F1F2F6step 1.1givenalgebra

Fix feasible $D$ and put $D_{k} = D + 1 / (k + 1)$ for $k \geq 0$ . By step 1.1, $R (D_{k})$ increases to a finite limit $L \leq R (D)$ . The finite channel simplex $S$ is closed and bounded, hence compact by [F6]. Distortion $δ (W)$ is linear and bit mutual information $I_{2} (W)$ is continuous on $S$ , by its finite entropy formula and continuity of $- u \ln u$ at zero. Thus $K_{k} : = {W \in S : δ (W) \leq D_{k}, I_{2} (W) \leq L}$ is closed in $S$ and nonempty by [F2], since $R (D_{k}) \leq L$ . These sets are nested. Their intersection is nonempty: otherwise their open complements would cover $S$ , and a finite subcover would force one $K_{k}$ to be empty, a contradiction. A single $W$ in the intersection satisfies $δ (W) \leq D$ and $I_{2} (W) \leq L$ , so $R (D) \leq L$ by [F1]. Hence $R (D_{k}) \to R (D)$ ; monotonicity then gives right-continuity by squeezing $R (D + h)$ between $R (D_{k})$ and $R (D)$ whenever $0 \leq h \leq 1 / (k + 1)$ . No sequence of minimizers is selected.

3.1step 1.1step 2.1step 2.2step 2.3∎

Steps 1.1, 2.1, 2.2, and 2.3 prove every assertion, including the degenerate case $D_{c} = D_{\min}$ , where the constant channel already gives zero on the entire feasible interval.

Depends on

Used by

Dependency tree · two levels

49 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Robert M. Gray, Source Coding Theory, first edition (standard reference, not scraped)
MIT OpenCourseWare 6.441, Chapter 23: Rate-distortion theory (standard reference, not scraped)