We introduce a novel representation for efficient classical rendering of photorealistic 3D face avatars. Leveraging recent advances in radiance fields anchored to parametric face models, our approach achieves controllable volumetric rendering of complex facial features, including hair, skin, and eyes. At enrollment time, we learn a set of radiance manifolds in 3D space to extract an explicit layered mesh, along with appearance and warp textures. During deployment, this allows us to control and animate the face through simple linear blending and alpha compositing of textures over a static mesh. This explicit representation also enables the generated avatar to be efficiently streamed online and then rendered using classical mesh and shader-based rendering on legacy graphics platforms, eliminating the need for any custom engineering or integration. https://syntec-research.github.io/LegacyAvatars/

Underwater acoustic environment estimation is a challenging but important task for remote sensing scenarios. Current estimation methods require high signal strength and a solution to the fragile echo labeling problem to be effective. In previous publications, we proposed a general deep learning-based method for two-dimensional environment estimation which outperformed the state-of-the-art, both in simulation and in real-life experimental settings. A limitation of this method was that some prior information had to be provided by the user on the number and locations of the reflective boundaries, and that its neural networks had to be re-trained accordingly for different environments. Utilizing more advanced neural network and time delay estimation techniques, the proposed improved method no longer requires prior knowledge the number of boundaries or their locations, and is able to estimate two-dimensional environments with one or two boundaries. Future work will extend the proposed method to more boundaries and larger-scale environments.

The ubiquitous time-delay estimation (TDE) problem becomes nontrivial when sensors are non-co-located and communication between them is limited. Building on the recently proposed "extremum encoding" compression-estimation scheme, we address the critical extension to complex-valued signals, suitable for radio-frequency (RF) baseband processing. This extension introduces new challenges, e.g., due to unknown phase of the signal of interest and random phase of the noise, rendering a naïve application of the original scheme inapplicable and irrelevant. In the face of these challenges, we propose a judiciously adapted, though natural, extension of the scheme, paving its way to RF applications. While our extension leads to a different statistical analysis, including extremes of non-Gaussian distributions, we show that, ultimately, its asymptotic behavior is akin to the original scheme. We derive an exponentially tight upper bound on its error probability, corroborate our results via simulation experiments, and demonstrate the superior performance compared to two benchmark approaches.

We propose *Score-of-Mixture Training* (SMT), a novel framework for training one-step generative models by minimizing a class of divergences called the $\alpha$-skew Jensen–Shannon divergence. At its core, SMT estimates the score of mixture distributions between real and fake samples across multiple noise levels. Similar to consistency models, our approach supports both training from scratch (SMT) and distillation using a pretrained diffusion model, which we call *Score-of-Mixture Distillation* (SMD). It is simple to implement, requires minimal hyperparameter tuning, and ensures stable training. Experiments on CIFAR-10 and ImageNet 64×64 show that SMT/SMD are competitive with and can even outperform existing methods.

This paper studies a family of estimators based on noise-contrastive estimation (NCE) for learning unnormalized distributions. The main contribution of this work is to provide a unified perspective on various methods for learning unnormalized distributions, which have been independently proposed and studied in separate research communities, through the lens of NCE. This unified view offers new insights into existing estimators. Specifically, for exponential families, we establish the finite-sample convergence rates of the proposed estimators under a set of regularity assumptions, most of which are new.

Large language models (LLMs) have demonstrated remarkable reasoning capabilities across diverse domains. Recent studies have shown that increasing test-time computation enhances LLMs' reasoning capabilities. This typically involves extensive sampling at inference time guided by an external LLM verifier, resulting in a two-player system. Despite external guidance, the effectiveness of this system demonstrates the potential of a single LLM to tackle complex tasks. Thus, we pose a new research problem: *Can we internalize the searching capabilities to fundamentally enhance the reasoning abilities of a single LLM?* This work explores an orthogonal direction focusing on post-training LLMs for autoregressive searching (*i.e.,* an extended reasoning process with self-reflection and self-exploration of new strategies). To achieve this, we propose the Chain-of-Action-Thought (COAT) reasoning and a two-stage training paradigm: 1) a small-scale format tuning stage to internalize the COAT reasoning format and 2) a large-scale self-improvement stage leveraging reinforcement learning. Our approach results in Satori, a 7B LLM trained on open-source models and data. Extensive empirical evaluations demonstrate that Satori achieves state-of-the-art performance on mathematical reasoning benchmarks while exhibits strong generalization to out-of-domain tasks. Code, data, and models are fully open-sourced.

The Koopman operator provides a principled framework for analyzing nonlinear dynamical systems through linear operator theory. Recent advances in dynamic mode decomposition (DMD) have shown that trajectory data can be used to identify dominant modes of a system in a data-driven manner. Building on this idea, deep learning methods such as VAMPnet and DPNet have been proposed to learn the leading singular subspaces of the Koopman operator. However, these methods require backpropagation through potentially numerically unstable operations on empirical second moment matrices, such as singular value decomposition and matrix inversion, during objective computation, which can introduce biased gradient estimates and hinder scalability to large systems. In this work, we propose a scalable and conceptually simple method for learning the top-$k$ singular functions of the Koopman operator for stochastic dynamical systems based on the idea of low-rank approximation. Our approach eliminates the need for unstable linear-algebraic operations and integrates easily into modern deep learning pipelines. Empirical results demonstrate that the learned singular subspaces are both reliable and effective for downstream tasks such as eigen-analysis and multi-step prediction.

Spectral decomposition of linear operators plays a central role in many areas of machine learning and scientific computing. Recent work has explored training neural networks to approximate eigenfunctions of such operators, enabling scalable approaches to representation learning, dynamical systems, and partial differential equations (PDEs). In this paper, we revisit a classical optimization framework from the computational physics literature known as the *orbital minimization method* (OMM), originally proposed in the 1990s for solving eigenvalue problems in computational chemistry. We provide a simple linear-algebraic proof of the consistency of the OMM objective, and reveal connections between this method and several ideas that have appeared independently across different domains. Our primary goal is to justify its broader applicability in modern learning pipelines. We adapt this framework to train neural networks to decompose positive semidefinite operators, and demonstrate its practical advantages across a range of benchmark tasks. Our results highlight how revisiting classical numerical methods through the lens of modern theory and computation can provide not only a principled approach for deploying neural networks in numerical simulation, but also effective and scalable tools for machine learning.

Double-descent refers to the unexpected drop in test loss of a learning algorithm beyond an interpolating threshold with over-parameterization, which is not predicted by information criteria in their classical forms due to the limitations in the standard asymptotic approach. We update these analyses using the information risk minimization framework and provide Akaike Information Criterion (AIC) and Bayesian Information Criterion (BIC) for models learned by the Gibbs algorithm. Notably, the penalty terms for the Gibbs-based AIC and BIC correspond to specific information measures, i.e., symmetrized KL information and KL divergence. We extend this information-theoretic analysis to over-parameterized models by providing two different Gibbs-based BICs to compute the marginal likelihood of random feature models in the regime where the number of parameters $p$ and the number of samples $n$ tend to infinity, with $p/n$ fixed. Our experiments demonstrate that the Gibbs-based BIC can select the high-dimensional model and reveal the mismatch between marginal likelihood and population risk in the over-parameterized regime, providing new insights to understand double-descent.

Motivated by the proliferation of mobile devices, we consider a basic form of the ubiquitous problem of time-delay estimation (TDE), but with communication constraints between two non co-located sensors. In this setting, when joint processing of the received signals is not possible, a compression technique that is tailored to TDE is desirable. For our basic TDE formulation, we develop such a joint compression-estimation strategy based on the notion of what we term "extremum encoding", whereby we send the index of the maximum of a finite-length time-series from one sensor to another. Subsequent joint processing of the encoded message with locally observed data gives rise to our proposed time-delay "maximum-index"-based estimator. We derive an exponentially tight upper bound on its error probability, establishing its consistency with respect to the number of transmitted bits. We further validate our analysis via simulations, and comment on potential extensions and generalizations of the basic methodology.

Computing eigenvalue decomposition (EVD) of a given linear operator, or finding its leading eigenvalues and eigenfunctions, is a fundamental task in many machine learning and scientific simulation problems. For high-dimensional eigenvalue problems, training neural networks to parameterize the eigenfunctions is considered as a promising alternative to the classical numerical linear algebra techniques. This paper proposes a new optimization framework based on the low-rank approximation characterization of a truncated singular value decomposition, accompanied by new techniques called nesting for learning the top-$L$ singular values and singular functions in the correct order. The proposed method promotes the desired orthogonality in the learned functions implicitly and efficiently via an unconstrained optimization formulation, which is easy to solve with off-the-shelf gradient-based optimization algorithms. We demonstrate the effectiveness of the proposed optimization framework for use cases in computational physics and machine learning.

A confidence sequence (CS) is a sequence of confidence sets that contains a target parameter of an underlying stochastic process at any time step with high probability. This paper proposes a new approach to constructing CSs for means of bounded multivariate stochastic processes using a general gambling framework, extending the recently established coin toss framework for bounded random processes. The proposed gambling framework provides a general recipe for constructing CSs for categorical and probability-vector-valued observations, as well as for general bounded multidimensional observations through a simple reduction. This paper specifically explores the use of the mixture portfolio, akin to Cover's universal portfolio, in the proposed framework and investigates the properties of the resulting CSs. Simulations demonstrate the tightness of these confidence sequences compared to existing methods. When applied to the sampling without-replacement setting for finite categorical data, it is shown that the resulting CS based on a universal gambling strategy is provably tighter than that of the posterior-prior ratio martingale proposed by Waudby-Smith and Ramdas.

We consider the issue of calibration in large language models (LLM). Recent studies have found that common interventions such as instruction tuning often result in poorly calibrated LLMs. Although calibration is well-explored in traditional applications, calibrating LLMs is uniquely challenging. These challenges stem as much from the severe computational requirements of LLMs as from their versatility, which allows them to be applied to diverse tasks. Addressing these challenges, we propose THERMOMETER, a calibration approach tailored to LLMs. THERMOMETER learns an auxiliary model, given data from multiple tasks, for calibrating a LLM. It is computationally efficient, preserves the accuracy of the LLM, and produces better-calibrated responses for new tasks. Extensive empirical evaluations across various benchmarks demonstrate the effectiveness of the proposed method.

Learning a fair predictive model is crucial to mitigate biased decisions against minority groups in high-stakes applications. A common approach to learn such a model involves solving an optimization problem that maximizes the predictive power of the model under an appropriate group fairness constraint. However, in practice, sensitive attributes are often missing or noisy resulting in uncertainty, and solely enforcing fairness constraints on uncertain sensitive attributes can fall significantly short of achieving the level of fairness without uncertainty. To understand this phenomenon, we consider the problem of fair learning for Gaussian data and reduce it to a quadratically constrained quadratic problem (QCQP). To ensure a strict fairness guarantee given uncertain sensitive attributes, we propose a robust QCQP, and characterize its solution with an intuitive geometric understanding. When uncertainty arises due to limited labeled sensitive attributes, our analysis identifies non-trivial regimes where uncertainty incurs no performance loss while continuing to guarantee strict fairness. As an illustrative example of our analysis, we propose a bootstrap-based algorithm that applies beyond the Gaussian case. We demonstrate the value of our analysis and algorithm on synthetic as well as real-world data.

This paper questions the effectiveness of a modern predictive uncertainty quantification approach, called *evidential deep learning* (EDL), in which a single neural network model is trained to learn a meta distribution over the predictive distribution by minimizing a specific objective function. Despite their perceived strong empirical performance on downstream tasks, a line of recent studies by Bengs et al. identify limitations of the existing methods to conclude their learned epistemic uncertainties are unreliable, e.g., in that they are non-vanishing even with infinite data. Building on and sharpening such analysis, we 1) provide a sharper understanding of the asymptotic behavior of a wide class of EDL methods by unifying various objective functions; 2) reveal that the EDL methods can be better interpreted as an out-of-distribution detection algorithm based on energy-based-models; and 3) conduct extensive ablation studies to better assess their empirical effectiveness with real-world datasets. Through all these analyses, we conclude that even when EDL methods are empirically effective on downstream tasks, this occurs despite their poor uncertainty quantification capabilities. Our investigation suggests that incorporating model uncertainty can help EDL methods faithfully quantify uncertainties and further improve performance on representative downstream tasks, albeit at the cost of additional computational complexity.

Various approaches have been developed to upper bound the generalization error of a supervised learning algorithm. However, existing bounds are often loose and even vacuous when evaluated in practice. As a result, they may fail to characterize the exact generalization ability of a learning algorithm. Our main contributions are exact characterizations of the expected generalization error of the well-known Gibbs algorithm (a.k.a. Gibbs posterior) using different information measures, in particular, the symmetrized KL information between the input training samples and the output hypothesis. Our result can be applied to tighten existing expected generalization errors and PAC-Bayesian bounds. Our information-theoretic approach is versatile, as it also characterizes the generalization error of the Gibbs algorithm with a data-dependent regularizer and that of the Gibbs algorithm in the asymptotic regime, where it converges to the standard empirical risk minimization algorithm. Of particular relevance, our results highlight the role the symmetrized KL information plays in controlling the generalization error of the Gibbs algorithm.

We consider communication over a state-dependent discrete memoryless channel subject to a constraint that the output sequence must be nearly independent of the state sequence. We consider both cases where the transmitter knows (causally or noncausally) and where it does not know the states. When it does not know the states, we show that capacity can increase when the encoder uses some source of randomness that is not shared with the decoder. We consider three different cases for the state sequence: where it is independent and identically distributed across channel uses, where it is quasi-static, and where it has memory but is not quasi-static. We present single-letter capacity formulas for most combinations of the above scenarios, and also provide some illustrative examples.

It is known that neural networks have the problem of being over-confident when directly using the output label distribution to generate uncertainty measures. Existing methods mainly resolve this issue by retraining the entire model to impose the uncertainty quantification capability so that the learned model can achieve desired performance in accuracy and uncertainty prediction simultaneously. However, training the model from scratch is computationally expensive, and a trade-off might exist between prediction accuracy and uncertainty quantification. To this end, we consider a more practical post-hoc uncertainty learning setting, where a well-trained base model is given, and we focus on the uncertainty quantification task at the second stage of training. We propose a novel Bayesian uncertainty learning approach using the Dirichlet meta-model, which is effective and computationally efficient. Our proposed method requires no additional training data and is flexible enough to quantify different uncertainties and easily adapt to different application settings, including out-of-domain data detection, misclassification detection, and trustworthy transfer learning. Finally, we demonstrate our proposed meta-model approach's flexibility and superior empirical performance on these applications over multiple representative image classification benchmarks.

Learning the physical environment is an important yet challenging task in reverberant settings such as the underwater and indoor acoustic domains. The locations of reflective boundaries, for example, can be estimated using echoes and leveraged for subsequent, more accurate localization. Current boundary estimation methods are constrained to a regime of high signal strength, or mitigate noise with heuristic (suboptimal) filters. These limitations can lead to fragile estimators that fail under non-ideal conditions. Furthermore, many algorithms in the literature also require a correct assignment of echoes to boundaries, which is combinatorially hard. To evade these limitations, we develop a convolutional neural network method for robust 2D boundary estimation, given known emitter and receiver locations. Our method uses as its input data format transform images, which are the potential boundary locations mapped into curves. We demonstrated in simulations that the proposed neural network method outperforms alternative state-of-the-art algorithms.

