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.

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 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 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.

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 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).

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.

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.

• A novel convex clustering with metric learning approach is proposed. • The convex clustering with distance metric problem is solved using an Alternating Direction Method of Multipliers (ADMM). • Shows that convex clustering and metric learning can be done iteratively and improve results of clustering solutions. • Numerical experiments show that metric learning can improve the results of convex clustering significantly. The convex clustering formulation of Chi and Lange (2015) is revisited. While this formulation can be precisely and efficiently solved, it uses the standard Euclidean metric to measure the distance between the data points and their corresponding cluster centers and hence its performance deteriorates significantly in the presence of outlier features. To address this issue, this paper considers a formulation that combines convex clustering with metric learning. It is shown that: (1) for any given positive definite Mahalanobis distance metric, the problem of convex clustering can be precisely and efficiently solved using the Alternating Direction Method of Multipliers ; (2) the problem of learning a positive definite Mahalanobis distance metric admits a closed-form solution; (3) an algorithm that alternates between convex clustering and metric learning can provide a significant performance boost over not only the original convex clustering formulation but also the recently proposed robust convex clustering formulation of Wang et al. (2017).

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 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.

This paper studies wireless networks with multiple real-time flows that have stringent requirements on both per-packet delay and long-term average delivery ratio. Each flow dynamically adjusts its traffic load based on its observation of network status. When the requirements of per-packet delay and delivery ratio are satisfied, each flow obtains some utility based on its traffic load. We aim to design joint rate control and scheduling policies that maximize the total utility in the system. We first show that the problem of maximizing total utility can be formulated as a submodular optimization problem with exponentially many constraints. We then propose two simple distributed policies that require almost no coordination between different entities in the network. The total utilities under these two policies can be made arbitrarily close to the theoretical upper-bound. Extensive simulations also show that they achieve much better performance than state-of-the-art policies.

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.

Because the exchange of information among all the users in a large network can take a long time, a successive omniscience protocol is proposed. Namely, subgroups of users first recover the information of other users in the same subgroup at an earlier stage called local omniscience. Then, the users recover the information of all other users at a later stage called global omniscience. To facilitate the information exchange, a distributed storage system is used, so that users can conveniently upload and download messages through some reliable central servers. The minimum upload bandwidth is characterized and a bandwidth-storage trade-off is discovered. The results reveal the new connections to the problem of secret key agreement and, consequently, provide meaningful interpretations of a recently proposed multivariate mutual information measure that was inspired by the secret key agreement problem.

We study the capacity region of the parallel Gaussian bidirectional relay channel with L independent subchannels and propose efficient coding schemes for approaching the capacity limit within a constant gap. A two-step approach is considered. First, the corresponding finite field linear deterministic model is studied, for which linear network coding across sub-channels is shown to achieve the capacity region of the channel. Next, based on the insight obtained, a lattice-based compute-and-forward scheme together with simple linear network coding across sub-channels is proposed and is shown to achieve the capacity region of the Gaussian model to within L bits per user regardless of the channel parameters. Even though coding across different sub-channels is necessary for approaching the capacity region, it is shown that this can be realized through a simple linear network coding scheme (across different sub-channels) at the relay.

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 prove that by imposing a conditional mutual independence constraint and a marginalisation constraint, the almost entropic region can be completely characterised by Shannon-type information inequalities. Such a property is applied to obtain an explicit lower bound on the generalised Wyner common information.

The limits of treating interference as noise are studied for the canonical two-user symmetric Gaussian interference channel. A two-step approach is proposed for finding approximately optimal input distributions in the high signal-to-noise ratio (SNR) regime. First, approximately and precisely optimal input distributions are found for the Avestimehr-Diggavi-Tse (ADT) linear deterministic model. These distributions are then translated, systematically, into Gaussian models, which we show can achieve the sum capacity to within O(log log(SNR)).

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.

The capacity for multiterminal secret-key agreement inspires a natural generalization of Shannon's mutual information from two random variables to multiple random variables. Under a general source model without helpers, the capacity is shown to be equal to the normalized divergence from the joint distribution of the random sources to the product of marginal distributions minimized over partitions of the random sources. The mathematical underpinnings are the works on co-intersecting submodular functions and the principle lattices of partitions of the Dilworth truncation. We clarify the connection to these works and enrich them with information-theoretic interpretations and properties that are useful in solving other related problems in information theory as well as machine learning.

