We study the problem of leaky private information retrieval (L-PIR), where the amount of privacy leakage is measured by the pure differential privacy parameter, referred to as the leakage ratio exponent. Unlike the previous L-PIR proposed by Samy et al., which is merely a re-allocation of the clean (low-cost) retrieval pattern within the generalized TSC family, we show that the active pure-DP constraints couple adjacent Hamming-weight layers of the random key, which reduces the optimization to a layered problem whose optimum is geometric across these layers. As a result, only cyclic permutations are needed without loss of optimality, and lower-Hamming weight keys should be assigned higher probabilities. This new scheme provides a significant improvement, leading to anO(logK) leakage ratio exponent with fixed download costD, in contrast to the previous art that only achieves a Θ(K) exponent, whereKis the number of messages.

With the strengths of both deep learning and kernel methods like Gaussian Processes (GPs), Deep Kernel Learning (DKL) has gained considerable attention in recent years. From the computational perspective, however, DKL becomes challenging when the input dimension of the GP layer is high. To address this challenge, we propose the Deep Additive Kernel (DAK) model, which incorporates i) an additive structure for the last-layer GP; and ii) induced prior approximation for each GP unit. This naturally leads to a last-layer Bayesian neural network (BNN) architecture. The proposed method enjoys the interpretability of DKL as well as the computational advantages of BNN. Empirical results show that the proposed approach outperforms state-of-the-art DKL methods in both regression and classification tasks.

Linguistic steganography aims to conceal information within natural language text without being detected. An effective steganography approach should encode the secret message into a minimal number of language tokens while preserving the natural appearance and fluidity of the stego-texts. We present a new framework to enhance the embedding efficiency of stego-texts generated by modifying the output of a large language model (LLM). The novelty of our approach is in abstracting the sequential steganographic embedding process as a Constrained Markov Decision Process (CMDP), which takes into consideration the long-term dependencies instead of merely the immediate effects. We constrain the solution space such that the discounted accumulative total variation divergence between the selected probability distribution and the original distribution given by the LLM is below a threshold. To find the optimal policy, we first show that the functional optimization problem can be simplified to a convex optimization problem with a finite number of variables. A closed-form solution for the optimal policy is then presented to this equivalent problem. It is remarkable that the optimal policy is deterministic and resembles water-filling in some cases. The solution suggests that usually adjusting the probability distribution for the state that has the least random transition probability should be prioritized, but the choice should be made by taking into account the transition probabilities at all states instead of only the current state.

It is well known that separation between lossy source coding and channel coding is asymptotically optimal under classical additive distortion measures. Recently, coding under a new class of quality considerations, often referred to as perception or realism, has attracted significant attention due to its close connection to neural generative models and semantic communications. In this work, we revisit source-channel separation under the consideration of distortion-perception. We show that when the perception quality is measured on the block level, i.e., in the strong sense, the optimality of separation still holds when common randomness is shared between the encoder and the decoder; however, separation is no longer optimal when such common randomness is not available. In contrast, when the perception quality is the average per-symbol measure, i.e., in the weak sense, the optimality of separation holds regardless of the availability of common randomness.

We study the problem of leaky private information retrieval (L- PIR), where the amount of privacy leakage is measured by the pure differential privacy parameter, referred to as the leakage ratio exponent. Unlike the previous L-PIR scheme proposed by Samy et al., which only adjusted the probability allocation to the clean (low-cost) retrieval pattern, we optimized the probabilities assigned to all the retrieval patterns jointly. It is demonstrated that the optimal probability distribution of the retrieval pattern is quite sophisticated and has a layered structure: the retrieval associated with the random key values of lower Hamming weights should be assigned higher probabilities. This new scheme provides a significant improvement, leading to an$O(\log K)$leakage ratio exponent with fixed download cost$D$and number of servers$N$, in contrast to the previous art that only achieves a$\theta(K)$exponent, where$K$is the number of messages.

The study of multimodality has garnered significant interest in fields where analyzing interactions among multiple information sources can enhance predictive modeling, data fusion, and interpretability. Partial information decomposition (PID) has emerged as a useful information-theoretic framework to quantify the degree to which individual modalities independently, redundantly, or synergistically convey information about a target variable. However, existing PID methods depend on optimizing over a joint distribution constrained by estimated pairwise probability distributions, which are costly and inaccurate for continuous and high-dimensional modalities. Our first key insight is that the problem can be solved efficiently when the pairwise distributions are multivariate Gaussians, and we refer to this problem as Gaussian PID (GPID). We propose a new gradient-based algorithm that substantially enhances computational efficiency for GPID based on an alternative formulation of the underlying optimization problem. To generalize the applicability to non-Gaussian data, we learn information-preserving encoders to transform random variables of arbitrary input distributions into pairwise Gaussian random variables. Along the way, we resolved an open problem regarding the optimality of joint Gaussian solutions for GPID. Empirical validation on diverse synthetic examples demonstrates that our proposed method provides more accurate and efficient PID estimates than existing baselines. We further evaluate on a series of large-scale multimodal benchmarks to show its utility in real-world applications of quantifying PID in multimodal datasets and selecting high-performing models.

We study the problem of weakly private information retrieval (PIR) when there is heterogeneity in servers’ trustworthiness under the maximal leakage (Max-L) metric and mutual information (MI) metric. A user wishes to retrieve a desired message from N non-colluding servers efficiently, such that the identity of the desired message is not leaked in a significant manner; however, some servers can be more trustworthy than others. We propose a code construction for this setting and optimize the probability distribution for this construction. For the Max-L metric, it is shown that the optimal probability allocation for the proposed scheme essentially separates the delivery patterns into two parts: a completely private part that has the same download overhead as the capacity-achieving PIR code, and a non-private part that allows complete privacy leakage but has no download overhead by downloading only from the most trustful server. The optimal solution is established through a sophisticated analysis of the underlying convex optimization problem and a reduction between the homogeneous setting and the heterogeneous setting. For the MI metric, the homogeneous case is studied first for which the code can be optimized with an explicit probability assignment, while a closed-form solution becomes intractable for the heterogeneous case. Numerical results are provided for both cases to corroborate the theoretical analysis.

We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an $\epsilon$-Nash equilibrium with time complexity $O(\frac{1}{\epsilon^2})$, given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with $\tilde{O}(\frac{1}{\min_{s,a}\pi(a|s)\delta})$ sample complexity to achieve $\delta$ approximation error w.r.t the $\ell_2$ norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of $\tilde{O}(1/\epsilon^5)$. Simulation studies are presented.

Generating 3D graphs of symmetry-group equivariance is of intriguing potential in broad applications from machine vision to molecular discovery. Emerging approaches adopt diffusion generative models (DGMs) with proper re-engineering to capture 3D graph distributions. In this paper, we raise an orthogonal and fundamental question of in what (latent) space we should diffuse 3D graphs. ❶ We motivate the study with theoretical analysis showing that the performance bound of 3D graph diffusion can be improved in a latent space versus the original space, provided that the latent space is of (i) low dimensionality yet (ii) high quality (i.e., low reconstruction error) and DGMs have (iii) symmetry preservation as an inductive bias. ❷ Guided by the theoretical guidelines, we propose to perform 3D graph diffusion in a low-dimensional latent space, which is learned through cascaded 2D–3D graph autoencoders for low-error reconstruction and symmetry-group invariance. The overall pipeline is dubbed latent 3D graph diffusion. ❸ Motivated by applications in molecular discovery, we further extend latent 3D graph diffusion to conditional generation given SE(3)-invariant attributes or equivariant 3D objects. ❹ We also demonstrate empirically that out-of-distribution conditional generation can be further improved by regularizing the latent space via graph self-supervised learning. We validate through comprehensive experiments that our method generates 3D molecules of higher validity / drug-likeliness and comparable or better conformations / energetics, while being an order of magnitude faster in training. Codes are released at https://github.com/Shen-Lab/LDM-3DG.

Particle-based Bayesian inference methods by sampling from a partition-free target (posterior) distribution, e.g., Stein variational gradient descent (SVGD), have attracted significant attention. We propose a path-guided particle-based sampling (PGPS) method based on a novel Log-weighted Shrinkage (LwS) density path linking an initial distribution to the target distribution. We propose to utilize a Neural network to learn a vector field motivated by the Fokker-Planck equation of the designed density path. Particles, initiated from the initial distribution, evolve according to the ordinary differential equation defined by the vector field. The distribution of these particles is guided along a density path from the initial distribution to the target distribution. The proposed LwS density path allows for an efficient search of modes of the target distribution while canonical methods fail. We theoretically analyze the Wasserstein distance of the distribution of the PGPS-generated samples and the target distribution due to approximation and discretization errors. Practically, the proposed PGPS-LwS method demonstrates higher Bayesian inference accuracy and better calibration ability in experiments conducted on both synthetic and real-world Bayesian learning tasks, compared to baselines, such as SVGD and Langevin dynamics, etc.

Foundational Large Language Models (LLMs) such as GPT-3.5-turbo allow users to refine the model based on newer information, known as "fine-tuning". This paper leverages this ability to analyze AC-DC converter behaviors, focusing on the ripple current in DC-link capacitors. Capacitors degrade faster under high ripple currents, complicating life monitoring and necessitating preemptive replacements. Using minimal invasive noisy hardware measurements from a full bridge rectifier and 90W Power Factor Correction (PFC) boost converter, an LLM-based models to predict ripple content in DC-link currents was developed which demonstrated the LLMs’ ability for near-accurate predictions. This study also highlights data requirements for precise nonlinear power electronic circuit parameter predictions to predict component degradation without any additional sensors. Furthermore, the proposed framework could be extended to any non-linear function mapping problem as well as estimating the capacitor Equivalent Series Resistance (ESR).

We study the problem of weakly private information retrieval (PIR) when there is heterogeneity in servers' trustfulness under the maximal leakage (Max-L) metric. A user wishes to retrieve a desired message from$N$non-colluding servers efficiently, such that the identity of the desired message is not leaked in a significant manner; however, some servers can be more trustworthy than others. We propose a code construction for this setting and optimize the probability distribution for this construction. It is shown that the optimal probability allocation for the proposed scheme essentially separates the delivery patterns into two parts: a completely private part that has the same download overhead as the capacity-achieving PIR code, and a non-private part that allows complete privacy leakage but has no download overhead by downloading only from the most trustful server. The optimal solution is established through a sophisticated analysis of the underlying convex optimization problem, and a reduction between the homogeneous setting and the heterogeneous setting.

We provide a new information-theoretic generalization error bound that is exactly tight (i.e., matching even the constant) for the canonical quadratic Gaussian mean estimation problem. Despite considerable existing efforts in deriving information-theoretic generalization error bounds, applying them to this simple setting where sample average is used as the estimate of the mean value of Gaussian data has not yielded satisfying results. In fact, most existing bounds are order-wise loose in this setting, which has raised concerns about the fundamental capability of information-theoretic bounds in reasoning the generalization behavior for machine learning. The proposed new bound adopts the individual-sample-based approach proposed by Bu et al., but also has several key new ingredients. Firstly, instead of applying the change of measure inequality on the loss function, we apply it to the generalization error function itself; secondly, the bound is derived in a conditional manner; lastly, a reference distribution, which bears a certain similarity to the prior distribution in the Bayesian setting, is introduced. The combination of these components produces a general KL-divergence-based generalization error bound. We further show that although the conditional bounding and the reference distribution can make the bound exactly tight, removing them does not significantly degrade the bound, which leads to a mutual-information-based bound that is also asymptotically tight in this setting.

We study a federated linear bandits model, where $M$ clients communicate with a central server to solve a linear contextual bandits problem with finite adversarial action sets that may be different across clients. To address the unique challenges of **adversarial finite** action sets, we propose the FedSupLinUCB algorithm, which extends the principles of SupLinUCB and OFUL algorithms in linear contextual bandits. We prove that FedSupLinUCB achieves a total regret of $\tilde{O}(\sqrt{d T})$, where $T$ is the total number of arm pulls from all clients, and $d$ is the ambient dimension of the linear model. This matches the minimax lower bound and thus is order-optimal (up to polylog terms). We study both asynchronous and synchronous cases and show that the communication cost can be controlled as $O(d M^2 \log(d)\log(T))$ and $O(\sqrt{d^3 M^3} \log(d))$, respectively. The FedSupLinUCB design is further extended to two scenarios: (1) variance-adaptive, where a total regret of $\tilde{O} (\sqrt{d \sum \nolimits_{t=1}^{T} \sigma_t^2})$ can be achieved with $\sigma_t^2$ being the noise variance of round $t$; and (2) adversarial corruption, where a total regret of $\tilde{O}(\sqrt{dT} + d C_p)$ can be achieved with $C_p$ being the total corruption budget. Experiment results corroborate the theoretical analysis and demonstrate the effectiveness of \alg on both synthetic and real-world datasets.

