Search

Shannon’s analysis of the fundamental capacity limits for memoryless communication channels has been refined over time. In this paper, the maximum volume M_ \mathrm avg^*(n,\epsilon ) of length- n codes subject to an average decoding error probability \epsilon is shown to satisfy the following tight asymptotic lower and upper bounds as n \to \infty : , where C is the Shannon capacity, V_\epsilon is the \epsilon -channel dispersion, or second-order coding rate, Q and \overline A_\epsilon are explicitly identified. This expression holds under mild regularity assumptions on the channel, including nonsingularity. The gap \overline A_\epsilon - \underline A_\epsilon is one nat for weakly symmetric channels in the Cover–Thomas sense, and typically a few nats for other symmetric channels, for the binary symmetric channel, and for the $Z$ channel. The derivation is based on strong large-deviations analysis and refined central limit asymptotics. A random coding scheme that achieves the lower bound is presented. The codewords are drawn from a capacity-achieving input distribution modified by an O(1/\sqrt {n}) correction term. [ABSTRACT FROM PUBLISHER]

When information is to be transmitted over a unknown, possibly unreliable channel, an erasure option at the decoder is desirable. Using constant-composition random codes, we propose a generalization of Csiszár and Körner's maximum mutual information (MMI) decoder with an erasure option for discrete memoryless channels. The new decoder is parameterized by a weighting function that is designed to optimize the fundamental tradeoff between undetected-error and erasure exponent for a compound class of channels. The class of weighting functions may be further enlarged to optimize a similar tradeoff for list decoders--in that case, undetected-error probability is replaced with average number of incorrect messages in the fist. Explicit solutions are identified. The optimal exponents admit simple expressions in terms of the sphere-packing exponent, at all rates below capacity. For small erasure exponents, these expressions coincide with those derived by Forney (1968) for symmetric channels, using maximum a posteriori decoding. Thus, for those channels at least, ignorance of the channel law is inconsequential. Conditions for optimality of the Csiszfir-Körner rule and of the simpler empirical-mutual-information thresholding rule are identified. The error exponents are evaluated numerically for the binary symmetric channel. [ABSTRACT FROM AUTHOR]

An analysis of steganographic systems subject to the following perfect undetectability condition is presented in this paper. Following embedding of the message into the covertext, the resulting stegotext is required to have exactly the same probability distribution as the covertext. Then no statistical test can reliably detect the presence of the hidden message. We refer to such steganographic schemes as perfectly secure. A few such schemes have been proposed in recent literature, but they have vanishing rate. We prove that communication performance can potentially be vastly improved; specifically, our basic setup assumes independent and identically distributed (i.i.d.) covertext, and we construct perfectly secure steganographic codes from public watermarking codes using binning methods and randomized permutations of the code. The permutation is a secret key shared between encoder and decoder. We derive (positive) capacity and random-coding exponents for perfectly secure steganographic systems. The error exponents provide estimates of the code length required to achieve a target low error probability. In some applications, steganographic communication may be disrupted by an active warden, modeled here by a compound discrete memoryless channel (DMC). The transmitter and warden are subject to distortion constraints. We address the potential loss in communication performance due to the perfect-security requirement. This loss is the same as the loss obtained under a weaker order-1 steganographic requirement that would just require matching of first-order marginals of the covertext and stegotext distributions. Furthermore, no loss occurs if the covertext distribution is uniform and the distortion metric is cyclically symmetric; steganographic capacity is then achieved by randomized linear codes. Our framework may also be useful for developing computationally secure steganographic systems that have near-optimal communication performance. [ABSTRACT FROM AUTHOR]

Capacity formulas and random-coding exponents are derived for a generalized family of Gel'fand-Pinsker coding problems. These exponents yield asymptotic upper bounds on the achievable log probability of error. In our model, information is to be reliably transmitted through a noisy channel with finite input and output alphabets and random state sequence, and the channel is selected by a hypothetical adversary. Partial information about the state sequence is available to the encoder, adversary, and decoder. The design of the transmitter is subject to a cost constraint. Two families of channels are considered: 1) compound discrete memoryless channels (CDMC), and 2) channels with arbitrary memory, subject to an additive cost constraint, or more generally, to a hard constraint on the conditional type of the channel output given the input. Both problems are closely connected. The random-coding exponent is achieved using a stacked binning scheme and a maximum penalized mutual information decoder, which may be thought of as an empirical generalized maximum a posteriori decoder. For channels with arbitrary memory, the random-coding exponents are larger than their CDMC counterparts. Applications of this study include watermarking, data hiding, communication in presence of partially known interferers, and problems such as broadcast channels, all of which involve the fundamental idea of binning. [ABSTRACT FROM AUTHOR]

