Understanding dynamic relationships between random processes is important in many applications, such as neuroscience. The interactive relationship between multiple recorded neural processes is a challenge to discover, particularly when the delays in these interactions are dynamic. Although informationtheoretic measures such as directed information have been adopted to understand propagation delays in neuroscience applications, they are insufficient to capture time-varying delays. We introduce a sample path causal measure to help infer the directed delay between two random processes that considers the relative entropy between two predictors, dynamically changing as needed, where one has more (delayed) information than another. We develop a procedure to determine dynamic delays by identifying phase transitions in these relative entropies as a function of delay order and time. We apply this procedure to a simulated constant delay case and a time-varying delay case using a sequential probability approach to dynamically track the evolving statistics. We demonstrate with simulations how the method identifies the delay in both the constant and dynamic situations.

We introduce the exponential server timing broadcast channel (ESTBC), where one sequence of packet timings is controlled and sent through two parallel exponential server timing channels (ESTCs) of different service rates. We use a discrete-time representation of the ESTC using a Z-channel and subsequently show degradedness of the ESTC. We also provide an achievable rate region for the ESTBC and show that it dominates the time-sharing region.

Surveillance for genetic variation of microbial pathogens, both within and among species, plays an important role in informing research, diagnostic, prevention, and treatment activities for disease control. However, large-scale systematic screening for novel genotypes remains challenging in part due to technological limitations. Towards addressing this challenge, we present an advancement in universal microbial high resolution melting (HRM) analysis that is capable of accomplishing both known genotype identification and novel genotype detection. Specifically, this novel surveillance functionality is achieved through time-series modeling of sequence-defined HRM curves, which is uniquely enabled by the large-scale melt curve datasets generated using our high-throughput digital HRM platform. Taking the detection of bacterial genotypes as a model application, we demonstrate that our algorithms accomplish an overall classification accuracy over 99.7% and perform novelty detection with a sensitivity of 0.96, specificity of 0.96 and Youden index of 0.92. Since HRM-based DNA profiling is an inexpensive and rapid technique, our results add support for the feasibility of its use in surveillance applications.

Heartbeat dynamics have been long studied in understanding the cardiovascular and autonomic nervous systems. Traditional methods use windowed time averaging in order to analyze heartbeat data and are unable to capture the fine temporal nature of heartbeat dynamics. In 2005, Barbieri et al., revolutionized the field by introducing a history-dependent Inverse Gaussian (IG) point process model of heartbeat dynamics, which allows for analysis of such data in continuous time. However, one limitation of this approach is that the maximum likelihood estimation problem is non-convex. This thus requires judicious selection of initial conditions for model fitting and leads to longer runtimes. In this paper, we propose a convex formulation of the point process heartbeat dynamics model utilizing a history-dependent Gamma generalized linear model. Using a dataset of human interbeat intervals, we show that this model uniformly outperforms the IG formulation in runtime, and has comparable goodness of fit, as assessed by the Kolmogorov-Smirnov (KS) distance.

MOTIVATION: The need to rapidly screen complex samples for a wide range of nucleic acid targets, like infectious diseases, remains unmet. Digital High-Resolution Melt (dHRM) is an emerging technology with potential to meet this need by accomplishing broad-based, rapid nucleic acid sequence identification. Here, we set out to develop a computational framework for estimating the resolving power of dHRM technology for defined sequence profiling tasks. By deriving noise models from experimentally generated dHRM datasets and applying these to in silico predicted melt curves, we enable the production of synthetic dHRM datasets that faithfully recapitulate real-world variations arising from sample and machine variables. We then use these datasets to identify the most challenging melt curve classification tasks likely to arise for a given application and test the performance of benchmark classifiers. RESULTS: This toolbox enables the in silico design and testing of broad-based dHRM screening assays and the selection of optimal classifiers. For an example application of screening common human bacterial pathogens, we show that human pathogens having the most similar sequences and melt curves are still reliably identifiable in the presence of experimental noise. Further, we find that ensemble methods outperform whole series classifiers for this task and are in some cases able to resolve melt curves with single-nucleotide resolution. AVAILABILITY AND IMPLEMENTATION: Data and code available on https://github.com/lenlan/dHRM-noise-modeling. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We present a sample path dependent measure of causal influence between time series. The proposed causal measure is a random sequence, a realization of which enables identification of specific patterns that give rise to high levels of causal influence. We show that these patterns cannot be identified by existing measures such as directed information (DI). We demonstrate how sequential prediction theory may be leveraged to estimate the proposed causal measure and introduce a notion of regret for assessing the performance of such estimators. We prove a finite sample bound on this regret that is determined by the worst case regret of the sequential predictors used in the estimator. Justification for the proposed measure is provided through a series of examples, simulations, and application to stock market data. Within the context of estimating DI, we show that, because joint Markovicity of a pair of processes does not imply the marginal Markovicity of individual processes, commonly used plug-in estimators of DI will be biased for a large subset of jointly Markov processes. We introduce a notion of DI with “stale history”, which can be combined with a plug-in estimator to upper and lower bound the DI when marginal Markovicity does not hold.

When estimating the directed information between two jointly stationary Markov processes, it is typically assumed that the recipient of the directed information is itself Markov of the same order as the joint process. While this assumption is often made explicit in the presentation of such estimators, a characterization of when we can expect the assumption to hold is lacking. Using the concept of d-separation from Bayesian networks, we present sufficient conditions for which this assumption holds. We further show that the set of parameters for which these conditions are not also necessary has Lebesgue measure zero. Given the strictness of these conditions, we introduce a notion of partial directed information, which can be used to bound the bias of directed information estimates when the directed information recipient is not itself Markov. Lastly we estimate this bound on simulations in a variety of settings to assess the extent to which the bias should be cause for concern.