We study robust reinforcement learning (RL) with the goal of determining a well-performing policy that is robust against model mismatch between the training simulator and the testing environment. Previous policy-based robust RL algorithms mainly focus on the tabular setting under uncertainty sets that facilitate robust policy evaluation, but are no longer tractable when the number of states scales up. To this end, we propose two novel uncertainty set formulations, one based on double sampling and the other on an integral probability metric. Both make large-scale robust RL tractable even when one only has access to a simulator. We propose a robust natural actor-critic (RNAC) approach that incorporates the new uncertainty sets and employs function approximation. We provide finite-time convergence guarantees for the proposed RNAC algorithm to the optimal robust policy within the function approximation error. Finally, we demonstrate the robust performance of the policy learned by our proposed RNAC approach in multiple MuJoCo environments and a real-world TurtleBot navigation task.

We study the effect of reward variance heterogeneity in the approximate top-$m$ arm identification setting. In this setting, the reward for the $i$-th arm follows a $\sigma^2_i$-sub-Gaussian distribution, and the agent needs to incorporate this knowledge to minimize the expected number of arm pulls to identify $m$ arms with the largest means within error $\epsilon$ out of the $n$ arms, with probability at least $1-\delta$. We show that the worst-case sample complexity of this problem is $$\Theta\left( \sum_{i =1}^n \frac{\sigma_i^2}{\epsilon^2} \ln\frac{1}{\delta} + \sum_{i \in G^{m}} \frac{\sigma_i^2}{\epsilon^2} \ln(m) + \sum_{j \in G^{l}} \frac{\sigma_j^2}{\epsilon^2} \text{Ent}(\sigma^2_{G^{r}}) \right), $$where $G^{m}, G^{l}, G^{r}$ are certain specific subsets of the overall arm set $\{1, 2, \ldots, n\}$, and $\text{Ent}(\cdot)$ is an entropy-like function which measures the heterogeneity of the variance proxies. The upper bound of the complexity is obtained using a divide-and-conquer style algorithm, while the matching lower bound relies on the study of a dual formulation.

The study of the fundamental limits of information systems is a central theme in information theory. Both the traditional analytical approach and the recently proposed computational approach have significant limitations, where the former is mainly due to its reliance on human ingenuity, and the latter due to its exponential memory and computational complexity. In this work, we propose a new computational approach to tackle the problem with much lower memory and computational requirements, which can naturally utilize certain intuitions, but also can maintain the strong computational advantage of the existing computational approach. A reformulation of the underlying optimization problem is first proposed, which converts the large linear program to a maximin problem. This leads to an iterative solving procedure, which uses the LP dual to carry over learned evidence between iterations. The key in the reformulated problem is the selection of good information inequalities, with which a relaxed LP can be formed. A particularly powerful intuition is a potentially optimal code construction, and we provide a method that directly utilizes it in the new algorithm. As an application, we derive a tighter outer bound for the storage-repair tradeoff for the (6,5,5) regenerating code problem, which involves at least 30 random variables and is impossible to compute with the previously known computational approach.

We study the problem of weakly private information retrieval (W-PIR), where a user wishes to retrieve a desired message from N non-colluding servers in a way that the privacy leakage regarding the desired message’s identity is less than or equal to a threshold. We propose a new code construction which significantly improves upon the best known result in the literature, based on the following critical observation. In previous constructions, for the extreme case of minimum download, the retrieval pattern is to download the message directly from N−1 servers; however this causes leakage to all these N−1 servers, and a better retrieval pattern for this extreme case is to download the message directly from a single server. The proposed code construction allows a natural transition to such a pattern, and for both the maximal leakage metric and the mutual information leakage metric, significant improvements can be obtained. We provide explicit solutions, in contrast to a previous work by Lin et al., where only numerical solutions were obtained.

We propose a new approach to apply the chaining technique in conjunction with information-theoretic measures to bound the generalization error of machine learning algorithms. Different from the deterministic approach previously proposed by Asadi et al., which is based on hierarchical partitions of a bounded metric space, we propose a stochastic approach that replaces the hierarchical partitions with an abstract Markov model inspired by successive refinement source coding in information theory. Our approach has three main benefits over the deterministic approach: 1) applicability to unbounded metric space, 2) feasibility of subsequent analysis to yield explicit bounds, and 3) increased flexibility for optimization. We illustrate these benefits through the problems of estimating Gaussian mean and phase retrieval. For the problem of estimating Gaussian mean, we derive a chaining bound that provides an order-wise improvement over previous results; for the problem of phase retrieval, we construct a stochastic chain that allows optimization over the chaining parameter.

We study policy optimization for Markov decision processes (MDPs) with multiple reward value functions, which are to be jointly optimized according to given criteria such as proportional fairness (smooth concave scalarization), hard constraints (constrained MDP), and max-min trade-off. We propose an Anchor-changing Regularized Natural Policy Gradient (ARNPG) framework, which can systematically incorporate ideas from well-performing first-order methods into the design of policy optimization algorithms for multi-objective MDP problems. Theoretically, the designed algorithms based on the ARNPG framework achieve $\tilde{O}(1/T)$ global convergence with exact gradients. Empirically, the ARNPG-guided algorithms also demonstrate superior performance compared to some existing policy gradient-based approaches in both exact gradients and sample-based scenarios.

The increasing prevalence of massive datasets makes the outsourcing of storage and computation tasks to distributed servers a necessity. This raises a number of concerns regarding the security and integrity of stored information, the privacy of accessing desired information, the communication overhead of distributed systems, the latency, reliability, and complexity of distributed computing, and privacy in distributed training and learning systems. Recent breakthroughs from coding, communication, and information-theoretic perspectives have opened up exciting new research avenues for these topics. There are many theoretical and practical open problems. This Special Issue is dedicated to communication theory, coding theory, information theory, signal processing, and networking aspects of privacy in information retrieval, privacy in coded computing over distributed servers, and privacy in distributed learning.

Most of our lives are conducted in the cyberspace. The human notion of privacy translates into a cyber notion of privacy on many functions that take place in the cyberspace. This article focuses on three such functions: how to privately retrieve information from cyberspace (privacy in information retrieval), how to privately leverage large-scale distributed/parallel processing (privacy in distributed computing), and how to learn/train machine learning models from private data spread across multiple users (privacy in distributed (federated) learning). The article motivates each privacy setting, describes the problem formulation, summarizes breakthrough results in the history of each problem, and gives recent results and discusses some of the major ideas that emerged in each field. In addition, the cross-cutting techniques and interconnections between the three topics are discussed along with a set of open problems and challenges.

Cauchy Reed-Solomon (CRS) codes are a class of erasure-resilient codes which are widely applicable in modern data storage systems. Several existing works have considered making the coding process of the extended CRS codes more efficient. It has been found that this efficiency is highly dependent on the underlying Cauchy coding matrices, particularly, the density of the associated bitmatrices. In this work, we revisit the problem of optimizing the coding bitmatrices, and propose three approaches aiming to find the bitmatrices with the lowest density in this context, namely a mixed integer linear programming approach, a local optimal algorithm with heuristic perturbation, and a branch-and-bound algorithm. Experimental results show that the proposed approaches are able to find bitmatrices with significantly lower density than those found using existing techniques. Moreover, the local optimal algorithm with heuristic perturbation is surprisingly efficient in finding good solutions under constrained computation time.

We propose an information-theoretic bound on the generalization error based on a combination of the error decomposition technique of Buet al.and the conditional mutual information (CMI) construction of Steinke and Zakynthinou. In a previous work, Haghifamet al.proposed a different bound combining the two aforementioned techniques, which we refer to as the conditional individual mutual information (CIMI) bound. However, in a simple Gaussian setting, both the CMI and the CIMI bounds are order-wise worse than that by Buet al.This observation motivated us to propose the bound, which overcomes this issue by reducing the conditioning terms in the conditional mutual information. In the process of establishing this bound, a conditional decoupling lemma is established, which also leads to a meaningful dichotomy and comparison among these information-theoretic bounds. As an application of the proposed bound, we analyze the noisy and iterative stochastic gradient Langevin dynamics and provide an upper bound on its generalization error.

We propose a new information-theoretic bound on generalization error based on a combination of the error decomposition technique of Bu et al. and the conditional mutual information (CMI) construction of Steinke and Zakynthinou. In a previous work, Haghifam et al. proposed a different bound combining the two aforementioned techniques, which we refer to as the conditional individual mutual information (CIMI) bound. However, in a simple Gaussian setting, both the CMI and the CIMI bounds are order-wise worse than that by Bu et al.. This observation motivated us to propose the new bound, which overcomes this issue by reducing the conditioning terms in the conditional mutual information. In the process of establishing this bound, a conditional decoupling lemma is established, which also leads to a meaningful dichotomy and comparison among these information-theoretic bounds.

In the conventional robust$T$-colluding private information retrieval (PIR) system, the user needs to retrieve one of the possible messages while keeping the identity of the requested message private from any$T$colluding servers. Motivated by the possible heterogeneous privacy requirements for different messages, we consider the ($N, T_{1}: K_{1}, T_{2}: K_{2}$) two-level PIR system, where$K_{1}$messages need to be retrieved privately against$T_{1}$colluding servers, and all the messages need to be retrieved privately against$T_{2}$colluding servers where$T_{2}\leq T_{1}$. We obtain a lower bound to the capacity by proposing a novel coding scheme, namely the non-uniform successive cancellation scheme. A capacity upper bound is also derived. The gap between the upper bound and the lower bound is analyzed, and shown to vanish when$T_{1}=T_{2}$.

We address the issue of safety in reinforcement learning. We pose the problem in an episodic framework of a constrained Markov decision process. Existing results have shown that it is possible to achieve a reward regret of $\tilde{\mathcal{O}}(\sqrt{K})$ while allowing an $\tilde{\mathcal{O}}(\sqrt{K})$ constraint violation in $K$ episodes. A critical question that arises is whether it is possible to keep the constraint violation even smaller. We show that when a strictly safe policy is known, then one can confine the system to zero constraint violation with arbitrarily high probability while keeping the reward regret of order $\tilde{\mathcal{O}}(\sqrt{K})$. The algorithm which does so employs the principle of optimistic pessimism in the face of uncertainty to achieve safe exploration. When no strictly safe policy is known, though one is known to exist, then it is possible to restrict the system to bounded constraint violation with arbitrarily high probability. This is shown to be realized by a primal-dual algorithm with an optimistic primal estimate and a pessimistic dual update.

Caching is a technique to reduce the communication load in peak hours by prefetching contents during off-peak hours. An information theoretic framework for coded caching was introduced by Maddah-Ali and Niesen in a recent work, where it was shown that significant improvement can be obtained compared to uncoded caching. Considerable efforts have been devoted to identify the precise information theoretic fundamental limits of the coded caching systems, however the difficulty of this task has also become clear. One of the reasons for this difficulty is that the original coded caching setting allows all possible multiple demand types during delivery, which in fact introduces tension in the coding strategy. In this paper, we seek to develop a better understanding of the fundamental limits of coded caching by investigating systems with certain demand type restrictions. We first consider the canonical three-user three-file system, and show that, contrary to popular beliefs, the worst demand type is not the one in which all three files are requested. Motivated by these findings, we focus on coded caching systems where every file must be requested by at least one user. A novel coding scheme is proposed, which can provide new operating points that are not covered by any previously known schemes.

We analyze the performance of Borda counting algorithm on noisy m-wise ranking data to accurately select the top-k items from a total of n items. This generalizes a previous result of a similar nature reported by Shah et al. on the noisy pairwise comparison data. We show that the associated score separation Δkbetween the k-th item and the (k+1)-th item plays an important role: if Δkis greater than a threshold depending on (n, k) and the scoring system in Borda counting, then the top-k selection is accurate asymptotically almost surely; if Δkis below a threshold, then the top-k selection will not be accurate with at least a constant probability. This separation between the two thresholds depends on m and the scoring systems in the Borda counting procedure.

We consider information leakage to the user in private information retrieval (PIR) systems. Information leakage can be measured in terms of individual message leakage or total leakage. Individual message leakage, or simply individual leakage, is defined as the amount of information that the user can obtain on any individual message that is not being requested, and the total leakage is defined as the amount of information that the user can obtain about all the other messages except the one being requested. In this work, we characterize the tradeoff between the minimum download cost and the individual leakage, and that for the total leakage, respectively. Coding schemes are proposed to achieve these optimal tradeoffs, which are also shown to be optimal in terms of the message size. We further characterize the optimal tradeoff between the minimum amount of common randomness and the total leakage. Moreover, we show that under individual leakage, common randomness is in fact unnecessary when there are more than two messages.

