Clustering single-cell RNA sequence (scRNA-seq) data poses statistical and computational challenges due to their high-dimensionality and data-sparsity, also known as 'dropout' events. Recently, Regularized Auto-Encoder (RAE) based deep neural network models have achieved remarkable success in learning robust low-dimensional representations. The basic idea in RAEs is to learn a non-linear mapping from the high-dimensional data space to a low-dimensional latent space and vice-versa, simultaneously imposing a distributional prior on the latent space, which brings in a regularization effect. This paper argues that RAEs suffer from the infamous problem of bias-variance trade-off in their naive formulation. While a simple AE wita latent regularization results in data over-fitting, a very strong prior leads to under-representation and thus bad clustering. To address the above issues, we propose a modified RAE framework (called the scRAE) for effective clustering of the single-cell RNA sequencing data. scRAE consists of deterministic AE with a flexibly learnable prior generator network, which is jointly trained with the AE. This facilitates scRAE to trade-off better between the bias and variance in the latent space. We demonstrate the efficacy of the proposed method through extensive experimentation on several real-world single-cell Gene expression datasets. The code for our work is available at https://github.com/arnabkmondal/scRAE.

Information-theoretic quantities like entropy and mutual information have found numerous uses in machine learning. It is well known that there is a strong connection between these entropic quantities and submodularity since entropy over a set of random variables is submodular. In this paper, we study combinatorial information measures that generalize independence, (conditional) entropy, (conditional) mutual information, and total correlation defined over sets of (not necessarily random) variables. These measures strictly generalize the corresponding entropic measures since they are all parameterized via submodular functions that themselves strictly generalize entropy. Critically, we show that, unlike entropic mutual information in general, the submodular mutual information is actually submodular in one argument, holding the other fixed, for a large class of submodular functions whose third-order partial derivatives satisfy a non-negativity property. This turns out to include a number of practically useful cases such as the facility location and set-cover functions. We study specific instantiations of the submodular information measures on these, as well as the probabilistic coverage, graph-cut, log-determinants, and saturated coverage functions and see that they all have mathematically intuitive and practically useful expressions. Finally, we also study generalized independence between subsets of datapoints (random variables in the entropic case), and connect the independence characterizations to independence in log-submodular distributions. Regarding applications, we connect the maximization of submodular (conditional) mutual information to problems such as mutual-information-based, query-based, and privacy preserving summarization—and we connect optimizing the multi-set submodular mutual information to clustering and robust partitioning. We perform real world as well as synthetic experiments on various data summarization tasks.

Recently a class of generalized information measures was defined on sets of items parametrized by submodular functions [7]. In this paper, we propose and study various notions of independence between sets with respect to such information measures, and connections thereof. Since entropy can also be used to parametrize such measures, we derive interesting independence properties for the entropy of sets of random variables. We also study the notion of multi-set independence and its properties. Finally, we present optimization algorithms for obtaining a set that is independent of another given set, and also discuss the implications and applications of combinatorial independence.

Generalization error captures the degree to which the output of a learning algorithm overfits the training data. We obtain a family of bounds which generalize the bounds developed by Xu & Raginsky (2017) and Bu, Zou and Veeravalli (2019), under certain assumptions. Our bounds are based on the Rényi analogue of the Donsker-Varadhan representation of Kullback-Leibler divergence. We also obtain bounds on the probability of generalization error which recover the bounds of Esposito, Gastpar and Issa (2020). We also give a multiplicative lower bound on the expected true loss for a 0-1 loss function.

