PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantization of Binary-Input Discrete Memoryless Channels

Brian M. Kurkoski, Hideki Yagi

arXiv:1107.5637v2cs.ITmath.IT

TL;DR

The paper addresses optimal output quantization for binary-input channels, where prior optimal results were restricted to certain channels or quantizer sizes. It derives optimality conditions using a classification-and-regression-tree result and searches quantizers with dynamic programming. The algorithm finds a mutual-information-maximizing quantizer for arbitrary binary-input DMCs with worst-case complexity proportional to M^3.

  • Problem

    Finding optimal output quantizers for binary-input DMCs beyond prior results restricted to symmetric channels or few quantizer outputs remains an open scope in the paper's account.

    Source: §V · p. 7

  • Method

    The paper derives quantizer optimality conditions from Burshtein et al.'s convex-preimage result for impurity minimization and uses dynamic programming to search quantizers satisfying them.

    Source: §I · p. 1, B. Learning Theory Connections · p. 2, B. Quantizer Design Algorithm · p. 5

  • Results

    For arbitrary binary-input DMCs, the algorithm finds a mutual-information-maximizing quantizer with worst-case complexity proportional to M^3.

    Source: §I · p. 1

  • Takeaways & Limitations

    For a memoryless channel with fixed input distribution, the mutual-information-maximizing quantizer gives the highest achievable communications rate.

    Source: A. Motivation · p. 2

Abstract

from arXiv · show

The quantization of the output of a binary-input discrete memoryless channel to a smaller number of levels is considered. An algorithm which finds an optimal quantizer, in the sense of maximizing mutual information between the channel input and the quantizer output is given. This result holds for arbitrary channels, in contrast to previous results for restricted channels or a restricted number of quantizer outputs. In the worst case, the algorithm complexity is cubic $M^3$ in the number of channel outputs $M$. Optimality is proved using the theorem of Burshtein, Della Pietra, Kanevsky, and N\'adas for mappings which minimize average impurity for classification and regression trees.

I. INTRODUCTION

For binary-input discrete memoryless channels, the paper gives an algorithm to find an output quantizer that maximizes mutual information. The algorithm works for arbitrary such channels and has worst-case complexity proportional to M^3.

I. INTRODUCTION

  • The design problem takes a channel transition law and a quantizer output count K, then seeks a quantizer maximizing I(X; Z).The paper focuses on K < M, since K ≥ M causes no loss in mutual information due to quantization.Source: §I · p. 1, Figure 1 · p. 1
  • For an arbitrary binary-input DMC, the algorithm finds a quantizer maximizing mutual information between X and Z.The quantizer may be stochastic; the theorem establishes that the algorithm finds an optimum.Source: §I · p. 1
  • Worst-case complexity is proportional to M^3, compared with an exponential search over all KM deterministic quantizers in the naive approach.The significance is a cubic-in-M route to an optimum for a problem framed as concave optimization.Source: §I · p. 1
  • The proof applies Burshtein et al.'s result on convex preimages for impurity minimization to derive conditions for optimal channel quantization [2].The resulting optimality conditions are used to prove the Quantizer Design Algorithm's optimality.Source: §I · pp. 1–2

II. RELATIONSHIP WITH PRIOR WORK

The paper motivates mutual-information-maximizing quantization as a way to preserve achievable rate while limiting receiver complexity, and connects the problem to classification-tree impurity minimization.

A. Motivation

  • Receiver algorithms use discretized physical measurements, while circuit complexity grows with quantization levels; with a fixed input distribution, maximizing mutual information gives the highest achievable communications rate.Source: A. Motivation · p. 2
  • The work also cites finite-message-alphabet LDPC decoders and polar-code construction as applications of discrete channel quantization.Source: A. Motivation · p. 2

B. Learning Theory Connections

  • Conditional entropy H(X|Z=z) serves as the impurity φ_z, and minimizing average impurity is equivalent to maximizing mutual information because H(X) is fixed.Source: B. Learning Theory Connections · p. 2
  • Burshtein et al.’s convex-preimage result applies because conditional entropy is in their impurity class; Chou’s K-means-based algorithm finds good, not necessarily optimal, quantizers.Source: B. Learning Theory Connections · p. 2