We consider the fundamental tradeoff between the storage cost and the download cost in private information retrieval systems, without any explicit structural restrictions on the storage codes, such as maximum distance separable codes or uncoded storage. Two novel outer bounds are provided, which have the following implications. When the messages are stored without any redundancy across the databases, the optimal PIR strategy is to download all the messages; on the other hand, for PIR capacity-achieving codes, each database can reduce the storage cost, from storing all the messages, by no more than one message on average. We then focus on the two-message two-database case, and show that a stronger outer bound can be derived through a novel pseudo-message technique.

In the canonical private information retrieval (PIR) problem, a user retrieves a message from a set of databases without allowing any individual database to obtain any knowledge regarding the identity of the requested message. This perfect privacy requirement may be too stringent in many cases, and the user may only wish to control the amount of the privacy leakage to below a given level, and in return, can retrieve the message at a lower communication cost. In this work, we study the tradeoff between the download cost and the amount of privacy leakage under the maximal leakage metric. A new scheme is proposed by allowing a more flexible query structure and probability distributions in a code previously proposed by Tian et al., which utilized a fixed query set and a uniform distribution. It is shown that the optimal probability distribution in the proposed scheme has a particularly simple structure, which leads to a closed form achievability bound for the optimal tradeoff between the download cost and the privacy leakage. The proposed scheme includes several known schemes, such as those proposed by Lin et al., by Samy et al., and by Jia, as special cases.

Time synchronization is crucial for the safe and reliable operation of the fifth generation (5G) network, especially for applications requiring ultra-reliable low-latency data transmissions. The time synchronization problem, however, becomes increasingly challenging in high-mobility scenarios because the channel conditions, e.g., the multipath delay spread may vary rapidly. While there exist numerous works on the design of efficient channel decoding algorithms, decoding linear codes such as polar codes in the presence of synchronization errors is a less-explored topic. In this paper, we aim to fill this void and develop a systemic approach to decode general binary linear codes over binary symmetric channels with synchronization errors in which the lack of synchronization is modeled as the deletion channel model. The maximum likelihood (ML) decoding problem for binary linear codes over deletion channels is first formulated as a nonlinear optimization problem, in which a set of linear constraints are employed to characterize the input-output relationship of a deletion channel. It turns out that both the objective function and the constraints of this optimization problem are nonlinear, which poses significant challenges against the design of efficient decoding algorithms. As a remedy, we first replace the nonlinear objective function of this optimization problem via a lower bound. And we prove this lower bound is a linear function in the special case that the input is binary. We then apply the linear programming (LP) relaxation approach to obtain an approximate solution to the proposed nonlinear optimization problem. An adaptive branch-and-cut decoding algorithm has also been developed by making use of the ML-certificate property of the LP decoder for deletion channel. It is seen through simulation studies that the proposed decoding algorithm can achieve close-to-optimal bit error rate (BER) decoding performance at moderate computational complexity.

We consider information leakage to the user in private information retrieval (PIR) systems. Information leakage can be measured in terms of individual message leakage or total leakage. Individual message leakage, or simply individual leakage, is defined as the amount of information that the user can obtain on any individual message that is not being requested, and the total leakage is defined as the amount of information that the user can obtain about all the other messages except the one being requested. In this work, we characterize the tradeoff between the minimum download cost and the individual leakage, and that for the total leakage, respectively. Coding schemes are proposed to achieve these optimal tradeoffs, which are also shown to be optimal in terms of the message size. We further characterize the optimal tradeoff between the minimum amount of common randomness and the total leakage. Moreover, we show that under individual leakage, common randomness is in fact unnecessary when there are more than two messages.

Multilevel diversity coding is a classical coding model where multiple mutually independent information messages are encoded, such that different reliability requirements can be afforded to different messages. It is well known that superposition coding, namely separately encoding the independent messages, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). In the current paper, we consider weakly secure SMDC where security constraints are injected on each individual message, and provide a complete characterization of the conditions under which superposition coding is sum-rate optimal. Two joint coding strategies, which lead to rate savings compared to superposition coding, are proposed, where some coding components for one message can be used as the encryption key for another. By applying different variants of Han's inequality, we show that the lack of opportunity to apply these two coding strategies directly implies the optimality of superposition coding. It is further shown that under a set of particular security constraints, one of the proposed joint coding strategies can be used to construct a code that achieves the optimal rate region.

We consider the fundamental tradeoff between the storage cost and the download cost in private information retrieval (PIR) systems, without any explicit structural restrictions on the storage codes, such as maximum distance separable codes or uncoded storage. Our focus in this work is on the two extreme points: the point when the storage cost is minimal, and the point when the download cost is minimal. Two novel outer bounds are provided, which have the following implications at these two extreme points. When the messages are stored without any redundancy across the databases, the optimal PIR strategy is to download all the messages; on the other hand, for PIR capacity-achieving codes, each database can reduce the storage cost, from storing all the messages, by no more than one message on average. To better understand the second extreme point, we then focus on the two-message two-database case, and show that a stronger outer bound can be derived through a novel pseudo-message technique. This stronger outer bound suggests that a precise characterization of the storage-download tradeoff may require more sophisticated bounding techniques.

We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from N non-colluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from accessing the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization factor) is significantly, in fact exponentially, lower than previously believed. More precisely, when K > T/ gcd(N, T) where K is the total number of messages in the system and gcd(·, ·) means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as lcm(N - T, T), where lcm(·, ·) means the least common multiple. On the other hand, when K is small, we show that it is in fact possible to design codes with a message size even smaller than lcm(N - T, T).

Various techniques have been proposed in the literature to improve erasure code computation efficiency, including optimizing bitmatrix design and computation schedule, common XOR (exclusive-OR) operation reduction, caching management techniques, and vectorization techniques. These techniques were largely proposed individually, and, in this work, we seek to use them jointly. To accomplish this task, these techniques need to be thoroughly evaluated individually and their relation better understood. Building on extensive testing, we develop methods to systematically optimize the computation chain together with the underlying bitmatrix. This led to a simple design approach of optimizing the bitmatrix by minimizing a weighted computation cost function, and also a straightforward coding procedure—follow a computation schedule produced from the optimized bitmatrix to apply XOR-level vectorization. This procedure provides better performances than most existing techniques (e.g., those used in ISA-L and Jerasure libraries), and sometimes can even compete against well-known but less general codes such as EVENODD, RDP, and STAR codes. One particularly important observation is that vectorizing the XOR operations is a better choice than directly vectorizing finite field operations, not only because of the flexibility in choosing finite field size and the better encoding throughput, but also its minimal migration efforts onto newer CPUs.

We propose a new capacity-achieving code for the private information retrieval (PIR) problem, and show that it has the minimum message size (being one less than the number of servers) and the minimum upload cost (being roughly linear in the number of messages) among a general class of capacity-achieving codes, and in particular, among all capacity-achieving linear codes. Different from existing code constructions, the proposed code is asymmetric, and this asymmetry appears to be the key factor leading to the optimal message size and the optimal upload cost. The converse results on the message size and the upload cost are obtained by a strategic analysis of the information theoretic proof of the PIR capacity, from which a set of critical properties of any capacity-achieving code in the code class of interest is extracted.

We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from N non-colluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from reading the contents of any T databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization level) is significantly, in fact exponentially, lower than previously believed. More precisely, when K > T/ gcd(N, T) where K is the total number of message in the system and gcd(·,·) means the greatest common divisor, we establish, by providing both a novel code construction and a matching converse, the minimum message size as lcm(N -T, T), where lcm(·,·) means the least common multiple. On the other hand, when K is small, we show that it is in fact possible to design codes with a message size even smaller than lcm(N - T, T).

Multilevel diversity coding is a classical coding model where multiple mutually independent information messages are encoded, such that different reliability requirements can be afforded to different messages. It is well known that superposition coding, namely separately encoding the independent messages, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999). In the current paper, we consider weakly secure SMDC where secrecy constraints are injected on each individual message, and provide a complete characterization of the conditions under which superposition coding is sum-rate optimal. Two joint coding strategies, which lead to rate savings compared to superposition coding, are proposed, where some coding components for one message can be used as the encryption key for another. By applying different variants of Han's inequality, we show that the lack of opportunities to apply these two coding strategies directly implies the optimality of superposition coding. It is further shown that under a particular security configuration, one of the proposed joint coding strategies can be used to achieve the optimal sum rate.

Caching is a technique to reduce the communication load in peak hours by prefetching contents during off-peak hours. Recently Maddah-Ali and Niesen introduced an information theoretic framework for coded caching, and showed that significant improvement can be obtained compared to uncoded caching. Considerable efforts have been devoted to identify the precise information theoretic fundamental limit of such systems, however the difficulty of this task has also become clear. One of the reasons for this difficulty is that the original coded caching setting allows multiple demand types during delivery, which in fact introduces tension in the coding strategy to accommodate all of them. In this paper, we seek to develop a better understanding of the fundamental limit of coded caching by investigating single demand type systems. We first show that in the canonical three-user three-file systems, such single demand type systems already provide important insights. Motivated by these findings, we focus on systems where the number of users and the number of files are the same, and the demand type is when all files are being requested. A novel coding scheme is proposed, which provides several optimal memory-transmission operating points. Outer bounds for this class of systems are also considered, and their relation with existing bounds is discussed.

We propose a new capacity-achieving code for the private information retrieval (PIR) problem, and show that it has the minimum message size (being one less than the number of servers) and the minimum upload cost (being roughly linear in the number of messages) among a general class of capacity-achieving codes, and in particular, among all capacity-achieving linear codes. Different from existing code constructions, the proposed code is asymmetric, and this asymmetry appears to be the key factor leading to the optimal message size and the optimal upload cost. The converse results on the message size and the upload cost are obtained by an analysis of the information theoretic proof of the PIR capacity, from which a set of critical properties of any capacity-achieving code in the code class of interest is extracted. The symmetry structure of the PIR problem is then analyzed, which allows us to construct symmetric codes from asymmetric ones, yielding a meaningful bridge between the proposed code and existing ones in the literature.

In last ISIT, we reported a generic transformation on maximum distance separable (MDS) codes, which can convert any non-binary (k+r, k) MDS code into another (k+r, k) MDS code such that an arbitrarily chosen r nodes will have the optimal repair bandwidth and the optimal rebuilding access by modifying their data. However, the resultant code thus obtained is no longer in a systematic form if we wish to optimal repair r systematic nodes, and another linear transformation is needed to convert it into one, which may break the inherent simplicity in the decoding and repair procedure. In this work, we propose an alternative generic transformation to solve this issue. In the alternative generic transformation, any r systematic nodes can be optimally repaired with their data keeping unchanged through instead modifying the data on the r parity nodes. As a result, by applying multiple times the two transformations in combination, we can directly obtain systematic MDS codes with optimal rebuilding access for all nodes or for a subset of nodes from any non-binary scalar MDS codes, which have the optimal sub-packatization level as well.

We propose a delayed parity generation technique for maximum distance separable (MDS) storage codes, for two possible applications: the first is to improve the write-speed during data intake where only a subset of the parities are initially produced and stored into the system, and the rest can be produced from the stored data during a later time of lower system load; the second is to provide better adaptivity, where a lower number of parities can be chosen initially in a storage system, and more parities can be produced when the existing ones are not sufficient to guarantee the needed reliability or performance. In both applications, it is important to reduce the data access as much as possible during the delayed parity generation procedure. For this purpose, we first identify the fundamental limit for delayed parity generation through a connection to the well-known multicast network coding problem, then provide an explicit and low-complexity code transformation that is applicable on any MDS codes to obtain optimal codes. The problem we consider is closely related to the regenerating code problem, however the proposed codes are much simpler and have a much smaller subpacketization factor than regenerating codes, and thus our result in fact shows that blindly adopting regenerating codes in these two settings is unnecessary and wasteful.

The problem of multilevel diversity coding with secure regeneration is revisited. Under the assumption that the eavesdropper can access the repair data for all compromised storage nodes, Shao el al. provided a precise characterization of the minimum-bandwidth-regeneration (MBR) point of the achievable normalized storage-capacity repair-bandwidth tradeoff region. In this paper, it is shown that the MBR point of the achievable normalized storage-capacity repair-bandwidth tradeoff region remains the same even if we assume that the eavesdropper can access the repair data for some compromised storage nodes (type II compromised nodes) but only the data contents of the remaining compromised nodes (type I compromised nodes), as long as the number of type I compromised nodes is no greater than that of type II compromised nodes.

We consider the storage-retrieval rate tradeoff in private information retrieval systems using a Shannon-theoretic approach. Our focus is on the canonical two-message two-database case, for which a coding scheme based on random codebook generation, joint typicality encoding, and the binning technique is proposed. It is first shown that when the retrieval rate is kept optimal, the proposed non-linear scheme uses less storage than the optimal linear scheme. Since the other extreme point corresponding to using the minimum storage requires both messages to be retrieved, the performance through space-sharing of the two points can also be achieved. However, using the proposed scheme, further improvement can be achieved over this simple strategy. Although the random-coding based scheme has a diminishing but nonzero probability of error, the coding error can be eliminated if variable-length codes are allowed. Novel outer bounds are finally provided and used to establish the superiority of the non-linear codes over linear codes.