The need to reason about uncertainty in large, complex, and multimodal data sets has become increasingly common across modern scientific environments. The ability to transform samples from one distribution [Formula: see text] to another distribution [Formula: see text] enables the solution to many problems in machine learning (e.g., Bayesian inference, generative modeling) and has been actively pursued from theoretical, computational, and application perspectives across the fields of information theory, computer science, and biology. Performing such transformations in general still leads to computational difficulties, especially in high dimensions. Here, we consider the problem of computing such “measure transport maps” with efficient and parallelizable methods. Under the mild assumptions that [Formula: see text] need not be known but can be sampled from and that the density of [Formula: see text] is known up to a proportionality constant, and that [Formula: see text] is log-concave, we provide in this work a convex optimization problem pertaining to relative entropy minimization. We show how an empirical minimization formulation and polynomial chaos map parameterization can allow for learning a transport map between [Formula: see text] and [Formula: see text] with distributed and scalable methods. We also leverage findings from nonequilibrium thermodynamics to represent the transport map as a composition of simpler maps, each of which is learned sequentially with a transport cost regularized version of the aforementioned problem formulation. We provide examples of our framework within the context of Bayesian inference for the Boston housing data set and generative modeling for handwritten digit images from the MNIST data set.

We present a sample path dependent measure of causal influence between two time series. The proposed measure is a random variable whose expected sum is the directed information. A realization of the proposed measure may be used to identify the specific patterns in the data that yield a greater flow of information from one process to another, even in stationary processes. We demonstrate how sequential prediction theory may be leveraged to obtain accurate estimates of the causal measure at each point in time and introduce a notion of regret for assessing the performance of estimators of the measure. We prove a finite sample bound on this regret that is determined by the regret of the sequential predictors used in obtaining the estimate. We estimate the causal measure for a simulated collection of binary Markov processes using a Bayesian updating approach. Finally, given that the measure is a function of time, we demonstrate how estimators of the causal measure may be extended to effectively capture causality in time-varying scenarios.

The Posterior Matching (PM) scheme is a mutual information maximizing scheme for efficiently communicating a message point in a continuum over a noisy channel with causal feedback. It was originally developed when the message point was on a subset of the real line, and we more recently generalized the framework to arbitrary dimensions with optimal transport theory. Here, we consider a class of encoder dynamical systems constructed with optimal transport and show that the ergodicity of the aforementioned state variable is a necessary and sufficient condition for posterior matching to be reliable. Lastly, we show a surprising “all or nothing” result: this same ergodicity condition is necessary and sufficient to achieve capacity.

We consider a general framework for a human-computer interface whereby the human's knowledge is represented as a point in Euclidean space, the intention of the human is signaled to the computer over a noisy channel, and the computer queries the human in a manner that is amenable to human operation. With these constraints at hand, we demonstrate a class of systems that are nonetheless information-theoretically optimal in that the computer very rapidly hones in on the intent of the human. Much recent work on feedback information theory has been dedicated to the exploration of methods by which optimal feedback may be derived for the purpose of expediting the communication of a message point between an inanimate encoder and decoder. Our framework not only takes advantage of previous work to demonstrate its communication optimality from this perspective as well as from an information-theoretic perspective but also contributes two distinct advantages. First, our framework provides a simplified method based on optimal transport theory to generate optimal feedback signals between the computer and human in high dimension, while still preserving communication optimality. Second, our framework specifically lends itself to the integration of a human user by attempting to moderate the difficulty of the task presented to the user, while still preserving optimality. We demonstrate applications of our framework within the context of multi-agent brain-computer interfaces.

We propose an approach for learning latent directed polytrees as long as there exists an appropriately defined discrepancy measure between the observed nodes. Specifically, we use our approach for learning directed information polytrees where samples are available from only a subset of processes. Directed information trees are a new type of probabilistic graphical models that represent the causal dynamics among a set of random processes in a stochastic system. We prove that the approach is consistent for learning minimal latent directed trees. We analyze the sample complexity of the learning task when the empirical estimator of mutual information is used as the discrepancy measure.

In this paper, we consider state space modeling for sequential continuous estimation. We consider the one-step prediction update, which transforms our previous belief state (posterior distribution of the previous state) to new belief state (posterior distribution of the current state). We demonstrate a recursive algorithm for updating the latent state at every time by avoiding intractable integral or Gaussian approximation. The construction of the desired map is pursued through the optimal transportation theory, and we demonstrate that for the large class of log-concave state transition functions, the one-step prediction problem for continuous hidden variable is solvable through convex optimization.

We present a framework to transform a sample from one continuous distribution P to another ℚ. Our previous work considered the special case of Bayesian inference where P is the prior and ℚ is the posterior, showing that this can be solved with convex optimization under appropriate conditions. Here, our contribution is two fold: (i) we consider the more general case of arbitrary P and ℚ and show using optimal transport theory and KL divergence minimization that convexity holds provided that ℚ has a log-concave density; (ii) we develop a largescale distributed solver. With this general framework finding the optimal Bayesian map is done through a series of MAP estimation problems. Interesting applications are also presented.