We study the single-channel source separation problem involving orthogonal frequency-division multiplexing (OFDM) signals, which are ubiquitous in many modern-day digital communication systems. Related efforts have been pursued in monaural source separation, where state-of-the-art neural architectures have been adopted to train an end-to-end separator for audio signals (as 1-dimensional time series). In this work, through a prototype problem based on the OFDM source model, we assess—and question—the efficacy of using audio-oriented neural architectures in separating signals based on features pertinent to communication waveforms. Perhaps surprisingly, we demonstrate that in some configurations, where perfect separation is theoretically attainable, these audio-oriented neural architectures perform poorly in separating co-channel OFDM waveforms. Yet, we propose critical domain-informed modifications to the network parameterization, based on insights from OFDM structures, that can confer about 30 dB improvement in performance.

Key challenges in developing underwater acoustic localization methods are related to the combined effects of high reverberation in intricate environments. To address such challenges, recent studies have shown that with a properly designed architecture, neural networks can lead to unprecedented localization capabilities and enhanced accuracy. However, the robustness of such methods to environmental mismatch is typically hard to characterize, and is usually assessed only empirically. In this work, we consider the recently proposed data-driven method [18] based on a deep convolutional neural network, and demonstrate that it can learn to localize in complex and mismatched environments. To explain this robustness, we provide an upper bound on the localization mean squared error (MSE) in the "true" environment, in terms of the MSE in a "presumed" environment and an additional penalty term related to the environmental discrepancy. Our theoretical results are corroborated via simulation results in a rich, highly reverberant, and mismatch channel.

Due to privacy, storage, and other constraints, there is a growing need for unsupervised domain adaptation techniques in machine learning that do not require access to the data used to train a collection of source models. Existing methods for multi-source-free domain adaptation (MSFDA) typically train a target model using pseudo-labeled data produced by the source models, which focus on improving the pseudo-labeling techniques or proposing new training objectives. Instead, we aim to analyze the fundamental limits of MSFDA. In particular, we develop an information-theoretic bound on the generalization error of the resulting target model, which illustrates an inherent bias-variance trade-off. We then provide insights on how to balance this trade-off from three perspectives, including domain aggregation, selective pseudo-labeling, and joint feature alignment, which leads to the design of novel algorithms. Experiments on multiple datasets validate our theoretical analysis and demonstrate the state-of-art performance of the proposed algorithm, especially on some of the most challenging datasets, including Office-Home and DomainNet.

We analyze the generalization ability of joint-training meta learning algorithms via the Gibbs algorithm. Our exact characterization of the expected meta generalization error for the meta Gibbs algorithm is based on symmetrized KL information, which measures the dependence between all meta-training datasets and the output parameters, including task-specific and meta parameters. Additionally, we derive an exact characterization of the meta generalization error for the super-task Gibbs algorithm, in terms of conditional symmetrized KL information within the super-sample and super-task framework introduced in [1] and [2], respectively. Our results also enable us to provide novel distribution-free generalization error upper bounds for these Gibbs algorithms applicable to meta learning.

A bilateral (i.e., upper and lower) bound on the mean-square error under a general model mismatch is developed. The bound, which is derived from the variational representation of the chi-square divergence, is applicable in the Bayesian and nonBayesian frameworks to biased and unbiased estimators. Unlike other classical MSE bounds that depend only on the model, our bound is also estimator-dependent. Thus, it is applicable as a tool for characterizing the MSE of a specific estimator. The proposed bounding technique has a variety of applications, one of which is a tool for proving the consistency of estimators for a class of models. Furthermore, it provides insight as to why certain estimators work well under general model mismatch conditions.

We propose a new method for separating superimposed sources using diffusion-based generative models. Our method relies only on separately trained statistical priors of independent sources to establish a new objective function guided by $\textit{maximum a posteriori}$ estimation with an $\textit{$\alpha$-posterior}$, across multiple levels of Gaussian smoothing. Motivated by applications in radio-frequency (RF) systems, we are interested in sources with underlying discrete nature and the recovery of encoded bits from a signal of interest, as measured by the bit error rate (BER). Experimental results with RF mixtures demonstrate that our method results in a BER reduction of 95\% over classical and existing learning-based methods. Our analysis demonstrates that our proposed method yields solutions that asymptotically approach the modes of an underlying discrete distribution. Furthermore, our method can be viewed as a multi-source extension to the recently proposed score distillation sampling scheme, shedding additional light on its use beyond conditional sampling. The project webpage is available at https://alpha-rgs.github.io.

We study the problem of extracting biometric information of individuals by looking at shadows of objects cast on diffuse surfaces. We show that the biometric information leakage from shadows can be sufficient for reliable identity inference under representative scenarios via a maximum likelihood analysis. We then develop a learning-based method that demonstrates this phenomenon in real settings, exploiting the subtle cues in the shadows that are the source of the leakage without requiring any labeled real data. In particular, our approach relies on building synthetic scenes composed of 3D face models obtained from a single photograph of each identity. We transfer what we learn from the synthetic data to the real data using domain adaptation in a completely unsupervised way. Our model is able to generalize well to the real domain and is robust to several variations in the scenes. We report high classification accuracies in an identity classification task that takes place in a scene with unknown geometry and occluding objects.

The fundamental communication problem in the wireless Internet-of-Things (IoT) is to discover a massive number of devices and to provide them with reliable access to shared channels. Oftentimes these devices transmit short messages randomly and sporadically. This paper proposes a novel signaling scheme for grant-free massive access, where each device encodes its identity and/or information in a sparse set of tones. Such transmissions are implemented in the form of orthogonal frequency-division multiple access (OFDMA). Under some mild conditions and assuming device delays to be bounded unknown multiples of sampling intervals, sparse OFDMA is proved to enable arbitrarily reliable asynchronous device identification and message decoding with a codelength that is$O(K(\log K+\log S + \log N))$, where$N$denotes the device population,$K$denotes the actual number of active devices, and$\log S$is essentially equal to the number of information bits each device can send. The computational complexity for discovery and decoding can be made to be$O(K(\log K)(\log K+\log S+\log N)+K^{2}\log K)$. As a proof of concept, a specific design is proposed to identify up to 200 active devices out of$N=2^{96}$possible devices with up to 20 samples of delay, moderate signal-to-noise ratios, and fading. If the device population is$N=2^{48}$instead, each active device can also transmit 48 bits to the access point at the same time. The codelength compares much more favorably with those of standard slotted ALOHA and carrier-sensing multiple access (CSMA) schemes.

We provide an information-theoretic analysis of the generalization ability of Gibbs-based transfer learning algorithms by focusing on two popular empirical risk minimization (ERM) approaches for transfer learning, $\alpha$-weighted-ERM and two-stage-ERM. Our key result is an exact characterization of the generalization behavior using the conditional symmetrized Kullback-Leibler (KL) information between the output hypothesis and the target training samples given the source training samples. Our results can also be applied to provide novel distribution-free generalization error upper bounds on these two aforementioned Gibbs algorithms. Our approach is versatile, as it also characterizes the generalization errors and excess risks of these two Gibbs algorithms in the asymptotic regime, where they converge to the $\alpha$-weighted-ERM and two-stage-ERM, respectively. Based on our theoretical results, we show that the benefits of transfer learning can be viewed as a bias-variance trade-off, with the bias induced by the source distribution and the variance induced by the lack of target samples. We believe this viewpoint can guide the choice of transfer learning algorithms in practice.

We study the potential of data-driven deep learning methods for separation of two communication signals from an observation of their mixture. In particular, we assume knowledge on the generation process of one of the signals, dubbed signal of interest (SOI), and no knowledge on the generation process of the second signal, referred to as interference. This form of the single-channel source separation problem is also referred to as interference rejection. We show that capturing high-resolution temporal structures (nonstationarities), which enables accurate synchronization to both the SOI and the interference, leads to substantial performance gains. With this key insight, we propose a domain-informed neural network (NN) design that is able to improve upon both “off-the-shelf” NNs and classical detection and interference rejection methods, as demonstrated in our simulations. Our findings highlight the key role communication-specific domain knowledge plays in the development of data-driven approaches that hold the promise of unprecedented gains.

As machine learning algorithms grow in popularity and diversify to many industries, ethical and legal concerns regarding their fairness have become increasingly relevant. We explore the problem of algorithmic fairness, taking an information-theoretic view. The maximal correlation framework is introduced for expressing fairness constraints and shown to be capable of deriving regularizers that enforce independence and separation-based fairness criteria, which admit optimization algorithms that are more computationally efficient than existing algorithms. We show that these algorithms provide smooth performance-fairness tradeoff curves and perform competitively with state-of-the-art methods on the Communities and Crimes dataset.

In a growing number of applications, there is a need to digitize a (possibly high) number of correlated signals whose spectral characteristics are challenging for traditional analog-to-digital converters (ADCs). Examples, among others, include multiple-input multiple-output systems where the ADCs must acquire at once several signals at a very wide but sparsely and dynamically occupied bandwidth supporting diverse services. In such scenarios, the resolution requirements can be prohibitively high. As an alternative, the recently proposed modulo-ADC architecture can in principle require dramatically fewer bits in the conversion to obtain the target fidelity, but requires that spatiotemporal information be known and explicitly taken into account by the analog and digital processing in the converter, which is frequently impractical. Building on our recent work, we address this limitation and develop a blind version of the architecture that requires no such knowledge in the converter. In particular, it features an automatic modulo-level adjustment and a fully adaptive modulo-decoding mechanism, allowing it to asymptotically match the characteristics of the unknown input signal. Simulation results demonstrate the successful operation of the proposed algorithm.

Selective regression allows abstention from prediction if the confidence to make an accurate prediction is not sufficient. In general, by allowing a reject option, one expects the performance of a regression model to increase at the cost of reducing coverage (i.e., by predicting on fewer samples). However, as we show, in some cases, the performance of a minority subgroup can decrease while we reduce the coverage, and thus selective regression can magnify disparities between different sensitive subgroups. Motivated by these disparities, we propose new fairness criteria for selective regression requiring the performance of every subgroup to improve with a decrease in coverage. We prove that if a feature representation satisfies the sufficiency criterion or is calibrated for mean and variance, then the proposed fairness criteria is met. Further, we introduce two approaches to mitigate the performance disparity across subgroups: (a) by regularizing an upper bound of conditional mutual information under a Gaussian assumption and (b) by regularizing a contrastive loss for conditional mean and conditional variance prediction. The effectiveness of these approaches is demonstrated on synthetic and real-world datasets.

Generalization error bounds are essential to understanding machine learning algorithms. This paper presents novel expected generalization error upper bounds based on the average joint distribution between the output hypothesis and each input training sample. Multiple generalization error upper bounds based on different information measures are provided, including Wasserstein distance, total variation distance, KL divergence, and Jensen-Shannon divergence. Due to the convexity of the information measures, the proposed bounds in terms of Wasserstein distance and total variation distance are shown to be tighter than their counterparts based on individual samples in the literature. An example is provided to demonstrate the tightness of the proposed generalization error bounds.

We consider learning a sparse pairwise Markov Random Field (MRF) with continuous-valued variables from i.i.d samples. We adapt the algorithm of Vuffray et al. (2019) to this setting and provide finite-sample analysis revealing sample complexity scaling logarithmically with the number of variables, as in the discrete and Gaussian settings. Our approach is applicable to a large class of pairwise MRFs with continuous variables and also has desirable asymptotic properties, including consistency and normality under mild conditions. Further, we establish that the population version of the optimization criterion employed in Vuffray et al. (2019) can be interpreted as local maximum likelihood estimation (MLE). As part of our analysis, we introduce a robust variation of sparse linear regression a‘ la Lasso, which may be of interest in its own right.

We present a passive non-line-of-sight method that infers the number of people or activity of a person from the observation of a blank wall in an unknown room. Our technique analyzes complex imperceptible changes in indirect illumination in a video of the wall to reveal a signal that is correlated with motion in the hidden part of a scene. We use this signal to classify between zero, one, or two moving people, or the activity of a person in the hidden scene. We train two convolutional neural networks using data collected from 20 different scenes, and achieve an accuracy of ≈ 94% for both tasks in unseen test environments and real-time online settings. Unlike other passive non-line-of-sight methods, the technique does not rely on known occluders or controllable light sources, and generalizes to unknown rooms with no recalibration. We analyze the generalization and robustness of our method with both real and synthetic data, and study the effect of the scene parameters on the signal quality.1

Selective classification is a powerful tool for decision-making in scenarios where mistakes are costly but abstentions are allowed. In general, by allowing a classifier to abstain, one can improve the performance of a model at the cost of reducing coverage and classifying fewer samples. However, recent work has shown, in some cases, that selective classification can magnify disparities between groups, and has illustrated this phenomenon on multiple real-world datasets. We prove that the sufficiency criterion can be used to mitigate these disparities by ensuring that selective classification increases performance on all groups, and introduce a method for mitigating the disparity in precision across the entire coverage scale based on this criterion. We then provide an upper bound on the conditional mutual information between the class label and sensitive attribute, conditioned on the learned features, which can be used as a regularizer to achieve fairer selective classification. The effectiveness of the method is demonstrated on the Adult, CelebA, Civil Comments, and CheXpert datasets.

We generalize the information bottleneck (IB) and privacy funnel (PF) problems by introducing the notion of a sensitive attribute, which arises in a growing number of applications. In this generalization, we seek to construct representations of observations that are maximally (or minimally) informative about a target variable, while also satisfying constraints with respect to a variable corresponding to the sensitive attribute. In the Gaussian and discrete settings, we show that by suitably approximating the Kullback-Liebler (KL) divergence defining traditional Shannon mutual information, the generalized IB and PF problems can be formulated as semi-definite programs (SDPs), and thus efficiently solved, which is important in applications of high-dimensional inference. We validate our algorithms on synthetic data and demonstrate their use in imposing fairness in machine learning on real data as an illustrative application.

Various approaches have been developed to upper bound the generalization error of a supervised learning algorithm. However, existing bounds are often loose and lack of guarantees. As a result, they may fail to characterize the exact generalization ability of a learning algorithm.Our main contribution is an exact characterization of the expected generalization error of the well-known Gibbs algorithm (a.k.a. Gibbs posterior) using symmetrized KL information between the input training samples and the output hypothesis. Our result can be applied to tighten existing expected generalization error and PAC-Bayesian bounds. Our approach is versatile, as it also characterizes the generalization error of the Gibbs algorithm with data-dependent regularizer and that of the Gibbs algorithm in the asymptotic regime, where it converges to the empirical risk minimization algorithm. Of particular relevance, our results highlight the role the symmetrized KL information plays in controlling the generalization error of the Gibbs algorithm.

We consider the question of learning the natural parameters of a $k$ parameter \textit{minimal} exponential family from i.i.d. samples in a computationally and statistically efficient manner. We focus on the setting where the support as well as the natural parameters are appropriately bounded. While the traditional maximum likelihood estimator for this class of exponential family is consistent, asymptotically normal, and asymptotically efficient, evaluating it is computationally hard. In this work, we propose a computationally efficient estimator that is consistent as well as asymptotically normal under mild conditions. We provide finite sample guarantees to achieve an ($\ell_2$) error of $\alpha$ in the parameter estimation with sample complexity $O(\mathrm{poly}(k/\alpha))$ and computational complexity ${O}(\mathrm{poly}(k/\alpha))$. To establish these results, we show that, at the population level, our method can be viewed as the maximum likelihood estimation of a re-parameterized distribution belonging to the same class of exponential family.