In order to characterize the fundamental limit of the tradeoff between the amount of cache memory and the delivery transmission rate in multiuser caching systems, various coding schemes have been proposed. These schemes can largely be categorized into two classes, namely uncoded prefetching schemes and coded prefetching schemes. The significant differences in the coding components between the two classes may leave the impression that they are largely unrelated. In this work, we provide a connection between the uncoded prefetching scheme proposed by Maddah Ali and Niesen (and its improved version by Yu et al.) and the coded prefetching scheme proposed by Tian and Chen. A critical observation is first given where a coding component in the Tian-Chen scheme can be replaced by a binary code, which enables us to view the two schemes as the extremes of a more general scheme. An explicit example is given to show that the intermediate operating points of this general scheme can in fact provide new memory-rate tradeoff points previously not known to be achievable in the literature. This new general coding scheme is then presented and analyzed rigorously, which yields a new inner bound to the memory-rate tradeoff for the caching problem. This inner bound does not have a closed form, but can be computed efficiently using a linear program.

In order to characterize the fundamental limit of the tradeoff between the amount of cache memory and the delivery transmission rate of multiuser caching systems, various coding schemes have been proposed in the literature. These schemes can largely be categorized into two classes, namely uncoded prefetching schemes and coded prefetching schemes. While uncoded prefetching schemes in general offer order-wise optimal performance, coded prefetching schemes often have better performance at the low cache memory regime. The significant differences in the coding components between the two classes may leave the impression that they are largely unrelated. In this paper, we provide a connection between the uncoded prefetching scheme proposed by Maddah Ali and Niesen (and its improved version by Yu et al.) and the coded prefetching scheme proposed by Tian and Chen. A critical observation is made, where a coding component in the Tian-Chen scheme can be replaced by a binary code, which enables us to view the two schemes as the extremes of a more general scheme. An explicit example is given to show that the intermediate operating points of this general scheme can provide new memory-rate tradeoff points previously not known to be achievable in the literature. This new general coding scheme is then presented and analyzed rigorously, which yields a new inner bound to the memory-rate tradeoff for the caching problem.

Information inequalities can be used to derive the fundamental limits of information systems. Many information inequalities and problem-specific constraints are linear equalities or inequalities of joint entropies, and thus, outer bounding the fundamental limits can be viewed as and in principle computed through linear programming. However, for many practical engineering problems, the resultant linear program (LP) is very large, rendering such a computational approach almost completely inapplicable in practice. It was shown recently that symmetry can be used to effectively reduce the scale of the LP; however, the precise amount of reduction was not well understood. In this paper, we provide a method to pinpoint this reduction by counting the number of orbits induced by the symmetry on the set of the LP variables and the LP constraints, respectively. The Pólya counting theorem is a powerful tool for such counting task, which requires identifying the cycle index function. We propose a generic three-layer decomposition of the group structures for the quantities in typical information systems to facilitate such a calculation. Three problems are studied using this approach: extremal pairwise cyclically symmetric entropy inequalities, the regenerating code problem, and the caching problem, for which explicit formulas are provided for the cycle indices of the induced permutations.

We propose a generic transformation that can convert any nonbinary (n = k + r, k) maximum distance separable (MDS) code into another (n, k) MDS code over the same field such that: 1) some arbitrarily chosen r nodes have the optimal repair bandwidth and the optimal rebuilding access; 2) for the remaining k nodes, the normalized repair bandwidth and the normalized rebuilding access (over the file size) are preserved; and 3) the sub-packetization level is increased only by a factor of r. Two immediate applications of this generic transformation are then presented. The first application is that we can transform any nonbinary MDS code with the optimal repair bandwidth or the optimal rebuilding access for the systematic nodes only, into a new MDS code which possesses the corresponding repair optimality for all nodes. The second application is that by applying the transformation multiple times, any nonbinary (n, k) scalar MDS code can be converted into an (n, k) MDS code with the optimal repair bandwidth and the optimal rebuilding access for all nodes, or only a subset of nodes, whose sub-packetization level is also optimal.

We propose a new coded caching scheme where linear combinations of the file segments are cached at the users, for the cases where the number of files is no greater than the number of users. When a user requests a certain file in the delivery phase, the other file segments in the cached linear combinations can be viewed as interference. The proposed scheme combines rank-metric codes and maximum distance-separable codes to facilitate the decoding and elimination of the interference and also to simultaneously deliver useful contents to the intended users. The performance of the proposed scheme can be explicitly evaluated, and we show that it can achieve improvement over known memory-rate tradeoff achievable results in the literature in some regime; for certain special cases, the new memory-rate tradeoff points can be shown to be optimal.

We consider the {n, k, d, l) secure exact-repair regenerating code problem, which generalizes the {n, k, d) exact-repair regenerating code problem with the additional constraint that the stored file needs to be kept information-theoretically secure against an eavesdropper, who can access the data transmitted to regenerate a total of l different failed nodes. For all known results on this problem, the achievable tradeoff regions between the normalized storage capacity and repair bandwidth have a single corner point, achieved by a scheme proposed by Shah, Rashmi and Kumar (the SRK point). Since the achievable tradeoff regions of the exact-repair regenerating code problem without any secrecy constraints are known to have multiple corner points in general, these existing results suggest a phase-change-like behavior, i.e., enforcing a secrecy constraint (l ≥ 1) immediately reduces the tradeoff region to one with a single corner point. In this work, we first show that when the secrecy parameter l is sufficiently large, the SRK point is indeed the only corner point of the tradeoff region. However, when £ is small, we show that the tradeoff region can in fact have multiple corner points. In particular, we establish a precise characterization of the tradeoff region for the (7, 6, 6,1) problem, which has exactly two corner points. Thus, a smooth transition, instead of a phase-change-type of transition, should be expected as the secrecy constraint is gradually strengthened.

We propose a generic transformation on maximum distance separable (MDS) codes, which can convert any non-binary (k+r, k) MDS code into another (k+r, k) MDS code with the following properties: 1) An arbitrarily chosen r nodes will have the optimal repair bandwidth and the optimal rebuilding access, 2) the repair bandwidth and rebuilding access efficiencies of all other nodes are maintained as in the code before the transformation, 3) it uses the same finite field as the code before the transformation, and 4) the sub-packetization is increased only by a factor of r. As two immediate applications of this powerful transformation, we show that 1) any non-binary MDS code with optimal repair bandwidth, or optimal rebuilding access, for only systematic nodes can be converted into an MDS code with the corresponding repair optimality for all nodes; and 2) any non-binary scalar MDS code can be converted to an MDS code with optimal repair bandwidth and rebuilding access for all nodes, or to an MDS code with optimal rebuilding access for all systematic nodes and moreover with the optimal sub-packatization, by applying the transformation multiple times.

We consider the (n, k, d, ℓ) secure exact-repair regenerating code problem, which generalizes the (n, k, d) exact-repair regenerating code problem with the additional constraint that the stored file needs to be kept information-theoretically secure against an eavesdropper, who can access the data transmitted to regenerate a total of ℓ different failed nodes. For all known results on this problem, the achievable tradeoff regions between the normalized storage capacity and repair bandwidth have a single corner point, achieved by a scheme proposed by Shah, Rashmi, and Kumar (the SRK point). Since the achievable tradeoff regions of the exact-repair regenerating code problem without any secrecy constraints are known to have multiple corner points in general, these existing results suggest a phasechange-like behavior, i.e., enforcing a secrecy constraint (ℓ ≥ 1) immediately reduces the tradeoff region to one with a single corner point. In this paper, we first show that when the secrecy parameter ℓ is sufficiently large, the SRK point is indeed the only corner point of the tradeoff region. However, when ℓ is small, we show that the tradeoff region can in fact have multiple corner points. In particular, we establish a precise characterization of the tradeoff region for the (7, 6, 6, 1) problem, which has exactly two corner points. Thus, a smooth transition, instead of a phase-change-type of transition, should be expected as the secrecy constraint is gradually strengthened.

We investigate whether uncoded schemes are optimal for Gaussian sources on multiuser Gaussian channels. Particularly, we consider two problems: the first is to send correlated Gaussian sources on a Gaussian broadcast channel where each receiver is interested in reconstructing only one source component (or one specific linear function of the sources) under the mean squared error distortion measure; the second is to send correlated Gaussian sources on a Gaussian multiple-access channel, where each transmitter observes a noisy combination of the sources, and the receiver wishes to reconstruct the individual source components (or individual linear functions) under the mean squared error distortion measure. It is shown that when the channel parameters satisfy certain general conditions, the induced distortion tuples are on the boundary of the achievable distortion region, and thus optimal. Instead of following the conventional approach of attempting to characterize the achievable distortion region, we ask the question whether and how a match can be effectively determined. This decision problem formulation helps to circumvent the difficult optimization problem often embedded in region characterization problems, and it also leads us to focus on the critical conditions in the outer bounds that make the inequalities become equalities, which effectively decouple the overall problem into several simpler sub-problems. Optimality results previously unknown in the literature are obtained using this novel approach. Explicit and novel outer bounds are derived for the two problems as the byproducts of our investigation.

Communication is a bottleneck for many distributed machine learning problems with large data sets. One effective approach is to exchange the set of good classifiers among the learners. The key challenge in such an approach is how to represent the set of good classifiers, which can be viewed as a source coding problem in communication systems. A nonuniform sampling framework is proposed for this source coding problem. A metric that describes the quality of the sampled data for the target hypothesis space is proposed. An optimization problem is formulated by minimizing the upper bound of the proposed metric, and an efficient weight based algorithm is provided to solve the optimization problem. Numerical simulations on synthetic and real world data set show that the learning performance based on the proposed sampling framework is close to the global optimum with high confidence, while requiring less samples than baseline random sampling algorithms.

The notion of orbit-entropy cone is introduced. Specifically, orbit-entropy cone equation is the projection of equation induced by G, where equation is the closure of entropy region for n random variables and G is a permutation group over {0; 1;...; n-1}. For symmetric group Sn(with arbitrary n) and cyclic group Cn(with n ≤ 5), the associated orbit-entropy cones are shown to be characterized by the Shannon type inequalities. Moreover, the extremal pairwise relationship between orbit-entropies is determined completely for partitioned symmetric groups and partially for cyclic groups.

A cyclically symmetric entropy inequality is of the form hO≥chO′, where hOand hO′are two cyclic orbit entropy terms. A computational approach is formulated for bounding the extremal value of c̄, which is denoted by c̄O,O′. For two non-empty orbits O and O′ of a cyclic group, it is said that O dominates O′ if c̄O,O′= 1. Special attention is paid to characterizing such dominance relationship, and a graphical method is developed for that purpose.

We propose a new caching scheme where linear combinations of the file segments are cached at the users, for the scenarios where the number of files is no greater than the number of users. When a user requests a certain file in the delivery phase, the other file segments in the cached linear combinations can be viewed as interferences. The proposed scheme combines rank metric codes and maximum distance separable codes to facilitate the decoding and elimination of these interferences, and also to simultaneously deliver useful contents to the intended users. The performance of the proposed scheme can be explicitly evaluated, and we show that the new scheme can strictly improve existing tradeoff inner bounds in the literature; for certain cases, the new tradeoff points are in fact optimal.

Digital contents distributed storage systems may have different reliability and access delay requirements, and erasure codes with different strengths can provide the best storage efficiency in these systems. At the same time, in such large-scale distributed storage systems, nodes fail on a regular basis, and the contents stored on them need to be regenerated from the data downloaded from the remaining nodes. The efficiency of this repair process is an important factor that affects the overall quality of service. In this paper, we formulate the problem of multilevel diversity coding with regeneration to address these considerations, for which the storage versus repair-bandwidth tradeoff is investigated. We show that the extreme point on the optimal tradeoff curve that corresponds to the minimum possible storage can be achieved by a simple coding scheme, in which contents with different reliability requirements are encoded separately with individual regenerating codes without any mixing. On the other hand, we establish the complete storage-repair-bandwidth tradeoff for the case of four storage nodes, which reveals that codes mixing different contents can, in general, strictly improve the optimal tradeoff over the separate-coding solution.