We propose a graphical model for representing networks of stochastic processes, the minimal generative model graph. It is based on reduced factorizations of the joint distribution over time. We show that under appropriate conditions, it is unique and consistent with another type of graphical model, the directed information graph, which is based on a generalization of Granger causality. We demonstrate how directed information quantifies Granger causality in a particular sequential prediction setting. We also develop efficient methods to estimate the topological structure from data that obviate estimating the joint statistics. One algorithm assumes upper bounds on the degrees and uses the minimal dimension statistics necessary. In the event that the upper bounds are not valid, the resulting graph is nonetheless an optimal approximation in terms of Kullback-Leibler (KL) divergence. Another algorithm uses near-minimal dimension statistics when no bounds are known, but the distribution satisfies a certain criterion. Analogous to how structure learning algorithms for undirected graphical models use mutual information estimates, these algorithms use directed information estimates. We characterize the sample-complexity of two plug-in directed information estimators and obtain confidence intervals. For the setting when point estimates are unreliable, we propose an algorithm that uses confidence intervals to identify the best approximation that is robust to estimation error. Last, we demonstrate the effectiveness of the proposed algorithms through the analysis of both synthetic data and real data from the Twitter network. In the latter case, we identify which news sources influence users in the network by merely analyzing tweet times.

The posterior matching (PM) scheme is a mutual information maximizing scheme for efficiently communicating a message point in a continuum over a noisy channel with feedback. It was recently developed when the message point was on a subset of the real line, and we more recently have generalized the framework to arbitrary dimensions with the theory of optimal transport. Although the PM scheme is guaranteed to maximize mutual information, in some situations it is not reliable (e.g. the posterior distribution does not converge to a point mass). Here, we show that the PM scheme is reliable if and only if the nonlinear filter of a certain hidden Markov model achieves maximal accuracy. We show that ergodicity of a random process pertaining to the channel input process is necessary for PM reliability. Lastly, we show that joint ergodicity of random processes pertaining to inputs and outputs of the channel is a sufficient condition for reliability. The latter results leverages optimal transport properties (invertibility) of the encoder map.

Modern neuroscientific recording technologies are increasingly generating rich, multimodal data that provide unique opportunities to investigate the intricacies of brain function. However, our ability to exploit the dynamic, interactive interplay among neural processes is limited by the lack of appropriate analysis methods. In this paper, some challenging issues in neuroscience data analysis are described, and some general-purpose approaches to address such challenges are proposed. Specifically, we discuss statistical methodologies with a theme of loss functions, and hierarchical Bayesian inference methodologies from the perspective of constructing optimal mappings. These approaches are demonstrated on both simulated and experimentally acquired neural data sets to assess causal influences and track time-varying interactions among neural processes on a fine time scale.

In this paper, we consider many problems in Bayesian inference - from drawing samples to posteriors, to calculating confidence intervals, to implementing posterior matching algorithms, by finding maps that push one distribution to another. We show that for a large class of problems (with log-concave likelihoods and log-concave priors), these problems can be efficiently solved using convex optimization. We provide example applications within the context of dynamic statistical signal processing.

We develop low-complexity algorithms to robustly identify the best directed tree approximation for a network of stochastic processes in the finite-sample regime. Directed information is used to quantify influence between stochastic processes and identify the best directed tree approximation in terms of Kullback-Leibler (KL) divergence. We provide finite-sample complexity bounds for confidence intervals of directed information estimates. We use these confidence intervals to develop a minimax framework to identify the best directed tree that is robust to point estimation errors. We provide algorithms for this minimax calculation and describe the relationships between exactness and complexity.

This paper presents the design and implementation of spyware communication circuits built into the widely used carrier sense multiple access with collision avoidance (CSMA/CA) protocol. The spyware components are embedded within the sequential and combinational communication circuit structure during synthesis, rendering the distinction or dissociation of the spyware from the original circuit impossible. We take advantage of the timing channel resulting from transmission of packets to implement a new practical coding scheme that covertly transfers the spied data. Our codes are robust against the CSMA/CA's random retransmission time for collision avoidance and in fact take advantage of it to disguise the covert communication. The data snooping may be sporadically triggered, either externally or internally. The occasional trigger and the real-time traffic's variability make the spyware timing covert channel detection a challenge. The spyware is implemented and tested on a widely used open-source wireless CSMA/CA radio platform. We identify the following performance metrics and evaluate them on our architecture: 1) efficiency of implementation of the encoder; 2) robustness of the communication scheme to heterogeneous CSMA/CA effects; and 3) difficulty of covert channel detection. We evaluate criterion 1) completely theoretically. Criterion 2) is evaluated by simulating a wireless CSMA/CA architecture and testing the robustness of the decoder in different heterogeneous wireless conditions. Criterion 3) is confirmed experimentally using the state-of-the-art covert timing channel detection methods.

The bit-wise unequal error protection problem, for the case when the number of groups of bits${\ell}$is fixed, is considered for variable-length block codes with feedback. An encoding scheme based on fixed-length block codes with erasures is used to establish inner bounds to the achievable performance for finite expected decoding time. A new technique for bounding the performance of variable-length block codes is used to establish outer bounds to the performance for a given expected decoding time. The inner and the outer bounds match one another asymptotically and characterize the achievable region of rate-exponent vectors, completely. The single-message message-wise unequal error protection problem for variable-length block codes with feedback is also solved as a necessary step on the way.