Auto-Encoder (AE) based neural generative frameworks model the joint-distribution between the data and the latent space using an Encoder-Decoder pair, with regularization imposed in terms of a prior over the latent space. Despite their advantages, such as stability in training, efficient inference, the performance of AE based models has not reached the superior standards of the other generative models such as Generative Adversarial Networks (GANs). Motivated by this, we examine the effect of the latent prior on the generation quality of deterministic AE models in this paper. Specifically, we consider the class of Generative AE models with deterministic Encoder-Decoder pair (such as Wasserstein Auto-Encoder (WAE), Adversarial Auto-Encoder (AAE)), and show that having a fixed prior distribution, a priori, oblivious to the dimensionality of the ‘true’ latent space, will lead to the infeasibility of the optimization problem considered. As a remedy to the issue mentioned above, we introduce an additional state space in the form of flexibly learnable latent priors, in the optimization objective of WAE/AAE. Additionally, we employ a latent-space interpolation based smoothing scheme to address the non-smoothness that may arise from highly flexible priors. We show the efficacy of our proposed models, called FlexAE and FlexAE-SR, through several experiments on multiple datasets, and demonstrate that FlexAE-SR is the new state-of-the-art for the AE based generative models in terms of generation quality as measured by several metrics such as Fr\’echet Inception Distance, Precision/Recall score.

Designing channel codes is one of the core research areas for modern communication systems. Canonical channel codes asymptotically achieve near-capacity performance under large block length regime for additive white gaussian noise channels. However, this achieved success does not generalize to many channels. Channels with output feedback, proposed by Shannon, is one of such channels where practical codes have been unknown for several decades.Recently it has been demonstrated that deep learning based code outperforms the state-of-the-art codes for channels with output feedback. While the success is promising and inspiring, there are a few major challenges that need to be addressed. Firstly, the channel assumes a feedback with a unit step delay, which is not very practical. Second is the lack of generalization to larger block lengths. In this work, we propose Feedback Auto Turbo Encoder (FTAE) which harmoniously combines interleaver and iterative decoding with CNN architectures and demonstrate the blocklength gain and improved performance in the block feedback setting.

Estimation of information theoretic quantities such as mutual information and its conditional variant has drawn interest in recent times owing to their multifaceted applications. Newly proposed neural estimators for these quantities have overcome severe drawbacks of classical $k$NN-based estimators in high dimensions. In this work, we focus on conditional mutual information (CMI) estimation by utilizing its formulation as a \textit{minmax} optimization problem. Such a formulation leads to a joint training procedure similar to that of generative adversarial networks. We find that our proposed estimator provides better estimates than the existing approaches on a variety of simulated datasets comprising linear and non-linear relations between variables. As an application of CMI estimation, we deploy our estimator for conditional independence (CI) testing on real data and obtain better results than state-of-the-art CI testers.

The field of neural generative models is dominated by the highly successful Generative Adversarial Networks (GANs) despite their challenges, such as training instability and mode collapse. Auto-Encoders (AE) with regularized latent space provide an alternative framework for generative models, albeit their performance levels have not reached that of GANs. In this work, we hypothesise that the dimensionality of the AE model’s latent space has a critical effect on the quality of generated data. Under the assumption that nature generates data by sampling from a “true" generative latent space followed by a deterministic function, we show that the optimal performance is obtained when the dimensionality of the latent space of the AE-model matches with that of the “true" generative latent space. Further, we propose an algorithm called the Mask Adversarial Auto-Encoder (MaskAAE), in which the dimensionality of the latent space of an adversarial auto encoder is brought closer to that of the “true" generative latent space, via a procedure to mask the spurious latent dimensions. We demonstrate through experiments on synthetic and several real-world datasets that the proposed formulation yields betterment in the generation quality.

Generative Adversarial networks (GANs) have obtained remarkable success in many unsupervised learning tasks and unarguably, clustering is an important unsupervised learning problem. While one can potentially exploit the latent-space back-projection in GANs to cluster, we demonstrate that the cluster structure is not retained in the GAN latent space. In this paper, we propose ClusterGAN as a new mechanism for clustering using GANs. By sampling latent variables from a mixture of one-hot encoded variables and continuous latent variables, coupled with an inverse network (which projects the data to the latent space) trained jointly with a clustering specific loss, we are able to achieve clustering in the latent space. Our results show a remarkable phenomenon that GANs can preserve latent space interpolation across categories, even though the discriminator is never exposed to such vectors. We compare our results with various clustering baselines and demonstrate superior performance on both synthetic and real datasets.