We investigate whether uncoded schemes are optimal for Gaussian sources on multiuser Gaussian channels. Particularly, we consider two problems: the first is to send correlated Gaussian sources on a Gaussian broadcast channel where each receiver is interested in reconstructing only one source component (or one specific linear function of the sources) under the mean squared error distortion measure; the second is to send correlated Gaussian sources on a Gaussian multiple-access channel, where each transmitter observes a noisy combination of the source, and the receiver wishes to reconstruct the individual source components (or individual linear functions) under the mean squared error distortion measure. It is shown that when the channel parameters match certain general conditions, the induced distortion tuples are on the boundary of the achievable distortion region, and thus optimal. Instead of following the conventional approach of attempting to characterize the achievable distortion region, we ask the question whether and how a match can be effectively determined. This decision problem formulation helps to circumvent the difficult optimization problem often embedded in region characterization problems, and it also leads us to focus on the critical conditions in the outer bounds that make the inequalities become equalities, which effectively decouples the overall problem into several simpler sub-problems.

The digital contents in large distributed storage systems may have different reliability and access delay requirements, and for this reason, erasure codes with different strengths need to be utilized to achieve the best storage efficiency. At the same time, in such large distributed storage systems, nodes fail on a regular basis, and the contents stored on them need to be regenerated and stored on other healthy nodes. We formulate the problem of multilevel diversity coding with regeneration to address these considerations, for which the storage vs. repair-bandwidth tradeoff is investigated. We show that the extreme point on this tradeoff corresponding to the minimum possible storage can be achieved by a simple coding scheme, where contents with different reliability requirements are encoded separately using individual regenerating codes without any mixing. On the other hand, we completely characterize the optimal storage-repairbandwidth tradeoff for the case of four storage nodes, and show that a non-vanishing gap exists between the optimal tradeoffs of mixing and non-mixing solutions.

A polar coding scheme is proposed for the multiple description coding (MDC) problem and is shown to be able to achieve a certain rate pair on the dominant line of the achievable rate region determined by El Gamal and Cover. This scheme is an adaptation of the one developed by ŗaşoğlu et al. for the multiple access channel (MAC) to the MDC setting. The analysis of the proposed scheme contains two new ingredients: 1) a certain MDC-MAC duality and 2) an auxiliary random process that involves both the mutual information and the Bhattacharyya parameter. The decorrelation effect of the polar transform is also investigated.

The problem of sending two correlated vector Gaussian sources over a bandwidth-matched two-user scalar Gaussian broadcast channel is studied in this paper, where each receiver wishes to reconstruct its target source under a covariance distortion constraint. We derive a lower bound on the optimal tradeoff between the transmit power and the achievable reconstruction distortion pair. Our derivation is based on a new bounding technique which involves the introduction of appropriate remote sources. Furthermore, it is shown that this lower bound is achievable by a class of hybrid schemes for the special case, where the weak receiver wishes to reconstruct a scalar source under the mean squared error distortion constraint.

We consider the problem of channel state amplification in a Gaussian channel with additive Gaussian channel states, where the encoder observes noncausally a noisy version of these states. A complete characterization is provided for the minimum reconstruction distortion under a transmitter power constraint, and it is shown that a simple analog scheme with power control is optimal. More precisely, if the power available to the encoder is below certain threshold, the analog scheme using full power is optimal, however, when the power available to the encoder is above that threshold, analog transmission using only a fixed amount of the available power is optimal. Furthermore, the problem of simultaneous message transmission and Gaussian state amplification with noisy observations is studied, for which an inner bound and two nontrivial outer bounds to the optimal tradeoff between the transmission rate and the state reconstruction distortion are provided. The coding scheme underlying the inner bound combines analog signaling and Gelfand-Pinsker coding, where the latter deviates from the operating point of Costa's dirty paper coding. The first outer bound is obtained by extending the channel decomposition technique, while the second outer bound requires a strategic analysis of the covariance matrix of the relevant random variables.

A new class of exact-repair regenerating codes is constructed by stitching together shorter erasure correction codes, where the stitching pattern can be viewed as block designs. The proposed codes have the help-by-transfer property where the helper nodes simply transfer part of the stored data directly, without performing any computation. This embedded error correction structure makes the decoding process straightforward, and in some cases the complexity is very low. We show that this construction is able to achieve performance better than space-sharing between the minimum storage regenerating codes and the minimum repair-bandwidth regenerating codes, and it is the first class of codes to achieve this performance. In fact, it is shown that the proposed construction can achieve a nontrivial point on the optimal functional-repair tradeoff, and it is asymptotically optimal at high rate, i.e., it asymptotically approaches the minimum storage and the minimum repair-bandwidth simultaneously.

The reliability of erasure-coded distributed storage systems, as measured by the mean time to data loss (MTTDL), depends on the repair bandwidth of the code. Repair-efficient codes provide reliability values several orders of magnitude better than conventional erasure codes. Current state of the art codes fix the number of helper nodes (nodes participating in repair) a priori. In practice, however, it is desirable to allow the number of helper nodes to be adaptively determined by the network traffic conditions. In this work, we propose an opportunistic repair framework to address this issue. It is shown that there exists a threshold on the storage overhead, below which such an opportunistic approach does not lose any efficiency from the optimal storage-repair-bandwidth tradeoff; i.e. it is possible to construct a code simultaneously optimal for different numbers of helper nodes. We further examine the benefits of such opportunistic codes, and derive the MTTDL improvement for two repair models: one with limited total repair bandwidth and the other with limited individual-node repair bandwidth. In both settings, we show orders of magnitude improvement in MTTDL. Finally, the proposed framework is examined in a network setting where a significant improvement in MTTDL is observed.

A coding scheme based on polar codes is proposed for the multiple description problem. This scheme is an adaptation of the one developed by ŗaşoğlu et al. for the multiple access channel to the multiple description setting. Specifically, it is shown that the proposed scheme is able to achieve a certain rate pair on the dominant line of the achievable rate region determined by El Gamal and Cover. Due to the dependence between the descriptions, a complication arises in the performance analysis. To resolve this difficulty, a novel technique is introduced which converts dependent descriptions to independent descriptions without affecting the coding rates.

Exact-repair regenerating codes are considered for the case (n,k,d) = (4,3,3), for which a complete characterization of the rate region is provided. This characterization answers in the affirmative the open question whether there exists a non-vanishing gap between the optimal bandwidth-storage tradeoff of the functional-repair regenerating codes (i.e., the cut-set bound) and that of the exact-repair regenerating codes. To obtain an explicit information theoretic converse, a computer-aided proof (CAP) approach based on primal and dual relation is developed. This CAP approach extends Yeung's linear programming (LP) method, which was previously only used on information theoretic problems with a few random variables due to the exponential growth of the number of variables in the corresponding LP problem. The symmetry in the exact-repair regenerating code problem allows an effective reduction of the number of variables, and together with several other problem-specific reductions, the LP problem is reduced to a manageable scale. For the achievability, only one non-trivial corner point of the rate region needs to be addressed in this case, for which an explicit binary code construction is given.

We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal in two general scenarios and is approximately optimal in a third scenario. The two scenarios for which separation is optimal complement each other: the first is when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, but the channels in this network are synchronized, orthogonal, and memoryless point-to-point channels; the second is when the memoryless sources are mutually independent, each of which is to be reconstructed only at one destination within a certain distortion, but the channels are general, including multi-user channels, such as multiple access, broadcast, interference, and relay channels, possibly with feedback. The third scenario, for which we demonstrate approximate optimality of source-channel separation, generalizes the second scenario by allowing each source to be reconstructed at multiple destinations with different distortions. For this case, the loss from optimality using the separation approach can be upper-bounded when a difference distortion measure is taken, and in the special case of quadratic distortion measure, this leads to universal constant bounds.

The demand for cloud storage is exploding as an ever increasing number of enterprises and consumers are storing and processing their data in the cloud. Hence, distributed object storage solutions (e.g., QFS, Swift, HDFS) are becoming very critical components of any cloud infrastructure. These systems are able to offer good reliability by distributing redundant information across a large number of commodity servers, making it possible to achieve 10 nines and beyond with relative ease. One drawback of these systems is that they are usually designed for deployment within a single data center, where node-to-node latencies are small. Geo-replication (i.e., distributing redundant information across data centers) for most open-source storage systems is, to the best of our knowledge, accomplished by asynchronously mirroring a given deployment. Given that geo-replication is critical for ensuring very high degrees of reliability (e.g., for achieving 16 nines), in this work we evaluate how these storage systems perform when they are directly deployed in a WAN setting. To this end, three popular distributed object stores, namely Quantcast-QFS, Swift and Tahoe-LAFS, are considered and tested in a three-wide data center environment and our findings are reported.

Current image quality estimators (QEs) compute a single score to estimate the perceived quality of a single input image. When comparing image quality between two images with such a QE, one only knows which image has a higher score; there is no knowledge about the uncertainty of these scores or what fraction of viewers might actually prefer the image with the lower score. In this paper, we present a Probabilistic Pairwise Preference Predictor (P4) that estimates the probability that one image will be preferred by a random viewer relative to a second image. We train a multilevel Bayesian logistic regression model using results from a large-scale subjective test and present the degree to which various factors influence subjective quality. We demonstrate our model provides well-calibrated estimates of pairwise image preferences using a validation set comprising pairs with 60 reference images outside the training set.

The problem of simultaneous message transmission and state amplification in a Gaussian channel with additive Gaussian state is studied when the sender has imperfect non-causal knowledge of the state sequence. Inner and outer bounds to the rate-state-distortion region are provided. The coding scheme underlying the inner bound combines analog signaling and Gelfand-Pinsker coding, where the latter deviates from the operating point of Costa's dirty paper coding.

Exact-repair regenerating codes are considered for the case (n, k, d) = (4, 3,3), for which a complete characterization of the rate region is provided. This characterization answers in the affirmative the open question whether there exists a non-vanishing gap between the optimal bandwidth-storage tradeoff of the functional-repair regenerating codes (i.e., the cut-set bound) and that of the exact-repair regenerating codes. The converse proof relies on the existence of symmetric optimal solutions. For the achievability, only one non-trivial corner point of the rate region needs to be addressed, for which an explicit binary code construction is given.

A new class of exact-repair regenerating codes is constructed by combining two layers of erasure correction codes together with combinatorial block designs. The proposed codes have the “uncoded repair” property where the nodes participating in the repair simply transfer part of the stored data directly, without performing any computation. The layered error correction structure results in a low-complexity decoding process. An analysis of our coding scheme is presented. This construction is able to achieve better performance than timesharing between the minimum storage regenerating codes and the minimum repair-bandwidth regenerating codes.

We propose a method to accelerate Yang's real-timeO(1) bilateral filtering algorithm, based on the observation that in the original algorithm, some of the computation can be strategically eliminated. To identify such computation, the algorithm steps are analyzed in conjunction with its recursive Gaussian filtering component. By block partitioning the image, the procedure to isolate these unnecessary computation is simplified, and the proposed algorithm only needs to skip some of the image blocks when performing recursive linear filtering. The resultant accelerated algorithm is able to achieve 1.5~5 times speedup, depending on the image statistics and the filtering parameters. The proposed algorithm only marginally degrades the accuracy of the filtering, and the simplicity and small memory footprint of Yang's original algorithm are largely maintained.

Channel coding over arbitrarily permuted parallel channels was first studied by Willems and coworkers. This paper introduces capacity-achieving polar coding schemes for arbitrarily permuted parallel channels where the component channels are memoryless, binary-input, and output-symmetric.

For delay-limited communication over block-fading channels, the difference between the ergodic capacity and the maximum achievable expected rate for coding over a finite number of coherent blocks represents a fundamental measure of the penalty incurred by the delay constraint. This paper introduces a notion of worst-case expected-capacity loss. Focusing on the slow-fading scenario (one-block delay), the worst-case additive and multiplicative expected-capacity losses are precisely characterized for the point-to-point fading channel. Extension to the problem of writing on fading paper is also considered, where both the ergodic capacity and the additive expected-capacity loss over one-block delay are characterized to within one bit per channel use.

Camera calibration is essential for many computer vision and image processing applications. However, this calibration process can be rather time consuming and may require a significant amount of human intervention. Calibration models traditionally employ a calibration grid whose four corner points must be marked by hand on a per-frame basis. The objective of this work is to develop a technique for processing these frames rapidly, with as little human intervention as possible. We propose an algorithm to extract the boundaries of the calibration grid automatically, based on a spectral analysis of HD (high-definition) video frames. The accuracy of the intrinsic parameters estimated using our automatic method is evaluated through comparison with those obtained using a method that requires hand labeling of the corner points.

The problem of sending a set of correlated Gaussian sources over a bandwidth-matched two-user scalar Gaussian broadcast channel is studied in this work, where the strong receiver wishes to reconstruct several source components (i.e., a vector source) under a distortion covariance matrix constraint and the weak receiver wishes to reconstruct a single source component (i.e., a scalar source) under the mean squared error distortion constraint. We provide a complete characterization of the optimal tradeoff between the transmit power and the achievable reconstruction distortion pair for this problem. The converse part is based on a new bounding technique which involves the introduction of an appropriate remote source. The forward part is based on a hybrid scheme where the digital portion uses dirty paper channel code and Wyner-Ziv source code. This scheme is different from the optimal scheme proposed by Tian et al. in a recent work for the scalar-scalar case, which implies that the optimal scheme for the scalar-scalar case is in fact not unique.