Real-time detection of intermittent events requires continual monitoring and processing of sensor data. A battery-powered device that supports multiple sensing modalities and processing algorithms has the potential to save energy by using expensive sensors and algorithms only when the event of interest is most likely to occur. To develop a policy for sensing and processing management, we adopt maximum sequential information gain as an objective criterion for such energy-limited systems, which can be solved via dynamic programming. For binary hypothesis testing with two sensing options, the optimal management policy is a simple two-threshold test on the posterior belief. Detection of bird presence/absence in a wildlife monitoring application shows up to a 37% reduction in error rate over standard constant-duty-cycle sensing.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD - We propose a framework for learning the structure of a minimal latent tree with an associated discrepancy measure. Specifically, we apply this algorithm to recover the minimal latent directed information tree on a mixture of set of observed and unobserved random processes. Directed information trees are a new type of probabilistic graphical model based on directed information that represent the casual dynamics among random processes in a stochastic systems. To the best of our knowledge, this is the first approach that recovers these type of latent graphical models where samples are available only from a subset of processes.

The Naval Research Laboratory (NRL) Network Pump, or Pump, is a standard for mitigating covert channels that arise in a multilevel secure (MLS) system when a high user (HU) sends acknowledgements to a low user (LU). The issue here is that HU can encode information in the "timings" of the acknowledgements. The Pump aims at mitigating the covert timing channel by introducing buffering between HU and LU, as well as adding noise to the acknowledgment timings. We model the working of the Pump in certain situations, as a communication system with feedback and use then this perspective to derive an upper bound on the capacity of the covert channel between HU and LU in the Pump. This upper bound is presented in terms of a directed information flow over the dynamics of the system. We also present an achievable scheme that can transmit information over this channel. When the support of the noise added by Pump to acknowledgment timings is finite, the achievable rate is nonzero, i.e., infinite number of bits can be reliably communicated. If the support of the noise is infinite, the achievable rate is zero and hence a finite number of bits can be communicated.

This represents a special session on information theory and neuroscience at ISIT 2011.

This paper further demonstrates an interplay between information theory and control theory, at the level of achievability of message-point communication schemes. We establish a relationship between reliable feedback communication and the stability of the nonlinear filter. With this, we show that a newly developed feedback communication encoder - the posterior matching scheme - achieves capacity if and only if it is reliable (i.e. any finite number of bits can be reliably decoded). By making this connection to hidden Markov models, we also provide sufficient conditions (e.g. ergodicity of the Markov process and non-degeneracy of the noisy channel) on when reliability occurs.

The exponential server timing channel - the simplest queuing timing channel - is non-stationary and has infinite memory. Thus, developing error-correcting codes for such channels is challenging. Previously, Coleman and Kiyavash developed a class of coding techniques that are reliable in limited scenarios, but have undesirable complexity-performance tradeoffs. This paper utilizes a recent result by Coleman on developing an achievability theorem based upon how the channel is memoryless conditioned upon intermediate queue states. In this paper, we use this property, along with the fact that the distribution of a Poisson process conditioned upon the number of counts at time T is a uniform distribution on the unordered time epochs on [0,T]. Our approach uses a sparse graph coding technique over finite fields of large alphabets. Unlike the previous coding scheme, all intermediate messages of the decoder are of a fixed alphabet and the graphical representation is equivalent to a sparse graph for decoding on memoryless channels. Simulation results demonstrate the effectiveness of this approach.

We propose a new type of probabilistic graphical model, based on directed information, to represent the causal dynamics between processes in a stochastic system. We show the practical significance of such graphs by proving their equivalence to generative model graphs which succinctly summarize interdependencies for causal dynamical systems under mild assumptions. This equivalence means that directed information graphs may be used for causal inference and learning tasks in the same manner Bayesian networks are used for correlative statistical inference and learning.

The exponential server timing channel is known to be the simplest, and in some sense canonical, queuing timing channel. The capacity of this infinite-memory channel is known. Here, we discuss practical finite-length restrictions on the codewords and attempt to understand the maximal rate that can be achieved for a target error probability. By using Markov chain analysis, we prove a lower bound on the maximal channel coding rate achievable at blocklength n and error probability ϵ. The bound is approximated by C - n-1/2σQ (ϵ) where Q denotes the Q-function and σ2is the asymptotic variance of the underlying Markov chain. A closed form expression for σ2is given.

This article presents a new approach to designing brain–computer interfaces (BCIs) that explicitly accounts for both the uncertainty of neural signals and the important role of sensory feedback. This approach views a BCI as the means by which users communicate intent to an external device and models intent as a string in an ordered symbolic language. This abstraction allows the problem of designing a BCI to be reformulated as the problem of designing a reliable communication protocol using tools from feedback information theory. Here, this protocol is given by a posterior matching scheme. This scheme is not only provably optimal but also easily understood and implemented by a human user. Experimental validation is provided by an interface for text entry and an interface for tracing smooth planar curves, where input is taken in each case from an electroencephalograph during left- and right-hand motor imagery.

We propose a new paradigm for blind watermark decoding in the presence of desynchronization attacks. Employing Forney-style factor graphs to model the watermarking system, we cast the blind watermark decoding problem as a probabilistic inference problem on a graph, and solve it via message-passing. We study a wide range of moderate to strong attacks including scaling, amplitude modulation, fractional shift, arbitrary linear and shift-invariant filtering, and blockwise filtering, and show that the graph-based iterative decoders perform almost as well as if they had exact knowledge of the desynchronization attack parameters. Other desirable features of the graph-based decoders include the flexibility to adapt to other types of attacks and the ability to cope with the “curse of dimensionality” problem that seemingly results when the desynchronization parameter space has high dimensionality. These properties are unlike most blind watermark decoders proposed to date.