C. Superficially Related Problems

Although channel quantization resembles other information-theoretic optimization problems, it maximizes mutual information over the quantizer rather than solving their different extrema. Prior quantizer-design work often treats restricted AWGN settings or uses local optimization for larger output alphabets.

C. Superficially Related Problems

D. Information-Theoretic Quantizer Design Criteria

E. Contributions of This Paper

The paper addresses gaps in globally optimal quantization by extending results to arbitrary discrete binary-input channels and quantization levels. Its structural argument establishes deterministic optima and uses separating conditions to support the algorithm’s optimality.

E. Contributions of This Paper

  • Earlier optimality results covered special symmetric-AWGN cases, while locally optimal methods lacked an optimality proof; this paper treats arbitrary discrete channels and quantization levels.Source: E. Contributions of This Paper · p. 3
  • The paper adds an optimality proof and non-uniform-input extension to the uniformly distributed-input algorithm previously presented at ITW 2010.Source: E. Contributions of This Paper · p. 3

III. THE STRUCTURE OF OPTIMAL QUANTIZERS

  • The structural analysis establishes deterministic quantizers, gives a separating-hyperplane condition for general input counts, and specializes it to binary-input channels as Lemma 3.Source: §III · p. 3

A. Restriction to Deterministic Quantizers

B. Separating Hyperplane Condition for Optimality

The separating-hyperplane condition expresses optimal quantization geometrically: channel outputs are represented as points, and distinct quantizer-output regions can be separated by a hyperplane.

B. Separating Hyperplane Condition for Optimality

C. Binary Input J = 2 Case

After sorting binary-channel outputs by their likelihoods, an optimal quantizer can group contiguous outputs into intervals. The boundary condition does not depend on the input distribution.

C. Binary Input J = 2 Case

  • Sorting outputs by their likelihoods permits restricting attention to optimal quantizers whose bins are contiguous intervals.The likelihood-ratio ordering can be expressed using log-likelihood ratios.Source: C. Binary Input J = 2 Case · p. 4
  • The ordering condition for contiguous bins does not depend on the input distribution p_x.Source: C. Binary Input J = 2 Case · p. 5
  • The contiguous-bin condition is necessary for an optimal deterministic quantizer, as shown using the restricted classification result of Coppersmith et al..The passage notes that Lemma 1 alone does not establish this necessity.Source: C. Binary Input J = 2 Case · p. 5
  • Combining adjacent outputs y and y + 1 as a single channel output preserves operational equivalence and mutual information.The combined output uses the sum of the two outputs' likelihoods for each input.Source: C. Binary Input J = 2 Case · p. 5

IV. QUANTIZER DESIGN ALGORITHM

For binary-input DMCs, the Quantizer Design Algorithm maximizes mutual information over ordered quantizer boundaries using dynamic programming. It builds that recursion from partial mutual-information contributions and can return one optimum, or all optimal deterministic quantizers with tie-preserving traceback.

IV. QUANTIZER DESIGN ALGORITHM

  • For binary-input DMCs, the algorithm maximizes mutual information over ordered boundaries, which Lemma 3 makes sufficient for finding a global optimum.The method is explicitly restricted to binary-input channels.Source: §IV · p. 5

A. Partial Mutual Information

  • Partial mutual information assigns each quantizer output its contribution to total mutual information, which is the sum of those contributions.For a bin spanning boundaries a′ to a, its contribution is denoted ι(a′ → a).Source: A. Partial Mutual Information · p. 5

B. Quantizer Design Algorithm

  • Dynamic programming stores S_z(y), the maximum partial mutual information for assigning outputs 1 through y to quantizer outputs 1 through z, and computes it recursively.The recursion conditions on the preceding state; the maximizing state sequence determines the optimal boundaries.Source: B. Quantizer Design Algorithm · p. 5
  • With arbitrary tie-breaking, the algorithm returns one optimal quantizer; preserving ties enables traceback of all optimal deterministic quantizers.The paper sketches that strict likelihood ordering also makes probabilistic quantizers suboptimal.Source: B. Quantizer Design Algorithm · p. 6

C. Complexity