We consider the problem of amplifying the channel states in a state-dependent Gaussian channel, where the encoder knows (non-causally) a noisy version of the channel states, i.e., the channel states are hidden under the noise. We provide a complete characterization of the minimum state reconstruction distortion at the decoder under a power constraint at the encoder, and show that a simple analog scheme with power control is optimal. More precisely, if the power available to the encoder is below certain threshold, the analog scheme using full power is optimal, however when the power available to the encoder is above that threshold, analog transmission using only a fixed amount of the available power is optimal. This is in contrast to the state amplification problem considered by Sutivong et al., when the channel states are known perfectly at the encoder for which the full power is always used in the optimal scheme. The converse proof of our result relies on a channel decomposition argument which was not necessary for the simpler case when the channel states are known perfectly.

An encoder, subject to a rate constraint, wishes to describe a Gaussian source under squared-error distortion. The decoder, besides receiving the encoder's description, also observes side information consisting of uncompressed source symbol subject to slow fading and noise. The decoder knows the fading realization but the encoder knows only its distribution. The rate-distortion function that simultaneously satisfies the distortion constraints for all fading states was derived by Heegard and Berger. A layered encoding strategy is considered in which each codeword layer targets a given fading state. When the side-information channel has two discrete fading states, the expected distortion is minimized by optimally allocating the encoding rate between the two codeword layers. For multiple fading states, the minimum expected distortion is formulated as the solution of a convex optimization problem with linearly many variables and constraints. Through a limiting process on the primal and dual solutions, it is shown that single-layer rate allocation is optimal when the fading probability density function is continuous and quasiconcave (e.g., Rayleigh, Rician, Nakagami, and log-normal). In particular, under Rayleigh fading, the optimal single codeword layer targets the least favorable state as if the side information was absent.

It is well-known that optimal digital coding schemes based on the source-channel separation principle suffer from the ``threshold effect" that they are sensitive to the channel condition. If the channel condition is worse than what the code is designed for, the code will fail to decode completely; on the other hand, if the channel condition is in fact better, a digital code can not provide any performance improvement. There exist more robust joint source-channel coding schemes in the literature which can achieve optimal performance for a given channel condition, and at the same time, either being useful when the channel condition is worse, or offering performance improvement when the channel condition is better, but not both. In this paper, we propose several schemes which use hybrid analog and digital signaling to provide benefits in both cases {\em simultaneously}, while still keeping it optimal for a given target channel condition. We further show that compared to the best known optimal schemes designed for the target channel condition, which takes into account only the worse channel condition, or only the better channel condition, these new set of schemes can in fact achieve the same performances for the better and the worse channel conditions simultaneously.

Han's inequality on the entropy rates of subsets of random variables is a classic result in information theory, which often finds its application in multiuser information theoretic problems. In this note, we generalize Han's inequality to allow common components among the random variables, or, in an equivalent manner, to replace the simple random variables in Han's inequality by subsets of random variables. This additional ingredient significantly complicates the matter and the form of the resultant inequalities are rather different from the original Han's inequality. Our proof only relies on the sub-modularity property of the entropy function and the super-modularity property of the conditional entropy function. This new set of inequalities also provides a new link between Han's inequality and the n-way sub-modularity inequality.

A previously designed architecture that endows a wavelength division multiplexed (WDM) optical network with network management capabilities is studied from an information theoretic perspective. The central component of this system is a degraded Σ-interference channel, which combines a multiple access channel and two degraded broadcast channels. Inner and outer bounds for the capacity region are derived for a general discrete memoryless model and a Gaussian model and are shown to provide a complete solution for the symmetric problem. Comparisons are drawn between the coding technique suggested by our information theoretic analysis and the coding method used in a working implementation.

We consider the problem of broadcast with common messages, and focus on the case that the common message rateRA, i.e., the rate of the message intended for all the receivers in the setA, is the same for all the setAof the same cardinality. Instead of attempting to characterize the capacity region of general broadcast channels, we only consider the structure of the capacity region that any broadcast channel should bear. The concept of latent capacity region is useful in capturing these underlying constraints, and we provide a complete characterization of the latent capacity region for the symmetric broadcast problem. The converse proof of this tight characterization relies on a deterministic broadcast channel model. The achievability proof generalizes the familiar rate transfer argument to include more involved erasure correction coding among messages, thus revealing an inherent connection between broadcast with common message and erasure correction codes.

We consider the joint source-channel coding problem of sending a Gaussian source on a K-user Gaussian broadcast channel with bandwidth mismatch. A new outer bound to the achievable distortion region is derived using the technique of introducing more than one additional auxiliary random variable, which was previously used to derive sum-rate lower bound for the symmetric Gaussian multiple description problem. By combining this outer bound with the achievability result based on source-channel separation, we provide approximate characterizations of the achievable distortion region within constant multiplicative factors. Furthermore, we show that the results can be extended to general broadcast channels, and the performance of the source-channel separation based approach is also within the same constant multiplicative factors of the optimum.

We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over bandwidth-matched Gaussian broadcast channels, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient. We further show that in this joint source channel coding setting, the Gaussian scenario is the worst scenario among the sources and channel noises with the same covariances.

In this paper, a three-layer scheme is developed for M-channel multiple description image coding. In each description, a subset of the source samples is encoded in the first layer. In the second layer, the remaining subsets are encoded sequentially by predicting from the already encoded subsets. The third layer encoding is designed to refine the reconstruction when only one description is lost, which is the dominant loss scenario in practice. We first derive the closed-form expressions of the expected distortion of the system for 1-D sources when different numbers of descriptions are received. The scheme is then applied to lapped transform based image coding. Simulation results show that the method outperforms some competing schemes.

We consider the optimality of source-channel separation in networks, and show that such a separation approach is optimal or approximately optimal for a large class of scenarios. More precisely, for lossy coding of memoryless sources in a network, when the sources are mutually independent, and each source is needed only at one destination (or at multiple destinations at the same distortion level), the separation approach is optimal; for the same setting but each source is needed at multiple destinations under a restricted class of distortion measures, the separation approach is approximately optimal, in the sense that the loss from optimum can be upper-bounded. The communication channels in the network are general, including various multiuser channels with finite memory and feedback, the sources and channels can have different bandwidths, and the sources can be present at multiple nodes.

We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over a bandwidth-matched Gaussian broadcast channel, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient.

Providing real-time multimedia services over a besteffort network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. The framework is based on the theoretical modeling where we consider two descriptions and high source coding rate region approximated within small constants. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that we need greater redundancy in the MD streams to protect against such failures. However, one surprising aspect of our study reveals that for large number of users who compete for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

We consider asynchronous Slepian-Wolf coding where the two encoders may not have completely accurate timing information to synchronize their individual block code boundaries, and propose LDPC code design in this scenario. A new information-theoretic coding scheme based on source splitting is provided, which can achieve the entire asynchronous Slepian-Wolf rate region. Unlike existing methods based on source splitting, the proposed scheme does not require common randomness at the encoder and the decoder, or the construction of super-letter from several individual symbols. We then design LDPC codes based on this new scheme, by applying the recently discovered source-channel code correspondence. Experimental results validate the effectiveness of the proposed method.

A low complexityM-channel multiple description coding scheme is developed in this paper, in which each description carries one subset of the input with a higher bit rate and the rest with a lower bit rate. The lower-rate codings in different descriptions are designed to be mutually refinable using staggered scalar quantizers. For correlated sources, a two-rate predictive coding is used in each description. Closed-form expressions of the distortions are derived when different numbers of descriptions are received. The application of the proposed scheme in lapped transform based image coding is also investigated, and the optimal transform is obtained. Experimental results using both 1-D memoryless sources and 2-D images demonstrate the superior performance of the proposed scheme.

We consider the asymmetric multilevel diversity (A-MLD) coding problem, where a set of2K- 1 information sources, ordered in a decreasing level of importance, is encoded intoKmessages (or descriptions). There are2K- 1 decoders, each of which has access to a nonempty subset of the encoded messages. Each decoder is required to reproduce the information sources up to a certain importance level depending on the combination of descriptions available to it. We obtain a single letter characterization of the achievable rate region for the 3-description problem. In contrast to symmetric multilevel diversity coding, source-separation coding is not sufficient in the asymmetric case, and ideas akin to network coding need to be used strategically. Based on the intuitions gained in treating the A-MLD problem, we derive inner and outer bounds for the rate region of the asymmetric Gaussian multiple description (MD) problem with three descriptions. Both the inner and outer bounds have a similar geometric structure to the rate region template of the A-MLD coding problem, and, moreover, we show that the gap between them is constant, which results in an approximate characterization of the asymmetric Gaussian three description rate region.

We propose novel coding schemes for the K-description problem with symmetric rates and symmetric distortion constraints. There are two main new ingredients in these schemes: the first one is akin to the method seen in the well-known butterfly network of network coding literature, and systematic erasure channel codes are applied on certain carefully chosen source coding component; the second approach is built on the quantization splitting technique which was previously proven useful in the Gaussian CEO problem. We first focus on a special case of the three description problem, where any two descriptions are rate-distortion optimal jointly, referred to as the no two description excess rate case. For this special case and the quadratic Gaussian source, we show that the two aforementioned approaches lead to rate-distortion points outside the achievable region based on the source-channel erasure codes, previously proposed by Pradhan, Puri, and Ramchandran. Interestingly, though only the symmetric problem is considered in our work, the proposed schemes in fact benefit from time-sharing several asymmetric rate-distortion points. The insights gained through the no two description excess rate case lead to strategic combination of the new ingredients with the existing coding scheme, yielding new coding schemes for the symmetric K -description problem.

We consider the problem of broadcasting a common message and two individual messages to two users on a product channel of two reversely degraded Gaussian multiple-input multiple-output (MIMO) broadcast channels. Though El Gamal provided a single letter characterization for the general discrete memoryless problem in 1980, this characterization in fact does not include a channel cost constraint, and thus does not apply directly to the Gaussian MIMO setting. We show El GamaFs single letter characterization can indeed be generalized to include channel cost constraints, however special care has to be taken and the characterization holds only with certain class of cost functions. This characterization has an equivalent form, and by utilizing this form, as well as the enhancement technique and an extremal inequality which were only discovered recently, we show that indeed Gaussian codebooks are optimal for this MIMO setting.

We consider asynchronous Slepian-Wolf coding where the two encoders may not have completely accurate timing information to synchronize their individual block code boundaries, and propose LDPC code design in this scenario. A new information-theoretic coding scheme based on source splitting is provided, which can achieve the entire asynchronous Slepian-Wolf rate region. Unlike existing methods based on source splitting, the proposed scheme does not require common randomness at the encoder and the decoder, or constructing super-letter from several individual symbols. Furthermore, we show that linear codes are sufficient for each coding step of this scheme. We subsequently design LDPC codes based on this new scheme, by applying the recently discovered source-channel code correspondence. Experimental results validate the effectiveness of the proposed method.

We consider the problem of broadcast with common messages, and focus on the case that the common message rate RA, i.e., the rate of the message intended for all the receivers in the set A, is the same for all the set A of the same cardinality. Instead of attempting to characterize the capacity region of general broadcast channels, we consider the structure of the capacity region that any broadcast channel should bear. The notion of latent capacity region is required to capture these underlining constraints, and we provide a complete characterization of the latent capacity region for the symmetric broadcast problem. The converse proof of this tight characterization relies on a deterministic broadcast channel model. The achievability proof generalizes the familiar rate transfer argument to include more involved erasure protection coding among messages, thus revealing an inherent connection between broadcast with common message and erasure correction codes.

We consider the joint source-channel coding problem of sending a Gaussian source over a K-user Gaussian broadcast channel with bandwidth mismatch. A new outer bound to the achievable distortion region is derived using the technique of introducing more than one additional auxiliary random variable, which was previously used to derive sum-rate lower bound for the Gaussian multiple description problem. By combining this outer bound with the source-channel-separation-based achievable region, we provide approximate characterizations of the achievable distortion region within constant multiplicative factors.

We propose a new coding scheme for the symmetric K-channel multiple description problem based on the quantization splitting technique, which was previously successfully applied to the Gaussian CEO problem. Unlike a coding scheme we discovered earlier, the scheme proposed here can provide performance better than the one by Pradhan, Puri and Ramchandran in a component-wise manner. Though the method is conceptually straightforward once the analogy to the Gaussian CEO coding scheme is made, the general coding scheme requires constraining the space of the splitting random variables in a much more delicate way. We provide a set of conditions for a specific choice of splitting structure to yield valid splitting random variables.