An explicit characterization of the capacity region of the general network coding problem is one of the best known open problems in information theory. A simple set of bounds that is often used in the literature to show that certain rate tuples are infeasible are based on the graph-theoretic notion of cut. The standard cut-set bounds, however, are known to be loose in general when there are multiple messages to be communicated in the network. This paper focuses on broadcast networks, for which the standard cut-set bounds are closely related to union as a specific set operation to combine different simple cuts of the network. A new set of explicit network coding bounds, which combine different simple cuts of the network via a variety of set operations (not just the union), are established via their connections to extremal inequalities for submodular functions. The tightness of these bounds are demonstrated via applications to combination networks.

We consider symmetric two-user Gaussian interference channel with common messages. We derive an upper bound on the sum capacity, and show that the upper bound is tight in the very low interference regime, where the optimal transmission scheme is to send no common messages and each receiver treats interference as noise. Our result shows that although the availability of common messages provides a cooperation opportunity for transmitters, in the low interference regime the presence of common messages does not help increase the sum capacity.

This paper provides a polyhedral description of the symmetrical latency capacity region of broadcast channels. The converse result is established via the recently proposed generalized cut-set bounds for broadcast networks. The achievability result is proved by considering a “pairwise exchange” scheme and successive encoding.

Symmetrical multilevel diversity coding (SMDC) is a classical model for coding over distributed storage. In this setting, a simple separate encoding strategy known as superposition coding was shown to be optimal in terms of achieving the minimum sum rate and the entire admissible rate region of the problem. The proofs utilized carefully constructed induction arguments, for which the classical subset entropy inequality played a key role. This paper consists of two parts. In the first part, the existing optimality proofs for classical SMDC are revisited, with a focus on their connections to subset entropy inequalities. Initially, a new sliding-window subset entropy inequality is introduced and then used to establish the optimality of superposition coding for achieving the minimum sum rate under a weaker source-reconstruction requirement. Finally, a subset entropy inequality recently proved by Madiman and Tetali is used to develop a new structural understanding of the work of Yeung and Zhang on the optimality of superposition coding for achieving the entire admissible rate region. Building on the connections between classical SMDC and the subset entropy inequalities developed in the first part, in the second part the optimality of superposition coding is extended to the cases where there is either an additional all-access encoder or an additional secrecy constraint.

We study broadcasting of two confidential messages to two groups of receivers over independent parallel subchannels. One group consists of an arbitrary number of receivers, interested in a common message, whereas the other group has only one receiver. Each message must be confidential from the receiver(s) in the other group. Each of the subchannels is assumed to be degraded in a certain fashion. While corner points of the capacity region of this setup were characterized in earlier works, we establish the complete capacity region, and show the optimality of a superposition coding technique. For Gaussian channels, we establish the optimality of a Gaussian input distribution by applying an extremal information inequality. By extending our coding scheme to block-fading channels, we demonstrate significant performance gains over a baseline time-sharing scheme.

The concept of channel capacity per unit cost was introduced by Verdu in 1990 to study the limits of cost-efficient wide-band communication. It was shown that orthogonal signaling can achieve the channel capacity per unit cost of memoryless stationary channels with a zero-cost input letter. This paper introduces a concept of secrecy capacity per unit cost to study cost-efficient wide-band secrecy communication. For degraded memoryless stationary wiretap channels, it is shown that an orthogonal coding scheme with randomized pulse position and constant pulse shape achieves the secrecy capacity per unit cost with a zero-cost input letter. For general memoryless stationary wiretap channels, the performance of orthogonal codes is studied, and the benefit of further randomizing the pulse shape is demonstrated via a simple example.

Symmetrical multilevel diversity coding (SMDC) is a network compression problem introduced by Roche (1992) and Yeung (1995). In this setting, a simple separate encoding strategy known as superposition coding was shown to be optimal in terms of achieving the minimum sum rate (Roche-Yeung-Hau 1997) and the entire admissible rate region (Yeung-Zhang 1999) of the general problem. This paper considers a natural generalization of SMDC to the secure communication setting with an additional eavesdropper. It is required that all sources need to be kept perfectly secret from the eavesdropper as long as the number of encoder outputs available at the eavesdropper is no more than a given threshold. First, the problem of encoding individual sources is studied. A precise characterization of the entire admissible rate region is established via a connection to the problem of ramp-type secret sharing (Yamamoto 1985 and Blakley-Meadows 1985) and utilizing some basic polyhedral structure of the admissible rate region. Building on this result, it is then shown that superposition coding remains optimal in terms of achieving the minimum sum rate for the general secure SMDC problem.