Designing channel codes under low latency constraints is one of the most demanding requirements in 5G standards. However, sharp characterizations of the performances of traditional codes are only available in the large block lengths limit. Code designs are guided by those asymptotic analyses and require large block lengths and long latency to achieve the desired error rate. Furthermore, when the codes designed for one channel (e.g. Additive White Gaussian Noise (AWGN) channel) are used for another (e.g. non-AWGN channels), heuristics are necessary to achieve any non trivial performance - thereby severely lacking in robustness as well as adaptivity. Obtained by jointly designing recurrent neural network (RNN) based encoder and decoder, we propose an end-to-end learned neural code which outperforms canonical convolutional code under block settings. With this gained experience of designing a novel neural block code, we propose a new class of codes under low latency constraint - Low-latency Efficient Adaptive Robust Neural (LEARN) codes, which outperform the state-of-the-art low latency codes as well as exhibit robustness and adaptivity properties. LEARN codes show the potential of designing new versatile and universal codes for future communications via tools of modern deep learning coupled with communication engineering insights.

Designing codes that combat the noise in a communication medium has remained a significant area of research in information theory as well as wireless communications. Asymptotically optimal channel codes have been developed by mathematicians for communicating under canonical models after over 60 years of research. On the other hand, in many non-canonical channel settings, optimal codes do not exist and the codes designed for canonical models are adapted via heuristics to these channels and are thus not guaranteed to be optimal. In this work, we make significant progress on this problem by designing a fully end-to-end jointly trained neural encoder and decoder, namely, Turbo Autoencoder (TurboAE), with the following contributions: (a) under moderate block lengths, TurboAE approaches state-of-the-art performance under canonical channels; (b) moreover, TurboAE outperforms the state-of-the-art codes under non-canonical settings in terms of reliability. TurboAE shows that the development of channel coding design can be automated via deep learning, with near-optimal performance.

Information theoretic quantities play an important role in various settings in machine learning, including causality testing, structure inference in graphical models, time-series problems, feature selection as well as in providing privacy guarantees. A key quantity of interest is the mutual information and generalizations thereof, including conditional mutual information, multivariate mutual information, total correlation and directed information. While the aforementioned information quantities are well defined in arbitrary probability spaces, existing estimators employ a $\Sigma H$ method, which can only work in purely discrete space or purely continuous case since entropy (or differential entropy) is well defined only in that regime. In this paper, we define a general graph divergence measure ($\mathbb{GDM}$), generalizing the aforementioned information measures and we construct a novel estimator via a coupling trick that directly estimates these multivariate information measures using the Radon-Nikodym derivative. These estimators are proven to be consistent in a general setting which includes several cases where the existing estimators fail, thus providing the only known estimators for the following settings: (1) the data has some discrete and some continuous valued components (2) some (or all) of the components themselves are discrete-continuous \textit{mixtures} (3) the data is real-valued but does not have a joint density on the entire space, rather is supported on a low-dimensional manifold. We show that our proposed estimators significantly outperform known estimators on synthetic and real datasets.

We study the problem of communicating a distributed correlated memoryless source over a memoryless network, from source nodes to destination nodes, under quadratic distortion constraints. We establish the following two complementary results: 1) for an arbitrary memoryless network, among all distributed memoryless sources of a given correlation, Gaussian sources are least compressible, that is, they admit the smallest set of achievable distortion tuples and 2) for any memoryless source to be communicated over a memoryless additive-noise network, among all noise processes of a given correlation, Gaussian noise admits the smallest achievable set of distortion tuples. We establish these results constructively by showing how schemes for the corresponding Gaussian problems can be applied to achieve similar performance for (source or noise) distributions that are not necessarily Gaussian but have the same covariance.