While the Hirschfeld-Gebelein-Rényi (HGR) maximal correlation and the Wyner common information share similar information processing purposes of extracting common knowledge structures between random variables, the relationships between these approaches are generally unclear. In this paper, we demonstrate such relationships by considering the Wyner common information in the weakly dependent regime, called ε-common information. We show that the HGR maximal correlation functions coincide with the relative likelihood functions of estimating the auxiliary random variables in ε-common information, which establishes the fundamental connections these approaches. Moreover, we extend the ε-common information to multiple random variables, and derive a novel algorithm for extracting feature functions of data variables regarding their common information. Our approach is validated by the MNIST problem, and can potentially be useful in multi-modal data analyses.

A modal decomposition is a useful tool that deconstructs the statistical dependence between two random variables by decomposing their joint distribution into orthogonal modes. Historically, modal decompositions have played important roles in statistics and information theory, e.g., in the study of maximal correlation. They are defined using the singular value decompositions of divergence transition matrices (DTMs) and conditional expectation operators corresponding to joint distributions. In this paper, we first characterize the set of all DTMs, and illustrate how the associated conditional expectation operators are the only weak contractions among a class of natural candidates. While modal decompositions have several modern machine learning applications, such as feature extraction from categorical data, the sample complexity of estimating them in such scenarios has not been analyzed. Hence, we also establish some non-asymptotic sample complexity results for the problem of estimating dominant modes of an unknown joint distribution from training data.

A loss function measures the discrepancy between the true values and their estimated fits, for a given instance of data. In classification problems, a loss function is said to be proper if a minimizer of the expected loss is the true underlying probability. We show that for binary classification, the divergence associated with smooth, proper, and convex loss functions is upper bounded by the Kullback-Leibler (KL) divergence, to within a normalization constant. This implies that by minimizing the logarithmic loss associated with the KL divergence, we minimize an upper bound to any choice of loss from this set. As such the logarithmic loss is universal in the sense of providing performance guarantees with respect to a broad class of accuracy measures. Importantly, this notion of universality is not problem-specific, enabling its use in diverse applications, including predictive modeling, data clustering and sample complexity analysis. Generalizations to arbitary finite alphabets are also developed. The derived inequalities extend several well-known $f$ -divergence results.

We consider the challenging problem of inferring a hidden moving scene from faint shadows cast on a diffuse surface. Recent work in passive non-line-of-sight (NLoS) imaging has shown that the presence of occluding objects in between the scene and the diffuse surface significantly improves the conditioning of the problem. However, that work assumes that the shape of the occluder is known a priori. In this paper, we relax this often impractical assumption, extending the range of applications for passive occluder-based NLoS imaging systems. We formulate the task of jointly recovering the unknown scene and unknown occluder as a blind deconvolution problem, for which we propose a simple but effective two-step algorithm. At the first step, the algorithm exploits motion in the scene in order to obtain an estimate of the occluder. In particular, it exploits the fact that motion in realistic scenes is typically sparse. The second step is more standard: using regularization, we deconvolve by the occluder estimate to solve for the hidden scene. We demonstrate the effectiveness of our method with simulations and experiments in a variety of settings.

We characterize the fundamental limits of coded aperture imaging systems up to universal constants by drawing upon a theorem of Nazarov regarding Fourier transforms. Our work is performed under a simple propagation and sensor model that accounts for thermal and shot noise, scene correlation, and exposure time. Focusing on mean square error as a measure of linear reconstruction quality, we show that appropriate application of a theorem of Nazarov leads to essentially optimal coded apertures, up to a constant multiplicative factor in exposure time. Additionally, we develop a heuristically efficient algorithm to generate such patterns that explicitly takes into account scene correlations. This algorithm finds apertures that correspond to local optima of a certain potential on the hypercube, yet are guaranteed to be tight. Finally, for i.i.d. scenes, we show improvements upon prior work by using spectrally flat sequences with bias. The development focuses on 1D apertures for conceptual clarity; the natural generalizations to 2D are also discussed.

It is commonly believed that the hidden layers of deep neural networks (DNNs) attempt to extract informative features for learning tasks. In this paper, we formalize this intuition by showing that the features extracted by DNN coincide with the result of an optimization problem, which we call the "universal feature selection" problem, in a local analysis regime. We interpret the weights training in DNN as the projection of feature functions between feature spaces, specified by the network structure. Our formulation has direct operational meaning in terms of the performance for inference tasks, and gives interpretations to the internal computation results of DNNs. Results of numerical experiments are provided to support the analysis.

We recover a video of the motion taking place in a hidden scene by observing changes in indirect illumination in a nearby uncalibrated visible region. We solve this problem by factoring the observed video into a matrix product between the unknown hidden scene video and an unknown light transport matrix. This task is extremely ill-posed, as any non-negative factorization will satisfy the data. Inspired by recent work on the Deep Image Prior, we parameterize the factor matrices using randomly initialized convolutional neural networks trained in a one-off manner, and show that this results in decompositions that reflect the true motion in the hidden scene.

The advent of deep learning algorithms for mobile devices and sensors has led to a dramatic expansion in the availability and number of systems trained on a wide range of machine learning tasks, creating a host of opportunities and challenges in the realm of transfer learning. Currently, most transfer learning methods require some kind of control over the systems learned, either by enforcing constraints during the source training, or through the use of a joint optimization objective between tasks that requires all data be co-located for training. However, for practical, privacy, or other reasons, in a variety of applications we may have no control over the individual source task training, nor access to source training samples. Instead we only have access to features pre-trained on such data as the output of "black-boxes.'' For such scenarios, we consider the multi-source learning problem of training a classifier using an ensemble of pre-trained neural networks for a set of classes that have not been observed by any of the source networks, and for which we have very few training samples. We show that by using these distributed networks as feature extractors, we can train an effective classifier in a computationally-efficient manner using tools from (nonlinear) maximal correlation analysis. In particular, we develop a method we refer to as maximal correlation weighting (MCW) to build the required target classifier from an appropriate weighting of the feature functions from the source networks. We illustrate the effectiveness of the resulting classifier on datasets derived from the CIFAR-100, Stanford Dogs, and Tiny ImageNet datasets, and, in addition, use the methodology to characterize the relative value of different source tasks in learning a target task.

We consider the problem of far-field sensing by means of a sensor array. Traditional array geometry design techniques are agnostic to prior information about the far-field scene. However, in many applications such priors are available and may be utilized to design more efficient array topologies. We formulate the problem of array geometry design with scene prior as one of finding a sampling configuration that enables efficient inference, which turns out to be a combinatorial optimization problem. While generic combinatorial optimization problems are NP-hard and resist efficient solvers, we show how for array design problems the theory of submodular optimization may be utilized to obtain efficient algorithms that are guaranteed to achieve solutions within a constant approximation factor from the optimum. We leverage the connection between array design problems and submodular optimization and port several results of interest. We demonstrate efficient methods for designing arrays with constraints on the sensing aperture, as well as arrays respecting combinatorial placement constraints. This novel connection between array design and submodularity suggests the possibility for utilizing other insights and techniques from the growing body of literature on submodular optimization in the field of array design.

We present a method for inferring a 4D light field of a hidden scene from 2D shadows cast by a known occluder on a diffuse wall. We do this by determining how light naturally reflected off surfaces in the hidden scene interacts with the occluder. By modeling the light transport as a linear system, and incorporating prior knowledge about light field structures, we can invert the system to recover the hidden scene. We demonstrate results of our inference method across simulations and experiments with different types of occluders. For instance, using the shadow cast by a real house plant, we are able to recover low resolution light fields with different levels of texture and parallax complexity. We provide two experimental results: a human subject and two planar elements at different depths.

There is growing interest in the use of coded aperture imaging systems for a variety of applications. Using an analysis framework based on mutual information, we examine the fundamental limits of such systems-and the associated optimum aperture coding-under simple but meaningful propagation and sensor models. Among other results, we show that when SNR is high and thermal noise dominates shot noise, spectrally-flat masks, which have 50% transmissivity, are optimal, but that when shot noise dominates thermal noise, randomly generated masks with lower transmissivity offer greater performance. We also provide comparisons to classical pinhole and lens-based cameras.

A loss function measures the discrepancy between the true values (observations) and their estimated fits, for a given instance of data. A loss function is said to be proper (unbiased, Fisher consistent) if the fits are defined over a unit simplex, and the minimizer of the expected loss is the true underlying probability of the data. Typical examples are the zero-one loss, the quadratic loss and the Bernoulli log-likelihood loss (log-loss). In this work we show that for binary classification problems, the divergence associated with smooth, proper and convex loss functions is bounded from above by the Kullback-Leibler (KL) divergence, up to a multiplicative normalization constant. It implies that by minimizing the log-loss (associated with the KL divergence), we minimize an upper bound to any choice of loss functions from this set. This property justifies the broad use of log-loss in regression, decision trees, deep neural networks and many other applications. In addition, we show that the KL divergence bounds from above any separable Bregman divergence that is convex in its second argument (up to a multiplicative normalization constant). This result introduces a new set of divergence inequalities, similar to the well-known Pinsker inequality.

We address the problem of optimal feature selection for a Gaussian vector pair in the weak dependence regime, when the inference task is not known in advance. In particular, we show that multiple formulations all yield the same solution, and correspond to the singular value decomposition (SVD) of the canonical correlation matrix. Our results reveal key connections between canonical correlation analysis (CCA), principal component analysis (PCA), the Gaussian information bottleneck, Wyner's common information, and the Ky Fan (nuclear) norms.

Deep neural networks, trained with large amount of labeled data, can fail to generalize well when tested with examples from a target domain whose distribution differs from the training data distribution, referred as the source domain. It can be expensive or even infeasible to obtain required amount of labeled data in all possible domains. Unsupervised domain adaptation sets out to address this problem, aiming to learn a good predictive model for the target domain using labeled examples from the source domain but only unlabeled examples from the target domain. Domain alignment approaches this problem by matching the source and target feature distributions, and has been used as a key component in many state-of-the-art domain adaptation methods. However, matching the marginal feature distributions does not guarantee that the corresponding class conditional distributions will be aligned across the two domains. We propose co-regularized domain alignment for unsupervised domain adaptation, which constructs multiple diverse feature spaces and aligns source and target distributions in each of them individually, while encouraging that alignments agree with each other with regard to the class predictions on the unlabeled target examples. The proposed method is generic and can be used to improve any domain adaptation method which uses domain alignment. We instantiate it in the context of a recent state-of-the-art method and observe that it provides significant performance improvements on several domain adaptation benchmarks.

We consider the problem of covert communication over a state-dependent channel, where the transmitter has causal or noncausal knowledge of the channel states. Here, covert means that a warden on the channel should observe similar statistics when the transmitter is sending a message and when it is not. When a sufficiently long secret key is shared between the transmitter and the receiver, we derive closed-form formulas for the maximum achievable covert communication rate (covert capacity) for discrete memoryless channels and, when the transmitter's channel-state information (CSI) is noncausal, for additive white Gaussian noise (AWGN) channels. For certain channel models, including the AWGN channel, we show that the covert capacity is positive with CSI at the transmitter, but is zero without CSI. We also derive lower bounds on the rate of the secret key that is needed for the transmitter and the receiver to achieve the covert capacity.

This paper addresses the problem of adding redundancy to a collection of physical objects so that the overall system is more robust to failures. In contrast to its information counterpart, which can exploit parity to protect multiple information symbols from a single erasure, physical redundancy can only be realized through duplication and substitution of objects. We propose a bipartite graph model for designing defect-tolerant systems, in which the defective objects are replaced by the judiciously connected redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size systems that approach these limits are constructed. Among other results, we show that the simple modular redundancy is in general suboptimal. As we develop, this combinatorial problem of defect tolerant system design has a natural interpretation as one of graph coloring, and the analysis is significantly different from that traditionally used in information redundancy for error-control codes.

We design finite antenna arrays for far-field sensing at multiple wavelengths, under two design paradigms. The first design paradigm is optimized for collection of measurements at multiple wavelengths, fusing these together for joint inference over an underlying scene. The second design paradigm is robust, in a sense that it is guaranteed to allow good inference over the scene at any one single wavelength at a time. We quantify inference quality via the D-Bayes optimality criterion and limit the design space by restricting the number of allowed sensors and the positions where these can be placed. We show that the resulting combinatorial optimization problems are instances of problems in a class known to have efficient guaranteed approximation algorithms, namely submodular optimization problems, and showcase the design of arrays under both paradigms utilizing simple greedy selection algorithms, and state-of-the-art robust submodular maximization algorithms.

We show that walls, and other obstructions with edges, can be exploited as naturally-occurring “cameras” that reveal the hidden scenes beyond them. In particular, we demonstrate methods for using the subtle spatio-temporal radiance variations that arise on the ground at the base of a wall's edge to construct a one-dimensional video of the hidden scene behind the wall. The resulting technique can be used for a variety of applications in diverse physical settings. From standard RGB video recordings, we use edge cameras to recover 1-D videos that reveal the number and trajectories of people moving in an occluded scene. We further show that adjacent wall edges, such as those that arise in the case of an open doorway, yield a stereo camera from which the 2-D location of hidden, moving objects can be recovered. We demonstrate our technique in a number of indoor and outdoor environments involving varied floor surfaces and illumination conditions.

We develop an information theoretic framework for addressing feature selection in applications where the inference task is not specified in advance and the data is from a large alphabet. We introduce a natural notion of universality for such problems, and show that locally optimal solutions are straight forward to obtain, admit natural interpretations via information geometry, have computationally efficient implementations, and represent a practically useful learning methodology. Our development also reveals the key role of Hirschfeld-Gebelein-Renyi maximal correlation and the alternating conditional expectations (ACE) algorithm in such problems.

We consider the problem of covert communication over a state-dependent channel, where the transmitter has non-causal knowledge of the channel states. Here, “covert” means that the probability that a warden on the channel can detect the communication must be small. In contrast with traditional models without noncausal channel-state information at the transmitter, we show that covert communication can be possible with positive rate. We derive closed-form formulas for the maximum achievable covert communication rate (“covert capacity”) in this setting for discrete memoryless channels as well as additive white Gaussian noise channels. We also derive lower bounds on the rate of the secret key that is needed for the transmitter and the receiver to achieve the covert capacity.

Multiple-input multiple-output (MIMO) radar systems have been shown to offer superior performance in direction of arrival (DOA) estimation applications compared to their phased array counterparts. The performance of these systems has been studied under various probing field-target interaction mechanisms. However, to the best of our knowledge, these have been restricted to linearized models. Motivated by various nonlinear imaging modalities we study DOA estimation in far field MIMO radar systems in conjunction with a power-law nonlinear probing field-target interaction mechanism and show that the nonlinearity increases the number of identifiable targets with a given number of antenna array elements.

This paper addresses the question of how to add redundancy to a collection of physical objects so that the overall system is more robust to failures. Physical redundancy can (generally) only be achieved by employing copy/substitute procedures. This is fundamentally different from information redundancy, where a single parity check simultaneously protects a large number of data bits against a single erasure. We propose a bipartite graph model of designing defect-tolerant systems where defective objects are repaired by reconnecting them to strategically placed redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size optimal systems are constructed. Mathematically, we say that a k by m bipartite graph corrects t defects over alphabet of size q if for every q-coloring of k left vertices there exists a coloring of m right vertices such that every left vertex is connected to at least t same-colored right vertices. We study the tradeoff between redundancy m/k and the total number of edges in the graph divided by k. The question is trivial when q ≥ k: the optimal solution is a simple t-fold replication. However, when q <; k some non-trivial savings are possible by leveraging the inherent repetition of colors.

The problem of finite-blocklength lossy compression is considered. Motivated by troubling behavior of the rate expressions under an excess-distortion probability constraint, we define the mean excess distortion criterion. We evaluate the asymptotic performance of various settings under this criterion, and show that sharp and insightful rate bounds can be derived.

