We study the evolution of the generalization Error of Federated Learning with the number of communication rounds between the clients and a parameter server (PS). We establish stability-based and rate-distortion theoretic-based bounds on the generalization error that account explicitly for the effect of the number of roundsR, in addition to the number of participating clientsKand individual datasets sizen. For distinct communication rounds, these bounds involve conditional mutual information terms that are coupled through the aggregated model; and, partly for this reason, their computation is not easy, especially in the one-shot regime,i.e., using only one training dataset. In this paper, we also develop algorithms that allow to estimate the established bounds using only one training dataset. In some cases, the bounds are more explicit, such as for FL-type Support Vector Machines (FSVM). In this case, we show that the bound increases withR, suggesting that more frequent communication with PS diminishes the generalization power. This implies that the population risk of FSVM decreases less rapidly withRthan does the empirical risk, a finding which we also validate experimentally. Finally, we provide experimental results obtained using neural networks (ResNet-56) which show that not only may our observations for FSVM hold more generally but also that more communication with PS (beyond some valueR‹ ofR) may even hurt the population risk.

We establish in-expectation and tail bounds on the generalization error of representation learning type algorithms. The bounds are in terms of the relative entropy between the distribution of the representations extracted from the training and "test'' datasets and a data-dependent symmetric prior, i.e., the Minimum Description Length (MDL) of the latent variables for the training and test datasets. Our bounds are shown to reflect the "structure" and "simplicity'' of the encoder and significantly improve upon the few existing ones for the studied model. We then use our in-expectation bound to devise a suitable data-dependent regularizer; and we investigate thoroughly the important question of the selection of the prior. We propose a systematic approach to simultaneously learning a data-dependent Gaussian mixture prior and using it as a regularizer. Interestingly, we show that a weighted attention mechanism emerges naturally in this procedure. Our experiments show that our approach outperforms the now popular Variational Information Bottleneck (VIB) method as well as the recent Category-Dependent VIB (CDVIB).

We study the problem of distributed multi-view representation learning. In this problem, two agents observe each one distinct, but possibly statistically correlated, view and independently extract from it a suitable representation so that a decoder that gets both representations correctly estimates the hidden label. In the absence of any explicit coordination between the agents, a central question is: what should each agent extract from its view that is necessary and sufficient for a correct estimation at the decoder? In this paper, we investigate this question from a generalization error perspective. First, we establish generalization bounds in terms of the relative entropy between the distribution of the representations extracted from training and “test” datasets and a data-dependent symmetric prior, i.e., the joint Minimum Description Length (MDL) of the extracted representations. Then, we use the obtained bound to devise a regularizer; and investigate in depth the question of the selection of a suitable prior. In particular, we show that the selection of the joint prior as Gaussian-product mixture, which induces Gaussian mixture marginal prior for each marginal view, implicitly encourages the agents to extract and output redundant features; a finding which is somewhat counter-intuitive. Interestingly, we show that a joint weighted attention mechanism emerges naturally in our approach. Finally, we conduct several experiments that validate the efficiency of our proposed method.

In this paper, we leverage stochastic projection and lossy compression to establish new conditional mutual information (CMI) bounds on the generalization error of statistical learning algorithms. It is shown that these bounds are generally tighter than the existing ones. In particular, we prove that for certain problem instances for which existing MI and CMI bounds were recently shown in Attias et al. [2024] and Livni [2023] to become vacuous or fail to describe the right generalization behavior, our bounds yield suitable generalization guarantees of the order of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the size of the training dataset. Furthermore, we use our bounds to investigate the problem of data "memorization" raised in those works, and which asserts that there are learning problem instances for which any learning algorithm that has good prediction there exist distributions under which the algorithm must "memorize'' a big fraction of the training dataset. We show that for every learning algorithm, there exists an auxiliary algorithm that does not memorize and which yields comparable generalization error for any data distribution. In part, this shows that memorization is not necessary for good generalization.

We investigate the generalization error of statistical learning models in a Federated Learning (FL) setting. Specifically, we study the evolution of the generalization error with the number of communication rounds $R$ between $K$ clients and a parameter server (PS), i.e. the effect on the generalization error of how often the clients' local models are aggregated at PS. In our setup, the more the clients communicate with PS the less data they use for local training in each round, such that the amount of training data per client is identical for distinct values of $R$. We establish PAC-Bayes and rate-distortion theoretic bounds on the generalization error that account explicitly for the effect of the number of rounds $R$, in addition to the number of participating devices $K$ and individual datasets size $n$. The bounds, which apply to a large class of loss functions and learning algorithms, appear to be the first of their kind for the FL setting. Furthermore, we apply our bounds to FL-type Support Vector Machines (FSVM); and derive (more) explicit bounds in this case. In particular, we show that the generalization bound of FSVM increases with $R$, suggesting that more frequent communication with PS diminishes the generalization power. This implies that the population risk decreases less fast with $R$ than does the empirical risk. Moreover, our bound suggests that the generalization error of FSVM decreases faster than that of centralized learning by a factor of $\mathcal{O}(\sqrt{\log(K)/K})$. Finally, we provide experimental results obtained using neural networks (ResNet-56) which show evidence that not only may our observations for FSVM hold more generally but also that the population risk may even start to increase beyond some value of $R$.

Neural network compression has been an increasingly important subject, not only due to its practical relevance, but also due to its theoretical implications, as there is an explicit connection between compressibility and generalization error. Recent studies have shown that the choice of the hyperparameters of stochastic gradient descent (SGD) can have an effect on the compressibility of the learned parameter vector. These results, however, rely on unverifiable assumptions and the resulting theory does not provide a practical guideline due to its implicitness. In this study, we propose a simple modification for SGD, such that the outputs of the algorithm will be provably compressible without making any nontrivial assumptions. We consider a one-hidden-layer neural network trained with SGD, and show that if we inject additive heavy-tailed noise to the iterates at each iteration, for _any_ compression rate, there exists a level of overparametrization such that the output of the algorithm will be compressible with high probability. To achieve this result, we make two main technical contributions: (i) we prove a "propagation of chaos" result for a class of heavy-tailed stochastic differential equations, and (ii) we derive error estimates for their Euler discretization. Our experiments suggest that the proposed approach not only achieves increased compressibility with various models and datasets, but also leads to robust test performance under pruning, even in more realistic architectures that lie beyond our theoretical setting.

In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a “variable-size compressibility” framework that we introduce newly here. In this framework, the generalization error of an algorithm is linked to a variable-size ‘compression rate’ of its input data. This is shown to yield bounds that depend on the value of the input training data sample at hand, rather than on its unknown distribution. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds. Moreover, it is shown that our framework also allows to derive general bounds on any function of the input data and output hypothesis random variables. In particular, these general bounds are shown to subsume and possibly improve over several existing PAC-Bayes and data-dependent intrinsic dimension-based bounds that are recovered as special cases, thus unveiling a unifying character of our approach.

A client device which has access to$n$training data samples needs to obtain a statistical hypothesis or model W and then to send it to a remote server. The client and the server devices share some common randomness sequence as well as a prior on the hypothesis space. In this problem a suitable hypothesis or model$W$should meet two distinct design criteria simultaneously: (i) small (population) risk during the inference phase and (ii) small ‘complexity’ for it to be conveyed to the server with minimum communication cost. In this paper, we propose a joint training and source coding scheme with provable in-expectation guarantees, where the expectation is over the encoder's output message. Specifically, we show that by imposing a constraint on a suitable Kullback-Leibler divergence between the conditional distribution induced by a compressed learning model$\hat{W}$given$W$and the prior, one guarantees simultaneously small average empirical risk (aka training loss), small average generalization error and small average communication cost. We also consider a one-shot scenario in which the guarantees on the empirical risk and generalization error are obtained for every encoder's output message.

In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a “variable-size compressibility” framework that we introduce newly here. In this framework, the generalization error of an algorithm is linked to a variable-size ‘compression rate’ of its input data. This is shown to yield bounds that depend on the empirical measure of the given input data at hand, rather than its unknown distribution. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds. Moreover, it is shown that our framework also allows to derive general bounds on any function of the input data and output hypothesis random variables. In particular, these general bounds are shown to subsume and possibly improve over several existing PAC-Bayes and data-dependent intrinsic dimension-based bounds that are recovered as special cases, thus unveiling a unifying character of our approach. For instance, a new data-dependent intrinsic dimension-based bound is established, which connects the generalization error to the optimization trajectories and reveals various interesting connections with the rate-distortion dimension of a process, the Rényi information dimension of a process, and the metric mean dimension.