The problem of optimal actuation for channel and source coding was recently formulated and solved in a number of relevant scenarios. In this class of models, actions are taken at encoders or decoders, either to acquire side information in an efficient way or to control or probe effectively the channel state. In this paper, the problem of embedding information on the actions is studied for both the source and the channel coding setups. In both cases, a decoder is present that observes only a function of the actions taken by an encoder or a decoder of an action-dependent point-to-point link. For the source coding model, this decoder wishes to reconstruct a lossy version of the source being transmitted over the point-to-point link, while for the channel coding problem, the decoder wishes to retrieve a portion of the message conveyed over the link. For the problem of source coding with actions taken at the decoder, a single letter characterization of the set of all achievable tuples of rate, distortions at the two decoders, and action cost is derived, under the assumption that the mentioned decoder observes a function of the actions noncausally, strictly causally or causally. A special case of the problem in which the actions are taken by the encoder is also solved. A single-letter characterization of the achievable capacity-cost region is then obtained for the channel coding setup with actions. Examples are provided that shed light into the effect of information embedding on the actions for the action-dependent source and channel coding problems.

We study communication over finite state channels (FSCs), where the encoder and the decoder can control the availability or the quality of noise-free feedback, which is fed back from the decoder to the encoder. Specifically, the instantaneous feedback is a function of an action taken by the encoder, an action taken by the decoder, and the channel output. Encoder and decoder actions take values from finite alphabet sets and may be subject to average cost constraints. We prove capacity results for such a setting by constructing a sequence of codes, using a simple scheme based on code tree, which generates channel input symbols along with encoder and decoder actions. We prove that the limit of this sequence exists, and provide an upper bound on the maximum achievable rate. Our upper and lower bounds coincide and hence yield the capacity for the case where the probability of initial state is positive for all states. Next, the capacity is given for indecomposable channels without intersymbol interference as the limit of normalized directed information between the input and output sequences, maximized over an appropriate set of causally conditioned distributions. As a special case of our framework, we characterize the capacity of coding on the backward link in FSCs, i.e., when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link. Finally, we propose an extension of the Blahut-Arimoto algorithm for evaluating the capacity when actions can be cost constrained and demonstrate its application in a few examples. Among these examples are those of to feed or not to feedback where the encoder takes binary actions that determine whether the current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back.

We consider finite state channels, where the state of the channel is its previous output. We refer to these as Previous Output is the STate (POST) channels. We first focus on POST(α) channels. These channels have binary inputs and outputs, where the state determines if the channel behaves as a Z or an S channel, both with parameter α. We show that the nonfeedback capacity of the POST(α) channel equals its feedback capacity, despite the memory of the channel. The proof of this surprising result is based on showing that the induced output distribution, when maximizing the directed information in the presence of feedback, can also be achieved by an input distribution that does not utilize the feedback. We show that this is a sufficient condition for the feedback capacity to equal the nonfeedback capacity for any finite state channel. We show that the result carries over from the POST(α) channel to a binary POST channel, where the previous output determines whether the current channel will be binary with parameters (a, b) or (b, a). Finally, we show that, in general, feedback may increase the capacity of a POST channel.

The problem of optimal actuation for channel and source coding was recently formulated and solved in a number of relevant scenarios. In this class of models, actions are taken either to acquire side information in an efficient way for source coding, or to control or probe effectively the channel state for channel coding. In this paper, the problem of embedding information on the actions is introduced by considering the presence of an additional decoder that observes only a function of the actions. For the source coding model, this decoder wishes to reconstruct a lossy version of the source being transmitted over the point-to-point link, while, for the channel coding problem, the decoder wishes to retrieve a portion of the message conveyed over the link. In both cases, single-letter performance characterizations are provided for various special cases, along with specific examples.

We consider finite state channels where the state of the channel is its previous output. We refer to such channels as POST (Previous Output is the STate) channels. Our focus is on a simple binary POST channel, with binary inputs and outputs where the state determines if the channel behaves as a Z or an S channel (of equal capacities). We show that the non feedback capacity equals the feedback capacity, despite the memory in the channel. The proof of this surprising result is based on showing that the induced output distribution, when maximizing the directed information in the presence of feedback, can also be achieved by an input distribution that is ignorant of the feedback. Indeed, we show that this is a necessary and sufficient condition for the feedback capacity to equal the non feedback capacity for any finite state channel.