A new multiple description coding paradigm is proposed by combining the time-domain lapped transform, block level source splitting, linear prediction, and prediction residual encoding. The method provides effective redundancy control and fully utilizes the source correlation. The joint optimization of all system components and the asymptotic performance analysis are presented. Image coding results demonstrate the superior performance of the proposed method, especially at low redundancies.

We consider the problem of multiple description coding for stationary Gaussian sources under the squared error distortion measure. The rate region is characterized for the 2-description case. It is shown that each supporting line of the rate region is achievable with a transform lattice quantization scheme. We show the optimal coding scheme has a natural spectral domain coding interpretation, which yields a reverse water-filling solution with a frequency-dependent water level instead of the flat water level as in the conventional single description case.

Let X , Y , Z be zero-mean, jointly Gaussian random vectors of dimensions nx, ny, and nz, respectively. Let P be the set of random variables W such that W harr Y harr (X, Z) is a Markov string. We consider the following optimization problem:WisinPminI(Y; Z) subject to one of the following two possible constraints: 1) I(X; W|Z) ges RI, and 2) the mean squared error between X and Xcirc = E(X|W, Z) is less than d . The problem under the first kind of constraint is motivated by multiple-input multiple-output (MIMO) relay channels with an oblivious transmitter and a relay connected to the receiver through a dedicated link, while for the second case, it is motivated by source coding with decoder side information where the sensor observation is noisy. In both cases, we show that jointly Gaussian solutions are optimal. Moreover, explicit water filling interpretations are given for both cases, which suggest transform coding approaches performed in different transform domains, and that the optimal solution for one problem is, in general, suboptimal for the other.

We consider multiple description (MD) coding for the Gaussian source withKdescriptions under the symmetric mean-squared error (MSE) distortion constraints, and provide an approximate characterization of the rate region. We show that the rate region can be sandwiched between two polytopes, between which the gap can be upper-bounded by constants dependent on the number of descriptions, but independent of the distortion constraints. Underlying this result is an exact characterization of the lossless multilevel diversity source coding problem: a lossless counterpart of the MD problem. This connection provides a polytopic template for the inner and outer bounds to the rate region. In order to establish the outer bound, we generalize Ozarow's technique to introduce a strategic expansion of the original probability space by more than one random variable. For the symmetric rate case with any number of descriptions, we show that the gap between the upper bound and the lower bound for the individual description rate-distortion function is no larger than 0.92 bit. The results developed in this work also suggest that the ldquoseparationrdquo approach of combining successive refinement quantization and lossless multilevel diversity coding is a competitive one, since its performance is only a constant away from the optimum. The results are further extended to general sources under the MSE distortion measure, where a similar but looser bound on the gap holds.

We present a novel technique for encoding and decoding constant weight binary vectors that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and then analyze its complexity. The complexity depends on the weight of the vector, rather than on the block length as in other algorithms. This approach is advantageous when the weight is smaller than the square root of the block length.

Symmetric multilevel diversity coding was introduced by Roche et al, where a set of K information sources is encoded by K encoders and the decoders reconstruct sources 1,...,k, where k is the number of encoders to which they have access. In this paper, we formulate an asymmetric multilevel diversity coding problem, where a set of 2K- 1 information sources is encoded by K encoders into K streams/descriptions. There are 2K- 1 decoders, each of which has access to a non-empty subset of the encoded messages. The decoders are assigned with ordered levels, and each of them has to decode a subset of the information sources, according to its level, which depends on the set of encoders to which it has access, not just the cardinality. We obtain a single letter characterization of the complete achievable rate region for the 3- description problem. In doing so, we show that it is necessary to jointly encode independent sources (i.e., similar to network coding), and that linear codes are optimal for this problem.

We consider symmetric multiple description coding for the Gaussian source, and provide upper and lower bounds for the individual description rate-distortion function. One of the main contributions of this work is a novel lower bound on the sum rate under symmetric distortion constraints, which yields a lower bound on the individual rate for the symmetric case. Two upper bounds are derived, the first of which is based on successive refinement coding coupled with multilevel diversity coding (SR-MLD), and the second is based on the multi-layer coding scheme proposed in literature. We show that the gaps between the lower bound and the upper bounds are no larger than certain constants depending only on the number of descriptions, but not the distortion constraints. Moreover, regardless of the number of descriptions, the gap between the lower bound and the upper bound using the SR-MLD coding scheme is less than 1.5 bits, and for the other case, the gap is less than 1 bit.

To provide real-time multimedia services over a network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Yet such services are beginning to be deployed over best effort networks. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that greater redundancy in the MD streams is needed to protect against such failures. However, one surprising aspect of our study reveals that for large number of users competing for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

We consider asymmetric multiple description (MD) source coding for Gaussian source under mean squared error distortion constraints, and focus on the three description problem. Inner and outer bounds for the rate region are derived, both of which can be represented as the intersection of ten half spaces with matching normal directions. Moreover, the gap between the inner and outer bounds is shown to be small. The inner bound relies on the rate region characterization of a lossless asymmetric multilevel diversity (MLD) coding problem treated in our earlier work, which is a natural generalization of the symmetric MLD coding problem previously considered by Roche et al. Different from symmetric MLD coding, superposition coding is not sufficient in the asymmetric case, and ideas akin to network coding need to be used strategically. Equipped with this finding, and motivated by the connection between symmetric MD and symmetric MLD coding, in this work we consider asymmetric MD as a lossy version of the asymmetric MLD coding, which requires coding beyond simple superposition. An outer bound is also derived, which bears a geometric structure particularly suitable for comparison with the inner bound. Combining the inner and outer bounds provides an approximate characterization of the rate region for the asymmetric Gaussian three description problem.

We propose a novel coding scheme for multiple description coding with K descriptions, with symmetric rate and symmetric distortion constraints. In this new coding scheme, channel codes are introduced on top of some carefully chosen source coding component. The channel coding component for k = 3 is akin to the network coding idea. We first show that for the quadratic Gaussian source, adding a simple channel coding component is able to achieve rate- distortion point outside the achievable region based on (n, k) source-channel erasure codes (SCEC), previously proposed by Puri et al, when Gaussian codebook is assumed to be optimal for that scheme. The channel coding component and (n, k) SCEC can be strategically combined, and for the special case of quadratic Gaussian three description case where any two of them are rate-distortion optimal jointly, the resulting scheme can achieve performance better than a direct time sharing between the new operating point and the (n, k) SCEC-based scheme. Moreover, this combination can be generalized naturally, which leads to a new coding scheme for the general if-description problem.

We consider multiple description coding for the Gaussian source with K descriptions under the symmetric mean squared error distortion constraints. Inner and outer bounds for the achievable rate region are derived and carefully tailored, such that they can be compared conveniently. The inner bound is based on a generalization of the multilayer scheme previously proposed by Puri et al., through a more flexible binning method. The resulting achievable region has the same geometric structure as the rate region of the lossless multilevel diversity coding problem, which reveals a strong connection between them. The outer bound is derived by combining the bounding technique for the sum rate in our earlier work, together with the α-resolution method introduced by Yeung and Zhang. Comparison between the inner and outer bounds shows that the gap in between is upper bounded by some constants. Particularly for the three description problem, the bounds can be written explicitly, and both the inner and outer bounds can be represented by ten planes with matching normal directions, between which the pairwise difference is small.

We show that when transmitting a Gaussian source over an average-power-constrained Gaussian channel with mismatched bandwidth, there exists an uncountable set of hybrid digital analog schemes which are optimal under the minimum mean squared error criterion. This generalizes the recent result by Bross et al. that for the bandwidth matched case, there exists an uncountable set of optimal schemes, with the uncoded transmission and the separation approach being the two extremes. The proposed schemes for bandwidth expansion and compression both require proper combination of various components such as power splitting, bandwidth splitting, rate splitting, Wyner-Ziv coding and dirty-paper coding. This set of schemes includes all the existing known optimal schemes as special cases. We show that this set of schemes can be applied to the broadcast scenario with three receivers, when the receiver with median channel SNR achieves optimal distortion, and it offers distortion tradeoff between of the good receiver and bad receiver. Interestingly, though continuous, this tradeoff curve is in fact concave, implying that its performance is worse than a direct time-sharing approach in this three user scenario. We further show even in a more general broadcast setting with a continuum of receivers the time sharing scheme is better than any given scheme in this set; somewhat surprisingly, there exists a unique time-sharing ratio for this to hold.

We investigate two closely related successive refinement (SR) coding problems: 1) In the hypothesis testing (HT) problem, bivariate hypothesis$H_{0}:P_{XY}$against$H_{1}: P_{X}P_{Y}$, i.e., test against independence is considered. One remote sensor collects data stream$X$and sends summary information, constrained by SR coding rates, to a decision center which observes data stream$Y$directly. 2) In the one-helper (OH) problem,$X$and$Y$are encoded separately and the receiver seeks to reconstruct$Y$losslessly. Multiple levels of coding rates are allowed at the two sensors, and the transmissions are performed in an SR manner. We show that the SR-HT rate-error-exponent region and the SR-OH rate region can be reduced to essentially the same entropy characterization form. Single-letter solutions are thus provided in a unified fashion, and the connection between them is discussed. These problems are also related to the information bottleneck (IB) problem, and through this connection we provide a straightforward operational meaning for the IB method. Connection to the pattern recognition problem, the notion of successive refinability, and two specific sources are also discussed. A strong converse for the SR-HT problem is proved by generalizing the image size characterization method, which shows the optimal type-two error exponents under constant type-one error constraints are independent of the exact values of those constants.

In this correspondence, we consider the multiuser successive refinement (MSR) problem, where the users are connected to a central server via links with different noiseless capacities, and each user wishes to reconstruct in a successive-refinement fashion. An achievable region is given for the two-user two-layer case and it provides the complete rate-distortion region for the Gaussian source under the MSE distortion measure. The key observation is that this problem includes the multiple description (MD) problem (with two descriptions) as a subsystem, and the techniques useful in the MD problem can be extended to this case. It is shown that the coding scheme based on the universality of random binning is suboptimal, because multiple Gaussian side informations only at the decoders do incur performance loss, in contrast to the case of single side information at the decoder. It is further shown that unlike the single user case, when there are multiple users, the loss of performance by a multistage coding approach can be unbounded for the Gaussian source. The result suggests that in such a setting, the benefit of using successive refinement is not likely to justify the accompanying performance loss. The MSR problem is also related to the source coding problem where each decoder has its individual side information, while the encoder has the complete set of the side informations. The MSR problem further includes several variations of the MD problem, for which the specialization of the general result is investigated and the implication is discussed.

We consider the problem of side-information scalable (SI-scalable) source coding, where the encoder constructs a two-layer description, such that the receiver with high quality side information will be able to use only the first layer to reconstruct the source in a lossy manner, while the receiver with low quality side information will have to receive both layers in order to decode. We provide inner and outer bounds to the rate-distortion (R-D) region for general discrete memoryless sources. The achievable region is tight when either one of the decoders requires a lossless reconstruction, and when the distortion measures are degraded and deterministic. Furthermore, the gap between the inner and the outer bounds can be bounded by certain constants when the squared error distortion measure is used. The notion of perfect scalability is introduced, for which necessary and sufficient conditions are given for sources satisfying a mild support condition. Using SI-scalable coding and successive refinement Wyner-Ziv coding as basic building blocks, we provide a complete characterization of the rate-distortion region for the important quadratic Gaussian source with multiple jointly Gaussian side informations, where the side information quality is not necessarily monotonic along the scalable coding order. A partial result is provided for the doubly symmetric binary source under the Hamming distortion measure when the worse side information is a constant, for which one of the outer bounds is strictly tighter than the other.

We consider the problem of transmitting a Gaussian source on a slowly fading Gaussian channel, subject to the mean-squared error distortion measure. The channel state information is known only at the receiver but not at the transmitter. The source is assumed to be encoded in a successive refinement (SR) manner, and then transmitted over the channel using the broadcast strategy. In order to minimize the expected distortion at the receiver, optimal power allocation is essential. We propose an efficient algorithm to compute the optimal solution in linear time , when the total number of possible discrete fading states. Moreover, we provide a derivation of the optimal power allocation when the fading state is a continuum, using the classical variational method. The proposed algorithm as well as the continuous solution is based on an alternative representation of the capacity region of the Gaussian broadcast channel.

We consider the problem of multiple description (MD) coding for stationary sources with the squared error distortion measure. The MD rate region is derived for the stationary and ergodic Gaussian sources, and is shown to be achievable with a practical transform lattice quantization scheme. Moreover, the proposed scheme is asymptotically optimal at high resolution for all stationary sources with finite differential entropy rate