This paper presents two new results on multiple-input multiple-output (MIMO) Gaussian broadcast channels with confidential messages. First, the MIMO Gaussian wiretap channel is revisited. A matrix characterization of the capacity-equivocation region is provided, which extends the previous result on the secrecy capacity to the more general imperfect secrecy setting. Next, the MIMO Gaussian broadcast channel with two receivers and three independent messages: a common message intended for both receivers, and two confidential messages each intended for one of the receivers but needing to be kept asymptotically perfectly secret from the other, is considered. A precise characterization of the capacity region is provided, generalizing the previous results which considered only two out of three possible messages.

We introduce two new source coding problems: robust sequential coding and robust predictive coding. For the Gauss-Markov source model with the mean squared error distortion measure, we characterize certain supporting hyperplanes of the rate region of these two coding problems. Our investigation also reveals an information-theoretic minimax theorem and the associated extremal inequalities.

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.

Symmetrical Multilevel Diversity Coding (SMDC) is a network compression problem introduced by Roche (1992) and Yeung (1995). This paper considers a generalization of SMDC for which, in addition to the randomly accessible encoders, there is also an all-access encoder. It is shown that a simple separate coding strategy known as superposition coding is optimal in terms of achieving the entire admissible rate region of the problem. Key to our proof is to identify the supporting hyperplanes that define the boundary of the admissible rate region and then builds on the result of Yeung and Zhang on a generalization of Han's subset inequality.

We study private broadcasting of two messages to two groups of users over reversely degraded parallel channels. Group 1 has two users, both interested in a common message whereas group 2 has only one user. The message for each group of users needs to be kept confidential from the other group. We characterize the capacity region for a special degradation structure of the channels and establish the optimality of a superposition codebook where codewords of a secure product-codebook form the cloud centers and codewords of a secure multicast codebook form the satellite codewords. An extension to Gaussian channels with a sum-power constraint is also obtained, where the optimality of Gaussian codebooks is established using an extremal inequality.

We introduce two new source coding problems: robust sequential coding and robust predictive coding. For the Gauss-Markov source model, we characterize certain supporting hyperplanes of the rate region of these two coding problems. Our investigation also reveals a class of extremal inequalities and minimax theorems.

For delay-limited communication over block-fading channels, the difference between the ergodic capacity and the maximum expected rate for coding over a finite number of coherent blocks represents the penalty incurred by the delay constraint. This paper introduces a notion of worst-case expected-rate loss. Focusing on the slow-fading scenario (one block delay), the worst-case expected-rate loss is precisely characterized for the point-to-point fading channel and is characterized to within one bit for the fading-paper channel.

This paper considers the problem of simultaneously communicating two messages, a high-security message and a low-security message, to a legitimate receiver, referred to as the security embedding problem. An information-theoretic formulation of the problem is presented. A coding scheme that combines rate splitting, superposition coding, nested binning, and channel prefixing is considered and is shown to achieve the secrecy capacity region of the channel in several scenarios. Specifying these results to both scalar and independent parallel Gaussian channels (under an average individual per-subchannel power constraint), it is shown that the high-security message can be embedded into the low-security message at full rate (as if the low-security message does not exist) without incurring any loss on the overall rate of communication (as if both messages are low-security messages). Extensions to the wiretap channel II setting of Ozarow and Wyner are also considered, where it is shown that "perfect" security embedding can be achieved by an encoder that uses a two-level coset code.

Recently, there has been a lot of success in using the deterministic approach to provide approximate characterization of Gaussian network capacity. In this paper, we take a deterministic view and revisit the problem of wiretap channel with side information. A precise characterization of the secrecy capacity is obtained for a linear deterministic model, which naturally suggests a coding scheme which we show to achieve the secrecy capacity of the degraded Gaussian model (dubbed as “secret writing on dirty paper”) to within half a bit.

Recently there has been a lot of success in using the deterministic approach to provide approximate characterization of Gaussian network capacity. In this paper, we take a deterministic view and revisit the problem of wiretap channel with side information. A precise characterization of the secrecy capacity is obtained for a linear deterministic model, which naturally suggests a coding scheme which we show to achieve the secrecy capacity of the degraded Gaussian model (dubbed as “secret writing on dirty paper”) to within (1/2) log 3 bits.