We consider the problem of communicating a distributed correlated memoryless source over a memoryless network, from source nodes to destination nodes, under quadratic distortion constraints. We show the following two complementary results: (a) for an arbitrary memoryless network, among all distributed memoryless sources with a particular correlation, Gaussian sources are the worst compressible, that is, they admit the smallest set of achievable distortion tuples, and (b) for any arbitrarily distributed memoryless source to be communicated over a memoryless additive noise network, among all noise processes with a fixed correlation, Gaussian noise admits the smallest achievable set of distortion tuples. In each case, given a coding scheme for the corresponding Gaussian problem, we provide a technique for the construction of a new coding scheme that achieves the same distortion at the destination nodes in a non-Gaussian scenario with the same correlation structure.

Summary form only given. Among other extremal properties, Gaussian sources are hardest to compress and communicate over. We review the main results of and exhibiting the generality in which such extremal properties hold in compression, communication and coding over networks. These properties are established via operational arguments, bypassing elusive characterizations of fundamental performance limits: schemes tailored for the Gaussian case are harnessed for constructions of schemes that provably do essentially as well under any other source of the same covariance. The talk will highlight the main ideas behind these constructions and how the results, which were established for memoryless sources and channels, carry over to the presence of memory.

BACKGROUND: Next Generation Sequencing technologies have revolutionized many fields in biology by reducing the time and cost required for sequencing. As a result, large amounts of sequencing data are being generated. A typical sequencing data file may occupy tens or even hundreds of gigabytes of disk space, prohibitively large for many users. This data consists of both the nucleotide sequences and per-base quality scores that indicate the level of confidence in the readout of these sequences. Quality scores account for about half of the required disk space in the commonly used FASTQ format (before compression), and therefore the compression of the quality scores can significantly reduce storage requirements and speed up analysis and transmission of sequencing data. RESULTS: In this paper, we present a new scheme for the lossy compression of the quality scores, to address the problem of storage. Our framework allows the user to specify the rate (bits per quality score) prior to compression, independent of the data to be compressed. Our algorithm can work at any rate, unlike other lossy compression algorithms. We envisage our algorithm as being part of a more general compression scheme that works with the entire FASTQ file. Numerical experiments show that we can achieve a better mean squared error (MSE) for small rates (bits per quality score) than other lossy compression schemes. For the organism PhiX, whose assembled genome is known and assumed to be correct, we show that it is possible to achieve a significant reduction in size with little compromise in performance on downstream applications (e.g., alignment). CONCLUSIONS: QualComp is an open source software package, written in C and freely available for download at https://sourceforge.net/projects/qualcomp.

In this paper, we consider a multiple-access channel (MAC) with partial cribbing encoders. This means that each of the two encoders obtains a deterministic function of the output of the other encoder with or without delay. The partial cribbing scheme is especially motivated by the additive noise Gaussian MAC, where perfect cribbing results in the degenerated case of full cooperation between the encoders and requires an infinite entropy link. We derive a single-letter characterization of the capacity of the MAC with partial cribbing for the cases of causal and strictly causal cribbing. Several numerical examples, such as those of quantized cribbing, are presented. We further consider and derive the capacity region where the cribbing depends on actions that are functions of the previous cribbed observations. In particular, we consider a scenario where the action is taken to decide “to crib or not to crib” and show that a naive time-sharing strategy is not optimal.

We study cooperation in multiterminal source coding models involving successive refinement. Specifically, we study the case of a single encoder and two decoders, where the encoder provides a common description to both the decoders and a private description to only one of the decoders. The decoders cooperate via cribbing, i.e., the decoder with access only to the common description is allowed to observe, in addition, a deterministic function of the reconstruction symbols produced by the other. We characterize the fundamental performance limits in the respective settings of noncausal, strictly causal, and causal cribbing. We use a coding scheme, referred to as Forward Encoding and Block Markov Decoding, which builds on one recently used by Cuff and Zhao for coordination via implicit communication. Finally, we use the insight gained to introduce and solve some dual-channel coding scenarios involving multiple-access channels with cribbing.