We study the generalization error of statistical learning models in a Federated Learning (FL) setting. Specifically, there are K devices or clients, each holding an independent own dataset of size n. Individual models, learned locally via Stochastic Gradient Descent, are aggregated (averaged) by a central server into a global model and then sent back to the devices. We consider multiple (say $ \in {{\mathbb{N}}^{\text{*}}}$ ) rounds of model aggregation and study the effect of R on the generalization error of the final aggregated model. We establish an upper bound on the generalization error that accounts explicitly for the effect of R (in addition to the number of participating devices K and dataset size ). It is observed that, for fixed $\left({n,K}\right)$, the bound increases with R, suggesting that the generalization of such learning algorithms is negatively affected by more frequent communication with the parameter server. Combined with the fact that the empirical risk, however, generally decreases for larger values of R, this indicates that R might be a parameter to optimize to reduce the population risk of FL algorithms. The results of this paper, which extend straightforwardly to the heterogeneous (non-i.i.d.) data setting, are also illustrated through numerical examples.

A major challenge in designing efficient statistical supervised learning algorithms is finding representations that perform well not only on available training samples but also on unseen data. While the study of representation learning has spurred much interest, most existing such approaches are heuristic; and very little is known about theoretical generalization guarantees. For example, the information bottleneck method seeks a good generalization by finding a minimal description of the input that is maximally informative about the label variable, where minimality and informativeness are both measured by Shannon’s mutual information. In this paper, we establish a compressibility framework that allows us to derive upper bounds on the generalization error of a representation learning algorithm in terms of the ``Minimum Description Length'' (MDL) of the labels or the latent variables (representations). Rather than the mutual information between the encoder’s input and the representation, which is often believed to reflect the algorithm’s generalization capability in the related literature but in fact, falls short of doing so, our new bounds involve the "multi-letter" relative entropy between the distribution of the representations (or labels) of the training and test sets and a fixed prior. In particular, these new bounds reflect the structure of the encoder and are not vacuous for deterministic algorithms. Our compressibility approach, which is information-theoretic in nature, builds upon that of Blum-Langford for PAC-MDL bounds and introduces two essential ingredients: block-coding and lossy-compression. The latter allows our approach to subsume the so-called geometrical compressibility as a special case. To the best knowledge of the authors, the established generalization bounds are the first of their kind for Information Bottleneck type encoders and representation learning. Finally, we partly exploit the theoretical results by introducing a new data-dependent prior. Numerical simulations illustrate the advantages of well-chosen such priors over classical priors used in IB.

We study a class of$K$-encoder hypothesis testing against conditional independence problems. Under the criterion that stipulates minimization of the Type II error subject to a (constant) upper bound$\epsilon $on the Type I error, we characterize the set of encoding rates and exponent for both discrete memoryless and memoryless vector Gaussian settings. For the DM setting, we provide a converse proof and show that it is achieved using the Quantize-Bin-Test scheme of Rahman and Wagner. For the memoryless vector Gaussian setting, we develop a tight outer bound by means of a technique that relies on the de Bruijn identity and the properties of Fisher information. In particular, the result shows that for memoryless vector Gaussian sources the rate-exponent region is exhausted using the Quantize-Bin-Test scheme with Gaussian test channels; and there is no loss in performance caused by restricting the sensors’ encoders not to employ time sharing. Furthermore, we also study a variant of the problem in which the source, not necessarily Gaussian, has finite differential entropy and the sensors’ observations noises under the null hypothesis are Gaussian. For this model, our main result is an upper bound on the exponent-rate function. The bound is shown to mirror a corresponding explicit lower bound, except that the lower bound involves the source power (variance) whereas the upper bound has the source entropy power. Part of the utility of the established bound is for investigating asymptotic exponent/rates and losses incurred by distributed detection as function of the number of sensors.

In this paper, we use tools from rate-distortion theory to establish new upper bounds on the generalization error of statistical distributed learning algorithms. Specifically, there are $K$ clients whose individually chosen models are aggregated by a central server. The bounds depend on the compressibility of each client's algorithm while keeping other clients' algorithms un-compressed, and leveraging the fact that small changes in each local model change the aggregated model by a factor of only $1/K$. Adopting a recently proposed approach by Sefidgaran et al., and extending it suitably to the distributed setting, enables smaller rate-distortion terms which are shown to translate into tighter generalization bounds. The bounds are then applied to the distributed support vector machines (SVM), suggesting that the generalization error of the distributed setting decays faster than that of the centralized one with a factor of $\mathcal{O}(\sqrt{\log(K)/K})$. This finding is validated also experimentally. A similar conclusion is obtained for a multiple-round federated learning setup where each client uses stochastic gradient Langevin dynamics (SGLD).

In the context of statistical learning, the Information Bottleneck (IB) method seeks a right balance between accuracy and generalization capability through a suitable tradeoff between compression complexity, measured by minimum description length, and distortion evaluated under logarithmic loss measure. In this paper, we study a variation of the problem, called scalable information bottleneck, in which the encoder outputs multiple descriptions of the observation with increasingly richer features. The model, which is of successive-refinement type with degraded side information streams at the decoders, is motivated by some application scenarios that require varying levels of accuracy depending on the allowed level of complexity. We establish an analytic characterization of the optimal relevance-complexity region for vector Gaussian sources. Then, we derive a variational inference type algorithm for general sources with unknown distribution; and show means of parametrizing it using neural networks. Finally, we provide experimental results on the MNIST dataset which illustrate that the proposed method generalizes better to unseen data compared to the standard IB with a single description.

We consider the problem of learning parametric distributions from their quantized samples in a network. Specifically,$n$agents or sensors observe independent samples of an unknown parametric distribution; and each of them uses$k$bits to describe its observed sample to a central processor whose goal is to estimate the unknown distribution. First, we establish a generalization of the well-known van Trees inequality to general$L_{p}$-norms, with$p > 1$, in terms of Generalized Fisher information. Then, we develop minimax lower bounds on the estimation error for two losses: general$L_{p}$-norms and the related Wasserstein loss from optimal transport.

The problem of distributed representation learning is one in which multiple sources of information X1,..., XKare processed separately so as to learn as much information as possible about some ground truth Y. We investigate this problem from information-theoretic grounds, through a generalization of Tishby's centralized Information Bottleneck (IB) method to the distributed setting. Specifically, K encoders, K ≥ 2, compress their observations X1,..., XKseparately in a manner such that, collectively, the produced representations preserve as much information as possible about Y. We study both discrete memoryless (DM) and memoryless vector Gaussian data models. For the discrete model, we establish a single-letter characterization of the optimal tradeoff between complexity (or rate) and relevance (or information) for a class of memoryless sources (the observations X1,..., XKbeing conditionally independent given Y). For the vector Gaussian model, we provide an explicit characterization of the optimal complexity-relevance tradeoff. Furthermore, we develop a variational bound on the complexity-relevance tradeoff which generalizes the evidence lower bound (ELBO) to the distributed setting. We also provide two algorithms that allow to compute this bound: i) a Blahut-Arimoto type iterative algorithm which enables to compute optimal complexity-relevance encoding mappings by iterating over a set of self-consistent equations, and ii) a variational inference type algorithm in which the encoding mappings are parametrized by neural networks and the bound approximated by Markov sampling and optimized with stochastic gradient descent. Numerical results on synthetic and real datasets are provided to support the efficiency of the approaches and algorithms developed in this paper.

This paper studies the problem of discriminating two multivariate Gaussian distributions in a distributed manner. Specifically, it characterizes in a special case the optimal type- II error exponent as a function of the available communication rate. As a side-result, the paper also presents the optimal type-II error exponent of a slight generalization of the hypothesis testing against conditional independence problem where the marginal distributions under the two hypotheses can be different.

We study a variant of the many-help one hypothesis testing against independence problem in which the source, not necessarily Gaussian, has finite differential entropy and the observation noises under the null hypothesis are Gaussian. Under the criterion that stipulates minimization of the Type II error exponent subject to a (constant) bound on the Type I error rate, we derive an upper bound on the exponent-rates function. The bound is shown to mirror a corresponding explicit lower bound, except that the lower bound involves the source power (variance) whereas the upper bound has the source entropy power. Part of the utility of the established bound is for investigating asymptotic exponent/rates and losses incurred by distributed detection as function of the number of observations.