The dynamic-programming algorithm reduces quantizer search from exponential enumeration to polynomial complexity. Its worst-case complexity is proportional to M^3, the number of channel outputs cubed.

C. Complexity

  • The algorithm has worst-case complexity proportional to M^3, compared with exponential complexity for searching all deterministic quantizers.Its more general complexity is K(M − K)^2.Source: C. Complexity · p. 6
  • Precomputing partial mutual information requires a number of computations proportional to M^2.The passage attributes this to the number of possible pairs of boundaries.Source: C. Complexity · p. 6
  • The recursion requires roughly 1/2 K(M − K)^2 add/compare operations, whose maximum over K is proportional to M^3.The maximum occurs at K = 1/3M and is 4/27M^3.Source: C. Complexity · p. 6

D. Example: Finely Quantized Continuous-Output Channel

The algorithm can produce coarse quantizers for continuous-output channels by first finely quantizing their outputs. The discussion identifies extension beyond binary inputs as possible in principle, but requiring new efficient enumeration methods.

D. Example: Finely Quantized Continuous-Output Channel

  • For a continuous-output binary-input AWGN channel, the algorithm is applied after uniform fine quantization, using K = 8 output levels.The example compares underlying DMCs with M = 2000 and M = 30 levels over the interval −2 to +2, with equally likely input symbols.Source: D. Example: Finely Quantized… · p. 6
  • With input-dependent Gaussian noise, the optimal quantizers are asymmetric, and the center boundary increases in the example.The example uses finely quantized DMCs with M = 2000 and M = 31.Source: D. Example: Finely Quantized… · pp. 6–7, Figure 5 · p. 7

V. DISCUSSION

  • The proof applies a classification-tree result because conditional entropy is an impurity function in the relevant class.The result establishes convexity of the optimal mapping's preimage.Source: §V · p. 7
  • The efficient algorithm is restricted to binary inputs, although the underlying theorem could support non-binary quantizer design.A J-input extension requires efficient enumeration of sets formed by separating hyperplanes in J − 1 dimensions.Source: §V · p. 7
  • Joint optimization of the input distribution and quantizer remains open, as does extending the method to other information-theoretic metrics.The paper describes the joint problem as difficult because it is convex-concave.Source: §V · p. 7

APPENDIX

The appendix proves that an optimal quantizer can be deterministic and connects mutual-information maximization to a convex-partition result for average impurity. It then applies that result to posterior-probability vectors.

A. Proof of Lemma 1

  • Mutual information is convex in Qz|y, and optimizing over each simplex admits a vertex solution with Qz|y entries 0 or 1, hence a deterministic optimum.A simplex vertex assigns each channel output to one quantizer output.Source: A. Proof of Lemma 1 · pp. 7–8

B. Minimum Average Impurity

  • The average-impurity result guarantees a no-worse partition of V whose inverse cells are convex.The cited result is attributed to Burshtein et al..Source: B. Minimum Average Impurity · p. 8

C. Proof of Lemma 2

  • For Lemma 2, impurity minimization is equivalent to maximizing I(X; Z), and the transformed quantizer partitions posterior-probability vectors into convex regions.The vectors E[U|Y=y] represent channel outputs in the convex hull used for quantization.Source: C. Proof of Lemma 2 · p. 8

D. Proof of Theorem’s Optimality Part

The proof establishes optimality by showing that an optimal partial quantization contains an optimal solution to a smaller subproblem. It completes the theorem with a complexity proportional to M^3.

D. Proof of Theorem’s Optimality Part

  • The optimal quantizer has ordered boundaries, and the proof frames its partial-quantization objective as a dynamic-programming subproblem.For each prefix of channel outputs, the subproblem maximizes partial mutual information over boundary choices.Source: D. Proof of Theorem’s Optimality Part · p. 8
  • An optimal quantization of an output prefix must remain optimal when used as the prefix of a larger quantization.Otherwise, replacing that prefix with a higher-mutual-information quantization would contradict optimality of the larger quantization.Source: D. Proof of Theorem’s Optimality Part · pp. 8–9
  • The theorem proof is completed with complexity proportional to M^3.The passage refers to an earlier complexity statement while completing the optimality proof.Source: D. Proof of Theorem’s Optimality Part · p. 9
Loading 1107.5637v2…