A framework is developed for decode-and-forward-based relaying using standard coding and decoding that are good for the single-input single-output (SISO) additive white Gaussian noise channel. The framework is applicable to various scenarios and is demonstrated for several important cases. Each of these scenarios is transformed into an equivalent Gaussian multiple-input multiple-output (MIMO) common-message broadcast problem, which proves useful even when all links are SISO ones. Over the effective MIMO broadcast channel, a recently developed Gaussian MIMO common-message broadcast scheme is applied. This scheme transforms the MIMO links into a set of parallel SISO channels with no loss of mutual information, using linear pre- and post-processing combined with successive decoding. Over these resulting SISO channels, off-the-shelf scalar codes may be used.

This paper considers the problem of communication over a discrete memoryless channel (DMC) or an additive white Gaussian noise (AWGN) channel subject to the constraint that the probability that an adversary who observes the channel outputs can detect the communication is low. In particular, the relative entropy between the output distributions when a codeword is transmitted and when no input is provided to the channel must be sufficiently small. For a DMC whose output distribution induced by the “off” input symbol is not a mixture of the output distributions induced by other input symbols, it is shown that the maximum amount of information that can be transmitted under this criterion scales like the square root of the blocklength. The same is true for the AWGN channel. Exact expressions for the scaling constant are also derived.

Current compression systems incorporate a data model, however formed, deeply into the coding process, leading to difficulties of an architectural nature. This work contributes an alternative "Model-Code Separation" architecture for general compression, based on model-free coding and iterative message-passing algorithms over graphical models representing the modeling and coding aspects of compression in decoding. Systems following this architecture resolve important challenges posed by current systems, and stand to benefit further from advances in the understanding of data and the algorithms that process them.

We consider a streaming communication system where the source packets must be played back sequentially at the destination and study the associated average playback delay. We assume that all the source packets are available before the start of transmission at the transmitter and consider the case of an i.i.d. erasure channel with perfect feedback. We first consider the case when the receiver buffer can be arbitrarily large, and show that the average playback delay remains bounded in the length of the stream provided that the channel bandwidth is greater than a critical threshold. Our analysis involves the application of martingale theory to study the transient behaviour of a one dimensional random walk with drift. Conversely when the channel bandwidth is smaller than the above threshold, the average playback delay increases linearly with the stream length. We also consider the finite buffer case and analyse the playback delay of a greedy dynamic bandwidth scheme. We further show through simulations that the achievable delay with a finite receiver buffer is close to the infinite buffer case for moderately large buffer values.

Source coding is concerned with optimally compressing data, so that it can be reconstructed up to a specified distortion from its compressed representation. Usually, in fixed-length compression, a sequence of n symbols (from some alphabet) is encoded to a sequence of k symbols (bits). The decoder produces an estimate of the original sequence of n symbols from the encoded bits. The rate-distortion function characterizes the optimal possible rate of compression allowing a given distortion in reconstruction as n grows. This function depends on the source probability distribution. In a locally recoverable decoding, to reconstruct a single symbol, only a few compressed bits are accessed. In this paper we find the limits of local recovery for rates near the rate-distortion function. For a wide set of source distributions, we show that, it is possible to compress within ε of the rate-distortion function such the local recoverability grows as Ω(log(1/ε)); that is, in order to recover one source symbol, at least Ω(log(1/ε)) bits of the compressed symbols are queried. We also show order optimal impossibility results. Similar results are provided for lossless source coding as well.

This paper considers the problem of communication over a discrete memoryless channel subject to the constraint that the probability that an adversary who observes the channel outputs can detect the communication is low. Specifically, the relative entropy between the output distributions when a codeword is transmitted and when no input is provided to the channel must be sufficiently small. For a channel whose output distribution induced by the zero input symbol is not a mixture of the output distributions induced by other input symbols, it is shown that the maximum number of bits that can be transmitted under this criterion scales like the square root of the blocklength. Exact expressions for the scaling constant are also derived.

High-performance Model-Code Separation (MCS) architectures for lossless compression are practically viable with graphical message-passing in the decoder. This paper extends separation architectures to lossy compression by constructing model-free but semantics-aware encoders and contributes a new inference-friendly low-density hashing quantizer (LDHQ) to support decoding.

We investigate the fundamental limits of communication over optical on-off-keying channels with crosstalk, where a light pulse may span over multiple time slots or spatial pixels, and the receiver is equipped with single-photon detectors. First, we analyze achievable rates of communication over such channels, and observe that increasing transmission power (expected number of photons emitted per slot or pixel) does not necessarily lead to higher rates. Under simple but reasonable models, the highest rates are often achieved in a low-photon regime, with an average of 3 to 7 photons received in each slot or pixel. We further characterize the tradeoff between information rate and photon efficiency (in terms of the expected number of bits transmitted per photon) in the presence of crosstalk. Finally, we develop guidelines for slot length and pixel size selection for different application scenarios. Our analysis reveals that optimum optical-communication systems do not minimize the level of crosstalk.

We investigate lossy compression (source coding) of data in the form of permutations. This problem has direct applications in the storage of ordinal data or rankings, and in the analysis of sorting algorithms. We analyze the rate-distortion characteristic for the permutation space under the uniform distribution, and the minimum achievable rate of compression that allows a bounded distortion after recovery. Our analysis is with respect to different practical and useful distortion measures, including Kendall tau distance, Spearman’s footrule, Chebyshev distance, and inversion-$\ell _{1}$distance. We establish equivalence of source code designs under certain distortions and show simple explicit code designs that incur low encoding/decoding complexities and are asymptotically optimal. Finally, we show that for the Mallows model, a popular nonuniform ranking model on the permutation space, both the entropy and the maximum distortion at zero rate are much lower than the uniform counterparts, which motivates the future design of efficient compression schemes for this model.

We investigate the lossy compression of permutations by analyzing the trade-off between the size of a source code and the distortion with respect to Kendall tau distance, Spearman's footrule, Chebyshev distance and ℓ1distance of inversion vectors. We show that given two permutations, Kendall tau distance upper bounds the ℓ1distance of inversion vectors and a scaled version of Kendall tau distance lower bounds the ℓ1distance of inversion vectors with high probability, which indicates an equivalence of the source code designs under these two distortion measures. Similar equivalence is established for all the above distortion measures, every one of which has different operational significance and applications in ranking and sorting. These findings show that an optimal coding scheme for one distortion measure is effectively optimal for other distortion measures above.

Motivated by recent circuit designs for Flash ADCs with imperfect comparators, we investigate the problem of scalar quantization with noisy partition points, where the partition point locations are perturbed from the designated values by noise during the placement process. For this problem setting, we derive a high resolution approximation for mean square error, and analyze the optimal partition point density accordingly. Our results indicate that it is necessary to take the effect of noise into account in the design process. In particular, we derive the optimal partition point density when the input distribution is Gaussian or uniform, and show when noise variance exceeds a certain threshold, a peculiar phase transition occurs and the optimal point density degenerates into a delta function at the origin. These theoretical results allow to optimize the design of flash ADCs and gain 1 bit in resolution over existing designs.

We study the discrete-time Poisson channel under the constraint that its average input power (in photons per channel use) must not exceed some constant ε. We consider the wideband, high-photon-efficiency extreme where ε approaches zero, and where the channel's “dark current” approaches zero proportionally with ε. Extending our previous work, we show that the influence of the dark current on channel capacity is mainly on the third-order term with respect to ε. We also show that pulse-position modulation with “soft-decision decoding” achieves data rates that accurately reflect such influence.

In this paper, we investigate the limits of communication over optical on-off-keying channels with 1-D or 2-D crosstalk, where photons are transferable between adjacent time slots or spatial pixels, and the receiver is equipped with single-photon detectors.We observe that high transmission power (measured by the expected number of photons emitted in each signal slot or pixel) may not lead to high information rate; the maximum capacity is typically achieved in a low-photon regime - with about expected 3 to 8 photons received in each signal slot or pixel. Furthermore, we study the selection of slot length for maximizing the channel bandwidth, as the slot length affects the crosstalk probability and hence the channel capacity. It reveals that optimum optical-communication systems do not minimize the level of crosstalk between slots or pixels.

In this paper, we study the problem of compressing a collection of sequences of variable length that allows us to efficiently add, read, or edit an arbitrary sequence without decompressing the whole data. This problem has important applications in data servers, file-editing systems, and bioinformatics. We propose a novel and practical compression scheme, which shows that, by paying a small price in storage space (3% extra storage space in our examples), we can retrieve or edit a sequence (a few hundred bits) by accessing compressed bits close to the entropy of the sequence.

Large-scale distributed computing systems divide a job into many independent tasks and run them in parallel on different machines. A challenge in such parallel computing is that the time taken by a machine to execute a task is inherently variable, and thus the slowest machine becomes the bottleneck in the completion of the job. One way to combat the variability in machine response is to replicate tasks on multiple machines and waiting for the machine that finishes first. While task replication reduces response time, it generally increases resource usage. In this work, we propose a theoretical framework to analyze the trade-off between response time and resource usage. Given an execution time distribution for machines, our analysis gives insights on when and why replication helps. We also propose efficient scheduling algorithms for large-scale distributed computing systems.

Motivated by distributed storage applications, we investigate the degree to which capacity achieving codes can be efficiently updated when a single information symbol changes, and the degree to which such codes can be efficiently repaired when a single encoded symbol is lost. Specifically, we first develop conditions under which optimum error-correction and update-efficiency are possible. We establish that the number of encoded bits that should change in response to a change in a single information bit must scale logarithmically in the block-length of the code, if we are to achieve any nontrivial rate with vanishing probability of error over the binary erasure or binary symmetric channels. Moreover, we show that there exist capacity-achieving codes with this scaling. With respect to local repairability, we develop tight upper and lower bounds on the number of remaining encoded bits that are needed to recover a single lost encoded bit. In particular, we show that when the rate of an optimal code is ε below capacity, the maximum number of codeword symbols required to recover one lost symbol must scale as log1/ε. Several variations on-and extensions of-these results are also developed, including to the problem of rate-distortion coding.

This paper considers the distribution of a secret key over an optical (bosonic) channel in the regime of high photon efficiency, i.e., when the number of secret key bits generated per detected photon is high. While, in principle, the photon efficiency is unbounded, there is an inherent tradeoff between this efficiency and the key generation rate (with respect to the channel bandwidth). We derive asymptotic expressions for the optimal generation rates in the photon-efficient limit, and propose schemes that approach these limits up to certain approximations. The schemes are practical, in the sense that they use coherent or temporally entangled optical states and direct photodetection, all of which are reasonably easy to realize in practice, in conjunction with off-the-shelf classical codes.

In the above-referenced paper, typesetting errors caused mismatch between labels of schemes and subscripts in equations. Schemes S-3, S-4, and S-5 should be relabeled S-1, S-2, and S-3, respectively.

We study the discrete-time Poisson channel under the constraint that its average input power (in photons per channel use) must not exceed some constant ε. We consider the wideband, high-photon-efficiency extreme where ε approaches zero, and where the channel's dark current approaches zero proportionally with ε. Improving over a previously obtained first-order capacity approximation, we derive a refined approximation, which includes the exact characterization of the second-order term, as well as an asymptotic characterization of the third-order term with respect to the dark current. We also show that pulse-position modulation is nearly optimal in this regime.

An efficient sparse antenna array architecture is developed for coherent imaging of sparse but otherwise unknown scenes. In this architecture, the array elements form a periodic nonuniform pattern. Using analysis that explicitly takes into account the presence of noise, we develop an efficient pattern design procedure based on co-arrays, describe an efficient scene support recovery algorithm as part of image reconstruction in the form of a modification to the MUSIC algorithm, and discuss a failure detection technique based on evaluating “back-projection” error. Since our development exploits a close connection to multi-coset sampling of bandlimited waveforms, our results may in turn may also be useful in the design of those systems.

We investigate the lossy compression of the permutation space by analyzing the trade-off between the size of a source code and the distortion with respect to either Kendall tau distance or ℓ1distance of the inversion vectors. For both distortion measures, we characterize the rate-distortion functions and provide explicit code designs that achieve them. Finally, we provide bounds on the higher order terms in the codebook size when the distortion levels lead to degenerate code rates (0 or 1).

Secret key extraction, the task of extracting a secret key from shared information that is partially known by an eavesdropper, has important applications in cryptography. Motivated by the requirements of high-speed quantum key distribution, we study secret-key extraction methods with simple and efficient hardware implementations, in particular, linear transformations based on low-density random matrices. We show that this method can achieve the information-theoretic upper bound (conditional Shannon entropy) on efficiency for a wide range of key-distribution systems. In addition, we introduce a numerical method that allows us to tightly estimate the quality of the generated secret key in the regime of finite block length, and use this method to demonstrate that low-density random matrices achieve very high performance for secret key extraction.

High-dimensional quantum key distribution (QKD) systems that exploit temporal correlation among entangled photons are of growing practical interest. In such systems, the observation time is typically partitioned into frames of fixed duration, with pulse-position modulation (PPM) coding used within each frame, via which a secret key is established between the parties. Such schemes can be very inefficient in their use of photons, since only a fraction of the frames can be used. As an alternative, we describe an efficient class of schemes with adaptive frame size whose performance can converge to the fundamental limit much more quickly. We analyze and compare the performances of both fixed and adaptive PPM schemes, taking into account photon transmission and detection losses. Further numerical results reveal the significant performance gain of adaptive PPM relative to fixed PPM.

Several aspects of the problem of asynchronous point-to-point communication without feedback are developed when the source is highly intermittent. In the system model of interest, the codeword is transmitted at a random time within a prescribed window whose length corresponds to the level of asynchronism between the transmitter and the receiver. The decoder operates sequentially and communication rate is defined as the ratio between the message size and the elapsed time between when transmission commences and when the decoder makes a decision. For such systems, general upper and lower bounds on capacity as a function of the level of asynchronism are established, and are shown to coincide in some nontrivial cases. From these bounds, several properties of this asynchronous capacity are derived. In addition, the performance of training-based schemes is investigated. It is shown that such schemes, which implement synchronization and information transmission on separate degrees of freedom in the encoding, cannot achieve the asynchronous capacity in general, and that the penalty is particularly significant in the high-rate regime.

We consider the problem of minimizing playback delay in streaming over a packet erasure channel with fixed bandwidth. When packets have to be played in order, the expected delay inherently grows with time. We analyze two cases, namely no feedback and instantaneous feedback. We find that in both cases the delay grows logarithmically with the time elapsed since the start of transmission, and we evaluate the growth constant, i.e. the pre-log term, as a function of the transmission bandwidth (relative to the source bandwidth). The growth constant with feedback is strictly better that the one without, but they have the same asymptotic value in the limit of infinite bandwidth.

An update efficient code is a mapping from messages to codewords such that small perturbations in the message induce only slight changes to the corresponding codeword. The parameter that captures this notion is called update-efficiency. In this paper we study update-efficient error-correcting codes and develop their basic properties. While update-efficiency and error-correction are two conflicting objectives, we deduce conditions for existence of such codes. In particular, logarithmically growing update-efficiency is achievable with a capacity-achieving linear code in both binary symmetric and binary erasure channels. On the other hand we show a tight converse result. Our result implies that it is not possible to have a capacity-achieving code in binary symmetric channel that has sub-logarithmic update-efficiency. This is true in the case of the binary erasure channel as well for linear codes. We also discuss a number of questions related to update-efficient adversarial error-correcting codes.

