Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAre Guessing, Source Coding, and Tasks Partitioning Birds of a Feather?
241
0
0.0
(
0
)
Added by
M. Ashok Kumar
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper establishes a close relationship among the four information theoretic problems, namely Campbell source coding, Arikan guessing, Huleihel et al. memoryless guessing and Bunte and Lapidoth tasks partitioning problems. We first show that the aforementioned problems are mathematically related via a general moment minimization problem whose optimum solution is given in terms of Renyi entropy. We then propose a general framework for the mismatched version of these problems and establish all the asymptotic results using this framework. Further, we study an ordered tasks partitioning problem that turns out to be a generalisation of Arikans guessing problem. Finally, with the help of this general framework, we establish an equivalence among all these problems, in the sense that, knowing an asymptotically optimal solution in one problem helps us find the same in all other problems.
rate research
Read More
We study four problems namely, Campbells source coding problem, Arikans guessing problem, Huieihel et al.s memoryless guessing problem, and Bunte and Lapidoths task partitioning problem. We observe a close relationship among these problems. In all these problems, the objective is to minimize moments of some functions of random variables, and Renyi entropy and Sundaresans divergence arise as optimal solutions. This motivates us to establish a connection among these four problems. In this paper, we study a more general problem and show that R{e}nyi and Shannon entropies arise as its solution. We show that the problems on source coding, guessing and task partitioning are particular instances of this general optimization problem, and derive the lower bounds using this framework. We also refine some known results and present new results for mismatched version of these problems using a unified approach. We strongly feel that this generalization would, in addition to help in understanding the similarities and distinctiveness of these problems, also help to solve any new problem that falls in this framework.
This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikans bounds, they are expressed in terms of the Arimoto-Renyi conditional entropy. Although Arikans bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Renyi entropy, for source codes that allow decoding errors.
Stationary memoryless sources produce two correlated random sequences $X^n$ and $Y^n$. A guesser seeks to recover $X^n$ in two stages, by first guessing $Y^n$ and then $X^n$. The contributions of this work are twofold: (1) We characterize the least achievable exponential growth rate (in $n$) of any positive $rho$-th moment of the total number of guesses when $Y^n$ is obtained by applying a deterministic function $f$ component-wise to $X^n$. We prove that, depending on $f$, the least exponential growth rate in the two-stage setup is lower than when guessing $X^n$ directly. We further propose a simple Huffman code-based construction of a function $f$ that is a viable candidate for the minimization of the least exponential growth rate in the two-stage guessing setup. (2) We characterize the least achievable exponential growth rate of the $rho$-th moment of the total number of guesses required to recover $X^n$ when Stage 1 need not end with a correct guess of $Y^n$ and without assumptions on the stationary memoryless sources producing $X^n$ and $Y^n$.
Analog coding decouples the tasks of protecting against erasures and noise. For erasure correction, it creates an analog redundancy by means of band-limited discrete Fourier transform (DFT) interpolation, or more generally, by an over-complete expansion based on a frame. We examine the analog coding paradigm for the dual setup of a source with erasure side-information (SI) at the encoder. The excess rate of analog coding above the rate-distortion function (RDF) is associated with the energy of the inverse of submatrices of the frame, where each submatrix corresponds to a possible erasure pattern. We give a partial theoretical as well as numerical evidence that a variety of structured frames, in particular DFT frames with difference-set spectrum and more general equiangular tight frames (ETFs), with a common MANOVA limiting spectrum, minimize the excess rate over all possible frames. However, they do not achieve the RDF even in the limit as the dimension goes to infinity.
Depth coding in 3D-HEVC for the multiview video plus depth (MVD) architecture (i) deforms object shapes due to block-level edge-approximation; (ii) misses an opportunity for high compressibility at near-lossless quality by failing to exploit strong homogeneity (clustering tendency) in depth syntax, motion vector components, and residuals at frame-level; and (iii) restricts interactivity and limits responsiveness of independent use of depth information for non-viewing applications due to texture-depth coding dependency. This paper presents a standalone depth sequence coder, which operates in the lossless to near-lossless quality range while compressing depth data superior to lossy 3D-HEVC. It preserves edges implicitly by limiting quantisation to the spatial-domain and exploits clustering tendency efficiently at frame-level with a novel binary tree based decomposition (BTBD) technique. For mono-view coding of standard MVD test sequences, on average, (i) lossless BTBD achieved $times 42.2$ compression-ratio and $-60.0%$ coding gain against the pseudo-lossless 3D-HEVC, using the lowest quantisation parameter $QP = 1$, and (ii) near-lossless BTBD achieved $-79.4%$ and $6.98$ dB Bj{o}ntegaard delta bitrate (BD-BR) and distortion (BD-PSNR), respectively, against 3D-HEVC. In view-synthesis applications, decoded depth maps from BTBD rendered superior quality synthetic-views, compared to 3D-HEVC, with $-18.9%$ depth BD-BR and $0.43$ dB synthetic-texture BD-PSNR on average.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