A real-time coding system with lookahead consists of a memoryless source, a memoryless channel, an encoder, which encodes the source symbols sequentially with knowledge of future source symbols up to a fixed finite lookahead$d$, with or without feedback of the past channel output symbols and a decoder, which sequentially constructs the source symbols using the channel output. The objective is to minimize the expected per-symbol distortion. For a fixed finite lookahead$d\geq 1$, we invoke the theory of controlled Markov chains to obtain an average cost optimality equation (ACOE), the solution of which, denoted by$D(d)$, is the minimum expected per-symbol distortion. With increasing$d$,$D(d)$bridges the gap between causal encoding,$d=0$, where symbol-by-symbol encoding–decoding is optimal and the infinite lookahead case,$d=\infty$, where Shannon Theoretic arguments show that separation is optimal. We extend the analysis to a system with finite-state decoders, with or without noise-free feedback. For a Bernoulli source and binary symmetric channel, under Hamming loss, we compute the optimal distortion for various source and channel parameters, and thus obtain computable bounds on$D(d)$. We also identify regions of source and channel parameters where symbol-by-symbol encoding–decoding is suboptimal. Finally, we demonstrate the wide applicability of our approach by applying it in additional coding scenarios, such as the case where the sequential decoder can take cost-constrained actions affecting the quality or availability of side information about the source.

We consider multiterminal source coding with a single encoder and multiple decoders where either the encoder or the decoders can take cost-constrained actions which affect the quality of the side information present at the decoders. For the scenario where decoders take actions, we characterize the rate-cost tradeoff region for lossless source coding, and give an achievability scheme for lossy source coding for two decoders which is optimum for a variety of special cases of interest. For the case where the encoder takes actions, we characterize the rate-cost tradeoff for a class of lossless source coding scenarios with multiple decoders. Finally, we also consider extensions to other multiterminal source coding settings with actions, and characterize the rate-distortion-cost tradeoff for a case of successive refinement with actions.

We study cooperation in multi terminal source coding models involving successive refinement. Specifically, we study the case of a single encoder and two decoders, where the encoder provides a common description to both the decoders and a private description to only one of the decoders. The decoders cooperate via cribbing, i.e., the decoder with access only to the common description is allowed to observe, in addition, a deterministic function of the reconstruction symbols produced by the other. We characterize the fundamental performance limits in the respective settings of non-causal, strictly-causal and causal cribbing. We use a new coding scheme, referred to as Forward Encoding and Block Markov Decoding, which is a variant of one recently used by Cuff and Zhao for coordination via implicit communication. Finally, we use the insight gained to introduce and solve some dual channel coding scenarios involving Multiple Access Channels with cribbing.

We consider the k-encoder source coding problem with a quadratic distortion measure. We show that among all source distributions with a given covariance matrix K, the jointly Gaussian source requires the highest rates in order to meet a given set of distortion constraints.

In this paper we consider the multiple access channel (MAC) with partial cribbing encoders which means that each encoder obtains a deterministic function of the other encoder output, possibly with delay. The partial cribbing is especially motivated by the additive noise Gaussian MAC since perfect cribbing results in the degenerated case of full cooperation between the encoders and requires an infinite entropy link. We derive a single letter characterization of the capacity of MAC with partial cribbing for the cases of causal and strictly causal partial cribbing. Several numerical examples such as quantized cribbing are presented.We further consider and derive the capacity region where the cribbing depends on actions that are function of the previous cribbed observations. In particular, we consider a scenario where the action is “to crib or not to crib” and show that a naive time-sharing strategy is not optimal.

We establish results assessing the fundamental limits on reliable communication over Finite State Channels (FSCs), when the encoder and the decoder can control the availability or the quality of the feedback. The instantaneous feedback is a function of a cost constrained action taken by the encoder, a cost constrained action taken by the decoder, and the channel output. Achievability is through construction of a sequence of convergent achievable rates, using a simple scheme based on `code tree' generation, that generates channel input symbols along with encoder and decoder actions. For a given block length N, we give an upper bound on the maximum achievable rate. For stationary indecomposable channels without intersymbol interference (ISI), the capacity is given as the limit of normalized directed information between the input and output sequence, maximized over an appropriate set of causally conditioned distributions. As important special cases, we characterize (a) the framework of `to feed or not to feed back' where either the encoder or the decoder takes binary actions to determine whether current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back, (b) the capacity of `coding on the backward link' in FSCs, i.e., when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link.