Single-message unequal error protection (UEP) is a channel coding scheme that protects one special message differently from other (regular) messages. This induces three different types of errors in the system: 1) miss (where we decode the special codeword as a regular codeword), 2) false alarm (where we decode a regular codeword as the special codeword), and 3) decoding error (where we decode a regular codeword to another regular codeword). In this paper, we investigate the fundamental limits of single-message UEP, in the context of discrete memoryless channels (DMCs) without feedback. Similar to Borade et al., we use error exponents as the performance metric, and discuss maximizing the miss error exponent and the false alarm error exponent, respectively. We provide a new converse proof for the miss reliability function, i.e., the optimal miss error exponent as a function of communication rate, and extend the inner and outer bound results for the false alarm reliability function in Borade et al. from rates close to capacity to all rates up to capacity.

This work considers practical implementation of the decode-and-forward relaying protocol for the full-duplex Gaussian relay channel. Unlike previous works which developed coding techniques tailored to this protocol, it is shown that standard codes which are good for the Gaussian scalar channel of fixed signal-to-noise ratio suffice to approach the theoretical performance promised by this protocol. The proposed technique employs only linear operations and successive interference cancelation in conjunction with fixed signal-to-noise ratio base codes, and the achievable rate is solely dictated by the performance of these base codes. The same approach and results carry over to the multiple-antenna case as well.

This work considers the definition of the excess-distortion exponent, used to measure the asymptotic finite blocklength behavior of joint source-channel coding. We arrive at the conclusion that it is not a meaningful measure for the operational tradeoffs of a scheme. We propose a new definition, which makes a distinction between the processing block of the coding scheme (which implies delay and may be connected to complexity), the fidelity blocklength (reflecting the quality of the reconstruction as required by the application), and the resource blocklength (depending on hardware or shared medium considerations). As an aside, the exponent of uncoded schemes is analyzed. This results in finding the joint source-channel coding excess-distortion exponent in some cases where it was not known previously.

We study the discrete-time Poisson channel under the constraint that its average input power (in photons per channel use) must not exceed some constant ε. We consider the wideband, high-photon-efficiency extreme where ε approaches zero, and where the channel's “dark current” approaches zero proportionally with ε. Improving over a previously obtained first-order capacity approximation, we derive a refined approximation which also includes the second-order term. We also show that pulse-position modulation is optimal on this channel up to the second-order term in capacity.

A rateless code-i.e., a rate-compatible family of codes-has the property that codewords of the higher rate codes are prefixes of those of the lower rate ones. A perfect family of such codes is one in which each of the codes in the family is capacity-achieving. We show by construction that perfect rateless codes with low-complexity decoding algorithms exist for additive white Gaussian noise channels. Our construction involves the use of layered encoding and successive decoding, together with repetition using time-varying layer weights. As an illustration of our framework, we design a practical three-rate code family. We further construct rich sets of near-perfect rateless codes within our architecture that require either significantly fewer layers or lower complexity than their perfect counterparts. Variations of the basic construction are also developed, including one for time-varying channels in which there is no a priori stochastic model.

We study the secret-key capacity in a joint source-channel coding setup-the terminals are connected over a discrete memoryless channel and have access to side information, modelled as a pair of discrete memoryless source sequences. As our main result, we establish the upper and lower bounds on the secret-key capacity. In the lower bound expression, the equivocation terms of the source and channel components are functionally additive even though the coding scheme generates a single secret-key by jointly taking into account the source and channel equivocations. Our bounds coincide, thus establishing the capacity, when the underlying wiretap channel can be decomposed into a set of independent, parallel, and reversely degraded channels. For the case of parallel Gaussian channels and jointly Gaussian sources we show that Gaussian codebooks achieve the secret-key capacity. In addition, when the eavesdropper also observes a correlated side information sequence, we establish the secret-key capacity when both the source and channel of the eavesdropper are a degraded version of the legitimate receiver. We finally also treat the case when a public discussion channel is available, propose a separation based coding scheme, and establish its optimality when the channel output symbols of the legitimate receiver and eavesdropper are conditionally independent given the input.

We consider the problem of delivering content cached in a wireless network of n nodes randomly located on a square of area n. The network performance is described by the 2n× n-dimensional caching capacity region of the wireless network. We provide an inner bound on this caching capacity region, and, in the high path-loss regime, a matching (in the scaling sense) outer bound. For large path-loss exponent, this provides an information-theoretic scaling characterization of the entire caching capacity region. The proposed communication scheme achieving the inner bound shows that the problems of cache selection and channel coding can be solved separately without loss of order-optimality. On the other hand, our results show that the common architecture of nearest-neighbor cache selection can be arbitrarily bad, implying that cache selection and load balancing need to be performed jointly.

Based on recent work on asynchronous communication, this paper proposes a slotted asynchronous channel model and investigates the fundamental limits of asynchronous communication, in terms of miss and false alarm error exponents. We propose coding schemes that are suitable for various asynchronous communication scenarios, and quantify more precisely the suboptimality of training-based schemes, i.e., communication strategies that separate synchronization from information transmission. In particular, we show that under a broad set of conditions, training-based schemes are suboptimal at all positive rates. Finally, we demonstrate these performance differences by specializing our results to BSCs and AWGN channels.

The problem of multicasting common data to several users over multiple-input multiple-output (MIMO) Gaussian channels is studied. A closed-loop setup is considered where the channel matrices are known to the transmitter and respective receivers. An incremental-redundancy (rateless) scenario is considered, where the effective rate is measured by the time that each user needs to stay online until it is able to decode the message. A practical transmission scheme for the two-user case is proposed which, by linear pre - and post-processing combined with successive decoding and interference cancellation, transforms the two MIMO channels into a set of parallel channels with no loss of mutual information, where each user needs to tune in for a duration of time proportional to its individual capacity. This scheme is used for designing a practical transmission scheme for the Gaussian MIMO half-duplex relay channel. We then turn to the related scenario of transmission to a single user over a MIMO channel with unknown but constant signal-to-noise ratio (SNR), for which we develop an optimal low-complexity hybrid ARQ coding scheme, which is optimal for two SNRs and propose a scheme for more SNRs, the loss of which vanishes when the SNRs are high. Finally, we show that even when applied to single-input single-output (“scalar”) channels, the scheme provides a practical solution for cases not covered by previous work.

We consider streaming over a blockage channel with long feedback delay, as arises in, e.g., real-time satellite communication from a comm-on-the-move (COTM) terminal. For this problem, we introduce a definition of delay that captures the real-time nature of the problem, which we show grows at least as fast as O(log(k)) for memoryless channels, where k corresponds to the number of packets in the transmission. Moreover, a tradeoff exists between this delay and a natural notion of throughput we introduce to capture the bandwidth requirements of the communication. We develop and analyze an efficient "multi-burst" transmission (MBT) protocol for achieving good delay-throughput tradeoffs within this framework, which we show to be robust and near-optimal within the class of retransmission protocols with fixed schedules. The MBT protocol can be augmented with coding for additional performance gains. Simulations validate the new protocols, including when peak bandwidth and delay constraints are imposed.

We study the capacity of secret-key agreement over a wiretap channel with state parameters. The transmitter, the legitimate receiver, and the eavesdropper are connected by a discrete memoryless wiretap channel with a memoryless state sequence. The transmitter and the legitimate receiver generate a secret-key that must be concealed from the eavesdropper. We assume that the state sequence is known noncausally to the transmitter and no public discussion channel is available. We derive lower and upper bounds on the secret-key capacity. The lower bound involves a source-channel codebook for constructing a common reconstruction sequence at the legitimate terminals and then mapping this sequence to a secret-key using a secret-key codebook. For the special case of Gaussian channels with additive interference (secret-keys from dirty paper channel) our bounds differ by 0.5 bit/symbol and coincide in the high signal-to-noise-ratio and high interference-to-noise-ratio regimes. In another special case-symmetric channel state information (CSI)-when the legitimate receiver is also revealed the state sequence, we establish optimality of our lower bound. In addition, only causal side information at the transmitter and the receiver suffices to attain the secret-key capacity in the case of symmetric CSI.

We propose a linear predictive quantization system for causally transmitting parallel sources with temporal memory (colored frames) over an erasure channel. By optimizing within this structure, we derive an achievability result in the high-rate limit and compare it to an upper bound on performance. The proposed system subsumes the well-known PCM and DPCM systems as special cases. While typically DPCM performs well without erasures and PCM suffers less with many erasures, we show that the proposed solution improves performance over both under all severities of erasures, with unbounded improvement in some cases.