A single-sensor two-detectors system is considered where the sensor communicates with both detectors and Detector 1 communicates with Detector 2, all over noise-free rate-limited links. The sensor and both detectors observe discrete memoryless source sequences whose joint probability mass function depends on a binary hypothesis. The goal at each detector is to guess the binary hypothesis in a way that, for increasing observation lengths, the probability of error under one of the hypotheses decays to zero with largest possible exponential decay, whereas the probability of error under the other hypothesis can decay to zero or to a small positive number arbitrarily slow. For the setting with positive communication rates from the sensor to the detectors and when both detectors are interested in maximizing the error exponent under the same hypothesis, we characterize the set of all possible exponents in a special case of testing against independence. In this case the cooperation link allows Detector 2 to increase its Type-II error exponent by an amount that is equal to the exponent attained at Detector 1. We also provide a general inner bound on the set of achievable error exponents that shows a tradeoff between the exponents at the two detectors in most cases. When the two detectors aim at maximizing the error exponent under different hypotheses and the distribution at the Sensor is different under the two hypotheses, then we show that such a tradeoff does not exist. We propose a general scheme that allows each detector to attain the same exponent as if it was the only detector in the system. For the setting with zero-rate communication on both links, we exactly characterize the set of possible exponents and the gain brought up by cooperation, in function of the number of bits that are sent over the two links. Notice that, for this setting, tradeoffs between the exponents achieved at the two detectors arise only in few particular cases. In all other cases, each detector achieves the same performance as if it were the only detector in the system.

In this paper, we study the vector Gaussian Chief Executive Officer (CEO) problem under logarithmic loss distortion measure. Specifically, K ≥ 2 agents observe independently corrupted Gaussian noisy versions of a remote vector Gaussian source, and communicate independently with a decoder or CEO over rate-constrained noise-free links. The CEO also has its own Gaussian noisy observation of the source and wants to reconstruct the remote source to within some prescribed distortion level where the incurred distortion is measured under the logarithmic loss penalty criterion. We find an explicit characterization of the rate-distortion region of this model. The result can be seen as the counterpart to the vector Gaussian setting of that by Courtade-Weissman which provides the rate-distortion region of the model in the discrete memoryless setting. For the proof of this result, we obtain an outer bound by means of a technique that relies on the de Bruijn identity and the properties of Fisher information. The approach is similar to Ekrem-Ulukus outer bounding technique for the vector Gaussian CEO problem under quadratic distortion measure, for which it was there found generally non-tight; but it is shown here to yield a complete characterization of the region for the case of logarithmic loss measure. Also, we show that Gaussian test channels with time-sharing exhaust the Berger-Tung inner bound, which is optimal. Furthermore, application of our results allows us to find the complete solutions of two related problems: a quadratic vector Gaussian CEO problem with determinant constraint and the vector Gaussian distributed Information Bottleneck problem. Finally, we develop Blahut-Arimoto type algorithms that allow to compute numerically the regions provided in this paper, for both discrete and Gaussian models. With the known relevance of the logarithmic loss fidelity measure in the context of learning and prediction, the proposed algorithms may find usefulness in a variety of applications where learning is performed distributively. We illustrate the efficiency of our algorithms through some numerical examples.

We study a class of distributed hypothesis testing against conditional independence problems. Under the criterion that stipulates minimization of the Type II error exponent subject to a (constant) upper bound c on the Type I error rate, we characterize the set of encoding rates and exponent for both discrete memoryless and memoryless vector Gaussian settings.

A detection system with a single sensor and K detectors is considered, where each of the terminals observes a memoryless source sequence and the sensor sends a common message to all the detectors. The communication of this message is assumed error-free but rate-limited. The joint probability mass function (pmf) of the source sequences observed at the terminals depends on an M-ary hypothesis (M ≥ K), and the goal of the communication is that each detector can guess the underlying hypothesis. Each detector k aims to maximize the error exponent under hypothesis k, while ensuring a small probability of error under all other hypotheses. This paper presents an achievable exponents region for the case of positive communication rate, and characterizes the optimal exponents region for the case of zero communication rate. All results extend also to a composite hypothesis testing scenario.

In this paper, we study the vector Gaussian Chief Executive Officer (CEO) problem under logarithmic loss distortion measure. Specifically, K > 2 agents observe independently corrupted Gaussian noisy versions of a remote vector Gaussian source, and communicate independently with a decoder or CEO over rate-constrained noise-free links. The CEO wants to reconstruct the remote source to within some prescribed distortion level where the incurred distortion is measured under the logarithmic loss penalty criterion. We find an explicit characterization of the rate-distortion region of this model. For the proof of this result, we obtain an outer bound on the region of the vector Gaussian CEO problem by means of a technique that relies on the de Bruijn identity and the properties of Fisher information. The approach is similar to Ekrem-Ulukus outer bounding technique for the vector Gaussian CEO problem under quadratic distortion measure, for which it was there found generally non-tight; but it is shown here to yield a complete characterization of the region for the case of logarithmic loss measure. Also, we show that Gaussian test channels with time-sharing exhaust the BergerTung inner bound, which is optimal. Furthermore, we also show that the established result under logarithmic loss provides an outer bound for a quadratic vector Gaussian CEO problem with determinant constraint, for which we characterize the optimal rate-distortion region.

This paper investigates the downlink of a cloud radio access network (C-RAN) in which a central processor communicates with two mobile users through two base stations (BSs). The BSs act as relay nodes and cooperate with each other through error-free rate-limited links. We develop and analyze two coding schemes for this scenario. The first coding scheme modifies the Liu-Kang scheme (to make it amenable to a rigorous analysis) and extends it to introduce common codewords and to apply for downlink C-RAN with BS-to-BS cooperation. This first coding scheme enables arbitrary correlation among the auxiliary codewords that are recovered by the BSs. We show that this scheme improves over previous schemes for various instances of Gaussian C-RAN channels. In particular, in many scenarios, the scheme can better exploit the possibility of BS-to-BS cooperation than other schemes. The second coding scheme extends the distributed decode and forward (DDF) scheme by means of Gray-Wyner compression and by exploiting the cooperation links between BSs. In addition and as a separate extension, we provide an improved capacity approximation for the DDF strategy for the capacity of a general N-BS L-user C-RAN model in the memoryless Gaussian case.

We study the transmission over a network in which users send information to a remote destination through relay nodes that are connected to the destination via finite-capacity error-free links, i.e., a cloud radio access network. The relays are constrained to operate without knowledge of the users' codebooks, i.e., they perform oblivious processing. The destination, or central processor, however, is informed about the users' codebooks. We establish a single-letter characterization of the capacity region of this model for a class of discrete memoryless channels in which the outputs at the relay nodes are independent given the users' inputs. We show that both relaying à-la Cover-El Gamal, i.e., compress-and-forward with joint decompression and decoding, and “noisy network coding” are optimal. The proof of the converse part establishes, and utilizes, connections with the Chief Executive Officer source coding problem under logarithmic loss distortion measure. Extensions to general discrete memoryless channels are also investigated. In this case, we establish the inner and outer bounds on the capacity region. For memoryless Gaussian channels within the studied class of channels, we characterize the capacity region when the users are constrained to time-share among Gaussian codebooks. Furthermore, we also discuss the suboptimality of separate decompression and decoding and the role of time sharing.

In this work, we establish a full single-letter characterization of the rate-distortion region of an instance of the Gray-Wyner model with side information at the decoders. In this model an encoder observes a pair of memoryless sources (Sn1, Sn2) and communicates with two receivers over a common error-free rate-limited link of capacity R0, as well as two individual error-free rate-limited links of capacities R1and R2. Both receivers reproduce the source component Sn2losslessly; and Receiver 1 also reproduces the source component Sn1lossily, to within some prescribed distortion level D1. Also, Receiver 1 and Receiver 2 observe each a memoryless side information sequence, Yn1and Yn2, assumed to be arbitrarily correlated among them, and with the source pair (Sn1, Sn2).

In this work, we study a three-terminal cascade source coding problem with side information Yi known to the source encoder and the first user, and side information Y2 known only to the second user. Each user wants to reconstruct some desired function of the source, lossily, to within some fidelity level. We establish single-letter characterization of the rate-distortion region of this model in some important special cases, including when the reconstruction is lossless at the first user. We then establish a connection among the studied model and the so-called side information-scalable source coding problem (i.e., Heegard-Berger problem with side information and successive refinement) to infer single-letter characterization of the rate-distortion region of some instances of the latter problem. In contrast with most previous related works, the results of this paper hold irrespective of the ordering among the source and side information sequences, which are then arbitrarily correlated.