We propose a new classification method, termed the Common Spatial Analytic Pattern, for brain-computer interfaces based on a simple EEG signal source and channel model. This blind source separation procedure recovers underlying source signals near the motor cortex which are indicative of motor imagery. A hidden Markov source model is applied to the evolution of the source signals and is used to estimate the type (left or right) of motor imagery performed by a subject. As a whole, the resulting asynchronous classifier offers significant improvement upon the current prevailing techniques in classification. Experiments show information transfer rates between subject and computer as high as 60.9 bits/minute.

This paper extends our prior work on “E-type” (exponential family type) channels. The channels considered here have transition kernels induced by an exponential family with a two-component sufficient statistic composed of an input-output distortion function and an output cost function. We demonstrate the existence of a mutual information saddle point in any E-type channel for which there exists a source distribution such that the induced output distribution is maximum-entropy under an output cost constraint. For additive-noise E-type channels, we provide necessary and sufficient conditions on the existence of saddle points which coincide with convolution divisibility of the additive noise law. This machinery generalizes many well-known saddle-point, capacity, and rate-distortion theorems, including those for the additive Gaussian and exponential-noise channels, and leads to a saddle point result on the non-additive exponential server timing channel, which appears to be new.

This paper considers the problem of source coding with feedforward, where an encoder compresses an i.i.d. source into a message, and the decoder takes this message, along with causal noiseless side information, to construct an estimate of the source. The posterior matching scheme is an optimal feedback communication scheme for memoryless channels that results in the channel outputs being i.i.d. The duality between channel coding with feedback and source coding with feedforward motivates the idea of dualizing posterior matching for this setting. We demonstrate, using a Lyapunov exponent approach, that such a scheme attains the rate-distortion function.

In this paper, we consider a dynamical system, whose state is an input to a memoryless channel. The state of the dynamical system is affected by its past, an exogenous input, and causal feedback from the channel's output. We consider maximizing the directed information between the input signal and the channel output, over all exogenous input distributions and/or dynamical system policies. We demonstrate that under certain conditions, reversibility of a Markov chain implies directed information is maximized. With this, we develop achievability theorems for channels with (infinite) memory as well as optimality conditions for sequential estimation of Markov processes through dynamical systems with causal feedback. We provide examples, which includes the exponential server timing channel and the trapdoor channel.

Bit-wise unequal error protection problem with two layers is considered for variable length block-codes with feedback. Inner and outer bounds are derived for achievable performance for finite expected decoding time. These bounds completely characterize the error exponent of the special bits as a function of overall rate R, overall error exponent E and the rate of the special bits Rs. Single message Message-wise unequal protection problem is also solved as a step on the way.

The NRL Network Pump®, or Pump, is a standard for mitigating covert channels that arise in a multi-level secure (MLS) system when a high user (HU) sends acknowledgements to a low user (LU). The issue here is that HU can encode information in the “timings” of the acknowledgements. The Pump aims at mitigating the covert timing channel by introducing buffering between HU and LU, as well as adding noise to the acknowledgment timings. Here, for the first time, we model the workings of the Pump in certain situations, as a communication system with feedback and use then this novel perspective to derive a upper bound on the rate of the covert channel between HU and LU in the Pump, in specific situations. This upper bound is presented in terms of a directed information flow over the dynamics of the system.

Chow and Liu considered the problem of approximating discrete joint distributions with dependence tree distributions where the goodness of the approximations were measured in terms of KL distance. They (i) demonstrated that the minimum divergence approximation was the tree with maximum sum of mutual informations, and (ii) specified a low-complexity minimum-weight spanning tree algorithm to find the optimal tree. In this paper, we consider an analogous problem of approximating the joint distribution on discrete random processes with causal, directed, dependence trees, where the approximation is again measured in terms of KL distance. We (i) demonstrate that the minimum divergence approximation is the directed tree with maximum sum of directed informations, and (ii) specify a low-complexity minimum weight directed spanning tree, or arborescence, algorithm to find the optimal tree. We also present an example to demonstrate the algorithm.

Point-process models have been shown to be useful in characterizing neural spiking activity as a function of extrinsic and intrinsic factors. Most point-process models of neural activity are parametric, as they are often efficiently computable. However, if the actual point process does not lie in the assumed parametric class of functions, misleading inferences can arise. Nonparametric methods are attractive due to fewer assumptions, but computation in general grows with the size of the data. We propose a computationally efficient method for nonparametric maximum likelihood estimation when the conditional intensity function, which characterizes the point process in its entirety, is assumed to be a Lipschitz continuous function but otherwise arbitrary. We show that by exploiting much structure, the problem becomes efficiently solvable. We next demonstrate a model selection procedure to estimate the Lipshitz parameter from data, akin to the minimum description length principle and demonstrate consistency of our estimator under appropriate assumptions. Finally, we illustrate the effectiveness of our method with simulated neural spiking data, goldfish retinal ganglion neural data, and activity recorded in CA1 hippocampal neurons from an awake behaving rat. For the simulated data set, our method uncovers a more compact representation of the conditional intensity function when it exists. For the goldfish and rat neural data sets, we show that our nonparametric method gives a superior absolute goodness-of-fit measure used for point processes than the most common parametric and splines-based approaches.

Information theory--a field at the intersection of applied mathematics and electrical engineering--was primarily developed for the purpose of addressing problems arising in data storage and data transmission over (noisy) communication media. Consequently, information theory provides the formal basis for much of today’s storage and communication infrastructure.