Brain machine interfaces work by mapping the relevant neural activity to the intended movement known as `decoding'. Here, we develop a recursive Bayesian decoder for goal-directed movements from neural observations, which exploits the optimal feedback control model of the sensorimotor system to build better prior state-space models. These controlled state models depend on the movement duration that is not known a priori. We thus consider a discretization of the task duration and develop a decoder consisting of a bank of parallel point-process filters, each combining the neural observation with the controlled state model of a discretization point. The final reconstruction is made by optimally combining these filter estimates. Using very coarse discretization and hence only a few parallel branches, our decoder reduces the root mean square (RMS) error in trajectory reconstruction in reaches made by a rhesus monkey by approximately 40%.

A dense antenna array architecture is developed to ease the circuit requirements of the radio frequency (RF) front-end in beamforming applications. In the architecture, antennas are spaced more closely than would otherwise be required to exploit the available degrees of freedom. Such an array structure is analogous to temporally oversampled data conversion systems, which have reduced quantizer resolution requirements. For a linear, uniformly-spaced array, we develop a spatial-domain version of ΔΣ quantization, and show that with binary quantization for the in-phase and quadrature components of antenna weights, even relatively modest amounts of oversampling can reproduce beamforming patterns of interest to practically useful levels of accuracy.

We consider the recovery of a nonnegative vector x from measurements y = Ax, where A ∈ {0, 1}m×n. We establish that when A corresponds to the adjacency matrix of a bipartite graph with sufficient expansion, a simple message-passing algorithm produces an estimate x^ of x satisfying ∥x-x^∥1≤ O(n/k) ∥x-x(k)∥1, where x(k)is the best k-sparse approximation of x. The algorithm performs O(n(log(n/k))2log (k)) computation in total, and the number of measurements required is m = O(k log(n/k)). In the special case when x is k-sparse, the algorithm recovers x exactly in time O(n log(n/k) log(k)). Ultimately, this work is a further step in the direction of more formally developing the broader role of message-passing algorithms in solving compressed sensing problems.

An achievable excess distortion exponent for compression of a white Gaussian source by dithered lattice quantization is derived. We show that for a required distortion level close enough to the rate-distortion function, and in the high-rate limit, the exponent equals the optimal quadratic-Gaussian excess distortion exponent. Using this approach, no further loss is incurred by the presence of any source interference known at the decoder (“Wyner-Ziv side-information”). The derivation of this achievable exponent involves finding the exponent of the probability that a combination of a spherically-bounded vector and a Gaussian vector leaves the Voronoi cell of a good lattice.

The role of multiple antennas for secure communication is investigated within the framework of Wyner's wiretap channel. We characterize the secrecy capacity in terms of generalized eigenvalues when the sender and eavesdropper have multiple antennas, the intended receiver has a single antenna, and the channel matrices are fixed and known to all the terminals, and show that a beamforming strategy is capacity-achieving. In addition, we study a masked beamforming scheme that radiates power isotropically in all directions and show that it attains near-optimal performance in the high SNR regime. Insights into the scaling behavior of the capacity in the large antenna regime as well as extensions to ergodic fading channels are also provided.

The capacity of the Gaussian wiretap channel model is analyzed when there are multiple antennas at the sender, intended receiver and eavesdropper. The associated channel matrices are fixed and known to all the terminals. A computable characterization of the secrecy capacity is established as the saddle point solution to a minimax problem. The converse is based on a Sato-type argument used in other broadcast settings, and the coding theorem is based on Gaussian wiretap codebooks.

We study secret-key agreement protocols over a wiretap channel controlled by a state parameter. The secret-key capacity is established when the wiretap channel is discrete and memoryless, the sender and receiver are both revealed the underlying state parameter, and no public discussion is allowed. An optimal coding scheme involves a two step approach — (i) design a wiretap codebook assuming that the state parameter is also known to the eavesdropper (ii) generate an additional secret key by exploiting the uncertainty of the state parameter at the eavesdropper. When unlimited public discussion is allowed between the legitimate terminals, we provide an upper bound on the secret-key capacity and establish its tightness when the channel outputs of the legitimate receiver and eavesdropper satisfy a conditional independence property. Numerical results for an on-off fading model suggest that the proposed coding schemes significantly outperform naive schemes that either disregard the contribution of the common state sequence or the contribution of the underlying channel.

We consider the problem of delivering content cached in a wireless network of n nodes randomly located on a square of area n. In the most general form, this can be analyzed by considering the 2ntimesn-dimensional caching capacity region of the wireless network. We propose a communication scheme for transmission of messages cached in the network. This provides an inner bound to the caching capacity region.

The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables. The iterative nature and simplicity of the algorithm has led to its application in many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm are known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. More precisely, we consider the impact of having a slowly time-varying domain over which the minimization takes place. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps somewhat surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.

A formulation of the problem of asynchronous point-to-point communication is developed. In the system model of interest, the message codeword is transmitted over a channel starting at a randomly chosen time within a prescribed window. The length of the window scales exponentially with the codeword length, where the scaling parameter is referred to as the asynchronism exponent. The receiver knows the transmission window, but not the transmission time. Communication rate is defined as the ratio between the message size and the elapsed time between when transmission commences and when the decoder makes a decision. Under this model, several aspects of the achievable tradeoff between the rate of reliable communication and the asynchronism exponent are quantified. First, the use of generalized constant-composition codebooks and sequential decoding is shown to be sufficient for achieving reliable communication under strictly positive asynchronism exponents at all rates less than the capacity of the synchronized channel. Second, the largest asynchronism exponent under which reliable communication is possible, regardless of rate, is characterized. In contrast to traditional communication architectures, there is no separate synchronization phase in the coding scheme. Rather, synchronization and communication are implemented jointly. The results are relevant to a variety of sensor network and other applications in which intermittent communication is involved.

Two rateless code constructions are developed for efficient communication over multi-input multi-output (MIMO) Gaussian channels. The key ingredients in both architectures are layering, dithering, and repetition. Both employ successive cancellation decoding along with minimum mean-square error (MMSE) combining and convert the MIMO channel into a scalar channel to which classical Gaussian base codes can be applied. The first construction based on simple layering induces an additive white Gaussian noise (AWGN) scalar channel and with perfect base codes achieves a substantial efficiency gain over a baseline repetition scheme. At typical spectral efficiencies, this scheme can achieve better than 85% of capacity for a rateless construction with two effective rates. The second construction which uses a diagonal layering (DL) structure is capacity achieving at any SNR and induces a particular time-varying scalar channel. This holds even if the MIMO channel is block constant but time-varying.

In this paper, we propose a time-domain method for uniform signal reconstruction from periodic nonuniform samples of a bandlimited signal when timing-skews are known. The algorithm computes a constrained least-squares estimate of the input via the pseudoinverse of a time-varying filter. The method exploits the oversampling in the system to provide increased performance in the presence of noise.

A joint-source-channel setup for secret-key generation between remote terminals is considered. The sender communicates to the receiver over a discrete memoryless wiretap channel and the sender and receiver observe a pair of correlated discrete memoryless sources. Lower and upper bounds for the secret-key rate are presented and shown to coincide for the case when the underlying channel is a reversely degraded parallel channel. Our setup also provides an operational significance to the rate-equivocation tradeoff of the wiretap channel, and this is illustrated in detail for the Gaussian case.

Two time-invariant rateless code constructions are developed for efficient communication over multi-input multi- output (MIMO) Gaussian channels. Both architectures employ layering, dithering, and repetition as key ingredients, and convert the MIMO channel into a scalar channel to which classical Gaussian base codes can be applied. Both constructions are convolutionally structured - one is based on faster-than-Nyquist (ftN) signaling, while the other on a diagonal layering (DL) structure. Moreover, both employ successive cancellation decoding. We show that ftN rateless codes are asymptotically capacity achieving at any signal-to-noise ratio (SNR) and induce a time-invariant scalar channel. We also show that DL codes are capacity achieving at any SNR, and induce a particular time-varying scalar channel to which standard LDPC base codes can be applied without significantly sacrificing performance.

We consider asynchronous communication over discrete memoryless channels. The transmitter starts sending one block codeword of length N at an instant that is uniformly distributed within a certain time period A, which represents the level of asynchronism between the transmitter and the receiver. The receiver, by means of a sequential decoder, must isolate the message without knowing when the codeword transmission starts but being cognizant of the asynchronism level. Motivated by certain monitoring type of applications, we are interested in communication strategies that 1) operate with short codeword length with respect to the asynchronism level and 2) that guarantee quick decoding. In a recent work the authors showed that the communication rate - defined with respect to the decoder's reaction delay to the sent message - can be strictly positive unlessAgrows faster than lscrNaand alpha exceeding the synchronization threshold. The present work focuses on the regime where a is smaller than thesynchronizationthreshold. The main contribution consists of simple expressions that give upper and lower bounds on the highest achievable rate for any alpha below the synchronization threshold. For random code constructions these bounds are tight.

We consider the “one-shot frame synchronization problem,” where a decoder wants to locate a sync pattern at the output of a memoryless channel on the basis of sequential observations. The sync pattern of length$N$starts being emitted at a random time within some interval of size$A$, where$A$characterizes the asynchronism level. We show that a sequential decoder can optimally locate the sync pattern, i.e., exactly, without delay, and with probability approaching one as$N \rightarrow \infty$, if the asynchronism level grows as$O(e^{N\alpha})$, with$\alpha$below thesynchronization threshold, a constant that admits a simple expression depending on the channel. If$\alpha$exceeds the synchronization threshold, any decoder, sequential or nonsequential, locates the sync pattern with an error that tends to one as$N\rightarrow \infty$. Hence, a sequential decoder can locate a sync pattern as well as the (nonsequential) maximum-likelihood decoder that operates on the basis of output sequences of maximum length$A+N-1$, but with far fewer observations.

We study a problem of broadcasting confidential messages to multiple receivers under an information-theoretic secrecy constraint. Two scenarios are considered: 1) all receivers are to obtain a common message; and 2) each receiver is to obtain an independent message. Moreover, two models are considered: parallel channels and fast-fading channels. For the case of reversely degraded parallel channels, one eavesdropper, and an arbitrary number of legitimate receivers, we determine the secrecy capacity for transmitting a common message, and the secrecy sum-capacity for transmitting independent messages. For the case of fast-fading channels, we assume that the channel state information of the legitimate receivers is known to all the terminals, while that of the eavesdropper is known only to itself. We show that, using a suitable binning strategy, a common message can be reliably and securely transmitted at a rate independent of the number of receivers. We also show that a simple opportunistic transmission strategy is optimal for the reliable and secure transmission of independent messages in the limit of large number of receivers.

The impact of side information about the distortion measure in problems of quantization is analyzed. It is shown that such "distortion side information" is not only useful in general, but that in many cases knowing it at only the encoder is as good as knowing it at both encoder and decoder, and knowing it at only the decoder is useless. Moreover, it is shown that the strategy of exploiting distortion side information at the encoder by describing it for the decoder is inefficient. Thus, distortion side information is a natural complement to side information about the source signal, as studied by Wyner and Ziv, which if available only at the decoder is often as good as knowing it at both encoder and decoder. When both types of side information are present, conditions are established under which encoder-only distortion side information and decoder-only signal side information are sufficient in the high-resolution limit, and the rate penalty for deviating from this configuration is characterized.

For orthogonal frequency-division multiplexing (OFDM) systems, peak to average power ratio (PAPR) can be a major impediment to efficient transmission due to the need to use inefficient highly linear amplifiers. This paper presents an iterative algorithm to reduce the PAPR of a low-power OFDM system by 3 dB at a clipping probability of 10-2, and over 5 dB for 10-5with asymptotically no loss in code rate for low signal to noise ratios (SNR). The reduced PAPR allows the system to use a more efficient form of linear amplifier, for an overall reduction in transmitter power consumption by over a factor of three at low SNR. In addition, the algorithm does not require any side information to be transmitted to the receiver to allow decoding.

Wyner's wiretap channel is generalized to the case when the sender, the receiver and the eavesdropper have multiple antennas. We consider two cases: the deterministic case and the fading case. In the deterministic case, the channel matrices of the intended receiver and the eavesdropper are fixed and known to all the nodes. In the fading case, the channel matrices experience block fading and the sender has only the intended receiver's channel state information (CSI) and statistical knowledge of the eavesdropper's channel. For the deterministic case, a scheme based on the generalized-singular-value-decomposition (GSVD) of the channel matrices is proposed and shown to achieve the secrecy capacity in the high signal-to-noise-ratio (SNR) limit. When the intended receiver has only one antenna (MISO case) the secrecy-capacity is characterized for any SNR. Next, a suboptimal "artificial noise" based scheme is considered. Its performance is characterized and observed to be nearly optimal in the high SNR regime for the MISO case. This scheme extends naturally to the fading case and results are reported for the MISO case. For the independent Rayleigh fading distribution as we simultaneously increase the number of antennas at the sender and the eavesdropper, the secrecy capacity approaches zero if and only if the ratio of the number of eavesdropper antennas to transmitter antennas is at least two.

The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables or equivalently of finding a point in the intersection of two sets. The iterative nature and simplicity of the algorithm has led to its application to many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm is quite well-known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. Our result is a generalization of the work by Csiszar and Tusnady on alternating minimization procedures. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.

We present a generalization of the well-known Bayesian change-point detection problem. Specifically, let {(Xi,Yi)}iges1be a sequence of pairs of random variables, and let S be a stopping time with respect to {Xi}iges1. We assume that the (Xi, Yi)'s take values in the same finite alphabet X times Y. For a fixed kappa ges 1, we consider the problem of finding a stopping time Ti}iges1that optimally tracks S, in the sense that T minimizes the average reaction time E(T - S)+, while it keeps the false-alarm probability P(Tkappa), and constructs the associated optimal stopping times T. In this paper, we provide a sufficient condition on {(Xi,Yi)}iges1and S under which the algorithm running time is polynomial in kappa, and we illustrate this condition with two examples: a Bayesian change-point problem and a pure tracking stopping time problem.

A generalization of the problem of writing on dirty paper is considered in which one transmitter sends a common message to multiple receivers. Each receiver experiences on its link an additive interference (in addition to the additive noise), which is known noncausally to the transmitter but not to any of the receivers. Applications range from wireless multiple-antenna multicasting to robust dirty paper coding. We develop results for memoryless channels in Gaussian and binary special cases. In most cases, we observe that the availability of side information at the transmitter increases capacity relative to systems without such side information, and that the lack of side information at the receivers decreases capacity relative to systems with such side information. For the noiseless binary case, we establish the capacity when there are two receivers. When there are many receivers, we show that the transmitter side information provides a vanishingly small benefit. When the interference is large and independent across the users, we show that time sharing is optimal. For the Gaussian case, we present a coding scheme and establish its optimality in the high signal-to-interference-plus-noise limit when there are two receivers. When the interference power is large and independent across all the receivers, we show that time-sharing is again optimal. Connections to the problem of robust dirty paper coding are also discussed

We consider communication over the Gaussian multiple access channel (MAC) with unknown set of active users. The proposed multiple access strategy is distributed and achieves a maximum sum rate point on the boundary of the capacity region for this channel for any set of active users S simultaneously, as if S were known at the transmitters. The proposed coding scheme splits each user into a set of virtual users, each of which can be decoded using a single-user decoder at the receiver instead of having to decode all users jointly. We also present a generalization of this scheme to the case where the channel gains differ between users and each user only knows its own channel gain.

This paper introduces a digital amplitude-to-phase conversion scheme to facilitate the outphase amplifying concept, enabling the use of high efficiency, non-linear power amplifiers in linear systems. The digital implementation enables a fast and accurate amplitude-to-phase conversion by exploiting the computational capability that can be easily incorporated in today’s integrated circuits (ICs). The proposed scheme minimizes amplitude variation of the outphase signals, which reduces the gain requirement of the power amplifiers that can be traded for higher efficiency. Our analysis demonstrates that outphase amplifying can be twice as efficient as the conventional class-A power amplifiers, and is suitable for wireless systems with large peak-to-average ratios.

The performance of high-resolution time-interleaved analog-to-digital converters is often significantly degraded by timing mismatch errors. This paper examines low-complexity methods for performing blind calibration of such converters. In particular, we develop a least squares formulation for estimating the unknown time-skew parameters and for performing signal reconstruction from these estimates. The complexity of the proposed algorithm scales linearly with the number of converters, making it an attractive solution for calibration. Tradeoffs between performance and complexity are also developed

We show that linear complexity capacity-approaching information embedding codes exist for information embedding problems. Specifically, we introduce the double-erasure information embedding channel model, and show that in at least some parameter regimes one can achieve rates arbitrarily close to capacity using suitably defined codes on graphs. Furthermore, we show that both encoding and decoding can be implemented with linear complexity by exploiting belief propagation techniques

A rateless code, or a rate-compatible family of codes, has the property that the higher rate codes have codewords that are prefixes of those of the lower rate ones. A perfect family of such codes is one in which each of the codes in the family is capacity-achieving. We show by construction that perfect rateless codes with low-complexity decoding algorithms exist for additive white Gaussian noise channels. As an illustration of our framework, we design a practical three-rate code family. We further demonstrate that a rich set of perfect or near-perfect rateless codes may be found via numerical optimization

We use the distortion side information (DSI) framework to study the gains in information embedding when the encoder exploits sensitivity of the source samples. Our study for the Gaussian source model extends the dirty paper coding result by Costa to the case of a weighted power constraint with the weights only known to the transmitter. A coding scheme based on fixed codebook variable-partition codes is presented for this problem. We also present another coding scheme that exploits the knowledge of DSI and is robust against intentional attacks. Finally, we study a related problem of Wyner-Ziv coding with reliability side information (RSI) at the decoder. This latter setup illustrates that fixed codebook variable-partition codes could also be fundamental in systems that rely on conventional distortion measures

We develop and analyze a simple, low-complexity system architecture for scheduling over a Gaussian multiple-input multiple-output (MIMO) broadcast channel with infinite message backlogs. In the system of interest, there is a transmitter with m antennas, and n receiving users, where n Gt m. We show that the proposed architecture is strongly asymptotically optimal with respect to average throughput. We further characterize the feedback requirements of the architecture, and highlight various tradeoffs available to the system designer

We study the information theoretic limits of communication over asynchronous discrete memoryless channels. The transmitter starts sending a block codeword of length N at a time v uniformly distributed within the interval [1, 2, ..., L]. We assume that the receiver knows L but not v. We give a scaling law of L with respect to N for which reliable communication can be achieved. Specifically, we propose a communication scheme with the property that, unless the asynchrony level L grows at least as eNC, where C denotes the capacity of the synchronized channel, arbitrary low error probability can be achieved. If L grows sub-exponentially in N, the capacity is the same as that of the ordinary synchronized channel. Further, we provide a lower bound to the error probability given a certain channel, codebook, and asynchrony level. This bound together with our scheme shows that, in certain cases, the condition L les eNC(1-delta)for any delta > 0 is an asymptotic necessary and sufficient condition for reliable communication. Finally we extend our analysis to a simple scenario where communication is carried over a Gaussian channel with antipodal signaling +radicP and -radicP. We show that a necessary condition on the amount of power needed in order to guarantee reliable communication is that P must scale as 1/NlogL when L rarr infin

We consider "bit stealing" scenarios where the rate of a source code must be reduced without prior planning. We first investigate the efficiency of source requantization to reduce rate, which we term successive degradation. We focus on finite-alphabet sources with arbitrary distortion measures as well as the Gaussian-quadratic and high-resolution scenarios. We show an achievable rate-distortion tradeoff and prove that this is the best guaranteeable tradeoff for any good source code. This tradeoff is in general different from the rate-distortion tradeoff with successive refinement, where there is prior planning. But, we show that with quadratic distortion measures, for all sources with finite differential entropy and at least one finite moment, the gap is at most 1/2 bit or 3 dB in the high-resolution limit. In the Gaussian-quadratic case, the gap is at most 1/2 bit for all resolutions. We further consider bit stealing in the form of information embedding, whereby an embedder acts on a quantized source and produces an output at the same rate and in the original source codebook. We develop achievable distortion-rate tradeoffs. Two cases are considered, corresponding to whether or not the source decoder is informed of the embedding rate. In the Gaussian-quadratic case, we show the informed decoder need only augment the regular decoder with simple post-reconstruction distortion compensation in the form of linear scaling for the resulting system to be as efficient as bit stealing via successive degradation. Finally, we show that the penalty for uninformed versus informed decoders is at most 3 dB or 0.21-bit in the Gaussian-quadratic case and that their performance also lies within the 1/2-bit gap to that of successive refinement.

A framework is developed for analyzing capacity gains from user cooperation in slow-fading wireless networks when the number of nodes (network size) is large. The framework is illustrated for the case of a simple multipath-rich Rayleigh-fading channel model. Both unicasting (one source and one destination) and multicasting (one source and several destinations) scenarios are considered. We introduce a meaningful notion of Shannon capacity for such systems, evaluate this capacity as a function of signal-to-noise ratio (SNR), and develop a simple two-phase cooperative network protocol that achieves it. We observe that the resulting capacity is the same for both unicasting and multicasting, but show that the network size required to achieve any target error probability is smaller for unicasting than for multicasting. Finally, we introduce the notion of a network "scaling exponent" to quantify the rate of decay of error probability with network size as a function of the targeted fraction of the capacity. This exponent provides additional insights to system designers by enabling a finer grain comparison of candidate cooperative transmission protocols in even moderately sized networks.

Rateless codes are good codes of infinite length that have the property that prefixes of such codes are themselves good codes. This makes them attractive for applications in which the channel quality is uncertain, where systems transmit as much of a codeword as necessary for decoding to be possible. In particular, rateless codes are potentially attractive for wireless communication. In a recent work, a rateless coding scheme was proposed for the AWGN channel, based on layering, repetition and random dithering. We extend this scheme to multiple-input single-output (MISO) Gaussian channels. We show that the rate loss associated with orthogonal design space-time codes may be alleviated by layering and dithering, very similar to the rateless approach for the AWGN channel. We then combine the two schemes and arrive at a close-to-capacity rateless code for MISO channels. The required complexity depends on the fraction of capacity that is targeted, is linear in the capacity of the channel and does not depend on the number of transmit antennas. Furthermore, the coding scheme uses only one base AWGN code

In this paper we introduce a blind parameter identification algorithm for Orthogonal Frequency Division Multiplexing (OFDM) signals. The algorithm correlation-based processes automatically estimate all parameters of OFDM signals with a blind process that works from a limited amount of data without any prior information. We also derive novel identification performances of algorithms under various conditions, assuming actual conditions in feasible systems: data offset, AWGN, frequency offset, and fading channels. The algorithm is essential for two systems: first, Cognitive Radios, one of the most exciting being radios that change fundamental parameters frequently to provide high throughput and high quality of services; and, second, Radio Monitoring Systems that detect illegal signals transmitted by unlicensed devices.

We consider transmitting a source across a pair of independent, nonergodic channels with random states (e.g., slow-fading channels) so as to minimize the average distortion. The general problem is unsolved. Hence, we focus on comparing two commonly used source and channel encoding systems which correspond to exploiting diversity either at the physical layer through parallel channel coding or at the application layer through multiple description (MD) source coding. For on-off channel models, source coding diversity offers better performance. For channels with a continuous range of reception quality, we show the reverse is true. Specifically, we introduce a new figure of merit called the distortion exponent which measures how fast the average distortion decays with signal-to-noise ratio. For continuous-state models such as additive white Gaussian noise (AWGN) channels with multiplicative Rayleigh fading, optimal channel coding diversity at the physical layer is more efficient than source coding diversity at the application layer in that the former achieves a better distortion exponent. Finally, we consider a third decoding architecture: MD encoding with joint source-channel decoding. We show that this architecture achieves the same distortion exponent as systems with optimal channel coding diversity for continuous-state channels, and maintains the advantages of MD systems for on-off channels. Thus, the MD system with joint decoding achieves the best performance from among the three architectures considered, on both continuous-state and on-off channels.

In a variety of applications, there is a need to authenticate content that has experienced legitimate editing in addition to potential tampering attacks. We develop one formulation of this problem based on a strict notion of security, and characterize and interpret the associated information-theoretic performance limits. The results can be viewed as a natural generalization of classical approaches to traditional authentication. Additional insights into the structure of such systems and their behavior are obtained by further specializing the results to Bernoulli and Gaussian cases. The associated systems are shown to be substantially better in terms of performance and/or security than commonly advocated approaches based on data hiding and digital watermarking. Finally, the formulation is extended to obtain efficient layered authentication system constructions.

We consider lossy source coding when side information affecting the distortion measure may be available at the encoder, decoder, both, or neither. For example, such distortion side information can model reliabilities for noisy measurements, sensor calibration information, or perceptual effects like masking and sensitivity to context. When the distortion side information is statistically independent of the source, we show that in many cases (e.g., for additive or multiplicative distortion side information) there is no penalty for knowing the side information only at the encoder, and there is no advantage to knowing it at the decoder. Furthermore, for quadratic distortion measures scaled by the distortion side information, we evaluate the penalty for lack of encoder knowledge and show that it can be arbitrarily large. In this scenario, we also sketch transform based quantizers constructions which efficiently exploit encoder side information in the high-resolution limit.

Calibration is a serious challenge in the design of high-speed time-interleaved analog-to-digital converters (ADC). We develop an iterative blind calibration technique for such converters. In particular, an expectation-maximize (EM) algorithm is used to estimate the associated unknown gains and time-offsets, from which the calibrated signal is reconstructed. Tradeoffs between the calibration time, reconstruction quality, and the oversampling factor are developed. The proposed algorithm can also be used in a variety of other applications, including problems of distributed sampling in sensor networks.

We study the problem of sending a common message to several users on a channel with side information. Specifically, each user experiences an additive interference which is known only to the sender. The sender has to simultaneously adapt its transmitted signal to all the interferences. We derive upper and lower bounds for the special case of binary channels and derive some optimality conditions.

This paper describes the source-channel coding diversity approaches for multimedia communication. The decision of which system to use should be based on both the benefits of a large distortion exponent as well cost, flexibility and ease of implementation

We introduce the idea of distortion side information, which does not directly depend on the source but instead affects the distortion measure. Such side information is not only useful at the encoder, but under many conditions of interest, knowing it at the encoder alone is sufficient and knowing it at the decoder alone is useless.

We develop coding strategies for estimation under communication constraints in tree-structured sensor networks. The strategies have a modular and decentralized architecture. This promotes the flexibility, robustness, and scalability that wireless sensor networks need to operate in uncertain, changing, and resource-constrained environments. The strategies are based on a generalization of Wyner-Ziv source coding with decoder side information. We develop solutions for general trees, and illustrate our results in serial (pipeline) and parallel (hub-and-spoke) networks. Additionally, the strategies can be applied to other network information theory problems. They have a successive coding structure that gives an inherently less complex way to attain a number of prior results, as well as some novel results, for the Chief Executive Officer problem, multiterminal source coding, and certain classes of relay channels.

We develop and analyze low-complexity cooperative diversity protocols that combat fading induced by multipath propagation in wireless networks. The underlying techniques exploit space diversity available through cooperating terminals' relaying signals for one another. We outline several strategies employed by the cooperating radios, including fixed relaying schemes such as amplify-and-forward and decode-and-forward, selection relaying schemes that adapt based upon channel measurements between the cooperating terminals, and incremental relaying schemes that adapt based upon limited feedback from the destination terminal. We develop performance characterizations in terms of outage events and associated outage probabilities, which measure robustness of the transmissions to fading, focusing on the high signal-to-noise ratio (SNR) regime. Except for fixed decode-and-forward, all of our cooperative diversity protocols are efficient in the sense that they achieve full diversity (i.e., second-order diversity in the case of two terminals), and, moreover, are close to optimum (within 1.5 dB) in certain regimes. Thus, using distributed antennas, we can provide the powerful benefits of space diversity without need for physical arrays, though at a loss of spectral efficiency due to half-duplex operation and possibly at the cost of additional receive hardware. Applicable to any wireless setting, including cellular or ad hoc networks-wherever space constraints preclude the use of physical arrays-the performance characterizations reveal that large power or energy savings result from the use of these protocols.

It is well-known that using multiple antennas can substantially increase the data rate and robustness of communication systems in a fading environment. It was recently established that there is a tradeoff between these two types of gains, termed diversity-multiplexing tradeoff. We develop a family of short structured space-time block codes that achieves the optimal tradeoff for the two-transmit two-receive antenna system with the minimum delay of two necessary for optimality. It uses the idea of rotation of cross-diagonal entries of an uncoded system to achieve spreading of information across space and time to obtain the maximum diversity while preserving multiplexing gain. Rotation angles that are optimal in terms of a determinant criterion and universal for all rates are identified. Performance analysis and simulation results are presented to demonstrate the achieved tradeoff.

Diversity techniques often arise as appealing means for improving the performance of multimedia communication over certain types of channels with independent parallel components (e.g., multiple antennas, frequency bands or time slots). Diversity can be obtained by channel coding across parallel components at the physical layer. Alternatively, the physical layer ca present an interface to the parallel components as separate, independent links thus allowing the application layer to implement diversity in the form of multiple description source coding. We compare these two approaches in terms of average end-to-end distortion as a function of channel signal-to-noise ratio (SNR). When specialized to the case of an independent, identically distributed Gaussian source over Rayleigh fading channels, our results suggest that parallel channel coding at the physical layer is more efficient than independent channel coding combined with multiple description source coding. More generally, we provide intuitive guidelines for allowing system designers to identify which types of systems are preferable under different scenarios of practical interest.

Aspects of the duality between the information-embedding problem and the Wyner-Ziv (1976) problem of source coding with side information at the decoder are developed and used to establish a spectrum new results on these and related problems, with implications for a number of important applications. The single-letter characterization of the information-embedding problem is developed and related to the corresponding characterization of the Wyner-Ziv problem, both of which correspond to optimization of a common mutual information difference. Dual variables and dual Markov conditions are identified, along with the dual role of noise and distortion in the two problems. For a Gaussian context with quadratic distortion metric, a geometric interpretation of the duality is developed. From such insights, we develop a capacity-achieving information-embedding system based on nested lattices. We show the resulting encoder-decoder has precisely the same decoder-encoder structure as the corresponding Wyner-Ziv system based on nested lattices that achieves the rate-distortion limit. For a binary context with Hamming distortion metric, the information-embedding capacity is developed, along with its relationship to the corresponding Wyner-Ziv rate-distortion function. In turn, an information-embedding system for this case based on nested linear codes is constructed having an encoder-decoder that is identical to the decoder-encoder structure for the corresponding system that achieves the Wyner-Ziv rate-distortion limit. Finally, based on these results, a simple layered joint source-channel coding system is developed with a perfectly symmetric encoder-decoder structure. Its application and performance is discussed in a broadcast setting in which there is a need to control the fidelity experienced by different receivers. Among other results, we show that such systems and their multilayer extensions retain attractive optimality properties in the Gaussian-quadratic case, but not in the binary-Hamming case.

We develop and analyze space-time coded cooperative diversity protocols for combating multipath fading across multiple protocol layers in a wireless network. The protocols exploit spatial diversity available among a collection of distributed terminals that relay messages for one another in such a manner that the destination terminal can average the fading, even though it is unknown a priori which terminals will be involved. In particular, a source initiates transmission to its destination, and many relays potentially receive the transmission. Those terminals that can fully decode the transmission utilize a space-time code to cooperatively relay to the destination. We demonstrate that these protocols achieve full spatial diversity in the number of cooperating terminals, not just the number of decoding relays, and can be used effectively for higher spectral efficiencies than repetition-based schemes. We discuss issues related to space-time code design for these protocols, emphasizing codes that readily allow for appealing distributed versions.

We consider source requantization in two forms - successive degradation (i.e., source fidelity reduction) and bit stealing (i.e., information embedding) when no forward planning has been done to facilitate the requantization. We focus on finite-alphabet sources with arbitrary distortion measures as well as the Gaussian-quadratic scenario. For the successive degradation problem, we show an achievable distortion-rate trade-off for non-hierarchically structured rate-distortion achieving codes, and compare it to the distortion-rate trade-off of successively refinable codes. We further consider source requantization in the form of bit stealing, whereby an information embedder acts on a quantized source, producing an output at the same rate. Building on the successive degradation results, we develop achievable distortion-rate trade-offs. Two cases are considered, corresponding to whether the source decoder is informed of any bit stealing or not. In the latter case, the embedder must produce outputs in the original source codebook. For the Gaussian-quadratic scenario, all trade-offs are within 0.5 bits/sample of the distortion-rate bound. Furthermore, for bit stealing, the use of simple post-reconstruction processing that is only a function of the embedded rate can eliminate the loss experienced by uninformed decoders.

We propose a new low-complexity strategy for approaching the matched filter bound on most practical ISI channels. At the transmitter, a form of channel-independent precoding is introduced to perform frequency-interleaving, which appropriately conditions the channel. At the receiver, a very low-complexity iterated-decision equalizer (Chan, A.M. and Wornell, G.W., IEEE Trans. Commun., vol.49, p.1966-76, 2001) is used. As an illustration, we use the system to attain the matched filter bound effectively on the 1+D channel without the use of error-control coding.

We develop and analyze space-time coded cooperative diversity protocols for combating multipath fading across multiple protocol layers in a wireless network. The protocols exploit spatial diversity available among a collection of distributed terminals that relay messages for one another in such a manner that the destination terminal can average the fading, even though it is unknown a priori which terminals will be involved. In particular, a source initiates transmission to its destination, and many relays potentially receive the transmission. Those terminals that can fully decode the transmission utilize a space-time code to cooperatively relay to the destination. We demonstrate that these protocols achieve full spatial diversity in the number of cooperating terminals, not just the number of decoding relays, and can be used effectively for higher spectral efficiencies than repetition-based schemes. We discuss issues related to space-time code design for these protocols, emphasizing codes that readily allow for appealing distributed versions.

Lattice-reduction (LR) techniques are developed for enhancing the performance of multiple-input multiple-output (MIMO) digital communication systems. When used in conjunction with traditional linear and nonlinear detectors, LR techniques substantially close the gap to fundamental performance limits with little additional system complexity. Results for individual channels and ensembles are developed, and illustrated in detail for the case of small (2 /spl times/ 2), uncoded, coherent systems. For example, we show that, relative to the maximum likelihood bound, LR techniques get us within 3dB for any Gaussian channel, and allow us to achieve the same diversity on the Rayleigh fading channel, when sufficiently large constellations are used.

The use of multiple description (MD) video coding and path diversity has been proposed to provide improved performance over lossy packet networks [1]. The goal of this work was to develop models to accurately and quickly predict and compare the distortion of MD video coding and path diversity against conventional single description (SD) video delivered over a single path. In the process, we developed (1) a model for the loss process of a two-path path diversity system, and (2) a distortion model that maps the loss model to MD distortion values. Given these models we present a number of comparisons between MD video coding and path diversity and conventional SD video over a single path. The proposed model for path diversity may also be useful in other applications not related to MD coding. Furthermore, other forms of MD coding may be analyzed using similar models for MD distortion.

There are numerous contexts in which systems need to buffer multimedia signal content. If such a buffer overflows, signal data are lost in an uncontrolled manner, which can lead to large end-to-end distortions. However, if the queued signals are distortion-tolerant, overflows can be avoided, and significant performance gains realized, by reducing the fidelity of the signals in a gradual, controlled, manner. Based on ideas of successive-approximation source coding, we design an adaptive-buffering algorithm to minimize end-to-end distortion. This algorithm performs nearly as well as a performance bound on all possible algorithms. Perhaps most importantly, the algorithm's performance remains robust across a wide range of (unpredictable) utilization rates (input rate/output rate).

In many multimedia applications, there is a need to authenticate a source that has been subjected to benign degradations in addition to potential tampering attacks. We develop a meaningful formulation of this problem, and identify and interpret the associated information-theoretic performance limits. The associated systems are shown to perform dramatically better than frequently proposed approaches based on information embedding techniques.

A promising class of nonlinear multiuser detector is introduced for CDMA systems. These "iterated-decision" multiuser detectors use optimized multipass algorithms to successively cancel multiple-access interference (MAI) from received data and generate symbol decisions whose reliability increases monotonically with each iteration. They significantly outperform decorrelating detectors and linear minimum mean-square error (MMSE) multiuser detectors, but have the same order of computational complexity. When the ratio of the number of users to the spreading factor is below a certain threshold, iterated-decision multiuser detectors asymptotically achieve the performance of the "optimum" multiuser detector, ie, maximum-likelihood (ML) decoding.

A new and efficient class of nonlinear equalizers is developed for intersymbol interference (ISI) channels. These -"iterated-decision equalizers" use an optimized multipass algorithm to successively cancel ISI from a block of received data and generate symbol decisions whose reliability increases monotonically with each iteration. These equalizers have an effective complexity comparable to the decision-feedback equalizer (DFE), yet asymptotically achieve the performance of maximum-likelihood sequence detection (MLSD). We show that, because their structure allows cancellation of both precursor and postcursor ISI, iterated-decision equalizers outperform the minimum mean-square error DFE by 2.507 dB on severe ISI channels even with uncoded systems. Moreover, unlike the DFE, iterated-decision equalizers can be readily used in conjunction with error-control coding, making them attractive for a wealth of applications.

We consider the problem of embedding one signal (e.g., a digital watermark), within another "host" signal to form a third, "composite" signal. The embedding is designed to achieve efficient tradeoffs among the three conflicting goals of maximizing the information-embedding rate, minimizing the distortion between the host signal and composite signal, and maximizing the robustness of the embedding. We introduce new classes of embedding methods, termed quantization index modulation (QIM) and distortion-compensated QIM (DC-QIM), and develop convenient realizations in the form of what we refer to as dither modulation. Using deterministic models to evaluate digital watermarking methods, we show that QIM is "provably good" against arbitrary bounded and fully informed attacks, which arise in several copyright applications, and in particular it achieves provably better rate distortion-robustness tradeoffs than currently popular spread-spectrum and low-bit(s) modulation methods. Furthermore, we show that for some important classes of probabilistic models, DC-QIM is optimal (capacity-achieving) and regular QIM is near-optimal. These include both additive white Gaussian noise (AWGN) channels, which may be good models for hybrid transmission applications such as digital audio broadcasting, and mean-square-error-constrained attack channels that model private-key watermarking applications.

Signal estimation from a sequential encoding in the form of quantized noisy measurements is considered. As an example context, this problem arises in a number of remote sensing applications, where a central site estimates an information-bearing signal from low-bandwidth digitized information received from remote sensors, and may or may not broadcast feedback information to the sensors. We demonstrate that the use of an appropriately designed and often easily implemented additive control input before signal quantization at the sensor can significantly enhance overall system performance. In particular, we develop efficient estimators in conjunction with optimized random, deterministic, and feedback-based control inputs, resulting in a hierarchy of systems that trade performance for complexity.

A new and efficient class of nonlinear equalizers is introduced for intersymbol interference (ISI) channels. These "iterated-decision equalizers" use an optimized multipass algorithm to successively cancel ISI from a block of received data and generate symbol decisions whose reliability increases monotonically with each iteration. Asymptotically they achieve the performance of maximum-likelihood sequence detection (MLSD), but only have a computational complexity on the order of a linear equalizer (LE). And because their structure allows cancellation of both pre- and post-cursor ISI, iterated-decision equalizers outperform the minimum mean-square error decision-feedback equalizer (DFE) by 2.5 dB on severe ISI channels even with uncoded systems. Even more importantly, unlike the DFE, iterated-decision equalizers can be readily used in conjunction with error-control coding, making them attractive for a wealth of applications.

We develop energy-efficient transmission protocols for wireless networks that exploit spatial diversity created by antenna sharing: coordinated transmission and/or processing by several distributed radios. We focus on single-user transmission and examine several possibilities for the strategy employed by the assisting radio, or relay, including decoding and forwarding as well as amplifying and forwarding. In each case, we develop receivers based upon maximum-likelihood and/or maximum signal-to-noise ratio criteria, relate their structures, and compare their bit-error probability performance by means of analysis and simulations. We cast single-hop and multihop routing into our framework for comparison purposes. All of our antenna sharing protocols offer diversity gains over single-hop and multihop transmission, and our results suggest that low-complexity amplifying and forwarding is energy-efficient in spite of noise amplification at the relay.

A variety of emerging applications require the design of systems for embedding one signal within another signal. We describe a new class of embedding methods called quantization index modulation (QIM) and develop a realization termed coded dither modulation in which the embedded information modulates the dither signal of a dithered quantizer. We also develop a framework in which one can analyze the performance trade-offs among robustness, distortion, and embedding rate, and we show that QIM systems have considerable performance advantages over previously proposed spread-spectrum and low-bit modulation systems.

Several aspects of the design and optimization of coded multiple-antenna transmission diversity methods for slowly time-varying channels are explored from an information-theoretic perspective. Both optimized vector-coded systems, which can achieve the maximum possible performance, and suboptimal scalar-coded systems, which reduce complexity by exploiting suitably designed linear precoding, are investigated. The achievable rates and associated outage characteristics of these spatial diversity schemes are evaluated and compared, both for the case when temporal diversity is being jointly exploited and for the case when it is not. Complexity and implementation issues more generally are also discussed.

The problem of equalization for spread-response precoding systems based on minimum mean-square error (MMSE) estimates of the fading channel coefficients is considered. These systems are attractive, low complexity alternatives to the combination of interleaving and error-control coding for achieving time diversity in fading environments. To make the performance of these systems robust to channel estimation errors, we derive the linear equalizer at the receiver that maximizes the effective signal-to-noise-and-interference ratio (SNIR) subject to uncertainty in the channel measurements. We examine the bit-error rate performance and develop fixed and dynamic solutions to the associated problem of optimal power allocation between the data transmissions and channel measurements. The effectiveness of these algorithms is demonstrated through measurements obtained from an indoor wireless setting.

Low-complexity schemes for digital encoding of a noise-corrupted signal and associated signal estimators are presented. This problem arises in wireless distributed sensor networks where an environmental signal of interest is to be estimated at a central site from low-bandwidth digitized information received from collections of remote sensors. We show that the use of a properly designed and often easily implemented additive control input before signal quantization can significantly enhance overall system performance. In particular, efficient estimators can be constructed and used with optimized pseudo-noise, deterministic, and feedback-based control inputs, resulting in a hierarchy of practical systems with very attractive performance-complexity characteristics.

The 1/f family of fractal processes provides useful models for the extraordinary variety of natural and man-made phenomena that exhibit long-term dependence. Using algorithms based on a multiscale-state-space representation, we address the problems of parameter estimation of discrete 1/f signals in white noise, estimation of deterministic signals in 1/f noise, and prediction of discrete 1/f processes. Among other results, distant past data are shown to have a dramatically greater effect on these estimators than when ARMA processes are involved.

A variety of related applications have emerged that require the design of systems for embedding one signal within another signal. We propose a new class of embedding methods called quantization index modulation (QIM) and develop an example of such a method called dither modulation in which the embedded information modulates the dither signal of a dithered quantizer. We also develop a framework within which one can analyze performance trade-offs among robustness, distortion, and embedding rate, and we show that QIM systems have considerable performance advantages over previously proposed spread-spectrum and low-bit modulation systems.

We derive performance limits for two closely related communication scenarios involving a wireless system with multiple-element transmitter antenna arrays: a point-to-point system with partial side information at the transmitter, and a broadcast system with multiple receivers. In both cases, ideal beamforming is impossible, leading to an inherently lower achievable performance as the quality of the side information degrades or as the number of receivers increases. Expected signal-tonoise ratio (SNR) and mutual information are both considered as performance measures. In the point-to-point case, we determine when the transmission strategy should use some form of beamforming and when it should not. We also show that, when properly chosen, even a small amount of side information can be quite valuable. For the broadcast scenario with an SNR criterion, we find the efficient frontier of operating points and show that even when the number of receivers is larger than the number of antenna array ...

The properties of chaotic dynamical systems make them useful for channel coding in a variety of practical communication applications. To illustrate this, a novel analog code based on tent map dynamics and having a fast decoding algorithm is developed for use on unknown, multiple, and time-varying signal-to-noise ratio (SNR) channels. This code is shown to be an attractive alternative to both digital codes and linear modulation in such scenarios. Several properties and interpretations of the codes are developed, along with some methods for their optimization.

A class of capacity-achieving, low-complexity, high-reliability, variable-rate coding schemes is developed for communication over discrete memoryless channels with noiseless feedback. Algorithms for encoding and decoding that require computations growing linearly with the number of channel inputs used are developed. The error exponent associated with the scheme is shown to be optimal and implies that capacity is achievable. Simulations are performed and support the analytically predicted high performance and low complexity.

The blocking artifacts that arise in the use of traditional vector quantization (VQ) schemes can, in general, be virtually eliminated via an efficient lapped VQ strategy. With lapped VQ, blocks are obtained from the source in an overlapped manner, and reconstructed via superposition of overlapped codevectors. The new scheme, which we term lapped orthogonal vector quantization (LOVQ), requires no increase in bit rate and, in contrast to other proposed approaches, no significant increase in computational complexity or memory requirements. Attractively, the use of LOVQ also leads to a modest increase in coding gain over traditional VQ schemes of comparable complexity.

Using a powerful, recently-developed multiscale representation for fractal point processes, we characterize these processes under fundamental transformations which arise in a variety of important applications such as data network traffic modeling. Distribution results are obtained, including the inter-arrival density for a fractal point process subject to random erasure, the counting process distribution for the superposition of fractal point processes, and the steady-state customer distribution in queues with self-similar customer arrivals. Interpretations and implications of these results for applications are also discussed.

The class of stochastic resonance systems based on M-level quantizer maps is developed. We derive expressions for the output invariant density and autocorrelation function of these maps when they are driven by a square wave in noise. These systems are shown to provide signal-to-noise ratio enhancement and robustness to noise characteristics. These properties render the quantizer maps potentially appealing for a wide range of signal processing applications such as interference suppression and robust communication. A framework for the analysis of more general discrete-time stochastic resonance systems is also presented, which is based on approximating these systems via quantizer maps.

A class of efficient strategies for exploiting transmit antenna diversity on fading channels is developed. These techniques, which we refer to as linear antenna precoding, asymptotically transform a nonselective Rayleigh fading channel into a nonfading, simple white marginally Gaussian noise channel with no intersymbol interference. Linear antenna precoding requires no additional power or bandwidth, and is also attractive in terms of computation, robustness and delay considerations.

Multirate systems and filter banks have traditionally played an important role in source coding and compression for contemporary communication applications, and many of the key design issues in such applications have been extensively explored. We review developments on the comparatively less explored role of multirate filter banks and wavelets in channel coding and modulation for some important classes of channels. Some representative examples of emerging potential applications are described. One involves the use of highly dispersive, broadband multirate systems for wireless multiuser communication (spread spectrum CDMA) in the presence of fading due to time-varying multipath. Another is the wavelet-based diversity strategy referred to as "fractal modulation" for use with unpredictable communication links and in broadcast applications with user-selectable quality of service. A final example involves multitone (multicarrier) modulation systems based on multirate filter banks and fast lapped transforms for use on channels subject to severe intersymbol and narrowband interference. Collectively, these constitute intriguing, interrelated paradigms within an increasingly broad and active area of research.

Interleaving is an important technique for improving the effectiveness of traditional error-correcting codes in data transmission systems that exhibit multipath fading. Such channels often arise in mobile wireless communications. We present an alternative to interleaving for such systems, which we term "spread-response precoding". From the perspective of the coded symbol stream, spread-response precoding effectively transforms an arbitrary Rayleigh fading channel into a nonfading, simple white marginally Gaussian noise channel. Furthermore, spread-response precoding requires no additional power or bandwidth, and is attractive in terms of computational complexity, robustness, and delay considerations.

Signals arising out of nonlinear dynamical systems are compelling models for a wide range of phenomena. We develop several properties of signals obtained from Markov maps, an important family of such systems, and present analytical techniques for computing their statistics. Among other results, we demonstrate that all Markov maps produce signals with rational spectra, and can therefore be viewed as "chaotic ARMA processes". Finally, we demonstrate how Markov maps can approximate to arbitrary precision any of a broad class of chaotic maps and their statistics.

The chaotic sequences corresponding to tent map dynamics are potentially attractive in a range of engineering applications. Optimal estimation algorithms for signal filtering, prediction, and smoothing in the presence of white Gaussian noise are derived for this class of sequences based on the method of maximum likelihood. The resulting algorithms are highly nonlinear but have convenient recursive implementations that are efficient both in terms of computation and storage. Performance evaluations are also included and compared with the associated Cramer-Rao bounds.>

A new class of orthogonal code-division multiple-access (CDMA) systems is developed for efficient multiuser communication in environments subject to multipath fading phenomena. The key characteristic of these new systems, which we refer to as "spread-signature CDMA" systems, is that the associated signature sequences are significantly longer than the interval between symbols. Using this approach, the transmission of each symbol of each user is, in effect, spread over a wide temporal and spectral extent, which is efficiently exploited to combat the effects of fading. These systems generalize and improve on the spread-response precoding systems. Both efficient signature sets and efficient receiver structures for such systems are developed. Several aspects of the performance of the resulting spread-signature CDMA systems are presented, including both the achievable bit-error rate characteristics and the effective capacity of such systems. The results suggest that spread-signature CDMA may be an attractive alternative to conventional CDMA in a variety of application scenarios.>

It is demonstrated that 1/f fractal processes are, in a broad sense, optimally represented in terms of orthonormal wavelet bases. Specifically, via a useful frequency-domain characterization for 1/f processes, the wavelet expansion's role as a Karhunen-Loeve-type expansion for 1/f processes is developed. As an illustration of potential, it is shown that wavelet-based representations naturally lead to highly efficient solutions to some fundamental detection and estimation problems involving 1/f processes.>

Because chaotic signals are potentially useful both in describing physical phenomena and in engineering applications, signal processing algorithms exploiting their unique characteristics are of interest. The authors consider issues pertaining to processing signals in convolutional distortion. Specifically, they discuss the effects of convolutional distortion on two parameters commonly used in the description of chaotic signals-the Lyapunov exponents and the fractal dimension of the attractor. In addition, a blind deconvolution technique based on minimizing a nonlinear prediction error for data generated by one-dimensional chaotic maps is presented.>

Signals generated by chaotic systems represent a potentially rich class of signals both for detecting and characterizing physical phenomena and in synthesizing new classes of signals for communications, remote sensing, and a variety of other signal processing applications. Since classical techniques for signal analysis do not exploit the particular structure of chaotic signals there is both a significant challenge and an opportunity in exploring new classes of algorithms matched to chaotic signals. The authors outline a variety of signal processing issues associated with the analysis and synthesis of chaotic signals. In addition two examples are described in detail, illustrating some possible ways in which the characteristics of chaotic signals and systems can be exploited. One example is a binary signaling scheme using chaotic signals. The second example is the use of synchronized chaotic systems for signal masking and recovery.>

A nonlinear generalization of the family of autoregressive signal models is introduced. This generalization can be viewed as an autoregressive model with state-varying parameters. For such signals, minimum mean-square error prediction can be reformulated as an interpolation problem. A novel interpretation of the signal as a codebook for its own prediction leads to an interpolation strategy resembling a predictive counterpart to vector quantization. The applicability of this model is then demonstrated empirically for a variety of signals.>

A potentially important family of self-similar signals based upon a deterministic scale-invariance characterization is introduced. These signals, which are referred to as 'dy-homogeneous' signals because they generalize the well-known homogeneous functions, have highly convenient representations in terms of orthonormal wavelet bases. In particular, wavelet representations can be exploited to construct orthonormal self-similar bases for these signals. The spectral and fractal characteristics of dy-homogeneous signals make them appealing candidates for use in a number of applications. As one potential example, their use in a communications-based context is considered. Specifically, a strategy for embedding information into a dy-homogeneous waveform on multiple time-scales is developed. This multirate modulation strategy, called fractal modulation, is potentially well-suited for use with noisy channels of simultaneously unknown duration and bandwidth.>

The problem of data transmission over additive Gaussian fractal noise channels is considered. Exploiting an efficient, wavelet-based representation for fractal processes, the problem of coherent detection in Gaussian fractal noise is addressed, from which the optimum receiver for bit-by-bit signaling is obtained. This leads to a multirate modulation strategy that is inherently well-suited for use with the fractal noise channel. Computationally efficient implementations of the transmitter and receiver structures for this system are also developed.>

While so-called 1/f or scaling processes emerge regularly in modeling a wide range of natural phenomena, as yet no entirely satisfactory framework has been described for the analysis of such processes. Orthonormal wavelet bases are used to provide a new construction for nearly 1/f processes from a set of uncorrelated random variables.>

A set of adaptive transform coding schemes is developed that is based on a family of composite block source models for imagery. An iterative maximum-likelihood algorithm is developed for resolving model parameters from training set data. Both unconstrained (adaptive transform, adaptive quantization) and constrained (fixed transform, adaptive quantization) coders are obtained from the image model parameters. The resulting coders give excellent performance in coding test imagery at a variety of bit rates, and they consistently outperform the adaptive transform coders of W.H. Chen and C.H. Smith (1977). For example, a 2-dB improvement over the Chen and Smith scheme is obtained with a constrained coder with 128 classes operating at 0.5 bits/pixel. Computational limitations inhibit the design of unconstrained order with more than approximately 15 classes.>