In this work, we study the problem of two-encoder multiterminal source coding with side information under logarithmic loss distortion measure. We establish a single-letter characterization of the rate-distortion region of this model in the discrete memoryless case. The proof of the converse relies heavily on that of Courtade-Weissman rate-distortion region of the classic two-encoder multiterminal distributed source coding without side information; and extends it to the case in which the decoder has access to a side information stream that is statistically dependent on the sources that need to be compressed. We also apply our result to the so-called Information Bottleneck Method and establish the optimal tradeoff between complexity and accuracy of the prediction in this setting.

In this paper, we present iterative algorithms that numerically compute the rate-distortion regions of two problems: the two-encoder multiterminal source coding problem and the Chief Executive Officer (CEO) problem, both under logarithmic loss distortion measure. With the clear connection of these models with the distributed information bottleneck method, the proposed algorithms may find usefulness in a variety of applications, such as clustering, pattern recognition and learning. We illustrate the efficiency of our algorithms through some numerical examples.

In this paper, we study transmission over a Gaussian interference relay channel. The system consists of two separate transmitters communicating with respective receivers concurrently, in the presence of a half-duplex relay node that assists both transmissions. We develop a coding scheme that is based on the relay node operating in the compute-forward mode, and analyze its performance in terms of offered data transmission rates. We also discuss the relevance of the strategy in various interference regimes. Furthermore, focusing on maximizing the allowed sum rate under individual power constraints, we formulate the problem as a mixed integer quadratically constrained quadratic program, and solve it through iterative methods. The results are illustrated through some numerical examples.

This work investigates the downlink of cloud radio access networks (C-RANs), assuming digital cooperation links among the base stations (BSs). A generalization of the data-sharing scheme is proposed for the case of two BSs and two mobile users. The generalized data-sharing scheme includes a common part and allows full exploitation of correlation among auxiliary codewords. The cooperation links between the BSs are used to exchange and to redirect indices precomputed at the central processor. On the other hand, by simplifying the achievable rate region of the distributed decode-forward (DDF) scheme, it is shown that the DDF scheme for broadcast achieves the capacity region of a downlink $N$-BS $L$-user C- RAN with BS cooperation under the memoryless Gaussian model to within a gap of $\frac{L}{2}#x002B;\frac{\min\ {N,L\log_2 N\}}{2}$ bits per dimension. Numerical evaluations for the memoryless Gaussian model indicate that the generalized data-sharing scheme 1) outperforms the DDF scheme in the low-power regime and when the channel gain matrix is ill-conditioned and 2) benefits more from BS cooperation.

We study the problem of receive beamforming in uplink cascade multiple-input multiple-output (MIMO) systems as an instance of that of cascade multiterminal source coding for lossy function computation. Using this connection, we develop two coding schemes for the second and show that their application leads to beamforming schemes for the first. In the first coding scheme, each terminal in the cascade sends a description of the source that it observes; the decoder reconstructs all sources, lossily, and then computes an estimate of the desired function. This scheme improves upon standard routing in that every terminal only compresses the innovation of its source w.r.t. the descriptions that are sent by the previous terminals in the cascade. In the second scheme, the desired function is computed gradually in the cascade network, and each terminal sends a finer description of it. In the context of uplink cascade MIMO systems, the application of these two schemes leads to centralized receive-beamforming and distributed receive-beamforming, respectively. Numerical results illustrate the performance of the proposed methods and show that they outperform standard routing.

We study the transmission over a cloud radio access network in which multiple base stations (BS) are connected to a central processor (CP) via finite-capacity backhaul links. We propose a lattice-based coding scheme in which the BSs decode linear combinations of the transmitted messages, in the spirit of Compute-and-Forward (CoF), but differs from it essentially in that the decoded equations are remapped to linear combinations of the channel input symbols, sent compressed in a lossy manner to the CP, and are not required to be linearly independent. Also, by opposition to the standard CoF, an appropriate multi-user decoder is utilized to recover the sent messages. This novel scheme differs from both classical Compute-and-Forward and Successive Wyner-Ziv (SWZ) and it is shown to outperform both schemes, in certain regimes, through some numerical examples.

We study the problem of secure transmission over a Gaussian multi-input single-output (MISO) two receiver channel with an external eavesdropper, under the assumption that the state of the channel which is available to each receiver is conveyed either perfectly (P) or with delay (D) to the transmitter. Denoting by S1, S2, and S3the channel state information at the transmitter (CSIT) of user 1, user 2, and eavesdropper, respectively, the overall CSIT can then alternate between eight possible states, i.e., (S1, S2, S3) ∈ {P,D}3. We denote by λS1S2S3the fraction of time during which the state S1S2S3occurs. Under these assumptions, we consider the multi-receiver setup and characterize the SDoF region of fixed hybrid states PPD, PDP, and DDP. We then focus our attention on the symmetric case in which λPDD= λDPD. For this case, we establish bounds on the SDoF region. The analysis reveals that alternating CSIT allows synergistic gains in terms of SDoF; and shows that, by opposition to encoding separately over different states, joint encoding across the states enables strictly better secure rates.

In this work, we investigate two secure source coding models, a Helper problem and a Gray-Wyner problem. In both settings, the encoder is connected to each of the legitimate receivers through a public link as well as a private link; and an external eavesdropper intercepts every information that is sent on the public link. Specifically, in the Helper problem, a memoryless source pair (S0; S1) is to be compressed and sent on both links such that the component S0can be recovered losslessly at the legitimate receiver while being kept completely secret from an eavesdropper that overhears on the public link, and the component S1is recovered lossily, to within some prescribed distortion level, at the legitimate receiver. In the Gray-Wyner model, a memoryless source triple (S0; S1; S2) is to be compressed and sent to two legitimate receivers, such that the component S0is recovered at both receivers losslessly and kept secret at an external eavesdropper that listens on the public link; and the component Sj, is to be recovered lossily at Receiver j, j = 1, 2. We establish single-letter characterizations of the optimal secure rate-distortion regions of both models. The analysis sheds important light on the role of the private link(s), i.e., for the transmission of the source S0or for sharing a secret key that is then used to encrypt the source S0over the public link.

We study the transmission over a cloud radio access network in which multiple relays are connected to a central processor (CP) via error-free finite-capacity links. We develop a lattice-based coding scheme in which each relay node computes a linear combination of the users' messages, in the spirit of standard compute-and-forward (CoF). However, rather than forwarding the computed equation to the CP as in standard CoF, the relay first maps this equation into one on the users' input symbols and then compresses it jointly with its channel output. The equations need not be linearly independent, and the compression also takes into account the correlation with the equations and channel outputs at other relay nodes through Wyner-Ziv coding. The CP first decompresses the signals and then decodes the users' messages successively. We analyze the sum-rate offered by this coding scheme, and show that it outperforms successive Wyner-Ziv scheme in all regimes, and it improves strictly upon the best of successive Wyner-Ziv and CoF in certain regimes.

We investigate two classes of lossy source coding problems under equivocation constraints, namely, an instance of the Helper problem and a Gray-Wyner network model. In the instance of the Helper problem that we consider, an encoder communicates with a legitimate receiver over two links, a private link and a public link; and an external eavesdropper overhears the transmission on the public link. The encoder observes two arbitrarily correlated discrete memoryless sources (Sn0n, S1n) and wishes to transmit the component S1nto the legitimate receiver lossily while maintaining the equivocation about the two sources at the external eavesdropper no smaller than some prescribed level. We establish a single-letter characterization of the optimal rate-distortion-equivocation region of this model. The analysis sheds important light on the role of the private link in this setting. In the Gray-Wyner network model with secrecy constraints that we consider, two sources (Sn1n, S2n) need to be transmitted lossily each to one user while concealing them from an external eavesdropper that overhears the transmission on the common link. For this model as well, we establish a single-letter characterization of the optimal rate-distortion-equivocation region. In particular, we show how the imposed security constraint modifies the standard Gray-Wyner compression scheme.

We study the transmission over a cloud radio access network in which multiple base stations, acting as relay nodes, are connected to a central processor (CP) via error-free rate-limited backhaul links. We propose two lattice-based coding schemes. In the first scheme, each relay node decodes linear combinations of the users' messages in the spirit of compute-and-forward (CoF), but departs from it essentially in that the decoded equations are remapped to equations on the users' input symbols, sent compressed in a lossy manner to the CP, and are not required to be linearly independent. The compression accounts for the correlation between equations at the relay nodes through Wyner-Ziv coding. Also, by opposition to the standard CoF, an appropriate multi-user decoder is utilized to recover the sent messages. The second scheme generalizes the first one by also allowing, at each relay node, a joint compression of the decoded equation on the users' input symbols and the received signal. Both schemes apply in general, but are especially suited for situations in which there are more users that relays. We show that both schemes can outperform standard CoF and successive Wyner-Ziv schemes in certain regimes, and illustrate the gains through some numerical examples.