We investigate the distributed successive refinement (SR) hypothesis testing problem. Bivariate hypothesis Ho : Pxy against Hi : PxPy, i.e., test against independence is considered, when a remote sensor sends compressed information about data stream X subject to SR coding constraints to a decision site, where data stream Y can be observed directly. We show that this problem is closely related to the SR lossless one-helper problem and the SR pattern recognition problem. More precisely, the rate-type-two-error-exponent region of the SR hypothesis testing problem, the rate region of the SR one-helper problem and that of the SR pattern recognition problem can be reduced to essentially the same entropy characterization form, up to an isometry. Single letter solution is subsequently given in this unified framework, and this connection is further explored. Strong converse result is proved by generalizing the image size characterization technique, which shows the optimal type-two error exponents for SR hypothesis testing under fixed type-one error constraints are independent of the exact values of those constraints. The notion of successive refinability is defined, and somewhat surprisingly for large value of type-one error constraints, a source is always successive refinable for hypothesis testing.

We consider the problem of scalable source coding with decoder side informations. Two special cases of this problem have been investigated in the literature, namely successive refinement Wyner-Ziv (SR-WZ) coding and side-information scalable (Si-Scalable) coding, whose distinction lies in the degradedness of the side informations. In this work, we first show the achievable region for the Si-scalable problem provided in a previous work is tight when either the first stage or the second stage requires lossless reconstruction. Then the notion of perfectly scalable coding is introduced as both the stages operate on the Wyner-Ziv bound, and a set of necessary and sufficient conditions is given for sources satisfying a mild support condition. Furthermore, generalizing the coding scheme for the SR-WZ and SI-scalable coding, we provide a conclusive solution for the (multistage) quadratic Gaussian scalable coding problem with jointly Gaussian side informations in an arbitrary order of quality.

We consider the problem of transmitting a Gaussian source on a slowly fading Gaussian channel, subject to the mean squared error distortion measure. The channel state information is known only at the receiver but not the transmitter. The source is assumed to be encoded in a successive refinement manner, and then transmitted over the channel using the broadcast strategy. In order to minimize the expected distortion at the receiver, optimal power allocation is essential. We propose an efficient algorithm to compute the optimal solution in linear time O(M). Moreover, we provide a derivation of the optimal power allocation when the fading state is a continuum, using the classical variational method. The proposed algorithm as well as the continuous solution is based on an alternative representation of the capacity region of the Gaussian broadcast channel.

In this correspondence, we provide a complete characterization of the rate-distortion region for themultistagesuccessive refinement of the Wyner–Ziv source coding problem with degraded side informations at the decoder. Necessary and sufficient conditions for a source to be successively refinable along a distortion vector are subsequently derived. A source–channel separation theorem is provided when the descriptions are sent over independent channels for the multistage case. Furthermore, the notion of generalized successive refinability with multiple degraded side informations is introduced. This notion captures whether progressive encoding to satisfy multiple distortion constraints for different side informations is as good as encoding without progressive requirement. Necessary and sufficient conditions for generalized successive refinability are given. It is shown that the following two sources are generalized successively refinable: 1) the Gaussian source with degraded Gaussian side informations and 2) the doubly symmetric binary source when the worse side information is a constant. Thus for both cases, the failure of being successively refinable is only due to the inherent uncertainty on which side information will occur at the decoder, but not the progressive encoding requirement.

We consider the problem of constructing visually optimized balanced multiple descriptions of images, instead of being op- timized with the conventional measure of mean squared error (MSE). The recently proposed Modified Multiple Description Scalar Quantizer (MMDSQ) is used because its central and side quantizers all have convex and uniform cells. Since the majority of research results on the visual distortion caused by quantization noise assumes convex and uniform quantizer cells, they can be conveniently applied to the system based on MMDSQ. The technique provides substantially higher side reconstruction perceived quality when compared at the same central reconstruction quality, which is verified through per- ceptual tests.

We provide a complete characterization of rate region for the multistage successive refinement of Wyner-Ziv source coding problem with degraded side information at the decoder. This problem was left open in a recent work by Steinberg and Merhav (T-IT, 2004), where it was solved for the special case of two stages. Furthermore, we introduce the notion of generalized successive refinability with multiple side informations. This captures whether progressive encoding to satisfy the distortion constraints for different side information as good as encoding without progressive requirement. For degraded side-information, we give necessary and sufficient conditions for generalized successive refinability. Using this, we show that for Gaussian source, the failure of being successively refinable with multiple side informations is only due to the inherent uncertainty on which side information will occur at the decoder, but not the progressive encoding requirement

The multiple description (MD) problem has received considerable attention as a model of information transmission over unreliable channels. A general framework for designing efficient MD quantization schemes is proposed in this paper. We provide a systematic treatment of the El Gamal-Cover (EGC) achievable MD rate-distortion region, and show it can be decomposed into a simplified-EGC (SEGC) region and a superimposed refinement operation. Furthermore, any point in the SEGC region can be achieved via a successive quantization scheme along with quantization splitting. For the quadratic Gaussian case, the proposed scheme has an intrinsic connection with the Gram-Schmidt orthogonalization, which implies that the whole Gaussian MD rate-distortion region is achievable with a sequential dithered lattice-based quantization scheme as the dimension of the (optimal) lattice quantizers becomes large. Moreover, this scheme is shown to be universal for all independent and identically distributed (i.i.d.) smooth sources with performance no worse than that for an i.i.d. Gaussian source with the same variance and asymptotically optimal at high resolution. A class of MD scalar quantizers in the proposed general framework is also constructed and is illustrated geometrically; the performance is analyzed in the high-resolution regime, which exhibits a noticeable improvement over the existing MD scalar quantization schemes

We investigate using a lattice and a staggered version of it for balanced multiple description quantization at high-resolution. By letting one side quantizer use a lattice codebook, and the other side quantizer use a codebook based on the same lattice with a slight shift, the joint quantizer as the central quantizer can naturally achieve a performance improvement over the side quantizers. Application of such a structure is meaningful when the side quantizers' distortions are of (equal) primary concern. Another immediate application of such a structure is when a refinement stage is added to further reduce the central distortion. We analyze the performance of this structure for these two applications, and then evaluate the root lattices A/sub n/, D/sub n/ (with dimension less than 9), E/sub 6/, E/sub 7/, E/sub 8/ and their duals. The results suggest that these two applications in fact lead to different choices of lattices: while the former requires good lattices in terms of their normalized second moments of inertia, the latter appears to perform better when the staggering of lattices generates more cells by intersection of the Voronoi regions of the two lattices. These observations also suggest a suboptimal but simple multiple description quantization scheme using lattices.

We propose a new class of universal multiple description lattice quantizers based on the method of quantization splitting. For Gaussian sources and squared error distortion measure, our scheme can achieve the whole multiple description rate-distortion region, as the dimension of the (optimal) lattice quantizers becomes large

We present a novel technique for encoding and decoding constant weight binary codes that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and analyze its complexity. The complexity of the proposed algorithm depends on the weight of the code, rather than on the block length as in previous algorithms. This approach is advantageous when the weight is smaller than the square root of the block length.

We introduce a new class of multiple description scalar quantizer (MDSQ), which will be referred to as the modified MDSQ (MMDSQ). The structure of MMDSQ is fundamentally different from the MDSQ proposed by Vaishampayan. Analysis shows that at high rates for sources with smooth pdfs, MMDSQ achieves the same performance as entropy-constrained MDSQ using a uniform central quantizer. Compared with MDSQ, MMDSQ features a more efficient central-side distortion tradeoff control mechanism, without requiring the design and implementation of a complicated index assignment scheme. The simple and efficient implementation of MMDSQ makes it suitable for image coding: It can be naturally incorporated into existing coders to form new multiple description coders. Such a system is constructed using an existing image coder, and the performance of the resulting system is compared to that of the same coder but using Vaishampayan's MDSQ. Simulation results on natural images reveal that the system based on MMDSQ outperforms that based on MDSQ.

This paper introduces a new sequential design method for multiple description scalar quantizers (MDSQs) to generate two or more balanced descriptions. In this design method, a multiple description system is divided into multiple stages, and the m-th stage can be understood intuitively as minimizing the distortion of receiving any m of all the descriptions, while looking ahead to the next stage to reduce the distortion if more descriptions are present. Entropy-constrained sequential MDSQ with two descriptions is shown to achieve the same asymptotic performance as entropy-constrained MDSQ with uniform stepsize. Then this method is applied to the design of sequential MDSQ with three descriptions, for which two slightly different designs are given and compared with a three description system based on unequal loss protection at high rate. The results suggest that if the quality of the decoded source with two or more descriptions (rather than a single description) is most important, general multiple description systems should be favored over unequal loss protection systems. However, if the quality of the decoded source with a single description is most important (in the case of, for example, high channel failure rates), the difference in their performances is not terribly large.

Recently, image compression systems based on the tarp filter, a type of recursive filter, have attracted much attention in the image processing community. While providing very good performance when used in a non-embedded manner, the original tarp-filter-based algorithm performs less competitively when used in an embedded manner (in spite of its operation on bitplanes), because of its raster scan encoding order. We propose a Tarp-filter-based system which utilizes Classification of coefficients to achieve Embedding (TCE). The algorithm classifies the coefficients according to their statistical properties, and the tarp filter only runs on the single class on which it tends to generate accurate probability estimates. TCE can achieve much better rate-distortion embedding performance than the original tarp-filter-based system when used in an embedded manner; it achieves slightly better performance than SPIHT with arithmetic coding, and is comparable with JPEG-2000 performance on average.

We introduce a special class of multiple description scalar quantizer (MDSQ), which is referred to as the modified MDSQ (MMDSQ). MMDSQ features simple implementations and an efficient central-side distortion trade-off control mechanism. These advantages make it suitable for multiple description image and video coding systems: the simplicity of MMDSQ facilitates the incorporation of multiple description coding into existing coding systems. Analysis shows that this class of MDSQ can achieve the same asymptotic high-rate performance as entropy-constrained MDSQ with uniform central quantizers, for sources with smooth pdf. The performance of MMDSQ on a unit-variance Gaussian i.i.d. source is compared with that of entropy-constrained MDSQ at different rates numerically, and the results confirm the satisfactory performance of MMDSQ at rates above 3 bps/description. Application of MMDSQ to image coding also shows promising results.

This paper introduces a new high-rate analysis of the multiple description scalar quantizer (MDSQ) with balanced descriptions. The analysis provides insight into the structure of the MDSQ, suggesting the nonoptimality of uniform central quantizer cell lengths, as well as a method to approximate optimal cell lengths. For both level-constrained and entropy-constrained MDSQ, new upper bounds on the granular distortion for sources with smooth probability density functions (pdfs) are derived under the mean-squared error measure, which are 0.4 dB lower than previous results. Based on the insights, a universal multiple description scalar quantizer (UMDSQ) is proposed which, at high rate, can achieve nearly the same performance as the fully optimized entropy-constrained MDSQ (ECMDSQ), without requiring extensive training. The proposed UMDSQ has only two control parameters, and a continuum of tradeoff points between the central and side distortions can be achieved as the two parameters are varied.

The asymptotic analysis of multiple-description vector quantization (MDVQ) with a lattice codebook for sources with smooth probability density functions (pdfs) is considered in this correspondence. Goyal et al. (2002) observed that as the side distortion decreases and the central distortion correspondingly increases, the quantizer cells farther away from the coarse lattice points shrink in a spatially periodic pattern. In this correspondence, two special classes of index assignments are used along strategic groupings of central quantizer cells to derive a straightforward asymptotic analysis, which provides an analytical explanation for the aforementioned observation. MDVQ with a lattice codebook was shown earlier to be asymptotically optimal in high dimensions, with a curious converging property, that the side quantizers achieve the space filling advantage of an n-dimensional sphere instead of an n-dimensional optimal polytope. The analysis presented here explains this behavior readily. While central quantizer cells on a uniform lattice are asymptotically optimal in high dimensions, the present authors have shown that by using nonuniform rather than uniform central quantizer cells, the central-side distortion product in an MDSQ can be reduced by 0.4 dB at asymptotically high rate. The asymptotic analysis derived here partially unifies these previous results in the same framework, though a complete characterization is still beyond reach.

A new high-rate analysis of the entropy-constrained multiple description scalar quantizer (ECMDSQ) is introduced. The analysis provides insight into the structure of the ECMDSQ, suggesting the non-optimality of uniform central quantizer cells with finite diagonals in the index assignment matrix, as well as a method to approximate optimal cell sizes. Based on these insights, a universal multiple description scalar quantizer (UMDSQ) is proposed which can achieve nearly the same performance as the fully optimized ECMDSQ, at much lower design complexity. The design requires selection of only two parameters, and the resulting UMDSQ can provide a continuum of trade-off points between the central and side distortions as the two parameters are varied.