This paper presents the first practical perfectly-secure steganography codes for covert communication via packet timings across interactive traffic relayed over network queuing systems. It has recently been shown that sparse-graph linear codes followed by shaping techniques, combined with message-passing decoding, can enable practical timing channel codes with low symbol error rates near the information capacity of the famous ldquobits through queuesrdquo channel. Inspired by this new class of codes, we use an alternative shaping technique that employs random dithers and construct provably secure steganographic codes for communication using packet timings in interactive traffic. To validate the perfect secrecy of our steganographic codes, we model interactive traffic as a two-state Markov modulated Poisson process (MMPP) and show its goodness-of-fit.

This paper discusses practical codes for communication via packet timings across network queuing systems - an instantiation of the "Bits Through Queues" result for timing channels. It has recently been shown that sparse-graph linear codes followed by shaping techniques, combined with message-passing decoding, can enable practical timing channel codes with low symbol error rates near the capacity. The previous work had two main drawbacks. First, the shaping technique was only effective for very large finite field sizes. Secondly, the complexity of the message-passing decoder was quadratic in the block length. In this work, 1) we develop an alternative shaping technique using random dithers with provably good statistical guarantees; 2) we exploit Little's Law from queuing theory along with a large deviations argument to reduce the message-passing decoder's complexity from quadratic to linear in block length. We illustrate the effectiveness of this approach on simulated queuing systems with low symbol error rates near the capacity.

This paper re-visits Shayevitz & Feder's recent dasiaPosterior Matching Schemepsila, a deterministic, recursive, capacity-achieving feedback encoding scheme for memoryless channels. We here consider the feedback encoder design problem from a stochastic control perspective. The state of the system is the posterior distribution of the message given current outputs of the channel. The per-trial reward is the average dasiareduction in distancepsila of the posterior to the target unit step function. We show that the converse to the channel coding theorem with feedback upper bounds the optimal reward, and that the posterior matching scheme is an optimal policy. We illustrate that this dasiareduction in distancepsila symbolism leads to the existence of a Lyapunov function on the Markov chain under this optimal policy, which leads to demonstration of achievability for all rates less than capacity.

This paper provides a conceptually simple, memoryless-style proof to the capacity of the Anantharam and Verdu's exponential server timing channel (ESTC). The approach is inspired by Rubin's approach for characterizing the rate-distortion of a Poisson process with structured distortion measures. This approach obviates the need for using the information density to prove achievability, by exploiting: 1) the ESTC channel on [0, nT] law is a product of [0, T] ESTC channel laws given intermediate queue states; 2) for Poisson inputs, the queue states form a Harris-recurrent Markov process. Achievability is subsequently shown by first demonstrating via the law of large numbers for Markov chains that an AEP holds, followed by standard random coding arguments. We extend our methodology to demonstrate achievability with Poisson inputs for any point process channel where the conditional intensity at any time is only a function of the queue state. Lastly, we demonstrate achievability with Poisson inputs for the tandem queue.

We consider a set of S independent encoders that must transmit a set of correlated sources through a network of noisy, independent, broadcast channels to T receivers, with no interference at the receivers. For the general problem of sending correlated sources through broadcast networks, it is known that the source-channel separation theorem breaks down and the achievable rate region as well as the proper method of coding are unknown. For our scenario, however, we establish the optimal rate region using a form of joint source-channel coding. When the optimal channel input distribution from transmitter i to receiver j is independent of j, our result has a max-flow/min-cut interpretation. Specifically, in this case, our result implies that if it is possible to send the sources to each receiver separately while ignoring the others, then it is possible to send to all receivers simultaneously.

This paper presents a proof of the rate distortion function of a Poisson process with a queuing distortion measure that is in complete analogy with the proofs associated with the rate distortion functions of a Bernoulli source with Hamming distortion measure and a Gaussian source with squared-error distortion measure. Analogous to those problems, the distortion measure that we consider is related to the logarithm of the conditional distribution relating the input to the output of a well-known channel coding problem, specifically the Anantharam and Verdu "Bits through Queues" [1] coding problem. Our proof of the converse utilizes McFadden's point process entropy formulation [2] and involves a number of mutual information inequalities, one of which exploits the maximum-entropy achieving property of the Poisson process. Our test channel uses Burke's theorem [3], [4] to prove achievability.

We propose a scheme for rate-constrained distributed non-parametric regression using a wireless sensor network. The scheme is universal across a wide range of sensor noise models, including unbounded and nonadditive noise; it has low complexity, requiring simple operations such as uniform scalar quantization with dither and message passing between neighboring nodes in the network; and attains minimax optimality for regression functions in common smoothness classes. We present theoretical results on the trade-off between the compression rate and the MSE and demonstrate empirical performance of the scheme using simulations.

We propose a complementary approach to the design of neural prosthetic interfaces that goes beyond the standard approach of estimating desired control signals from neural activity. We exploit the fact that the for a user's intended application, the dynamics of the prosthetic in fact impact subsequent desired control inputs. We illustrate that changing the dynamic response of a prosthetic device can make specific tasks significantly easier to accomplish. Our approach relies upon principles from stochastic control and feedback information theory, and we illustrate its effectiveness both theoretically and experimentally - in terms of spelling words from a menu of characters using binary surface electromyography classification.

