Monotonicity conjecture for optimal Variant II CPC compositions

About 17 years old · traced to

Let J>1J>1. For a Variant II concentric permutation code, let u=(n1,obreak ⊥)\boldsymbol{\boldsymbol{ u}}=(n_1, obreak\thinspace\bot) be its composition, where nin_i denotes the multiplicity associated with index ii, and let u\boldsymbol{\boldsymbol{ u}} be optimized over admissible compositions. Assume that E[ηℓ]E[\eta_\ell] is convex in ℓ\ell, namely

E[ηℓ+2]−2E[ηℓ+1]+E[ηℓ]≥0,1≤ℓ≤n−2.E\left[\eta_{\ell+2}\right]-2E\left[\eta_{\ell+1}\right]+E\left[\eta_{\ell}\right]\geq 0,\qquad 1\leq \ell\leq n-2.

Monotonicity conjecture. If J>1J>1 and E[ηℓ]E[\eta_\ell] is convex in ℓ\ell, then the optimal multiplicities nin_i for Variant II CPCs increase monotonically with ii.

This conjecture is an analogue of a necessary condition known for optimal compositions of ordinary permutation codes. The paper notes that the convexity condition holds for a large class of source distributions, including Gaussian sources, and that the conjecture would substantially reduce the search space for optimal compositions; only a restricted-codeword version is proved.

References

Primary source

Ha Q. Nguyen, Lav R. Varshney and Vivek K Goyal, “Concentric Permutation Source Codes”, arXiv:0909.0704 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.