We consider multi-terminal source coding with a single encoder and multiple decoders where either the encoder or the decoders can take actions which affect the quality or availability of the side information present at the decoders, subjected to an additional cost constraint on the actions taken. For the scenario where a joint action is taken at the decoders, we characterize the rate-cost trade-off region for lossless source coding, and give an achievability scheme for lossy source coding for two decoders which is optimum for several special cases. For the case where the encoder takes actions, we characterize the rate-cost trade-off for a class of lossless source coding scenarios with multiple decoders.

We consider the problem of optimal probing of states of a channel by transmitter and receiver for maximizing rate of reliable communication. The channel is discrete memoryless (DMC) with i.i.d. states. The encoder takes probing actions dependent on the message. It then uses the state information obtained from probing causally or noncausally to generate channel input symbols. The decoder may also take channel probing actions as a function of the observed channel output and use the channel state information thus acquired, along with the channel output, to estimate the message. We refer to the maximum achievable rate for reliable communication for such systems as the “Probing Capacity”. We characterize this capacity when the encoder and decoder actions are cost constrained. To motivate the problem, we begin by characterizing the trade-off between the capacity and fraction of channel states the encoder is allowed to observe, while the decoder is aware of channel states. In this setting of `to observe or not to observe' state at the encoder, we compute certain numerical examples which exhibit a pleasing phenomenon, where encoder can observe a relatively small fraction of states and yet communicate at maximum rate, i.e., rate when observing states at encoder is not cost constrained.

Consider a wireless system where a transmitter may send data to a set of receivers, or on various channels, experiencing random time-varying fading. The transmitter can send data to a single receiver or on a single channel at a time and may adapt its transmission power to the radio conditions of the chosen receiver/channel. Its objective is to implement a strategy defining at each time how to select the receiver/channel and transmission power, so as to maximize its throughput, i.e., its average sending rate, under an average power constraint. The optimization problem is easy when the fading conditions of all the receivers/channels are known. In many situations however, the instantaneous fading conditions are not known a priori, instead they have to be acquired, i.e., receivers/channels have to be probed, which consumes resources (time, spectrum, energy) in proportion of the number of probed receivers/channels. Hence, the transmitter may choose not to acquire the radio conditions of all the receivers/channels so as to spare resources for actual transmissions. In this paper, we aim at characterizing a joint probing, receiver/channel selection and power control strategy maximizing throughput. We provide an adaptive algorithm converging to the throughput optimal strategy. This algorithm may be used in a wide class of wireless systems with limited information, such as broadcast systems without a priori knowledge of the instantaneous Channel-State Information (CSI). But it can be also used to solve dynamic spectrum access problems such as those arising in cognitive radio systems, where secondary users can access large parts of the spectrum, but have to discover which portions of the spectrum offer more favorable radio conditions or less interference from primary users.

Opportunistic scheduling is a key mechanism for improving the performance of wireless systems. However, this mechanism requires that transmitters are aware of channel conditions (or CSI, Channel State Information) to the various possible receivers. CSI is not automatically available at the transmitters, rather it has to be acquired. Acquiring CSI consumes resources, and only the remaining resources can be used for actual data transmissions. We explore the resulting trade-off between acquiring CSI and exploiting channel diversity to the various receivers. Specifically, we consider a system consisting of a transmitter and a fixed number of receivers/users. An infinite buffer is associated to each receiver, and packets arrive in this buffer according to some stochastic process with fixed intensity. We study the impact of limited channel information on the stability of the system. We characterize its stability region, and show that an adaptive queue length-based policy can achieve stability whenever doing so is possible. We formulate a Markov Decision Process problem to characterize this queue length-based policy. In certain specific and yet relevant cases, we explicitly compute the optimal policy. In general case, we provide a scheduling policy that achieves a fixed fraction of the system's stability region. Scheduling with limited information is a problem that naturally arises in cognitive radio systems, and our results can be used in these systems.