In this paper, we investigate an instance of the Heegard-Berger problem with two sources and arbitrarily correlated side information sequences at two decoders, in which the reconstruction sets at the decoders are degraded. Specifically, two sources are to be encoded in a manner that one of the two is reproduced losslessly by both the decoders, and the other is reproduced within some prescribed distortion level at one of the two decoders. We establish a single-letter characterization of the rate-distortion function for this model. In particular, we show that the optimal coding scheme for this setting is one in which the common description to be recovered by both the decoders should allow to involve all or part of the source that is to be reproduced at only one decoder. Furthermore, we also generalize our result to the setting in which the source component that is to be recovered by both users is reconstructed in a lossy fashion, under the requirement that all terminals (i.e., the encoder and both the decoders) can share an exact copy of the compressed version of this source component, i.e., a common encoder-decoder reconstruction constraint. For this model as well, we establish a single-letter characterization of the associated rate-distortion function.

We study the problem of secure transmission over a two-user Gaussian multi-input single-output (MISO) broadcast channel under the assumption that the channel to each receiver is conveyed either perfectly (P) or with delay (D) to the transmitter. Denoting S1and S2to be the channel state information at the transmitter (CSIT) of user 1 and user 2, respectively; the overall CSIT can then alternate between four states, i.e., (S1, S2) ∈ {P,D}2. We denote λS1S2be the fraction of time the state S1S2occurs, and focus on the symmetric case such that λS1S2= λS2S1. Under these assumptions, we first consider the Gaussian MISO wiretap channel and characterize the secure degrees of freedom (SDoF). Next, we generalize this model to the two-user Gaussian MISO broadcast channel and establish an inner bound on the SDoF region. This result shows the synergistic SDoF gains of alternating CSIT and illustrates that, as opposed to encoding separately over different states, an improved SDoF region is achievable by joint encoding across these states.

In this paper, we first study a two-user interference channel with generalized feedback. We establish an inner bound on its capacity region. The coding scheme that we employ for the inner bound is based on an appropriate combination of Han-Kobayash rate splitting and compress-and-forward at the senders. Each sender compresses the channel output that is observes using a compression scheme that is à-la Lim et al. noisy network coding and Avestimeher et al. quantize-map-and-forward. Next, we study an injective deterministic model in which the senders obtain output feedback only intermittently. Specializing the coding scheme of the model with generalized feedback to this scenario, we obtain useful insights onto effective ways of combining noisy network coding with interference alignment techniques. We also apply our results to linear deterministic interference channels with intermittent feedback.

We consider a two-user multiaccess channel with degraded messages sets in which the channel state information (CSI) is revealed, strictly causally or with one-unit delay, to only the encoder that sends the common message. We study the capacity region of this model. We establish inner and outer bounds on the capacity region. We also identify some special cases in which the bounds meet, thereby characterizing the capacity region in these cases. The outer bound is non-trivial and has a relatively simple convenient expression (it incorporates only one auxiliary random variable). The coding scheme that we use for the inner bound utilizes rate-splitting to resolve a tension at the informed encoder among exploiting the knowledge of the (delayed) CSI (through a noisy network coding or quantize-map-and-forward state compression) and sending information cooperatively with the other encoder. Together with some previous results on closely related models, the results in this paper shed more light on the utility of delayed CSI for increasing the capacity region of multiaccess channels; and tie with some recent progress in this framework.

We consider a cooperative two-user multiaccess channel in which the transmission is controlled by a random state. Both encoders transmit a common message and, one of the encoders also transmits an individual message. We study the capacity region of this communication model for different degrees of availability of the states at the encoders, causally or strictly causally. In the case in which the states are revealed causally to both encoders but not to the decoder we find an explicit characterization of the capacity region in the discrete memoryless case. In the case in which the states are revealed only strictly causally to both encoders, we establish inner and outer bounds on the capacity region. The outer bound is nontrivial, and has a relatively simple form. It has the advantage of incorporating only one auxiliary random variable. In particular, it suggests that there is none, or at best only little, to gain from having the encoder that transmits both messages also sending an individual description of the state to the receiver, in addition to the compressed version that is sent cooperatively with the other encoder. We then introduce a class of cooperative multiaccess channels with states known strictly causally at both encoders for which the inner and outer bounds agree, and so we characterize the capacity region for this class. In this class of channels, the state can be obtained as a deterministic function of the channel inputs and output. We also study the model in which the states are revealed, strictly causally, in an asymmetric manner, to only one encoder. Throughout this paper, we discuss a number of examples, and compute the capacity region of some of these examples. The results shed more light on the utility of delayed channel state information for increasing the capacity region of state-dependent cooperative multiaccess channels, and tie with recent progress in this framework.

This paper studies a Gaussian two-way relay channel where two communication nodes exchange messages with each other via a relay. It is assumed that all nodes operate in half-duplex mode without any direct link between the communication nodes. A compress-and-forward relaying strategy using nested lattice codes is first proposed. Then, the proposed scheme is improved by performing layered coding: A common layer is decoded by both receivers, and a refinement layer is recovered only by the receiver that has the best channel conditions. The achievable rates of the new scheme are characterized and are shown to be higher than those provided by the decode-and-forward strategy in some regions.

We consider a system in which two users communicate with a destination with the help of a half-duplex relay. Based on the compute-and-forward scheme, we develop and evaluate the performance of coding strategies that are of network coding spirit. In this framework, instead of decoding the users' information messages, the destination decodes two integer-valued linear combinations that relate the transmitted codewords. Two decoding schemes are considered. In the first one, the relay computes one of the linear combinations and then forwards it to the destination. The destination computes the other linear combination based on the direct transmissions. In the second one, accounting for the side information available at the destination through the direct links, the relay compresses what it gets using lattice-based Wyner-Ziv compression and conveys it to the destination. The destination then computes the two linear combinations, locally. For both coding schemes, we discuss the design criteria, and derive the allowed symmetric-rate. Next, we address the power allocation and the selection of the integer-valued coefficients to maximize the offered symmetric-rate; an iterative coordinate descent method is proposed. The analysis shows that the first scheme can outperform standard relaying techniques in certain regimes, and the second scheme, while relying on feasible structured lattice codes, can at best achieve the same performance as regular compress-and-forward for the multiaccess relay network model that we study. The results are illustrated through some numerical examples.

We study a system in which two sources communicate with a destination with the help of a half-duplex relay. We consider a decoding strategy, based on the compute-and-forward strategy, in which the destination decodes two integer-valued linear combinations that relate the transmitted codewords. In this strategy, the relay compresses its observation using Wyner-Ziv compression and then forwards it to the destination. The destination appropriately combines what it gets from the direct transmission and the relay. Then, using this combination, it computes two integer-valued linear combinations. We discuss the encoding/decoding strategy, and evaluate the achievable sum-rate. Next, we consider the problem of allocating the powers and selecting the integer-valued coefficients of the recovered linear combinations in order to maximize the sum-rate. For the model under consideration, the optimization problem is NP hard. We propose an iterative algorithm to solve this problem using coordinate descent method. The results are illustrated through some numerical examples.

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known, causally or only strictly causally, at both encoders, but not at the decoder. Both encoders transmit a common message and, one of the encoders also transmits an individual message. We study the capacity region of this communication model for both causal and strictly causal settings. For the model with causal states, we find an explicit characterization of the capacity region in the discrete memoryless case. For the model with strictly causal states, we establish inner and outer bounds on the capacity region. The outer bound is nontrivial, has a relatively simple form and has the advantage of incorporating only one auxiliary random variable. In particular, it suggests that there is none, or at best only little, to gain from having the encoder that transmits both messages also sending an individual description of the state to the receiver, in addition to the compressed version that is sent cooperatively with the other encoder. The results shed more light on the utility of delayed channel state information for increasing the capacity region of multiaccess channels; and tie with some recent progress in this framework.