A precise matrix characterization of the capacity-equivocation region of the multiple-input multiple-output (MIMO) Gaussian wiretap channel is established. This characterization is obtained via a connection to the problem of simultaneously communicating a private and a confidential messages over a MIMO Gaussian broadcast channel, for which the secrecy capacity region can be established using previous results on the secrecy capacity of the MIMO Gaussian wiretap channel.

This paper considers the problem of secret communication over a two-receiver multiple-input multiple-output (MIMO) Gaussian broadcast channel. The transmitter has two independent, confidential messages and a common message. Each of the confidential messages is intended for one of the receivers but needs to be kept perfectly secret from the other, and the common message is intended for both receivers. It is shown that a natural scheme that combines secret dirty-paper coding with Gaussian superposition coding achieves the secrecy capacity region. To prove this result, a channel-enhancement approach and an extremal entropy inequality of Weingarten et al. are used.

This paper considers the problem of simultaneously communicating high-security and low-security messages, referred to as the security embedding problem. An information-theoretic model is presented. A coding scheme that combines superposition coding and random binning is proposed and is shown to achieve the capacity region in several communication scenarios. As an application, it is shown that a simple scheme that combines security embedding codes and secure network coding can achieve the secrecy capacity of a parallel multi-eavesdropper wiretap channel with two reversely degraded components.

This paper considers an entropy-power inequality (EPI) of Costa and presents a natural vector generalization with a real positive semidefinite matrix parameter. The new inequality is proved using a perturbation approach via a fundamental relationship between the derivative of mutual information and the minimum mean-square error (MMSE) estimate in linear vector Gaussian channels. As an application, a new extremal entropy inequality is derived from the generalized Costa EPI and then used to establish the secrecy capacity regions of the degraded vector Gaussian broadcast channel with layered confidential messages.

This paper considers the problem of secret communication over a two-receiver multiple-input multiple-output (MIMO) Gaussian broadcast channel. The transmitter has two independent messages, each of which is intended for one of the receivers but needs to be kept asymptotically perfectly secret from the other. It is shown that, surprisingly, under a matrix power constraint, both messages can be simultaneously transmitted at their respective maximal secrecy rates. To prove this result, the MIMO Gaussian wiretap channel is revisited and a new characterization of its secrecy capacity is provided via a new coding scheme that uses artificial noise (an additive prefix channel) and random binning.

This paper considers the problem of the multiple-input multiple-output (MIMO) Gaussian broadcast channel with two receivers (receivers 1 and 2) and two messages: a common message intended for both receivers and a confidential message intended only for receiver 1 but needing to be kept asymptotically perfectly secure from receiver 2. A matrix characterization of the secrecy capacity region is established via a channel enhancement argument. The enhanced channel is constructed by first splitting receiver 1 into two virtual receivers and then enhancing only the virtual receiver that decodes the confidential message. The secrecy capacity region of the enhanced channel is characterized using an extremal entropy inequality previously established for characterizing the capacity region of a degraded compound MIMO Gaussian broadcast channel.

We study the transmission capacities of two coexisting wireless networks (a primary network vs. a secondary network) that operate in the same geographic region and share the same spectrum. We define transmission capacity as the product among the density of transmissions, the transmission rate, and the successful transmission probability (1 minus the outage probability). The primary (PR) network has a higher priority to access the spectrum without particular considerations for the secondary (SR) network, where the SR network limits its interference to the PR network by carefully controlling the density of its transmitters. Assuming that the nodes are distributed according to Poisson point processes and the two networks use different transmission ranges, we quantify the transmission capacities for both of these two networks and discuss their tradeoff based on asymptotic analysis. Our results show that if the PR network permits a small increase of its outage probability, the sum transmission capacity of the two networks (i.e., the overall spectrum efficiency per unit area) will be boosted significantly over that of a single network.

The concept of channel capacity per unit cost was introduced by Verdú in 1990 to study the limits of wideband communication. It was shown that an orthogonal coding scheme achieves the channel capacity per unit cost of memoryless stationary channels with a zero-cost input letter. This paper introduces the concept of secrecy capacity per unit cost to study wideband secrecy communications. For degraded memoryless stationary wiretap channels, it is shown that an orthogonal coding scheme achieves the secrecy capacity per unit cost with a zero-cost input letter. For general memoryless stationary wiretap channels, the performance of orthogonal codes is studied and lower and upper bounds on the secrecy capacity per unit cost are provided.