The Karhunen-Loéve transform (KLT) is known to be optimal for high-rate transform coding of Gaussian vectors for both fixed-rate and variable-rate encoding. The KLT is also known to be suboptimal for some non-Gaussian models. This paper proves high-rate optimality of the KLT for variable-rate encoding of a broad class of non-Gaussian vectors: Gaussian vector-scale mixtures (GVSM), which extend the Gaussian scale mixture (GSM) model of natural signals. A key concavity property of the scalar GSM (same as the scalar GVSM) is derived to complete the proof. Optimality holds under a broad class of quadratic criteria, which include mean-squared error (MSE) as well as generalized f-divergence loss in estimation and binary classification systems. Finally, the theory is illustrated using two applications: signal estimation in multiplicative noise and joint optimization of classification/reconstruction systems. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A broad set of sufficient conditions that guarantees the existence of the maximum entropy (maxent) distribution consistent with specified bounds on certain generalized moments is derived. Most results in the literature are either focused on the minimum cross-entropy distribution or apply only to distributions with a bounded-volume support or address only equality constraints. The results of this work hold for general moment inequality constraints for probability distributions with possibly unbounded support, and the technical conditions are explicitly on the underlying generalized moment functions. An analytical characterization of the maxent distribution is also derived using results from the theory of constrained optimization in infinite-dimensional norms linear spaces. Several auxiliary results of independent Interest pertaining to certain properties of convex coercive functions are also presented. [ABSTRACT FROM AUTHOR]

Rates of reliable transmission of hidden information are derived for watermarking problems involving parallel Gaussian sources, which are often used to model host images and audio signals. Constraints are imposed on the average squared-error distortion that can be introduced by the information hider and by the attacker. When distortions are measured with respect to the original host data, the optimal covert and attack channels are two banks of Gaussian test channels. The solution to the watermarking game involves an optimal allocation of distortions by the information hider and by the attacker to the different channels. A fast algorithm is given for computing the optimal solution based on duality theory. For each channel, we derive analytical expressions for two asymptotic regimes: weak and strong host signals. Finally, we extend these results to the class of stationary Gaussian host signals with bounded, continuous spectral density. The analysis also provides an upper bound on watermarking capacity for non-Gaussian host signals. [ABSTRACT FROM AUTHOR]

An information-theoretic analysis of information hiding is presented in this paper, forming the theoretical basis for design of information-hiding systems. Information hiding is an emerging research area which encompasses applications such as copyright protection for digital media, watermarking, fingerprinting, steganography, and data embedding. In these applications, information is hidden within a host data set and is to be reliably communicated to a receiver. The host data set is intentionally corrupted, but in a covert way, designed to be imperceptible to a casual analysis. Next, an attacker may seek to destroy this hidden information, and for this purpose, introduce additional distortion to the data set. Side information (in the form of cryptographic keys and/or information about the host signal) may be available to the information hider and to the decoder. We formalize these notions and evaluate the hiding capacity, which upper-bounds the rates of reliable transmission and quantifies the fundamental tradeoff between three quantities: the achievable information-hiding rates and the allowed distortion levels for the information hider and the attacker. The hiding capacity is the value of a game between the information hider and the attacker. The optimal attack strategy is the solution of a particular rate-distortion problem, and the optimal hiding strategy is the solution to a channel-coding problem. The hiding capacity is derived by extending the Gel'fand-Pinsker theory of communication with side information at the encoder. The extensions include the presence of distortion constraints, side information at the decoder, and unknown communication channel. Explicit formulas for capacity are given in several cases, including Bernoulli and Gaussian problems, as well as the important special case of small distortions. In some cases, including the last two above, the hiding capacity is the same whether or not the decoder knows the host data set. It is shown that... [ABSTRACT FROM AUTHOR]

Presents a study which applied the complexity-regularization principle to statistical ill-posed inverse problems in imaging. Methodology; Results; Discussion.

Investigates various connections between shrinkage methods and Maximum A Posteriori estimation using Gaussian and complexity priors. Application of the Minimum Description Length principle; Development of analytical expressions implied by Gaussian distributions.

Let $X_{i}, i~\in V$ form a Markov random field (MRF) represented by an undirected graph $G = (V,E)$ , and $V'$ be a subset of $V$. We determine the smallest graph that can always represent the subfield $X_{i}, i~\in V'$ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When $G$ is a path so that $X_{i}, i~\in V$ form a Markov chain, it is known that the $I$ -Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the $I$ -Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002). [ABSTRACT FROM AUTHOR]