We investigate the problem of secure transmission over a two-user multi-input multi-output (MIMO) X-channel with noiseless local feedback and delayed channel state information (CSI) available at transmitters. The transmitters are equipped with M antennas each, and the receivers are equipped with N antennas each. For this model, we characterize the optimal sum secure degrees of freedom (SDoF) region. We show that, in presence of local feedback and delayed CSI, the sum SDoF region of the MIMO X-channel is same as the SDoF region of a two-user MIMO BC with 2M antennas at the transmitter and N antennas at each receiver. This result shows that, upon availability of feedback and delayed CSI, there is no performance loss in sum SDoF due to the distributed nature of the transmitters. Next, we show that this result also holds if only global feedback is conveyed to the transmitters. We also study the case in which only local feedback is provided to the transmitters, i.e., without CSI, and derive a lower bound on the sum SDoF for this model. Furthermore, we specialize our results to the case in which there are no security constraints. In particular, similar to the setting with security constraints, we show that the optimal sum degrees of freedom (sum DoF) region of the (M, M, N, N)-MIMO X-channel is same of the DoF region of a two-user MIMO BC with 2M antennas at the transmitter and N antennas at each receiver. We illustrate our results with some numerical examples.

Parallel two-way relay channel models a cooperative communication scenario where a relay helps two terminals to exchange their messages over independent Gaussian channels. For the single channel case, we have shown previously that lattice-based physical layer network coding achieves the same rate as compress-and-forward scheme with a random coding strategy. A direct extension of this lattice-based scheme to parallel Gaussian channel is to repeat the same strategy for each subchannel. However this approach is not scalable with the number of sub-channels since the complexity of the scheme becomes prohibitive when a large number of sub-channels is employed. In this contribution, we investigate a lattice-based physical layer network coding scheme where the relay jointly processes all the sub-channels together. We characterize the rate region allowed by our coding scheme and assess the performance penalty compared to the separate channel processing approach.

We study a special case of Willems's two-user multiaccess channel with partially cooperating encoders from a security perspective. This model differs from Willems's setup in that only one encoder, Encoder 1, is allowed to conference; Encoder 2 does not transmit any message, and there is an additional passive eavesdropper from whom the communication should be kept secret. For the discrete memoryless (DM) case, we establish inner and outer bounds on the capacity-equivocation region. The inner bound is based on a combination of Willems's coding scheme, noise injection, and additional binning that provides randomization for security. For the memoryless Gaussian model, we establish lower and upper bounds on the secrecy capacity. We also show that, under certain conditions, these bounds agree in some extreme cases of cooperation between the encoders. We illustrate our results through some numerical examples.

We investigate the problem of secure transmission over a two-user multi-input multi-output (MIMO) X-channel in which channel state information is provided with one-unit delay to both transmitters (CSIT), and each receiver feeds back its channel output to a different transmitter. We refer to this model as MIMO X-channel with asymmetric output feedback and delayed CSIT. The transmitters are equipped with M antennas each, and the receivers are equipped with N antennas each. For this model, accounting for both messages at each receiver, we characterize the optimal sum secure degrees of freedom (SDoF) region. We show that, in the presence of asymmetric output feedback and delayed CSIT, the sum SDoF region of the MIMO X-channel is the same as the SDoF region of a two-user MIMO BC with 2M antennas at the transmitter, N antennas at each receiver, and delayed CSIT. This result shows that, upon availability of asymmetric output feedback and delayed CSIT, there is no performance loss in terms of sum SDoF due to the distributed nature of the transmitters. Next, we show that this result also holds if only output feedback is conveyed to the transmitters, but in a symmetric manner, i.e., each receiver feeds back its output to both transmitters and no CSIT. We also study the case in which only asymmetric output feedback is provided to the transmitters, i.e., without CSIT, and derive a lower bound on the sum SDoF for this model. Furthermore, we specialize our results to the case in which there are no security constraints. In particular, similar to the setting with security constraints, we show that the optimal sum DoF region of the (M,M,N,N)-MIMO X-channel with asymmetric output feedback and delayed CSIT is the same as the DoF region of a two-user MIMO BC with 2M antennas at the transmitter, N antennas at each receiver, and delayed CSIT. We illustrate our results with some numerical examples.

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known noncausally to one of the encoders and only strictly causally to the other encoder. Both encoders transmit a common message and, in addition, the encoder that knows the states noncausally transmits an individual message. We find explicit characterizations of the capacity region of this communication model in both discrete memoryless and memoryless Gaussian cases. In particular, the capacity region analysis demonstrates the utility of the knowledge of the states only strictly causally at the encoder that sends only the common message in general. More specifically, in the discrete memoryless setting, we show that such a knowledge is beneficial and increases the capacity region in general. In the Gaussian setting, we show that such a knowledge does not help, and the capacity is same as if the states were completely unknown at the encoder that sends only the common message. Furthermore, we also study the special case in which the two encoders transmit only the common message and show that the knowledge of the states only strictly causally at the encoder that sends only the common message is not beneficial in this case, in both discrete memoryless and memoryless Gaussian settings. The analysis also reveals optimal ways of exploiting the knowledge of the state only strictly causally at the encoder that sends only the common message when such a knowledge is beneficial. The encoders collaborate to convey to the decoder a lossy version of the state, in addition to transmitting the information messages through a generalized Gel'fand–Pinsker binning. Particularly important in this problem are the questions of 1) optimal ways of performing the state compression and 2) whether or not the compression indices should be decoded uniquely. By developing two optimal coding schemes that perform this state compression differently, we show that when used as parts of appropriately tuned encoding and decoding processes, both compression à-la noisy network coding by Limor the quantize-map-and-forward by Avestimeher, i.e., with no binning, and compression using Wyner–Ziv binning are optimal. The scheme that uses Wyner–Ziv binning shares elements with Cover and El Gamal original compress-and-forward, but differs from it mainly in that backward decoding is employed instead of forward decoding and the compression indices are not decoded uniquely. Finally, by exploring the properties of our outer bound, we show that, although not required in general, the compression indices can in fact be decoded uniquely essentially without altering the capacity region, but at the expense of larger alphabets sizes for the auxiliary random variables.

We consider a three-terminal state-dependent relay channel with the channel state available noncausally at only the source. Such a model may be of interest for node cooperation in the framework of cognition, i.e., collaborative signal transmission involving cognitive and noncognitive radios. We study the capacity of this communication model. One principal problem is caused by the relay's not knowing the channel state. For the discrete memoryless (DM) model, we establish two lower bounds and an upper bound on channel capacity. The first lower bound is obtained by a coding scheme in which the source describes the state of the channel to the relay and destination, which then exploit the gained description for a better communication of the source's information message. The coding scheme for the second lower bound remedies the relay's not knowing the states of the channel by first computing, at the source, the appropriate input that the relay would send had the relay known the states of the channel, and then transmitting this appropriate input to the relay. The relay simply guesses the sent input and sends it in the next block. The upper bound accounts for not knowing the state at the relay and destination. For the general Gaussian model, we derive lower bounds on the channel capacity by exploiting ideas in the spirit of those we use for the DM model; and we show that these bounds are optimal for small and large noise at the relay irrespective to the strength of the interference. Furthermore, we also consider a relay model with orthogonal channels from the source to the relay and from the source and relay to the destination in which the source input component that is heard by the relay does not depend on the channel states. We establish a better upper bound for both DM and Gaussian cases and we also characterize the capacity in a number of special cases.

We consider a multiple access relay channel (MARC), in which a relay, based on the recently proposed compute-and-forward protocol, helps two transmitters to communicate with a common destination. The relay decodes a linear combination of the received symbols instead of the individual symbols then forwards the new symbol to the destination. The destination recovers two linear equations from the decoded signals. The two equations relate the transmitted symbols with integer coefficients at different computational rates. We propose an iterative algorithm to optimize the integer coefficients and the power allocation at the transmitters alternatively, so that the sum-rate is maximized. In each iteration, the integer coefficients are updated by solving a mixed-integer quadratic programming (MIQP) problem with quadratic constraints, while the power allocation is updated by solving a series of geometric programs using a successive convex approximation method. The simulation results show that the compute-and-forward strategy and the proposed optimization method can offer substantial gain over the standard amplify-and-forward and decode-and-forward protocols for this model.

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known non-causally to one of the encoders and only strictly causally to the other encoder. Both encoders transmit a common message and, in addition, the encoder that knows the states non-causally transmits an individual message. We find explicit characterizations of the capacity region of this communication model. The analysis also reveals optimal ways of exploiting the knowledge of the state only strictly causally at the encoder that sends only the common message when such a knowledge is beneficial. The encoders collaborate to convey to the decoder a lossy version of the state, in addition to transmitting the information messages through a generalized Gel'fand-Pinsker binning. Particularly important in this problem are the questions of 1) optimal ways of performing the state compression and 2) whether or not the compression indices should be decoded uniquely. We show that both compression à-la noisy network coding, i.e., with no binning, and compression using Wyner-Ziv binning are optimal. The scheme that uses Wyner-Ziv binning shares elements with Cover and El Gamal original compress-and-forward, but differs from it mainly in that backward decoding is employed instead of forward decoding and the compression indices are not decoded uniquely. Finally, by exploring the properties of our outer bound, we show that, although not required in general, the compression indices can in fact be decoded uniquely essentially without altering the capacity region, but at the expense of larger alphabets sizes for the auxiliary random variables.