This paper considers an entropy-power inequality (EPI) of Costa and presents a natural vector generalization with a real positive semidefinite matrix parameter. This new inequality is proved using a perturbation approach via a fundamental relationship between the derivative of mutual information and the minimum mean-square error (MMSE) estimate in linear vector Gaussian channels. As an application, a new extremal entropy inequality is derived from the generalized Costa EPI and then used to establish the secrecy capacity regions of the degraded vector Gaussian broadcast channel with layered confidential messages.

This paper considers the problem of secret communication over a two-receiver multiple-input multiple-output (MIMO) Gaussian broadcast channel. The transmitter has two independent messages, each of which is intended for one of the receivers but needs to be kept asymptotically perfectly secret from the other. It is shown that, surprisingly, under a matrix power constraint both messages can be simultaneously transmitted at their respective maximal secrecy rates. To prove this result, the MIMO Gaussian wiretap channel is revisited and a new characterization of its secrecy capacity is provided via a new coding scheme that uses artificial noise (a prefix channel) and random binning.

This paper considers the problem of communicating private messages over Gaussian broadcast channels with receiver message side information and proposes a separate physical and network coding strategy that combines layered codes and linear index codes. Though generally suboptimal, the proposed separate physical and network coding scheme is shown to achieve the capacity region of the channel within one bit per user with less or equal to three users for any given channel parameters and any given side information configuration.

We study the transmission capacities of two coexisting wireless networks (a primary network vs. a secondary network) that operate in the same geographic region and share the same spectrum. The primary (PR) network has a higher priority to access the spectrum without particular considerations for the secondary (SR) network, where the SR network limits its interference to the PR network by carefully controlling its node density. Considering general power-law wireless channels with path-loss exponent α ≫ 2 and small-scale Rayleigh fading, based on the stochastic geometry theory, we derive the transmission capacities for both of the two networks and quantify their tradeoff via asymptotic analysis. Our results show that if the PR network permits a small increase of its outage probability, the sum transmission capacity of the two networks (i.e., the overall spectrum efficiency per unit area) will be boosted significantly over that of a single network, which generalizes our previous result in [1] over a special case of deterministic power-law channel with α = 4.

The secrecy capacity of the multiantenna wiretap channel was recently characterized independently by Khisti and Wornell and Oggier and Hassibi using a Sato-like argument and matrix analysis tools. This paper presents an alternative characterization of the secrecy capacity of the multiantenna wiretap channel using a channel-enhancement argument. Compared with the approach of Khisti-Wornell and Oggier-Hassibi, this characterization is by nature information- rather than matrix-theoretic. Moreover, it extends the previous results from the average total power constraint to the more general matrix power constraint.

The problem of efficient communication over a scalar quasi-static fading channel is considered. The single-layer transmission (SLT) and multi-layer transmission (MLT) schemes do not require any knowledge of the channel state information (CSI) at the transmitter, but their performance is also limited. It is shown that using Hybrid-ARQ (HARQ) can significantly improve the average rate performance, provided that the rate assignment between different ARQ rounds is carefully chosen. The average rate performance of several HARQ schemes is optimized and compared. In addition, optimal power allocation among retransmissions is derived and shown to further increase the average rate. This power allocation gain is remarkable at low signal-to-noise ratio (SNR), but becomes negligible at high SNR. Comparison of two different types of limited feedback, sequential feedback (ARQ) and one-shot feedback (quantized CSI), is made from several perspectives. Although the optimization problem is formed with respect to the average rate, simulation results give a comprehensive comparison under different metrics, including average rate, outage probability, and the combination of both. Substantial performance improvement is observed with even one ARQ retransmission in all simulations. More importantly, this gain appears to be robust with respect to the fading distributions.

The secrecy capacity of the multiple-antenna wiretap channel under the average total power constraint was recently characterized, independently, by Khisti and Wornell and Oggier and Hassibi using a Sato-like argument and matrix analysis tools. This paper presents an alternative characterization of the secrecy capacity of the multiple-antenna wiretap channel under a more general matrix constraint on the channel input using a channel-enhancement argument. This characterization is by nature information-theoretic and is directly built on the intuition regarding to the optimal transmission strategy in this communication scenario.