This paper examines more closely the probabilistic dynamics of queueing timing channels and discusses a new practical coding scheme which is tailored to them and approaches capacity. We consider using sparse graph coset codes over nonbinary finite fields. We use a shaping technique to map algebraic symbols to non-uniform codewords using the inverse cumulative distribution of a target random variable. We exploit the graphical structure of the conditional distribution of the departure process given the arrival process to arrive at a Forney factor graph of the joint likelihood that has graphical structure reminiscent of coding on inter-symbol interference channels with LDPC codes. We show through simulation that this technique, when using low-complexity iterative decoding, is capacity-approaching.

We design a study assess to improve the speed in a P300 Brain-Computer Interface, originally described by Farewell and Donchin in 1988. A grid of characters is displayed on a screen randomly, and when the character of interest is illuminated, 300 ms afterwards a deflection in the EEG signal is generated. In such scenarios, the time to specify a menu option is proportional to its size. Most researchers in the past have considered fixed menu size and focused on more advanced statistical detection/classification techniques. We propose to use statistical language structure to introduce a new degree of freedom in this paradigm. Finding the optimal policy to display menus, given previously conveyed characters, can be cast in terms of ldquodynamic programmingrdquo or ldquostochastic controlrdquo. We illustrate how the optimal policy of this dynamic programming problem satisfies a menu depth to character probability relation analogous to that of the Huffman code in data compression and information theory. By exploiting this optimality property, we illustrate how the state space of the stochastic control problem can be greatly diminished (from exponential growth to linear growth), and we exhibit optimal policies for a probabilistic model pertaining to the statistical structure of the English language.

Point process models have been shown to be useful in characterizing neural spiking activity as a function of extrinsic and intrinsic factors. Most point process models of neural spiking are parametric as they are often efficiently computable. However, if the actual point process does not lie in the assumed parametric class of functions, misleading inferences can arise. Nonparametric methods are attractive due to fewer assumptions, but most methods require excessively complex algorithms. We propose a computationally efficient method for nonparametric maximum likelihood estimation when the conditional intensity function, which characterizes the point process in its entirety, is assumed to satisfy a Lipschitz continuity condition. We show that by exploiting the structure of the likelihood function of a point process, the problem becomes efficiently solvable via Lagrangian duality and we compare our nonparametric estimation method to the most commonly used parametric approaches on goldfish retinal ganglion neural data. In this example, our nonparametric method gives a superior absolute goodness-of-fit measure than all parametric approaches analyzed.

We discuss two approaches for decoding at arbitrary rates in the Slepian-Wolf problem - time sharing and source splitting - both of which rely on constituent vertex decoders. We consider the error exponents for both schemes and conclude that source-splitting is more robust at coding at arbitrary rates, as the error exponent for time-sharing degrades significantly at rates near vertices. As a by-product of our analysis, we exhibit an interesting connection between minimum mean-squared error estimation and error exponents

We consider a set of S independent encoders that must transmit a set of correlated sources through a network of noisy, independent, broadcast channels to T receivers. For the general problem of sending correlated sources through broadcast networks, it is known that the source-channel separation theorem breaks down and the achievable rate region as well as the proper method of coding are unknown. For our scenario, however, we not only establish the optimal rate region, but we show that a type of source-channel separation is possible at the transmitter, provided joint source-channel decoding is used at the receiver. Furthermore, we show that while joint source-channel encoding is unnecessary, not using joint source-channel decoding is suboptimal. Finally, when the optimal input distribution from transmitter i to receiver j is independent of j, our result has a max-flow/min-cut interpretation. Specifically, in this case our result implies that if it is possible to send the sources to each receiver separately while ignoring the others, then it is possible to send to all receivers simultaneously

This paper discusses the Slepian-Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the achievable region. The technique employs a simple "source-splitting" strategy that does not require common sources of randomness at the encoders and decoders. This approach allows for pipelined encoding and decoding so that the system operates with the complexity of a single user encoder and decoder. Moreover, when this splitting approach is used in conjunction with iterative decoding methods, it produces a significant simplification of the decoding process. We demonstrate this approach for synthetically generated data. Finally, we consider the Slepian-Wolf problem when linear codes are used as syndrome-formers and consider a linear programming relaxation to maximum-likelihood (ML) sequence decoding. We note that the fractional vertices of the relaxed polytope compete with the optimal solution in a manner analogous to that observed when the "min-sum" iterative decoding algorithm is applied. This relaxation exhibits the ML-certificate property: if an integral solution is found, it is the ML solution. For symmetric binary joint distributions, we show that selecting easily constructable "expander"-style low-density parity check codes (LDPCs) as syndrome-formers admits a positive error exponent and therefore provably good performance

Minimum-entropy decoding is a universal decoding algorithm used in decoding block compression of discrete memoryless sources as well as block transmission of information across discrete memoryless channels. Extensions can also be applied for multiterminal decoding problems, such as the Slepian-Wolf source coding problem. The 'method of types' has been used to show that there exist linear codes for which minimum-entropy decoders achieve the same error exponent as maximum-likelihood decoders. Since minimum-entropy decoding is NP-hard in general, minimum-entropy decoders have existed primarily in the theory literature. We introduce practical approximation algorithms for minimum-entropy decoding. Our approach, which relies on ideas from linear programming, exploits two key observations. First, the 'method of types' shows that that the number of distinct types grows polynomially in n. Second, recent results in the optimization literature have illustrated polytope projection algorithms with complexity that is a function of the number of vertices of the projected polytope. Combining these two ideas, we leverage recent results on linear programming relaxations for error correcting codes to construct polynomial complexity algorithms for this setting. In the binary case, we explicitly demonstrate linear code constructions that admit provably good performance.