We investigate the problem of secure communication over parallel relay channel in the presence of a passive eavesdropper. We consider a four-terminal relay-eavesdropper channel which consists of multiple relay-eavesdropper channels as subchannels. For the discrete memoryless model, we establish outer and inner bounds on the rate-equivocation region. The inner bound allows mode selection at the relay. For each subchannel, secure transmission is obtained through one of two coding schemes at the relay: decoding-and-forwarding the source message or confusing the eavesdropper through noise injection. For the Gaussian memoryless channel, we establish lower and upper bounds on the perfect secrecy rate. Furthermore, we study a special case in which the relay does not hear the source and show that under certain conditions the lower and upper bounds coincide. The results established for the parallel Gaussian relay-eavesdropper channel are then applied to study the fading relay-eavesdropper channel. Analytical results are illustrated through some numerical examples.

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known non-causally to one of the encoders and only strictly causally to the other encoder. Both encoders transmit a common message and, in addition, the encoder that knows the states non-causally transmits an individual message. We study the capacity region of this communication model. In the discrete memoryless case, we establish inner and outer bounds on the capacity region. Although the encoder that sends both messages knows the states fully, we show that the strictly causal knowledge of these states at the other encoder can be beneficial for this encoder, and in general enlarges the capacity region. Furthermore, we find an explicit characterization of the capacity in the case in which the two encoders transmit only the common message. In the Gaussian case, we characterize the capacity region for the model with individual message as well. Our converse proof in this case shows that, for this model, strictly causal knowledge of the state at one of the encoders does not increase capacity if the other is informed non-causally, a result which sheds more light on the utility of conveying a compressed version of the state to the decoder in recent results by Lapidoth and Steinberg on a multiacess model with only strictly causal state at both encoders and independent messages.

We consider a three-terminal state-dependent relay channel with the channel state available non-causally at only the source. Such a model may be of interest for node cooperation in the framework of cognition, i.e., collaborative signal transmission involving cognitive and non-cognitive radios. We study the capacity of this communication model. One principal problem in this setup is caused by the relay's not knowing the channel state. In the discrete memoryless (DM) case, we establish lower bounds on channel capacity. For the Gaussian case, we derive lower and upper bounds on the channel capacity. The upper bound is strictly better than the cut-set upper bound. We show that one of the developed lower bounds comes close to the upper bound, asymptotically, for certain ranges of rates.

In this paper, we consider a three-terminal state-dependent relay channel (RC) with the channel state noncausally available at only the relay. Such a model may be useful for designing cooperative wireless networks with some terminals equipped with cognition capabilities, i.e., the relay in our setup. In the discrete memoryless (DM) case, we establish lower and upper bounds on channel capacity. The lower bound is obtained by a coding scheme at the relay that uses a combination of codeword splitting, Gel'fand-Pinsker binning, and decode-and-forward (DF) relaying. The upper bound improves upon that obtained by assuming that the channel state is available at the source, the relay, and the destination. For the Gaussian case, we also derive lower and upper bounds on the capacity. The lower bound is obtained by a coding scheme at the relay that uses a combination of codeword splitting, generalized dirty paper coding (DPC), and DF relaying; the upper bound is also better than that obtained by assuming that the channel state is available at the source, the relay, and the destination. In the case of degraded Gaussian channels, the lower bound meets with the upper bound for some special cases, and, so, the capacity is obtained for these cases. Furthermore, in the Gaussian case, we also extend the results to the case in which the relay operates in a half-duplex mode.

We consider an OFDM (orthogonal frequency division multiplexing) point to point transmission scheme improved by a relay. For each carrier, symbols sent by the source may be retransmitted during a second time slot by the relay, which is assumed to be of the decode-and-forward (DF) type. For each relayed carrier the destination implements maximum ratio combining. Assuming perfect CSI (channel state information) knowledge the paper investigates the power allocation problem in order to maximize the rate offered by the scheme. Compared to, the second time slot is better used. The source is allowed to transmit a new symbol during this second time slot when the relay is inactive. For this improved protocol, the optimization has been conducted for a sum power constraint and reported in. The present paper is devoted to the case of individual power constraints at the source and at the relay. The theoretical analysis is illustrated by numerical results.

A relay interferer channel consists of the classic relay channel with an additional source of interference. A three- terminal full-duplex Gaussian relay interferer channel with a cognitive source is analyzed. Each of the relay node and the destination node experiences on its link an additive Gaussian outside interference, in addition to additive noise. Only the source node, referred to as being the cognitive encoder, knows the interferences, in a non-causal manner. We first focus on the case in which the links to the relay and to the destination are corrupted by the same interference; and then we focus on the case of independent interferences. For each of these two models, we establish a lower bound on the channel capacity. The coding schemes for the lower bounds use techniques of dirty paper coding or carbon copying onto dirty paper, interference reduction at the source and decode-and-forward relaying. The results reveal that, by opposition to carbon copying onto dirty paper and its root Costa's initial dirty paper coding (DPC), it may be beneficial in our setup that the informed source uses a part of its power to partially cancel the effect of the interference so that the uninformed relay benefits from this cancellation, and so the source benefits in turn.

We consider a two-user state-dependent multiaccess channel in which only one of the encoders is informed, non-causally, of the channel states. Two independent messages are transmitted: a common message transmitted by both the informed and uninformed encoders, and an individual message transmitted by only the uninformed encoder. We derive inner and outer bounds on the capacity region of this model in the discrete memoryless case as well as the Gaussian case. Further, we show that the bounds for the Gaussian case are tight in some special cases.

We consider the problem of transmission over a relay version of the carbon-copying onto dirty paper. In this setup, additive Gaussian outside interferences corrupt both transmissions to the relay and to the destination; and only the source knows the interferences (in a noncausal manner). We first focus on the case of one interference corrupting both links; and then we focus on the case of two independent interferences. For each of these two models, we establish a lower bound on the channel capacity. The coding schemes for the lower bounds use techniques of dirty paper coding or carbon copying onto dirty paper, interference reduction at the source and decodeand-forward relaying. The results reveal that, by opposition to carbon copying onto dirty paper and its root Costa's initial dirty paper coding (DPC), it may be beneficial in our setup that the informed source uses a part of its power to partially cancel the effect of the interference so that the uninformed relay benefits from this cancellation, and so the source benefits in turn. The established results may be of importance for the emerging field of cooperation in presence of some cognitive radios that might be aware of some of other users messages intended to a common receiver.

We consider an OFDM (orthogonal frequency division multiplexing) point to point transmission scheme improved by means of multiple relays. For each carrier, symbols sent by the source during a first time slot, may be retransmitted during a second time slot by the relays, which are assumed to be of the decode-and-forward (DF) type. For each relayed carrier the destination implements maximum ratio combining. Assuming perfect CSI (channel state information) knowledge the paper investigates the power allocation problem in order to maximize the rate offered by the scheme. Similarly to the protocol proposed in, the source is allowed to transmit a new symbol during the second time slot when none of the relay is assisting. The constraints of decodability at the relays are properly handled. The optimization is conducted for a constraint on the sum of powers at the source and at the relays. Next to the optimized solution, a suboptimum method based on relay selection is proposed and discussed. The theoretical analysis is illustrated by numerical results.

Cooperative information embedding deals with the problem of embedding unperceived information into some cover signal by different users or partners, cooperatively. It models applications in which embedded signals, or watermarks, transmitted over wireless networks need to be reinforced in order to withstand channel impairments. In cooperative information embedding, each embedder that can reinforce the embedded signal may or may not know the original cover signal. In this paper, we concentrate on the two user cases: (1) an initial embedder and (2) an assisting embedder or helper collaborate to embed some watermark into given digital media content which is transmitted over a wireless network. One important application is that of infrastructure-aided information embedding, a case in which the network provider plays the role of a helper and contributes to securing the distribution of the media, not only by blocking unauthorized signals but also by reinforcing the watermarks in legitimate signals. We investigate the two scenarios in which the helper does or does not know the cover signal. For each scenario, we derive lower and upper bounds on channel capacity. Furthermore, we also design implementable coding schemes and derive the embedding rates practically allowed by these schemes, for both scenarios. Among others, the performance characterization shows that for cooperative information embedding to be effective, careful code design is required at the initial embedder and the helper. The careful design concerns the joint conception of the embedded codes and the exploitation of the knowledge of the cover signal, if any.