The capacity region of a compound multiple-antenna broadcast channel is characterized when the users exhibit a certain degradedness order. The channel under consideration has two users, each user has a finite set of possible realizations. The transmitter transmits two messages, one for each user, in such a manner that regardless of the actual realizations, both users will be able to decode their messages correctly. An alternative view of this channel is that of a broadcast channel with two common messages, each common message is intended to a different set of users. The degradedness order between the two sets of realizations/users is defined through an additional, fictitious, user whose channel is degraded with respect to all realizations/users from one set while all realizations/users from the other set are degraded with respect to him.

The problem of efficient communication over a quasi-static wireless fading channel is considered in this paper. The disadvantages of two well-known schemes, single-layer transmission (SLT) and multi-layer transmission (MLT), are pointed out. A new scheme named aggressive transmission with ARQ (AT-ARQ) is developed and optimized to provide better performance, at the expense of requiring ARQ feedback. Optimal power allocation among (re)transmissions is derived. A comprehensive performance comparison of the three schemes, under different performance metrics such as throughput, outage probability, and the combination of two, is reported via numerical simulations. Substantial performance improvement is observed with even 1-bit ARQ feedback in Rayleigh fading.

The capacity region of a compound multi-antenna broadcast channel is characterized when the users exhibit a certain degradedness order. For this purpose, we bring to bear a new extremal inequality for information theory and utilize a channel enhancement technique.

We prove a new extremal inequality, motivated by the vector Gaussian broadcast channel and the distributed source coding with a single quadratic distortion constraint problems. As a corollary, this inequality yields a generalization of the classical entropy-power inequality (EPI). As another corollary, this inequality sheds insight into maximizing the differential entropy of the sum of two dependent random variables

We prove a new extremal inequality, motivated by the vector Gaussian broadcast channel and the distributed source coding with a single quadratic distortion constraint problem. As a corollary, this inequality yields a generalization of the classical vector entropy-power inequality (EPI). As another corollary, this inequality sheds insight into maximizing differential entropy of a sum of jointly distributed random variables, generalizing a classical result of Cover and Zhang

Modulo lattice additive noise (MLAN) channels appear in the analysis of structured binning codes for Costa's dirty-paper channel and of nested lattice codes for the additive white Gaussian noise (AWGN) channel. In this paper, we derive a new lower bound on the error exponents of the MLAN channel. With a proper choice of the shaping lattice and the scaling parameter, the new lower bound coincides with the random-coding lower bound on the error exponents of the AWGN channel at the same signal-to-noise ratio (SNR) in the sphere-packing and straight-line regions. This result implies that, at least for rates close to channel capacity, 1) writing on dirty paper is as reliable as writing on clean paper; and 2) lattice encoding and decoding suffer no loss of error exponents relative to the optimal codes (with maximum-likelihood decoding) for the AWGN channel.

A simple scheme that achieves the capacity and the reliability function of the wideband Costa dirty-paper channel is proposed. The scheme can be interpreted as an opportunistic version of pulse position modulation (PPM). This interpretation suggests a natural generalization of the scheme which we show to achieve the capacity per unit cost of Gel'fand-Pinsker channels with a zero-cost input letter.

We present a new lower bound for the error exponents of nested lattice codes for the additive white Gaussian noise (AWGN) channel. The exponents are closely related to those of an unconstrained additive noise channel where the noise is a weighted sum of a white Gaussian and a spherically uniform random vector. The new lower bound improves the previous result derived by Erez and Zamir (2002) and stated in terms of the Poltyrev exponents. More surprisingly, the new lower bound coincides with the random coding error exponents of the optimal Gaussian codes for the AWGN channel in the nonexpurgated regime. One implication of this result is that minimum mean squared error (MMSE) scaling, despite its key role in achieving capacity of the AWGN channel, is no longer fundamental in achieving the best error exponents for rates below channel capacity. These exponents are achieved using a lattice inflation parameter derived from a large-deviation analysis.

Quantization index modulation (QIM) is a powerful host-interference rejecting method for data hiding. The paper applies QIM to one-bit watermarking and proposes a simple but powerful watermark detector. We derive lower bounds on the error exponents for the detector under a quadratic distortion constraint for the watermarker and additive white Gaussian noise attacks. These bounds are independent of the host-signal distribution and are substantially better than recently derived bounds for public (blind) spread-spectrum watermarking.