We address practical coding schemes for the Slepian-Wolf distributed data compression problem. We consider three approaches. First, we apply a source-splitting technique to code at any rate in the achievable rate region with low complexity. It is well known that vertices in the achievable rate region can be implemented with low complexity. The source-splitting approach transforms any achievable rate point into a vertex in a higher-dimensional Slepian-Wolf achievable rate region. Secondly, we consider linear programming relaxations of the maximum-likelihood decoding problem. We give a polynomial complexity construction for linear codes with a certificate property. Lastly, when the decoder does not have any knowledge of the source statistics, we present practical schemes for universal decoding, a topic heretofore confined primarily to theory.

We show that the deterministic broadcast channel, where a single source transmits to M receivers across a deterministic mechanism, may be reduced, via a rate-splitting transformation, to another (2M - 1)-receiver deterministic broadcast channel problem where a successive encoding approach suffices. Analogous to rate-splitting for the multiple access channel and source-splitting for the Slepian-Wolf problem, all achievable rates (including non-vertices) apply. This amounts to significant complexity reduction at the encoder

We motivate the consideration of deterministic broadcast channel coding as an interference management technique in wireless scenarios. We address practical coding strategies for such channels and discuss two approaches. The first relies upon enumerative source coding and can be applied for any deterministic broadcast channel problem as the first step in pipelined encoding for vertex rates. The second approach addresses a wireless interference management scenario and is a complete, practical, capacity-achieving strategy that dualizes the Luby transform code construction and encoding/decoding algorithms. This results in the first practical, nontrivial, capacity achieving code construction for the deterministic broadcast channel.

We introduce three new innovations for compression using LDPCs for the Slepian-Wolf problem. The first is a general iterative Slepian-Wolf decoding algorithm that incorporates the graphical structure of all the encoders and operates in a 'turbo-like' fashion. The second innovation introduces source-splitting to enable low-complexity pipelined implementations of Slepian-Wolf decoding at rates besides corner points of the Slepian-Wolf region. This innovation can also be applied to single-source block coding for reduced decoder complexity. The third approach is a linear programming relaxation to maximum-likelihood sequence decoding that exhibits the ML-certificate property. This can be used for decoding a single binary block-compressed source as well as decoding at vertex points for the binary Slepian-Wolf problem. All three of these innovations were motivated by recent analogous results in the channel coding domain.

It is shown that achieving an arbitrary rate-point in the achievable region of the M-source Slepian-Wolf [1] problem may be reduced via a practical source-splitting transformation to achieving a corner point in a 2M - 1 source Slepian-Wolf problem. Moreover, each source must be split at most once. This approach extends the ideas introduced in [2] to a practical setting: it does not require common randomness shared between splitters and the decoders, the cardinality of each source split is strictly smaller than the original, and practical iterative decoding methods can achieve rates near the theoretical bound.

We consider a dynamical probabilistic traffic model for the number of users transmitting at any time. This model captures both user mobility and traffic burstiness. Moreover, we assume no centralized controller, such as a scheduler, is available. When multiple users transmit simultaneously, multiple-access interference (MAI) affects throughput considerably. Most queue control schemes assume individual users know the states of their own queues (local queue information) along with the states of other users queues (shared queue information) and address issues of scheduling; but this sharing of information may be onerous in a practical system. While shared queue information has recently been shown (Me/spl acute/dard et al., 2004) not to affect the capacity of such systems, it has a considerable impact on delay. We introduce a scheme, where for each user, a bit of shared queue information specifies whether its queue length is above or below a threshold. Our scheme relies on two different service classes implemented through a superposition coding scheme (first proposed with Me/spl acute/dard and Goldsmith, 1999, further studied and expanded with Me/spl acute/dard et al., 2004). The first class experiences no delay due to multiple-access interference, while the second class requires retransmissions when such an event occurs. We show how our scheme affords an energy-delay tradeoff. Moreover, when configured properly, our scheme can attain boundary points of the region corresponding to minimum energy with no shared queue information for zero delay along with minimum energy subject to system stability. We derive bounds on the performance of the multiple-access system using our proposed scheme by introducing Lyapunov function bounds in a manner similar to Bertsimas et al., 2001.

We study different notions of capacity for time-slotted ALOHA systems. In these systems, multiple users synchronously send packets in a bursty manner over a common additive white Gaussian noise (AWGN) channel. The users do not coordinate their transmissions, which may collide at the receiver. For such a system, we define both single-slot capacity and multiple-slot capacity. We then construct a coding and decoding scheme for single-slot capacity that achieves any rate within this capacity region. This coding and decoding scheme for a single time slot combines aspects of multiple access rate splitting and of broadcast codes for degraded AWGN channels. This design allows some bits to be reliably received even when collisions occur and more bits to be reliably received in the absence of collisions. The exact number of bits reliably received under both of these scenarios is part of the code design process, which we optimize to maximize the expected rate in each slot. Next, we examine the behavior of the system asymptotically over multiple slots. We show that there exist coding and decoding strategies such that regardless of the burstiness of the traffic, the system is stable as long as the average rate of the users is within the multiple access capacity region of the channel. In other words, we show that bursty traffic does not decrease the Cover-Wyner capacity region of the multiple access channel. A vast family of codes, which includes the type of codes we introduce for the single-slot transmission, achieve the capacity region, in a sense we define, for multiple-slot transmissions. These codes are stabilizing, using only local information at each of the individual queues. The use of information regarding other queues or the use of scheduling does not improve the multiple-slot capacity region.