We consider OFDM (orthogonal frequency division multiplexing) transmission helped by a relay. Symbols sent by the source may or may not be retransmitted by a relay during a second time slot. The relay is supposed to operate in Decode-and-Forward (DF) mode. For each carrier the destination implements maximum ratio combining. Assuming perfect CSI (channel state information) knowledge the paper investigates the power allocation problem for rate maximization of the scheme. Both cases of a sum power constraint, and of individual power constraints at the source and at the relay are tackled. The theoretical analysis is illustrated by numerical results for both types of constraints.

We consider a state-dependent full-duplex relay channel with the state of the channel non-causally available at only the relay. In the framework of cooperative wireless networks, some specific terminals can be equipped with cognition capabilities, i.e, the relay in our model. In the discrete memoryless (DM) case, we derive lower and upper bounds on channel capacity. The lower bound is obtained by a coding scheme at the relay that consists in a combination of codeword splitting, Gelpsilafand-Pinsker binning, and a decode-and-forward scheme. The upper bound is better than that obtained by assuming the availability of state at the source, the relay, and the destination. For the Gaussian case, we also derive lower and upper bounds on channel capacity. The lower bound, obtained by a coding scheme based on combination of codeword splitting and generalized dirty paper coding, is tight in some cases if the channel is physically degraded. The upper bound is also better than that obtained by assuming that the channel state is available at the source, the relay, and the destination.

In this paper, we investigate diversity gain in coding for a 2-user multiple-access-channel (MAC) with cooperating transmitters-the MAC with relaying. We propose a simple distributed space-time-frequency block coding (D-STFBC) scheme and analyze the offered diversity gain. In particular, we show that full diversity (order 3) is possible if collaboration is well enough and rigorous signal processing is assumed both at the transmitters and the receiver. Bit-error-rate (BER) analysis and curves are provided for illustrative purposes.

In this paper, we propose an audio watermarking scheme based on the scalar Costa scheme specifically calibrated with a perceptual model allowing to increase the embedding power. For our study, this scheme is designed to be efficient for low bit-rate embedding with sufficient robustness to channel degradations. We present here the main characteristics of our scheme and the way for introducing perceptual models in such a Costa based watermarking scheme without introducing any noticeable artifacts. An evaluation of the robustness of the embedding system is also theoretically discussed by the way of the main channel attack : additive noise from low to high level. We illustrate its relevance in practice using Monte Carlo simulations.

This paper investigates the sensitivity of the achievables rates for the full-duplex relay channel to small additive disturbances on channel links. The focus is on two relaying strategies - the decode-and-forward (DF) mode and the compress-and-forward (CF) mode. We use Fisher Information and De-Bruijn's identity to assess the decrease in the corresponding rates due to small additive contaminating noise. Analysis sheds light on the respective sensitivity levels of these schemes and hence, provides insights onto the choice of appropriate relaying strategies in the situations where some trade-off between transmission rate and sensitivity is needed. Next, we show that these results can be used to emphasize the effect of channel estimation error on relaying transmissions. An important (somehow intuitive) observation at this stage is that transmission through the direct link (i.e., relay is off) may improve upon both decode-and-forward and compress-and-forward schemes, when the channel is "bad enough". Finally, a lower bound on the capacity of a relay channel under channel estimation error is obtained by combining well known relaying strategies, each over the appropriate SNR range. Analysis is supported by some examples.

In this work, coding for the relay channel (RC) and the cooperative relay broadcast channel (RBC) controlled by random parameters are studied. In the first channel, the RC, information is transferred from the transmitter to the receiver through a multiplicity of nodes which all "simply" act as relays. In the second channel, the cooperative RBC, each intermediate node also acts as a receiver, i.e., it decodes a "private message". For each of these two channels, we consider the situation when side information (SI) Snon the random parameters is non- causally provided to the transmitter and all the intermediate nodes but not the final receiver, and derive an achievable rate region based on the relays using the decode-and-forward scheme. In the special case when the channels are degraded Gaussian and the side information (SI) is additive i.i.d. Gaussian, we show that 1) the rate regions are tight and provide the corresponding capacity regions and 2) the state Sndoes not affect these capacity regions, even though the final receiver has no knowledge of the state. For the degraded Gaussian RC, the results in this paper can be seen as an extension of those by Kim et al. to the case of more than one relay.

In this work, we consider a partially cooperative relay broadcast channel (PC-RBC) controlled by random parameters. We provide rate regions for two different situations: (1) when side information (SI) Snon the random parameters is non-causally known at both the source and the relay and, (2) when side information Snis non-causally known at the source only. These achievable regions are derived for the general discrete memoryless case first and then extended to the case when the channel is degraded Gaussian and the SI is additive i.i.d. Gaussian. In this case, the source uses generalized dirty paper coding (GDPC), i.e., DPC combined with partial state cancellation, when only the source is informed, and DPC alone when both the source and the relay are informed. It appears that, even though it can not completely eliminate the effect of the SI (in contrast to the case of source and relay being informed), GDPC is particularly useful when only the source is informed.

Multiple user information embedding is concerned with embedding several messages into the same host signal. While emphasizing the tight relationship with conventional multiple user information theory, this paper presents several implementable "dirty paper coding" (DPC) based schemes for multiple user information embedding. These are obtained by exploring strong connections with the well-known Gaussian multiple access channel (MAC) with state information at the encoders. Two practical schemes are compared. The first -rather intuitive- consists in a straightforward superimposition of DPC schemes. The second consists in a joint design of these dirty paper coding schemes, based on the ideal DPC-based coding for the equivalent MAC channel. These results extend to the multiple user case the practical implementations (QIM and SCS) that have been originally conceived for one user. Then, we extend the results to a more general coding based on lattice (vector) codebooks, showing that the gap to full performances can be bridged up by using finite dimensional lattice codebooks, at the cost of an increased computational complexity. The improvements brought by a joint design are illustrated by bit error rates curves and achievable rates region

In some situations of channel coding with state information (CCSI), the encoder and/or the decoder may not have perfect knowledge of the state information. In these situations, the state information may be viewed as the sum of a dominant (nominal) state information and a relatively weak perturbation. We consider the general case of channel with arbitrary pair of independent and identically distributed (i.i.d), possibly correlated, state information (S1, S2) available at the transmitter and at the receiver, respectively. We first analyze the decrease in capacity, or channel sensitivity to this perturbing noise. Both lower and upper bounds on this channel sensitivity are provided, using Fisher Information. The lower bound turns to be relatively tight, at low Signal-to-Noise-Ratio (SNR), in the Gaussian case, for which we provide a closed form expression of channel capacity degradation. Next, we show that these results can be used so as to increase system immunity to noise, by adapting the encoder to the channel uncertainty. Also, we straightforwardly extend these results to the more practical case where the state information is known only causally at the transmitter. Finally, for illustration purposes, two possible applications in the non-causal and the causal case, respectively, are discussed.

Multiple watermarking is concerned with embedding several messages into the same host signal, with different robustness and transparency requirements. This paper proposes two implementable scalar schemes for multiple user "dirty paper coding". The first - straightforward - approach consists of an independent superposition of two scalar dirty paper coding schemes. The second consists in the joint design of a scalar dirty paper coding. This joint approach is based on the ideal dirty paper coding scheme for broadcast channels with noncausal side information known to the transmitter. For this purpose, the "scalar Costa scheme" that has been originally conceived for one user is extended to two users. Performance evaluations, including bit error rates and capacity region curves are provided for both methods, illustrating the improvements brought by a joint design.

Information embedding has recently been recognized as power-limited communication over a "super"-channel with state information non-causally known at the encoder. Based on this equivalence many encoding schemes have been proposed. Quantization index modulation (QIM) family has emerged as an asymptotically information-theoretically optimal embedding function. Optimum transmission rates are achieved when both the watermark-to-noise ratio (WNR) and quantizers dimensionality become sufficiently large. At low WNR however, a trade-off between transmission rate and robustness should be found. This paper is concerned with deriving lattice encoding performances over the resulting modulo lattice additive noise channel (MLAN) for both high and low WNR regimes. To this end, some lattices with good packing and quantizing properties are used and corresponding capacity and bit-error rate (BER) curves are provided for both regular QIM, and distortion-compensated QIM.