We study the problem of Non-Stationary Reinforcement Learning (NS-RL) without prior knowledge about the system’s non-stationarity. A state-of-the-art, black-box algorithm, known as MASTER, is considered, with a focus on identifying the conditions under which it can achieve its stated goals. Specifically, we prove that MASTER’s non-stationarity detection mechanism is not triggered for practical choices of horizon, leading to performance akin to a random restarting algorithm. Moreover, we show that the regret bound for MASTER, while being order optimal, stays above the worst-case linear regret until unreasonably large values of the horizon. To validate these observations, MASTER is tested for the special case of piecewise stationary multi-armed bandits, along with methods that employ random restarting, and others that use quickest change detection to restart. A simple, order optimal random restarting algorithm, that has prior knowledge of the non-stationarity is proposed as a baseline. The behavior of the MASTER algorithm is validated in simulations, and it is shown that methods employing quickest change detection are more robust and consistently outperform MASTER and other random restarting approaches.

This paper addresses the problem of quickest change detection of an unknown mean-shift in multiple Gaussian data streams. We propose a novel extension of the window-limited CuSum (WL-CuSum) test which utilizes the James-Stein estimator to improve detection performance. Compared to traditional maximum likelihood-based approaches, the proposed approach can considerably reduce the detection delay, especially when the number of streams is large. Our theoretical results indicate that the proposed test asymptotically optimal, and non-asymptotically a uniform improvement over its maximum likelihood alternative. The performance is improved for all values of the unknown post-change parameter, as long as the number of the data streams is greater than three. Overall, the results suggest that shrinkage estimators, such as the James-Stein estimator, can provide substantial performance improvement in change detection problems with unknown parameters.

We study the problem of quickest change detection (QCD) when the post-change distribution has parametric uncertainty. The generalized likelihood ratio (GLR) cumulative sum (CuSum) procedure is known to be asymptotically optimum in this setting. However, this rule requires significant memory and computational resources, making it difficult to implement in practice. To overcome this limitation, sliding window approaches, such as the window-limited GLR CuSum and window-limited adaptive CuSum tests, have been employed, where the test statistic is computed over a fixed window of the latest observations. We propose the K-Best rule which instead keeps track of K hypothesized change points that have the largest test statistic. This allows the hypothesized change points to reduce epistemic uncertainty over time, while restricting the number of hypothesized change points considered. We characterize the growth rate of the K-Best window necessary to achieve the detection performance of the GLR-CuSum rule and quantify the computational benefits over the existing windowing approaches.

State of the art methods for target tracking with sensor management (or controlled sensing) are model-based and are obtained through solutions to Partially Observable Markov Decision Process (POMDP) formulations. In this paper a Reinforcement Learning (RL) approach to the problem is explored for the setting where the motion model for the object/target to be tracked is unknown to the observer. It is assumed that the target dynamics are stationary in time, the state space and the observation space are discrete, and there is complete observability of the location of the target under certain (a priori unknown) sensor control actions. Then, a novel Markov Decision Process (MDP) rather than POMDP formulation is proposed for the tracking problem with controlled sensing, which is termed as Track-MDP. In contrast to the POMDP formulation, the Track-MDP formulation is amenable to an RL based solution. It is shown that the optimal policy for the Track-MDP formulation, which is approximated through RL, is guaranteed to track all significant target paths with certainty. The Track-MDP method is then compared with the optimal POMDP policy, and it is shown that the infinite horizon tracking reward of the optimal Track-MDP policy is the same as that of the optimal POMDP policy. In simulations it is demonstrated that Track-MDP based RL leads to a policy that can track the target with high accuracy.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. A finite-horizon variant of the quickest change detection problem is investigated, which is motivated by a change detection problem that arises in piecewise stationary bandits. The goal is to minimize the latency, which is smallest threshold such that the probability that the detection delay exceeds the threshold is below a desired low level, while controlling the false alarm probability to a desired low level. When the pre- and post-change distributions are unknown, two tests are proposed as candidate solutions. These tests are shown to attain order-optimality in terms of the horizon. Furthermore, the growth in their latencies with respect to the false alarm probability and late detection probability satisfies a property that is desirable in regret analysis for piecewise stationary bandits. Numerical results are provided to validate the theoretical performance results.

The problem of quickest change detection is studied in the context of detecting an arbitrary unknown mean-shift in multiple independent Gaussian data streams. The James-Stein estimator is used in constructing detection schemes that exhibit strong detection performance both asymptotically and non-asymptotically. Our results indicate that utilizing the James-Stein estimator in the recently developed window-limited CuSum test constitutes a uniform improvement over its typical maximum likelihood variant. That is, the proposed James-Stein version achieves a smaller detection delay simultaneously for all possible post-change parameter values and every false alarm rate constraint, as long as the number of parallel data streams is greater than three. Additionally, an alternative detection procedure that utilizes the James-Stein estimator is shown to have asymptotic detection delay properties that compare favorably to existing tests. The second-order asymptotic detection delay term is reduced in a predefined low-dimensional subspace of the parameter space, while second-order asymptotic minimaxity is preserved. The results are verified in simulations, where the proposed schemes are shown to achieve smaller detection delays compared to existing alternatives, especially when the number of data streams is large.

The problem of quickest detection of a change in the distribution of streaming data is considered. It is assumed that the pre-change distribution is known, while the only information about the post-change is through a (small) set of labeled data. This post-change data is used in a data-driven minimax robust framework, where an uncertainty set for the post-change distribution is constructed. The robust change detection problem is studied in an asymptotic setting where the mean time to false alarm goes to infinity. It is shown that the least favorable distribution (LFD) is an exponentially tilted version of the pre-change density and can be obtained efficiently. A Cumulative Sum (CuSum) test based on the LFD, which is referred to as the distributionally robust (DR) CuSum test, is then shown to be asymptotically robust. The results are extended to the case with multiple post-change uncertainty sets and validated using synthetic and real data examples.

We study the problem of Quickest Change Detection (QCD) in a complex networked system consisting of a set of heterogeneous agents that sequentially feed information to a central fusion center. At any unknown deterministic time, a persistent anomaly occurs, causing the distribution of observations from an unknown distinguishable subset of agents to simultaneously change from a nominal (pre-change) distribution to an anomalous (post-change) distribution, and the goal of the fusion center is to detect the change as quickly as possible subject to a false alarm constraint. Traditionally, various fusion rules have been proposed that assume that the distributions at each agent are either completely known or unknown and are locally solved using the Cumulative Sum (CuSum) and Generalized Likelihood Ratio (GLR) statistics, respectively. When an agent has access to training data, the Uncertain Likelihood Ratio (ULR) test generalizes distributional assumptions using uncertain distributions. However, the ULR has not been implemented for network change detection. This paper empirically studies incorporating the ULR statistics into the existing fusion rules for QCD and compares the average detection delay. Our results show that the ULR test can improve the average detection delay over the GLR tests using certain fusion techniques, while approaching the detection delay of the CuSum tests as the training data increases. Our results provide insights into future theoretical analysis to improve network QCD with imprecise knowledge of the distributions.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. A finite horizon variant of the quickest change detection problem is studied, in which the goal is to minimize a delay threshold (latency), under constraints on the probability of false alarm and the probability that the latency is exceeded. In addition, the horizon is not known to the change detector. A variant of the cumulative sum (CuSum) test with a threshold that increasing logarithmically with time is proposed as a candidate solution to the problem. An information-theoretic lower bound on the minimum value of the latency under the constraints is then developed. This lower bound is used to establish certain asymptotic optimality properties of the proposed test in terms of the horizon and the false alarm probability. Some experimental results are given to illustrate the performance of the test.

The problem of robust multi-hypothesis testing in the Bayesian setting is studied in this paper. Under the$m\geq 2$hypotheses, the data-generating distributions are assumed to belong to uncertainty sets constructed through some moment functions, i.e., the sets contain distributions whose moments are centered around empirical moments obtained from some training data sequences. The goal is to design a test that performs well under all distributions in the uncertainty sets, i.e., a test that minimizes the worst-case probability of error over the uncertainty sets. Insights on the need for optimization-based approaches to solve the robust testing problem with moment constrained uncertainty sets are provided. The optimal (robust) test based on the optimization approach is derived for the case where the observations belong to a finite-alphabet. When the size of the alphabet is infinite, the optimization problem is infinite-dimensional and intractable, and therefore a tractable finite-dimensional approximation is proposed, whose optimal value converges to the optimal value of the original problem as the size of the dimension of the approximation goes to infinity. A robust test is constructed from the solution to the approximate problem, and guarantees on its worst-case error probability over the uncertainty sets are provided. Numerical results are provided to demonstrate the performance of the proposed robust test.

The problem of quickest change detection in a sequence of independent observations is considered. The pre-change distribution is assumed to be known, while the post-change distribution is unknown. Two tests based on post-change density estimation are developed for this problem, the window-limited non-parametric generalized likelihood ratio (NGLR) CuSum test and the non-parametric window-limited adaptive (NWLA) CuSum test. Both tests do not assume any knowledge of the post-change distribution, except that the post-change density satisfies certain smoothness conditions that allows for efficient non-parametric estimation; also, they do not require any pre-collected post-change training samples. Under certain convergence conditions on the density estimator, it is shown that both tests are first-order asymptotically optimal, as the false alarm rate goes to zero. The analysis is validated through numerical results, where both tests are compared with baseline tests that have distributional knowledge.

The problem of quickest change detection in a sequence of independent observations is considered. The pre-change distribution is assumed to be known, while the post-change distribution is completely unknown. A window-limited leave-one-out (LOO) CuSum test is developed, which does not assume any knowledge of the post-change distribution, and does not require any post-change training samples. It is shown that, with certain convergence conditions on the density estimator, the LOO-CuSum test is first-order asymptotically optimal, as the false alarm rate goes to zero. The analysis is validated through numerical results, where the LOO-CuSum test is compared with baseline tests that have distributional knowledge.

The problem of robust binary hypothesis testing is studied. Under both hypotheses, the data-generating distributions are assumed to belong to uncertainty sets constructed through moments; in particular, the sets contain distributions whose moments are centered around the empirical moments obtained from training observations. The goal is to design a test that performs well under all distributions in the uncertainty sets, i.e., minimize the worst-case error probability over the uncertainty sets. In the finite-alphabet case, the optimal test is obtained. In the infinite-alphabet case, a tractable approximation to the worst-case error is derived that converges to the optimal value A test is further constructed to generalize to the entire alphabet. An exponentially consistent test for testing batch samples is also proposed. Numerical results are provided to demonstrate the performance of the proposed robust tests.

Compressed Stochastic Gradient Descent (SGD) algorithms have been proposed to address the communication bottleneck in distributed and decentralized optimization problems such as federated machine learning. Many existing compressed SGD algorithms use non-adaptive step-sizes (constant or diminishing) to provide theoretical convergence guarantees. Since non-adaptive step-sizes typically involve unknown system parameters, the step-sizes are fine-tuned in practice to obtain good empirical performance for the given dataset and learning model. Such fine-tuning might be impractical in many scenarios. Thus, it is of interest to study compressed SGD using adaptive step-sizes. Motivated by prior work that use adaptive step-sizes for uncompressed SGD, we develop an Armijo rule based step-size selection method for compressed SGD. In particular, we introduce a scaling technique for the descent step, which we use to establish order-optimal convergence rates for convex-smooth and strong convex-smooth objectives under an interpolation condition, and for non-convex objectives under a strong growth condition. We present experimental results on deep neural networks trained on real-world datasets, and compare the performance of our proposed algorithm with state-of-the-art compressed SGD methods to demonstrate improved performance at various levels of compression.

We study the problem of Out-of-Distribution (OOD) detection, that is, detecting whether a Machine Learning (ML) model's output can be trusted at inference time. While a number of tests for OOD detection have been proposed in prior work, a formal framework for studying this problem is lacking. We propose a definition for the notion of OOD that includes both the input distribution and the ML model, which provides insights for the construction of powerful tests for OOD detection. We also propose a multiple hypothesis testing inspired procedure to systematically combine any number of different statistics from the ML model using conformal p-values. We further provide strong guarantees on the probability of incorrectly classifying an in-distribution sample as OOD. In our experiments, we find that threshold-based tests proposed in prior work perform well in specific settings, but not uniformly well across different OOD instances. In contrast, our proposed method that combines multiple statistics performs uniformly well across different datasets and neural networks.

The problem of robust Sparse Linear Discriminant Analysis (LDA) in high-dimensions is studied, in which a fraction of the training data may be corrupted by an adversary. A computationally efficient algorithm is proposed by adapting robust mean estimation along with a calibration framework for LDA. Theoretical properties of the proposed algorithm are established for both the estimation error of the optimal projection vector and the mis-classification rate. Results from extensive numerical studies on both synthetic and real datasets are reported to show the usefulness of our algorithm.

We study the problem of out-of-distribution (OOD) detection, that is, detecting whether a machine learning (ML) model's output can be trusted at inference time. While a number of tests for OOD detection have been proposed in prior work, a formal framework for studying this problem is lacking. We propose a definition for the notion of OOD that includes both the input distribution and the ML model, which provides insights for the construction of powerful tests for OOD detection. We also propose a multiple hypothesis testing inspired procedure to systematically combine any number of different statistics from the ML model using conformal p-values. We further provide strong guarantees on the probability of incorrectly classifying an in-distribution sample as OOD. In our experiments, we find that threshold-based tests proposed in prior work perform well in specific settings, but not uniformly well across different OOD instances. In contrast, our proposed method that combines multiple statistics performs uniformly well across different datasets and neural networks architectures.

The problem considered is one of maximizing the information flow through a sensor network tasked with estimating, at a fusion center, an underlying parameter in a linear observation model. The sensor nodes take observations, quantize them, and send them to the fusion center through a network of relay nodes. The links in the network are assumed to satisfy certain capacity constraints in terms of the maximum number of bits that can be transmitted on the links. Furthermore, the relay nodes are assumed to satisfy flow conservation constraints, i.e., the number of bits flowing into a relay node is equal to the number of bits flowing out of it. It is shown that this flow optimization problem for estimation can be cast as a Network Utility Maximization (NUM) problem by suitably defining the utility functions at the sensors. The inference problem considered is one of parameter estimation with a linear observation model, which is studied in both Bayesian and non-Bayesian settings. Upper bounds on the mean-squared error (MSE) of optimal linear estimators are obtained in both settings, and these bounds are used to construct utility functions for the corresponding NUM problems. It is verified via simulations that the bit assignments at the sensors obtained through the solutions to the NUM problems, in both the Bayesian and non-Bayesian settings, yield considerably better estimation performance than the Max-Flow solution that simply assigns bits to the sensors in such a way as to maximize the total bits transmitted to the fusion center.

The problem of robust mean estimation in high dimensions is studied, in which a certain fraction (less than half) of the datapoints can be arbitrarily corrupted. Motivated by compressive sensing, the robust mean estimation problem is formulated as the minimization of the ℓ0-‘norm’ of anoutlier indicator vector, under a second moment constraint on the datapoints. The ℓ0-‘norm’ is then relaxed to the ℓp-norm (0p≤ 1) in the objective, and it is shown that the global minima for each of these objectives are order-optimal and have optimal breakdown point for the robust mean estimation problem. Furthermore, a computationally tractable iterative ℓp-minimization and hard thresholding algorithm is proposed that outputs an order-optimal robust estimate of the population mean. The proposed algorithm (with breakdown point ≈ 0.3) does not require prior knowledge of the fraction of outliers, in contrast with most existing algorithms, and forp= 1 it has near-linear time complexity. Both synthetic and real data experiments demonstrate that the proposed algorithm outperforms state-of-the-art robust mean estimation methods.

The problem of quickest detection of a change in the distribution of a sequence of independent observations is considered. The pre-change observations are assumed to be stationary with a known distribution, while the post-change observations are allowed to be non-stationary with some possible parametric uncertainty in their distributions. In particular, it is assumed that the cumulative Kullback-Leibler divergence between the post-change and the pre-change distributions grows in a certain manner with time after the change-point. For the case where the post-change distributions are known, a universal asymptotic lower bound on the delay is derived, as the false alarm rate goes to zero. Furthermore, a window-limited Cumulative Sum (CuSum) procedure is developed, and shown to achieve the lower bound asymptotically. For the case where the post-change distributions have parametric uncertainty, a window-limited (WL) generalized likelihood-ratio (GLR) CuSum procedure is developed and is shown to achieve the universal lower bound asymptotically. Extensions to the case with dependent observations are discussed. The analysis is validated through numerical results on synthetic data. The use of the WL-GLR-CuSum procedure in monitoring pandemics is also demonstrated.

The problem of quickest detection of a change in the distribution of a sequence of independent observations is considered. The prechange distribution is assumed to be known and stationary, while the post-change distributions are assumed to evolve in a pre-determined non-stationary manner with some possible parametric uncertainty. In particular, it is assumed that the cumulative KL divergence between the post-change and the pre-change distributions grows superlinearly with time after the change-point. For the case where the post-change distributions are known, a universal asymptotic lower bound on the delay is derived, as the false alarm rate goes to zero. Furthermore, a window-limited CuSum test is developed, and shown to be asymptotically optimal. For the case where the post-change distributions have parametric uncertainty, a window-limited generalized likelihood-ratio test is developed and is shown to be asymptotically optimal. The analysis is validated through numerical results on synthetic data. The use of the window-limited generalized likelihood-ratio test in monitoring pandemics is also demonstrated.

The problem of robust mean estimation in high dimensions is studied, in which a certain fraction (less than half) of the datapoints can be arbitrarily corrupted. Motivated by compressive sensing, the robust mean estimation problem is formulated as the minimization of the ℓ0-‘norm’ of an outlier indicator vector, under a second moment constraint on the datapoints. The ℓ0-‘norm’ is then relaxed to the ℓp-norm (0p-minimization and hard thresholding algorithm is proposed that outputs an order-optimal robust estimate of the population mean. The proposed algorithm (with breakdown point ≈0.3) does not require prior knowledge of the fraction of outliers, in contrast with most existing algorithms, and for p = 1 it has near-linear time complexity. Both synthetic and real data experiments demonstrate that the proposed algorithm outperforms state-of-the-art robust mean estimation methods.

In the problem of quickest change detection, a change occurs at some unknown time in the distribution of a sequence of random vectors that are monitored in real time, and the goal is to detect this change as quickly as possible subject to a certain false alarm constraint. In this work we consider this problem in the presence of parametric uncertainty in the post-change regime and controlled sensing. That is, the post-change distribution contains unknown parameters, and the distribution of each observation, before and after the change, is affected by a control action. In this context, in addition to a stopping rule that determines the time at which it is declared that the change has occurred, one also needs to determine a sequential control policy, which chooses the control action at each time based on the already collected observations that is "best" for the unknown post-change parameter. We formulate this problem mathematically using Lorden’s minimax criterion, and assuming that there are finitely many possible actions and post-change parameter values. We establish a universal lower bound on the worst-case detection delay, as the mean time to false alarm goes to infinity, which needs to be satisfied by any procedure for quickest change detection with controlled sensing. We then propose a specific procedure for this problem, which we call the Chernoff-CuSum procedure, for which the conditional expected detection delay, for any fixed value of the change-point, matches the universal lower bound up to a first-order asymptotic approximation as the mean time to false alarm goes to infinity.

The problem of quickest detection of a change in the mean of a sequence of independent observations is studied. The pre-change observations are assumed to be stationary, while the post-change observations are allowed to be non-stationary. The case where the pre-change distribution is known is studied first, and then the extension where only the mean and variance of the pre-change distribution are known. No knowledge of the post-change distributions is assumed other than that the means of the observations are above some pre-specified threshold larger than the pre-change mean. For the case where the pre-change distribution is known, a test is derived that asymptotically minimizes the worst-case detection delay over all possible post-change distributions, as the false alarm rate goes to zero. Towards deriving this asymptotically optimal test, some new results are provided for the general problem of asymptotic minimax robust quickest change detection in non-stationary settings. Then, the limiting form of the optimal test is studied as the gap between the pre- and post-change means goes to zero, called the Mean-Change Test (MCT). It is shown that the MCT can be designed with only knowledge of the mean and variance of the pre-change distribution. The performance of the MCT is also characterized when the mean gap is moderate, under the additional assumption that the distributions of the observations have bounded support. The analysis is validated through numerical results for detecting a change in the mean of a beta distribution. The use of the MCT in monitoring pandemics is also demonstrated.

We consider a fully decentralized multi-player stochastic multi-armed bandit setting where the players cannot communicate with each other and can observe only their own actions and rewards. The environment may appear differently to different players, i.e., the reward distributions for a given arm are heterogeneous across players. In the case of a collision (when more than one player plays the same arm), we allow for the colliding players to receive non-zero rewards. The time-horizon T for which the arms are played is not known to the players. Within this setup, where the number of players is allowed to be greater than the number of arms, we present a policy that achieves near order-optimal expected regret of order O(log1+δ T) for δ > 0 (however small) over a time-horizon of duration T.

To achieve better connectivity in future communication networks, the deployment of different types of access points (APs) is underway. APs are expected to be equipped with self-organizing capabilities to reduce costs. Moreover, due to the spectrum crunch, frequency reuse among the deployed APs is inevitable, exacerbating the problem of inter-cell interference (ICI). Therefore, ICI mitigation in self-organizing networks (SONs) is commonly identified as a key radio resource management mechanism to enhance performance. To this end, this paper proposes a novel solution for the uncoordinated channel and power allocation problems. Based on the multi-armed bandits (MAB) framework, the proposed technique does not require any communication between the APs. The case of varying channel rewards across APs is considered. In contrast to previous work on channel allocation using the MAB framework, APs are permitted to choose multiple channels for transmission. Moreover, non-orthogonal multiple access is used, allowing multiple APs to access each channel simultaneously. This results in an MAB model with varying channel rewards, multiple plays and non-zero reward on collision. The proposed algorithm has an expected regret in the order ofO(log2T), with extensive numerical results revealing it significantly outperforms a well-known baseline algorithm in terms of energy efficiency.

The downlink of a two-layered heterogeneous network is studied with macro basestations (MBs), small-cell basestations (SBs) that act as half-duplex analog relays, and mobile terminals (MTs). The first layer is a wireless backhaul layer between MBs and SBs, and the second is the transmission layer between SBs and MTs. The layers use the same time/frequency resources for communication, limiting the maximum per user degrees of freedom (puDoF) to half, due to the half-duplex nature of the SBs. For linear network models, it is established that the optimal puDoF can be achieved by cooperation with an appropriate number of antennas that depends on the connectivity of the network. The proposed zero-forcing schemes achieve cooperation without overloading the backhaul, through each MB sending an appropriate linear combination of MTs' message signals to the SBs in the backhaul layer. The achievable schemes exploit the half-duplexity of the SBs, and schedule the SBs and MTs to be active in different time-slots to manage interference. These results are then extended to a more realistic hexagonal cellular network and it is shown that the optimal puDoF of half can be approached using only zero-forcing schemes.

We show that model compression can improve the population risk of a pre-trained model, by studying the tradeoff between the decrease in the generalization error and the increase in the empirical risk with model compression. We first prove that model compression reduces an information-theoretic bound on the generalization error; this allows for an interpretation of model compression as a regularization technique to avoid overfitting. We then characterize the increase in empirical risk with model compression using rate distortion theory. These results imply that the population risk could be improved by model compression if the decrease in generalization error exceeds the increase in empirical risk. We show through a linear regression example that such a decrease in population risk due to model compression is indeed possible. Our theoretical results further suggest that the Hessian-weighted K-means clustering compression approach can be improved by regularizing the distance between the clustering centers. We provide experiments with neural networks to support our theoretical assertions.

The problem of maximizing the information flow through a sensor network tasked with an inference objective at the fusion center is considered. The sensor nodes take observations, compress and send them to the fusion center through a network of relays. The network imposes capacity constraints on the rate of transmission in each connection and flow conservation constraints. It is shown that this rate-constrained inference problem can be cast as a Network Utility Maximization problem by suitably defining the utility functions for each sensor, and can be solved using existing techniques. Two practical settings are analyzed: multi-terminal parameter estimation and binary hypothesis testing. It is verified via simulations that using the proposed formulation gives better inference performance than the Max-Flow solution that simply maximizes the total bit-rate to the fusion center.

The problem of quickest growing dynamic anomaly detection in sensor networks is studied. Initially, the observations at the sensors, which are sampled sequentially by the decision maker, are generated according to a pre-change distribution. At some unknown but deterministic time instant, a dynamic anomaly emerges in the network, affecting different sets of sensors as time progresses. The observations of the affected sensors are generated from a post-change distribution. It is assumed that the number of affected sensors increases with time, and that only the initial and the final size of the anomaly are known to the decision maker. The goal is to detect the emergence of the anomaly as quickly as possible while guaranteeing a sufficiently low frequency of false alarm (FA) events. This detection problem is posed as a stochastic optimization problem by using a delay metric that is based on the worst possible path of the anomaly. A detection rule is proposed that is asymptotically optimal as the mean time to false alarm goes to infinity. Finally, numerical results are provided to validate our theoretical analysis.

The problem studied is one of quickest detection of an anomaly that emerges in a sensor network, and which may move across the network after it emerges. Each sensor in the network is characterized by a non-anomalous and an anomalous data-generating distribution, and these distributions could be different across the sensors. Initially, the observations at all the sensors are generated according to their corresponding non-anomalous distribution. After some unknown but deterministic time instant, a dynamic anomaly emerges in the network, affecting a different sensor as time progresses. The observations generated by the affected sensor follow the corresponding anomalous distribution. The goal is to detect the onset of the dynamic anomaly as quickly as possible, subject to constraints on the frequency of false alarms. This detection problem is posed in a quickest change detection framework where candidate stopping procedures are evaluated according to a delay metric that considers the worst trajectory of the dynamic anomaly. A detection rule is proposed and established to be asymptotically optimal as the mean time to false alarm goes to infinity. Finally, numerical results are provided to validate our theoretical analysis.

In this paper, an algorithm based on the multiplayer multi-armed bandit (MAB) framework is proposed to solve an uncoordinated spectrum access problem. The proposed technique does not require any communication or coordination between users. The case of varying channel rewards across users is considered. In contrast to previous work, the users are permitted to choose multiple channels for transmission, resulting in a MAB model with multiple plays. The proposed algorithm has an expected regret of the order O(log2T), which is validated by simulation results.

The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than η nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results.

An adversarial multi-user multi-armed bandit framework is used to develop algorithms for uncoordinated spectrum access. It is assumed that the number of users is unknown, and that users receive zero reward on collision. The users do not coordinate with each other, and an adversary chooses different rewards for different users on the same channel. The proposed algorithm combines the Exp3.P algorithm developed in prior work for single user adversarial bandits with a collision resolution mechanism to achieve sub-linear regret. It is shown that if every user employs the proposed algorithm, the system wide regret is of the order O(T3/4) over a horizon of time T. The algorithm is then extended to the dynamic case where the number of users in the system evolves over time, and it is shown to lead to sub-linear regret.

Model change detection is studied, in which there are two sets of samples that are independently and identically distributed (i.i.d.) according to a pre-change probabilistic model with parameter θ, and a post-change model with parameter θ', respectively. The goal is to detect whether the change in the model is significant, i.e., whether the difference between the pre-change parameter and the post-change parameter ∥θ - θ'∥2is larger than a pre-determined threshold ρ. The problem is considered in a Neyman-Pearson setting, where the goal is to maximize the probability of detection under a false alarm constraint. Since the generalized likelihood ratio test (GLRT) is difficult to compute in this problem, we construct an empirical difference test (EDT), which approximates the GLRT and has low computational complexity. Moreover, we provide an approximation method to set the threshold of the EDT to meet the false alarm constraint. Experiments with linear regression and logistic regression are conducted to validate the proposed algorithms.

The problem of quickest detection of significant events in networks is studied. A distributed setting is investigated, where there is no fusion center, and each node only communicates with its neighbors. After an event occurs in the network, a number of nodes are affected, which changes the statistics of their observations. The nodes may possibly perceive the event at different times. The goal is to design a distributed sequential detection rule that can detect when the event is "significant", i.e., the event has affected no less than η nodes, as quickly as possible, subject to false alarm constraints. A distributed algorithm is proposed, which is based on a novel combination of the alternating direction method of multipliers (ADMM) and average consensus approaches. Numerical results are provided to demonstrate the performance of the proposed algorithm.

A mutual information based upper bound on the generalization error of a supervised learning algorithm is derived in this paper. The bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm, which requires weaker conditions on the loss function, but provides a tighter characterization of the generalization error than existing studies. Examples are further provided to demonstrate that the bound derived in this paper is tighter, and has a broader range of applicability. Application to noisy and iterative algorithms, e.g., stochastic gradient Langevin dynamics (SGLD), is also studied, where the constructed bound provides a tighter characterization of the generalization error than existing results.

To be considered for the 2019 IEEE Jack Keil Wolf ISIT Student Paper Award. The problem of quickest detection of a moving target in sensor networks is studied. At some unknown time, a target emerges in the sensor network, and one of the sensors in the network is affected, whose data generating distribution undergoes a change. It is assumed that as the target moves around in the sensor network, the sensor that is affected by the target changes with time. Specifically, if a sensor becomes unaffected, then its data generating distribution changes back to the pre-change mode. A discrete time Markov chain is used to model the location of the affected sensor, and thus the data generating distribution of the sensor network after the target emerges is a hidden Markov model. The goal is to detect the existence of the target as quickly as possible subject to false alarm constraints. A windowed test based on a generalized likelihood ratio approach is constructed, and its asymptotic optimality is further established. Numerical results are provided to demonstrate its performance.

The problem of anomaly detection is considered when multiple processes are observed sequentially, but it is possible to sample only a subset of them at a time according to an adaptive sampling policy. The problem is to stop sampling as soon as possible and identify the anomalous processes, while controlling appropriate error probabilities. We consider two versions of this problem: in the first one there is no assumption regarding the anomalous processes, in the second their number is assumed to be known a priori. For each version, we obtain the optimal asymptotic performance as the error probabilities vanish and characterize the sampling rules that lead to asymptotic optimality. Moreover, we present two sampling rules for each setup, which differ in terms of the computational complexity and the actual performance they imply.

Degrees of freedom (DoFs) gains are studied in wireless networks with cooperative transmission under a backhaul load constraint that limits the average number of messages that can be delivered from a centralized controller to base station transmitters. The backhaul load is defined as the sum of all the messages available at all the transmitters per channel use, normalized by the number of users. For Wyner's linear interference network, where each transmitter is connected to the receiver having the same index as well as one succeeding receiver, the per user DoF is characterized and the optimal scheme is presented. Furthermore, it is shown that the optimal assignment of messages to transmitters is asymmetric and satisfies a local cooperation constraint and the optimal coding scheme relies only on one-shot cooperative zero-forcing transmit beamforming. Using insights from the analysis of Wyner's linear interference network, the results are extended to the more practical hexagonal sectored cellular network, and coding schemes based on cooperative zero-forcing are shown to deliver significant DoF gains. It is established that by allowing for cooperative transmission and a flexible message assignment that is constrained only by an average backhaul load, one can deliver the rate gains promised by information-theoretic upper bounds with practical one-shot schemes that incur little or no additional load on the backhaul. Finally, useful upper bounds on the per user DoF for schemes based on cooperative zero-forcing are presented for lower values of the average backhaul load constraint, and an optimization framework is formulated for the general converse problem.

The problem of quickest change detection under transient dynamics is studied, where the change from the initial distribution to the final persistent distribution does not happen instantaneously, but after a series of transient phases. The observations within the different phases are generated by different distributions. The objective is to detect the change as quickly as possible, while controlling the average run length (ARL) to false alarm, when the durations of the transient phases are completely unknown. Two algorithms are considered: the dynamic Cumulative Sum (CuSum) algorithm, proposed in earlier work, and a newly constructed weighted dynamic CuSum algorithm. Both algorithms admit recursions that facilitate their practical implementation, and they are adaptive to the unknown transient durations. Specifically, their asymptotic optimality is established with respect to both Lorden's and Pollak's criteria as the ARL to false alarm and the durations of the transient phases go to infinity at any relative rate. Numerical results are provided to demonstrate the adaptivity of the proposed algorithms and to validate the theoretical results.

We consider the problem of quickest detection of dynamic events in sensor networks. After an event occurs, a number of sensors are affected and undergo a change in the statistics of their observations. We assume that the event is dynamic and can propagate with time, i.e., different sensors perceive the event at different times. The goal is to design a sequential algorithm that can detect when the event has affected no less than η sensors as quickly as possible, subject to false alarm constraints. We design a computationally efficient algorithm that is adaptive to unknown propagation dynamics, and demonstrate its asymptotic optimality as the false alarm rate goes to zero. We also provide numerical simulations to validate our theoretical results.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

The problem of estimating the Kullback-Leibler divergence D(P∥Q) between two unknown distributions P and Q is studied, under the assumption that the alphabet size k of the distributions can scale to infinity. The estimation is based on m independent samples drawn from P and n independent samples drawn from Q. It is first shown that there does not exist any consistent estimator that guarantees asymptotically small worst case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions, with density ratio bounded by a function f (k) is further considered. An augmented plug-in estimator is proposed, and its worst case quadratic risk is shown to be within a constant factor of ((k/m) + (kf (k)/n))2+ (log2f (k)/m) + ( f (k)/n), if m and n exceed a constant factor of k and kf (k), respectively. Moreover, the minimax quadratic risk is characterized to be within a constant factor of ((k/(m log k)) + (kf (k)/(n log k)))2+ (log2f (k)/m) + ( f (k)/n), if m and n exceed a constant factor of k/ log(k) and kf (k)/ log k, respectively. The lower bound on the minimax quadratic risk is characterized by employing a generalized Le Cam's method. A minimax optimal estimator is then constructed by employing both the polynomial approximation and the plug-in approaches.

Degrees of freedom (DoF) is studied in the downlink of a heterogenous wireless network modeled as a two-layered interference network. The first layer of the interference network is the backhaul layer between macro base stations (MBs) and small cell base stations (SBs), which is modeled as a Wyner type linear network. The second layer is the transmission layer between SBs and mobile terminals (MTs), which is modeled as a linear Wyner LTnetwork. The SBs are assumed to be half-duplex, thus restricting the per user degrees of freedom (puDoF) in the system to 1/2. It is established that the optimal puDoF of 1/2 can be achieved in the linear network with sufficient number of antennas using only interference avoidance schemes. For the case of higher connectivity in the transmission layer, it is shown that the optimal puDoF is achieved by sending an appropriate linear combination to the SB to zero-force interference at the intended user. These results are also extended to a more realistic hexagonal cellular model.

In multichannel sequential change detection, multiple sensors monitor a system in which an abrupt change occurs at some unknown time and is perceived by an unknown subset of sensors. The goal is to detect this change quickly, while controlling the rate of false alarms. In the traditional asymptotic analysis of this problem, the false alarm rate goes to 0 while all other parameters remain fixed. We argue that this framework is not very informative, as the corresponding asymptotic optimality property cannot differentiate between universal and parsimonious rules. We propose an asymptotic framework in which the number of sensors also goes to infinity, and we show that in this context universal rules may fail to be asymptotically optimal when the number of streams is not very small. On the other hand, parsimonious rules are shown to be asymptotically optimal under reasonable sparsity conditions.

This paper considers the problem of quickest detection of a change in distribution under the assumption that the pre-change distribution π is known, and the post-change distribution μ is unknown and belongs to a general class of distributions. Using the knowledge of the pre-change distribution π, the sample space is partitioned into equiprobable intervals and the number of samples falling into each of these intervals is monitored to detect the change. A test statistic that approximates the generalized likelihood ratio test is proposed. A recursive update scheme to compute the statistic efficiently and an approximation of the average run-length to false alarm are also derived. Simulations show that our approach is comparable in performance to two other non-parametric quickest change detection methods if the change is either a shift in distribution mean or variance, respectively. But our method significantly outperforms them if these distribution change assumptions are violated.

The problem of transient quickest change detection (QCD) is studied, in which the change from the initial to the final phase does not happen instantaneously, but after a series of cascading transient phases of finite durations, each one corresponding to a different probability distribution. The goal is to design a stopping rule to detect the change as quickly as possible, subject to false alarm constraints. In previous work, the D-CuSum algorithm was proposed for such a QCD problem. The D-CuSum does not incorporate any prior statistical information about the durations of the transient periods. In this work, we develop an algorithm, the D-S-R algorithm, which incorporates geometric priors on the durations of the transient periods. We compare the D-CuSum and D-S-R algorithms in numerical examples to develop some insights about the role of the prior on the transient durations on the performance.

The downlink of a two-layered heterogeneous hexag- onal cellular network is studied with macro base stations (MB), small cell base stations (SB) that act as half duplex analog relays, and mobile terminals (MT). The first layer is a point- to-multipoint wireless backhaul between macro base stations and small cell base stations, and the second layer is the transmission layer between SBs and MTs. The wireless backhaul layer and the transmission layer use the same time/frequency resources for communication. The degrees of freedom (DoF) metric is used to characterize the capacity of the network at high signal to noise ratio (SNR). The maximum achievable per user DoF in the system is equal to half, due to the half-duplex nature of the SBs. The proposed schemes are simple zero forcing schemes that employ joint processing and achieve cooperation without overloading the wireless backhaul. This is achieved by sending an appropriate linear combination from the MBs that zero force (ZF) interference at the MTs directly. The achievable schemes exploit the half duplexity of the SBs in the system and schedule the SBs and MTs to be active in different time- slots in a smart manner to reduce interference. The optimal per user DoF of half can be approached in the hexagonal sectored cellular network using only zero forcing schemes, without the use of interference alignment.

We study a universal outlying sequence detection problem, in which there are M sequences of samples out of which a small subset of outliers need to be detected. A sequence is considered as an outlier if the observations therein are generated by a distribution different from those generating the observations in the majority of the sequences. In the universal setting, the goal is to identify all the outliers without any knowledge about the underlying generating distributions. In prior work, this problem was studied as a universal hypothesis testing problem, and a generalized likelihood (GL) test was constructed and its asymptotic performance characterized. In this paper, we propose a different class of tests for this problem based on distribution clustering. Such tests are shown to be exponentially consistent and their time complexity is linear in the total number of sequences, in contrast with the GL test, which has time complexity that is exponential in the number of outliers. Furthermore, our tests based on clustering are applicable to more general scenarios. For example, when both the typical and outlier distributions form clusters, the clustering based test is exponentially consistent, but the GL test is not even applicable.

We study the problem of testing between a sparse signal in noise, modeled as a mixture distribution, versus pure noise, with a Gaussian signal and noise of same variance, but differing means as the mixture proportion tends to zero. We construct a simple new adaptive test based on quantizing data with sample size-dependent quantizers and prove its consistency. The proposed test has almost linear time complexity and sublinear space complexity, which is better than existing tests, and in particular, the celebrated Higher Criticism test. Moreover, our numerical results show that the proposed test is competitive with commonly used tests even with a small number of quantizer levels.

The problem of quickest change detection (QCD) under transient dynamics is studied, in which the change from the initial distribution to the final persistent distribution does not happen instantaneously, but after a series of cascading transient phases. It is assumed that the durations of the transient phases are deterministic but unknown. The goal is to detect the change as quickly as possible subject to a constraint on the average run length to false alarm. The dynamic CuSum (D-CuSum) algorithm is investigated, which is based on reformulating the QCD problem into a dynamic composite hypothesis testing problem, and has a recursion that facilitates implementation. We show that this algorithm is adaptive to the unknown change point, as well as the unknown transient duration. And under mild conditions of the pre-change and post-change distributions, its asymptotic optimality is demonstrated for all possible asymptotic regimes as the transient duration and the average run length to false alarm go to infinity.

The following detection problem is studied, in which there are M sequences of samples out of which one outlier sequence needs to be detected. Each typical sequence contains n independent and identically distributed (i.i.d.) continuous observations from a known distribution π, and the outlier sequence contains n i.i.d. observations from an outlier distribution μ, which is distinct from n, but otherwise unknown. A universal test based on Kullback-Leibler (KL) divergence is built to approximate the maximum likelihood test, with known π and unknown μ. A KL divergence estimator based on data-dependent partitions is employed, and is shown to converge to its true value exponentially fast when the density ratio satisfies 0 <; Kl ≤ dμ/dπ ≤ K2, where K1 and K2 are positive constants. The performance of such a KL divergence estimator further implies that the outlier detection test is exponentially consistent. The detection performance of the KL divergence based test is compared with that of a recently introduced test for this problem based on the machine learning approach of maximum mean discrepancy (MMD). Regimes in which the KL divergence based test is better than the MMD based test are identified.

Multiple observation sequences are collected, among which there is a small subset of outliers. A sequence is considered an outlier if the observations therein are generated by a mechanism different from that generating the observations in the majority of sequences. In the universal setting, the goal is to identify all the outliers without any knowledge about the underlying generating mechanisms. In prior work, this problem was studied as a universal hypothesis testing problem, and a generalized likelihood test was constructed and its asymptotic performance characterized. Here a connection is made between the generalized likelihood test and clustering algorithms from machine learning. It is shown that the generalized likelihood test is equivalent to combinatorial clustering over the probability simplex with the Kullback-Leibler divergence being the dissimilarity measure. Applied to synthetic data sets for outlier hypothesis testing, the performance of the generalized likelihood test is shown to be superior to that of a number of other clustering algorithms for sufficiently large sample sizes.

In this paper, we study the rate of decay of the probability of error for distinguishing between a sparse signal with noise, modeled as a sparse mixture, from pure noise. This problem has many applications in signal processing, evolutionary biology, bioinformatics, astrophysics and feature selection for machine learning. We let the mixture probability tend to zero as the number of observations tends to infinity and derive oracle rates at which the error probability can be driven to zero for a general class of signal and noise distributions. In contrast to the problem of detection of non-sparse signals, we see the log-probability of error decays sublinearly rather than linearly and is characterized through the x2-divergence rather than the Kullback-Leibler divergence. This work provides the first characterization of the rate of decay of the error probability for this problem.

We propose a statistical algorithm for detecting line outages in a power system and show that it has better performance than other schemes proposed in the literature. Our algorithm is based on the Cumulative Sum (CuSum) test from the Quickest Change Detection (QCD) literature. It exploits the statistical properties of the measured voltage phase angles before, during, and after a line outage, whereas other methods in the literature only utilize the change in statistics that occurs at the instant of outage.

A framework is introduced for solving a sequence of slowly changing optimization problems, including those arising in regression and classification applications, using optimization algorithms such as stochastic gradient descent (SGD). The optimization problems change slowly in the sense that the minimizers change at either a fixed or bounded rate. A method based on estimates of the change in the minimizers and properties of the optimization algorithm is introduced for adaptively selecting the number of samples needed from the distributions underlying each problem in order to ensure that the excess risk, i.e., the expected gap between the loss achieved by the approximate minimizer produced by the optimization algorithm and the exact minimizer, does not exceed a target level. Experiments with synthetic and real data are used to confirm that this approach performs well.

The problem of estimating the KL divergence between two unknown distributions is studied. The alphabet size k of the distributions can scale to infinity. The estimation is based on m and n independent samples respectively drawn from the two distributions. It is first shown that there does not exist any consistent estimator to guarantee asymptotic small worst-case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions with bounded ratio f(k) is further considered. An augmented plug-in estimator is proposed, and is shown to be consistent if and only if m = ω(k ⋁ log2(f(k)) and n = ω(k f(k)). Furthermore, if f(k) ≥ log2k and log2(f(k)) = o(k), it is shown that any consistent estimator must satisfy the necessary conditions: m = ω( k/log k ⋁ log2(f(k)) and n = ω( k f(k)/log k).

We are interested in the sequential detection of a change in the statistical behavior of a random process. Specifically we consider changes that are not abrupt but exhibit a transitory phase before reaching their steady-state behavior. Adopting the classical worst-case conditional detection delay proposed by Lorden as our performance measure and constraining the average false-alarm period, we derive the sequential test that optimizes, in the exact sense, the proposed criterion. The resulting optimum rule resembles the well known CUSUM rule with the corresponding test-statistic-update being not only a function of all pre- and post-change pdfs but also of the false-alarm constraint.

Estimation in a two node sensor network is considered, with one sensor of high quality but potentially affected by an adversary and one sensor of low quality but immune to the actions of the adversary. The observations of the sensors are combined at a fusion center to produce a minimum mean square error (MSE) estimate taking into account the actions of the adversary. An approach based on hypothesis testing is introduced to decide whether the high quality sensor should be used. The false alarm probability of the hypothesis test introduces a natural trade-off between the MSE performance when the adversary takes no action and when the adversary acts. Finally, a method is developed to select the false alarm probability robustly to ensure good performance regardless of the adversary's action.

BACKGROUND: Metagenomics is a genomics research discipline devoted to the study of microbial communities in environmental samples and human and animal organs and tissues. Sequenced metagenomic samples usually comprise reads from a large number of different bacterial communities and hence tend to result in large file sizes, typically ranging between 1-10 GB. This leads to challenges in analyzing, transferring and storing metagenomic data. In order to overcome these data processing issues, we introduce MetaCRAM, the first de novo, parallelized software suite specialized for FASTA and FASTQ format metagenomic read processing and lossless compression. RESULTS: MetaCRAM integrates algorithms for taxonomy identification and assembly, and introduces parallel execution methods; furthermore, it enables genome reference selection and CRAM based compression. MetaCRAM also uses novel reference-based compression methods designed through extensive studies of integer compression techniques and through fitting of empirical distributions of metagenomic read-reference positions. MetaCRAM is a lossless method compatible with standard CRAM formats, and it allows for fast selection of relevant files in the compressed domain via maintenance of taxonomy information. The performance of MetaCRAM as a stand-alone compression platform was evaluated on various metagenomic samples from the NCBI Sequence Read Archive, suggesting 2- to 4-fold compression ratio improvements compared to gzip. On average, the compressed file sizes were 2-13 percent of the original raw metagenomic file sizes. CONCLUSIONS: We described the first architecture for reference-based, lossless compression of metagenomic data. The compression scheme proposed offers significantly improved compression ratios as compared to off-the-shelf methods such as zip programs. Furthermore, it enables running different components in parallel and it provides the user with taxonomic and assembly information generated during execution of the compression pipeline. AVAILABILITY: The MetaCRAM software is freely available at http://web.engr.illinois.edu/~mkim158/metacram.html. The website also contains a README file and other relevant instructions for running the code. Note that to run the code one needs a minimum of 16 GB of RAM. In addition, virtual box is set up on a 4GB RAM machine for users to run a simple demonstration.

In outlier hypothesis testing, multiple observation sequences are collected, a small subset of which are outliers. Observations in an outlier sequence are generated by a mechanism different from that generating the observations in the majority of sequences. The goal is to best discern all the outlier sequences without any knowledge of the underlying generating mechanisms. A generalized likelihood test is considered in the fixed sample size setting. In the sequential setting, a test based on the Multihypothesis Sequential Probability Ratio Test and the repeated significance test is considered. The sequential test outperforms the generalized likelihood test when the lengths of the observation sequences exceed certain values. Applied to a real data set for spam detection, the performance of the proposed tests is shown to be superior to those based on the maximum mean discrepancy for large sample size.

We propose a novel interference management framework for the cellular downlink through cooperative transmission. A sectored cellular network is studied where the interference is only due to sectors in neighboring cells and intra cell interference is ignored. We first explore the potential degrees of freedom (DoF) gain in a scenario where mobile receivers can be associated to any neighboring cell but no cooperative transmission is allowed. We show that the maximum achievable per user DoF for orthogonal schemes is between 1/3 and 3/7. On the other hand, if cooperative transmission is combined with flexible message assignment to the transmitters, we show that it is possible to achieve a per user DoF of 7/15. In addition, the proposed cooperative transmission scheme does not require extra backhaul capacity, as it uses a smart assignment of messages to transmitters to meet an average backhaul load constraint of one message per transmitter.

Quickest outlier detection and isolation is studied in universal settings. Initially, multiple data streams are commonly distributed according to a “typical” distribution. At the change time, an outlier stream emerges and starts to be distributed according to the “outlier” distribution, while the rest of the streams remain to be distributed according to the typical one. Two tests are proposed to quickly isolate the outlier. The first test is shown to be asymptotically optimal universally when only the typical distribution is known, and in the limit of the large number of streams when neither the outlier nor typical distribution is known. The performance of the second test, which is more practical, is also characterized.

The problem of quickest change detection is studied, where there is an additional constraint on the cost of observations used before the change point and where the post-change distribution is composite. Minimax formulations are proposed for this problem. It is assumed that the post-change family of distributions has a member which is least favorable in a well-defined sense. An algorithm is proposed in which ON-OFF observation control is employed using the least favorable distribution, and a generalized likelihood ratio-based approach is used for change detection. Under additional conditions on the post-change family of distributions, it is shown that the proposed algorithm is asymptotically optimal, uniformly for all possible post-change distributions.

A method to detect and isolate power system transmission line outages in near real-time is proposed. In particular, a linearized power system model is presented and a statistical model for line outage detection and isolation is developed using this model. To detect and isolate the line outage quickly, algorithms based on statistical quickest change detection are employed.

The problem of quickest change detection is studied, where there is an additional constraint on the cost of observations used before the change point and where the post-change distribution is unknown. An algorithm is proposed for the case where there are finite number of possibilities for the unknown post-change distribution. It is shown that if the post-change family of distributions satisfies some additional conditions, then the proposed algorithm is asymptotically optimal uniformly for all possible post-change distributions.

The considered problem is that of maximizing the degrees of freedom (DoF) in cellular downlink, under a backhaul load constraint that limits the number of messages that can be delivered from a centralized controller to the base station transmitters. A linear interference channel model is considered, where each transmitter is connected to the receiver having the same index as well as one succeeding receiver. The backhaul load is defined as the sum of all the messages available at all the transmitters normalized by the number of users. When the backhaul load is constrained to an integer level B, the asymptotic per user DoF is shown to equal equation, and it is shown that the optimal assignment of messages to transmitters is asymmetric and satisfies a local cooperation constraint and that the optimal coding scheme relies only on zero-forcing transmit beamforming. Finally, an extension of the presented coding scheme for the case where B = 1 is shown to apply for more general locally connected and two-dimensional networks.

Welcome to Paradise. It is our utmost pleasure to welcome you to the city of Honolulu, Hawaii and to the 2014 IEEE International Symposium on Information Theory. We hope that you will find the Symposium technically rewarding and the Hawaiian nature/ambiance equally interesting.

Universal outlier hypothesis testing is studied in a sequential setting. Multiple observation sequences are collected, one of which is an outlier. Observations in the outlier sequence are generated by a unique mechanism, different from that generating the observations in all other sequences. The goal is to design a universal test to best discern the outlier sequence with the fewest observations on average. Based on the Multihypothesis Sequential Probability Ratio Test and the generalized likelihood test, a universal test is proposed and shown to be universally exponentially consistent. A lower bound on the achievable error exponents of such a test is derived. The proposed test can be modified to accommodate an additional null hypothesis with no outlier. In particular, it is shown to be consistent under the null hypothesis while retaining universally exponential consistency under all other hypotheses.

The multiple-input-multiple-output (MIMO) interference channel (IC) is considered with constant channel coefficients, N transmit and receive antennas at each user, and coordinated multipoint (CoMP) transmission, in which each message is jointly transmitted by Mt successive transmitters. It is shown that the degrees of freedom with CoMP transmission using a two-stage scheme involving both zero forcing and interference alignment can be significantly greater than without CoMP transmission. In particular, all K users can achieve d degrees of freedom almost surely if d ≤ ⌊(2N)/(K - Mt+ 1)⌋ and Mt≤ K - 2. Additionally, the first Mt- 1 users can achieve d1degrees of freedom, and the last K - Mt+ 1 users can achieve d2degrees of freedom almost surely if d2≤ ⌊(2N)/(K -Mt+1)⌋, Mt≤ K - 2, and d1+ (K - Mt+ 1) d2≤ 2N. Next, the analysis of the constant MIMO IC with CoMP transmission is applied to the development of iterative algorithms to design transmit and receive vectors analogous to those without CoMP transmission. The degrees of freedom analysis is shown through simulations to provide a good guideline for choosing how many beams each user should send for the iterative algorithms. Furthermore, it is seen in the numerical results that CoMP transmission can result in greatly improved convergence speed for the iterative interference alignment algorithms.

Coordinated multipoint (CoMP) transmission is an infrastructural enhancement under consideration for next generation wireless networks. In this paper, the capacity gain achieved through CoMP transmission is studied in various models of wireless networks that have practical significance. The capacity gain is analyzed through the degrees of freedom (DoF) criterion. The DoF available for communication provides an analytically tractable way to characterize the capacity of interference channels. The considered channel model has K transmitter/receiver pairs, and each receiver is interested in one unique message from a set of K independent messages. Each message can be available at more than one transmitter. The maximum number of transmitters at which each message can be available, is defined as the cooperation order M. For fully connected interference channels, it is shown that the asymptotic per user DoF, as K goes to infinity, remains at 1/2 as M is increased from 1 to 2. Furthermore, the same negative result is shown to hold for all M ≥ 2 for any message assignment that satisfies a local cooperation constraint. On the other hand, when the assumption of full connectivity is relaxed to local connectivity, and each transmitter is connected only to its own receiver as well as L neighboring receivers, it is shown that local cooperation is optimal. The asymptotic per user DoF is shown to be at least max {1/2, 2M/(2M + L)} for locally connected channels, and is shown to be 2M/(2M + 1) for the special case of Wyner's asymmetric model where L = 1. An interesting feature of the proposed achievability scheme is that it relies on simple zero-forcing transmit beams and does not require symbol extensions. Also, to achieve the optimal per user DoF for Wyner's model, messages are assigned to transmitters in an asymmetric fashion unlike traditional assignments where message i has to be available at transmitter i. It is also worth noting that some receivers have to be inactive, and fractional reuse is needed to achieve equal DoF for all users.

Outlier hypothesis testing is studied in a universal setting. Multiple sequences of observations are collected, a small subset of which are outliers. A sequence is considered an outlier if the observations in that sequence are distributed according to an outlier distribution, distinct from the typical distribution governing the observations in all the other sequences. Nothing is known about the outlier and typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier sequence(s). For models with exactly one outlier sequence, the generalized likelihood test is shown to be universally exponentially consistent. A single-letter characterization of the error exponent achievable by the test is derived, and it is shown that the test achieves the optimal error exponent asymptotically as the number of sequences approaches infinity. When the null hypothesis with no outlier is included, a modification of the generalized likelihood test is shown to achieve the same error exponent under each non-null hypothesis, and also consistency under the null hypothesis. Then, models with more than one outlier are studied in the following settings. For the setting with a known number of distinctly distributed outliers, the achievable error exponent of the generalized likelihood test is characterized. The limiting error exponent achieved by such a test is characterized, and the test is shown to be asymptotically exponentially consistent. For the setting with an unknown number of identically distributed outliers, a modification of the generalized likelihood test is shown to achieve a positive error exponent under each non-null hypothesis, and also consistency under the null hypothesis. When the outlier sequences can be distinctly distributed (with their total number being unknown), it is shown that a universally exponentially consistent test cannot exist, even when the typical distribution is known and the null hypothesis is excluded.

A distributed or multi-channel system consisting of multiple sensors is considered. At each sensor a sequence of observations is taken, and at each time step, a summary of available information is sent to a central decision maker, called the fusion center. At some point of time, the distribution of observations at an unknown subset of the sensor nodes changes. The objective is to detect this change as quickly as possible, subject to constraints on the false alarm rate, the cost of observations taken at the sensors and the cost of communication between the sensors and the fusion center. Minimax formulations are proposed for this problem. An algorithm called DE-Censor-Sum is proposed, and is shown to be asymptotically optimal for the proposed formulations, for each possible post-change scenario, as the false alarm rate goes to zero. It is also shown, via numerical studies, that the DE-Censor-Sum algorithm performs significantly better than the approach of fractional sampling, where the cost constraints are met based on the outcome of a sequence of biased coin tosses, independent of the observation process.

An energy efficient sleep control algorithm is developed for application to the tracking problem in a wireless sensor network. This simple algorithm applies intuition gained by examining a more complicated dynamic programming solution approximation. The algorithm is shown through simulation analysis to exhibit improved efficiency beyond simple sensor duty cycling, very nearly achieving the effectiveness of the original dynamic programming solution. Additionally a testbed is developed specifically to evaluate the feasibility of implementation of the algorithm on a physical system. The algorithm is shown to work on this testbed, successfully tracking a light source in the network.

The problem of classifying graphs with respect to connectivity via partial observations of nodes is posed as a composite hypothesis testing problem with controlled sensing. An observation at a node is a subset of edges incident to the node on the complete graph drawn according to a probability model, which are modeled as conditionally independent given their neighborhoods. Connectivity is measured through average node degree and is classified with respect to a threshold. A simple approximation of the controlled sensing test is derived and simulated on Erdös-Rènyi Model A graphs to characterize error probabilities as a function of expected stopping times. It is shown that the proposed test achieves favorable tradeoffs between the classification error and the number of measurements and further outperforms existing approaches, especially at low target error rates. Furthermore, the proposed test achieves asymptotically optimal error performance, as the error rate goes to zero.

The problem of decentralized quickest change detection is studied with an additional constraint on the cost of observations used at each sensor. Minimax problem formulations are proposed for the problem. A distributed algorithm called the DE-All algorithm is proposed in which on-off observation control is employed locally at each sensor. It is shown that the proposed algorithm is asymptotically optimal up to first order for the proposed formulations.

The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M ≥ 3 coordinates. When a given coordinate is the outlier, the observations in that coordinate are assumed to be distributed according to the “outlier” distribution, distinct from the common “typical” distribution governing the observations in all the other coordinates. Nothing is known about the outlier and the typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier coordinate. A universal test based on the generalized likelihood principle is proposed and is shown to be universally exponentially consistent, and a single-letter characterization of the error exponent achievable by the test is derived. It is shown that as the number of coordinates approaches infinity, our universal test is asymptotically efficient. Specifically, it achieves a limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known.

A new model for controlled sensing for multiphypothesis testing is proposed and studied in both the sequential and fixed sample size settings. This new model, termed a stationary Markov model, exhibits a more complicated memory structure in the controlled observations than the existing stationary memoryless model. In the sequential setting, an asymptotically optimal sequential test using a stationary causal Markov control policy enjoying a strong asymptotic optimality condition is proposed for this new model, and its asymptotic performance is characterized. In the fixed sample size setting, bounds for the optimal error exponent for binary hypothesis testing are derived; it is conjectured that the structure of the asymptotically optimal control for the stationary Markov model will be much more complicated than that for the stationary memoryless model.

Metagenomics is an emerging field of molecular biology concerned with analyzing the genomes of environmental samples comprising many different diverse organisms. Given the nature of metagenomic data, one usually has to sequence the genomic material of all organisms in a batch, leading to a mix of reads coming from different DNA sequences. In deep high-throughput sequencing experiments, the volume of the raw reads is extremely high, frequently exceeding 600 Gb. With an ever increasing demand for storing such reads for future studies, the issue of efficient metagenomic compression becomes of paramount importance. We present the first known approach to metagenome read compression, termed MCUIUC (Metagenomic Compression at UIUC). The gist of the proposed algorithm is to perform classification of reads based on unique organism identifiers, followed by reference-based alignment of reads for individually identified organisms, and metagenomic assembly of unclassified reads. Once assembly and classification are completed, lossless reference based compression is performed via positional encoding. We evaluate the performance of the algorithm on moderate sized synthetic metagenomic samples involving 15 randomly selected organisms and describe future directions for improving the proposed compression method.

The classical problem of quickest change detection is studied with an additional constraint on the cost of observations used in the detection process. The change point is modeled as an unknown constant, and minimax formulations are proposed for the problem. The objective in these formulations is to find a stopping time and an ON-OFF observation control policy for the observation sequence, to minimize a version of the worst possible average delay, subject to constraints on the false alarm rate and the fraction of time observations are taken before change. An algorithm called DE-CuSum is proposed and is shown to be asymptotically optimal for the proposed formulations, as the false alarm rate goes to zero. Numerical results are used to show that the DE-CuSum algorithm has good tradeoff curves and performs significantly better than the approach of fractional sampling, in which the observations are skipped using the outcome of a sequence of coin tosses, independent of the observation process. This study is guided by the insights gained from an earlier study of a Bayesian version of this problem.

A Rayleigh fading spatially correlated broadcast setting with$M = 2$antennas at the transmitter and two users (each with a single antenna) is considered. It is assumed that the users have perfect channel information about their links, whereas the transmitter has only statistical information of each user's link (covariance matrix of the vector channel). A low-complexity linear beamforming strategy that allocates equal power and one spatial eigenmode to each user is employed at the transmitter. Beamforming vectors on the Grassmann manifold that depend only on statistical information are to be designed at the transmitter to maximize the ergodic sum-rate delivered to the two users. Toward this goal, the beamforming vectors are first fixed and a closed-form expression is obtained for the ergodic sum-rate in terms of the covariance matrices of the links. This expression is nonconvex in the beamforming vectors ensuring that the classical Lagrange multiplier technique is not applicable. Despite this difficulty, the optimal solution to this problem is shown to be the same as the solution to the maximization of an appropriately defined average signal-to-interference and noise ratio metric for each user. This solution is the dominant generalized eigenvector of a pair of positive-definite matrices where the first matrix is the covariance matrix of the forward link and the second is an appropriately designed “effective” interference covariance matrix. In this sense, our work is a generalization of optimal signalling along the dominant eigenmode of the transmit covariance matrix in the single-user case. Finally, the ergodic sum-rate for the general broadcast setting with$M$antennas at the transmitter and$M$-users (each with a single antenna) is obtained in terms of the covariance matrices of the links and the beamforming vectors.

The ensemble properties of random vector quantization (RVQ) codebooks for limited-feedback beamforming in multiinput multioutput (MIMO) systems are studied with the metrics of interest being the received \ssr SNR loss and mutual information loss, both relative to a perfect channel state information (CSI) benchmark. The simplest case of unskewed codebooks is first studied in the correlated MIMO setting and these loss metrics are computed as a function of the number of bits of feedback ( B), transmit antenna dimension ( Nt), and spatial correlation. In particular, it is established that: 1) the loss metrics are a product of two components-a quantization component and a channel-dependent component; 2) the quantization component, which is also common to analysis of channels with i.i.d. fading, decays as B increases at the rate 2-B/(Nt-1); 3) the channel-dependent component reflects the condition number of the channel. Further, the precise connection between the received \ssr SNR loss and the squared singular values of the channel is shown to be a Schur-convex majorization relationship. Finally, the ensemble properties of skewed codebooks that are generated by skewing RVQ codebooks with an appropriately designed fixed skewing matrix are studied. Based on an estimate of the loss expression for skewed codebooks, it is established that the structure of a good skewing matrix is critically dependent on the condition numbers of the effective channel (product of the true channel and the skewing matrix) and the skewing matrix.

The problem of designing linear transmit signaling strategies for the multiple input, multiple output (MIMO) interference channel is considered. For this problem, the best known iterative solution, in terms of maximizing signal to interference plus noise ratio (SINR) at the receivers, is the Max SINR algorithm. However, there is no proof that the Max SINR algorithm converges. In this paper, a modification to the Max SINR algorithm is proposed, in which a power control step is used to make a metric similar to the sum rate increase monotonically with each iteration, thus making the modified Max SINR algorithm convergent. It is further shown that with successive interference cancellation (SIC), the metric that the modified Max SINR algorithm optimizes is exactly the sum rate. Finally, simulations are used to demonstrate that the performance of the modified Max SINR algorithm, unlike other convergent alternatives, is nearly identical to that of the original Max SINR algorithm.

In [1], a Bayesian two-threshold algorithm was obtained for quickest detection of a change in the distribution of a sequence of random variables, subject to constraints of probability of false alarm and observation cost. This algorithm was shown to be asymptotically optimal and to have good trade-off curves. In this paper, the results in [1] are extended to the more practically relevant minimax setting. Motivated by the structure of the algorithm developed in [1], a CUSUM based algorithm, called DE-CUSUM is proposed, which can be used for on-off observation control and to detect change as quickly as possible subject to a false alarm constraint. It is shown that the DE-CUSUM algorithm inherits the good qualities of the algorithm in [1], i.e., it is also asymptotically optimal and has good trade-off curves. Numerical results show that the DE-CUSUM algorithm provides a substantial savings in the observation cost over the naive approach of fractional sampling.

In this paper, the problem of multiple hypothesis testing with observation control is considered. The structure of the optimal controller under various asymptotic regimes is studied. First, a setup with a fixed sample size is considered. In this setup, the asymptotic quantity of interest is the optimal exponent for the maximal error probability. For the case of binary hypothesis testing, it is shown that the optimal error exponent corresponds to the maximum Chernoff information over the choice of controls. It is also shown that a pure stationary control policy, i.e., a fixed policy which does not depend on specific realizations of past measurements and past controls (open-loop), is asymptotically optimal even among the class of all causal control policies. We also derive lower and upper bounds for the optimal error exponent for the case of multiple hypothesis testing. Second, a sequential setup is considered wherein the controller can also decide when to stop taking observations. In this case, the objective is to minimize the expected stopping time subject to the constraints of vanishing error probabilities under each hypothesis. A sequential test is proposed for testing multiple hypotheses and is shown to be asymptotically optimal.

The degrees of freedom (DoF) available for communication provides an analytically tractable way to characterize the information-theoretic capacity of interference channels. In this paper, the DoF of a K-user interference channel is studied under the assumption that the transmitters can cooperate via coordinated multi-point (CoMP) transmission. In [1], the authors considered the linear asymmetric model of Wyner, where each transmitter is connected to its own receiver and its successor, and is aware of its own message as well as M − 1 preceding messages. The per user DoF was shown to go to M/M+1 as the number of users increases to infinity. In this work, the same model of channel connectivity is considered, with a relaxed cooperation constraint that bounds the maximum number of transmitters at which each message can be available, by a cooperation order M. We show that the relaxation of the cooperation constraint, while maintaining the same load imposed on a backhaul link needed to distribute the messages, results in a gain in the DoF. In particular, the asymptotic limit of the per user DoF under the cooperation order constraint is 2M/2M+1. Moreover, the optimal transmit set selection satisfies a local cooperation constraint. i.e., each message needs only to be available at neighboring transmitters.

The problem of controlled sensing for multihypothesis testing is considered. Prior to decision making, a controller sequentially chooses among a set of control actions to shape the quality of the observations. The goal is to design an efficient control policy, a stopping rule and a final decision rule, to minimize the expected stopping time subject to hard constraints on the risks associated with wrong decisions about each hypothesis. We propose a sequential test, which is shown to be asymptotically optimal when the risks are sufficiently small. Optimality is based on a derived lower bound on the minimum expected stopping time of tests in the class of tests satisfying the predefined risk constraints. Furthermore, by viewing the variable-length coding problem as a special case of sequential multihypothesis testing with observation control, we recover the classic result of Burnašev on the expected coding length for variable-length coding over Discrete Memoryless Channels (DMCs) at zero rate.

We consider locally connected K-user MISO interference channels where each transmitter has N antennas and is connected to the receiver with the same index as well as [L/2] successively preceding receivers and [L/2] following receivers. We assume that each receiver is interested in one message, which can be available at a maximum of M transmitters. Under these assumptions, we study the available degrees of freedom as well as the optimal way to assign messages to transmitters. For the case where each message is assigned to the transmitter with the same index, we know from [1] that [KN/N+1] DoF is achievable for the considered locally connected channel using interference alignment as the number of symbol extensions goes to infinity. In this work, we show that a simple linear strategy employing zero forcing transmit beams achieves min {2MN/M(N+1)+L, 1} per user degrees of freedom. In particular, the N/N+1 per user DoF is achievable by coding over only one channel realization, for any value of M ≥ L/N+1. Moreover, we show that the proposed scheme is optimal among a class of linear strategies where each receiver is either inactive or enjoys interference-free communication. Finally, we generalize the upper bound proved for Wyner's asymmetric channel model (L = 1) in [2], and show that message assignments satisfying a local cooperation constraint are optimal for a general setting of the parameters.

We study the degrees of freedom (DoF) of the$K$-user interference channel with coordinated multipoint (CoMP) transmission and reception. Each message is jointly transmitted by$M_{t}$successive transmitters, and is jointly received by$M_{r}$successive receivers. We refer to this channel as the CoMP channel with a transmit cooperation order of$M_{t}$and receive cooperation order of$M_{r}$. Since the channel has a total of$K$transmit antennas and$K$receive antennas, the maximum possible DoF is equal to$K$. We show that the CoMP channel has$K$DoF if and only if$M_{t} + M_{r} \geq K+1$. The key idea is that the zero forcing of the interference corresponding to the$i{{\rm th}}$message at the decoder of the$j{{\rm th}}$message, where$j \ne i$, can be viewed as a shared responsibility between the$M_{t}$transmitters carrying the$i{{\rm th}}$message, and the$M_{r}$receivers decoding the$j{{\rm th}}$message. For the general case, we derive an outer bound that states that the DoF is bounded above by$\left \lceil (K+M_{t}+M_{r}-2)/2\right \rceil$. For the special case with only CoMP transmission, i.e,$M_{r} = 1$, we propose a scheme that can achieve$(K+M_{t}-1)/2$DoF for all$K < 10$, and conjecture that the result holds true for all$K$. In the proposed coding scheme, the$M_{t}$transmitters carrying each message are used to cancel the interference introduced by this message at the first$M_{t}-1$receivers, thereby allowing each of these receivers to enjoy 1 DoF, and asymptotic interference alignment is used to align the interfering signals at each other receiver to occupy half the signal space. The achievability proofs are based on the notion of algebraic independence from algebraic geometry.

We study the degrees of freedom (DoF) of a Gaussian interference network with K transmitters and K receivers, where the transmitters are allowed to cooperate (partially) to transmit information to the receivers.

We consider the problem of designing signals to transmit over the MIMO interference channel by extending the Max SINR algorithm. The Max SINR algorithm starts with arbitrary beamformers and then designs optimal receivers to maximize the SINR at each receiver. The Max SINR algorithm then alternates the direction of communication and repeats this process. This algorithm is known to perform well but there is no proof that it converges. We propose a modification to Max SINR using a power control step to make a metric similar to the sum rate converge. If we also use successive interference cancellation(SIC), then our metric is exactly the sum rate. We show via simulations that performance of the modified Max SINR algorithm, unlike the other convergent alternatives, is nearly identical to that of the original Max SINR algorithm.

Using Gaussian inputs and treating interference as noise at the receivers has recently been shown to be sum capacity achieving for the two-user single-input single-output (SISO) Gaussian interference channel in a low interference regime, where the interference levels are below certain thresholds. In this paper, such a low interference regime is characterized for multiple-input multiple-output (MIMO) Gaussian interference channels. Conditions are provided on the direct and cross channel gain matrices under which using Gaussian inputs and treating interference as noise at the receivers is sum capacity achieving. For the special cases of the symmetric multiple-input single-output (MISO) and single-input multiple-output (SIMO) Gaussian interference channels, more explicit expressions for the low interference regime are derived. In particular, the threshold on the interference levels that characterize low interference regime is related to the input SNR and the angle between the direct and cross channel gain vectors. It is shown that the low interference regime can be quite significant for MIMO interference channels, with the low interference threshold being at least as large as the sine of the angle between the direct and cross channel gain vectors for the MISO and SIMO cases.

The focus of this paper is on spatial precoding in correlated multiantenna channels where the number of data-streams is adapted independent of the number of transmit antennas. Towards the goal of a low-complexity implementation, a statistical semiunitary precoder is studied where the precoder matrix evolves fairly slowly with respect to the channel evolution. While prior work on statistical precoding has focussed on information-theoretic limits, most of these computations result in complicated functional dependencies of the mutual information with the channel statistics that do not explicitly reveal the impact of statistics on performance. In contrast, estimates that are directly in terms of the channel statistics are obtained here for the relative mutual information loss of a semiunitary precoder with respect to a perfect channel information benchmark. Based on these estimates, matching metrics are developed that capture the degree of matching of a channel to the precoder structure continuously and allow ordering two matrix channels in terms of their mutual information performance. While these metrics are based on bounds, numerical studies are used to show that the proposed metrics capture the performance tradeoffs accurately. The main conclusion of this work is a simple-to-state fundamental principle in the context of signaling design for single-user MIMO systems: the best channel for the statistical precoder is the channel that is matched to it.

For the universal hypothesis testing problem, where the goal is to decide between the known null hypothesis distribution and some other unknown distribution, Hoeffding proposed a universal test in the nineteen sixties. Hoeffding's universal test statistic can be written in terms of Kullback-Leibler (K-L) divergence between the empirical distribution of the observations and the null hypothesis distribution. In this paper a modification of Hoeffding's test is considered based on a relaxation of the K-L divergence, referred to as the mismatched divergence. The resulting mismatched test is shown to be a generalized likelihood-ratio test (GLRT) for the case where the alternate distribution lies in a parametric family of distributions characterized by a finite-dimensional parameter, i.e., it is a solution to the corresponding composite hypothesis testing problem. For certain choices of the alternate distribution, it is shown that both the Hoeffding test and the mismatched test have the same asymptotic performance in terms of error exponents. A consequence of this result is that the GLRT is optimal in differentiating a particular distribution from others in an exponential family. It is also shown that the mismatched test has a significant advantage over the Hoeffding test in terms of finite sample size performance for applications involving large alphabet distributions. This advantage is due to the difference in the asymptotic variances of the two test statistics under the null hypothesis.

The popular criteria of optimality for quickest change detection procedures are the Lorden criterion, the Pollak criterion, and the Bayesian criterion. In this paper, a robust version of these quickest change detection problems is considered when the pre-change and post-change distributions are not known exactly but belong to known uncertainty classes of distributions. For uncertainty classes that satisfy a specific condition, it is shown that one can identify least favorable distributions (LFDs) from the uncertainty classes, such that the detection rule designed for the LFDs is optimal for the robust problem in a minimax sense. The condition is similar to that required for the identification of LFDs for the robust hypothesis testing problem originally studied by Huber. An upper bound on the delay incurred by the robust test is also obtained in the asymptotic setting under the Lorden criterion of optimality. This bound quantifies the delay penalty incurred to guarantee robustness. When the LFDs can be identified, the proposed test is easier to implement than the CUSUM test based on the Generalized Likelihood Ratio (GLR) statistic which is a popular approach for such robust change detection problems. The proposed test is also shown to give better performance than the GLR test in simulations for some parameter values.

We consider the K-user Gaussian interference channel in the context of the downlink of a cellular system where the base stations can exchange messages through a backhaul network, and the interfering users can be jointly served by multiple base stations. To limit the load on the backhaul network, the number of (base station) transmitters sharing a given message is bounded by a number M, which we call the cooperation order. We provide outer bounds on the sum degrees of freedom of this system, which are shown to be tight in special cases.

A spatially correlated broadcast setting with M antennas at the base station and M users (each with a single antenna) is considered. We assume that the users have perfect channel information about their links and the base station has only statistical information about each user's link. The base station employs a linear beamforming strategy with one spatial eigen-mode allocated to each user. The goal of this work is to understand the structure of the beamforming vectors that maximize the ergodic sum-rate achieved by treating interference as noise. In the M = 2 case, we first fix the beamforming vectors and compute the ergodic sum-rate in closed-form as a function of the channel statistics. We then show that the optimal beamforming vectors are the dominant generalized eigenvectors of the covariance matrices of the two links. It is difficult to obtain intuition on the structure of the optimal beamforming vectors for M > 2 due to the complicated nature of the sum-rate expression. Nevertheless, in the case of asymptotic M, we show that the optimal beamforming vectors have to satisfy a set of fixed-point equations.

Goodness-of-fit tests are statistical procedures used to test the hypothesis H0that a set of observations were drawn according to some given probability distribution. Decision thresholds used in goodness-of-fit tests are typically set for guaranteeing a target false-alarm probability. In many popular testing procedures results on the weak convergence of the test statistics are used for setting approximate thresholds when exact computation is infeasible. In this work, we study robust procedures for goodness-of-fit where accurate models are not available for the distribution of the observations under hypothesis H0. We develop procedures for setting thresholds in two specific examples - a robust version of the Kolmogorov-Smirnov test for continuous alphabets and a robust version of the Hoeffding test for finite alphabets.

The focus of this work is on the analysis of transmit beamforming schemes with a low-rate feedback link in wireless sensor/relay networks, where nodes in the network need to implement beamforming in a distributed manner. Specifically, the problem of distributed phase alignment is considered, where neither the transmitters nor the receiver has perfect channel state information, but there is a low-rate feedback link from the receiver to the transmitters. In this setting, a framework is proposed for systematically analyzing the performance of distributed beamforming schemes. To illustrate the advantage of this framework, a simple adaptive distributed beamforming scheme that was recently proposed by Mudambai et al. is studied. Two important properties of the received signal magnitude function are derived. Using these properties and the systematic framework, it is shown that the adaptive distributed beamforming scheme converges both in probability and in mean. Furthermore, it is established that the time required for the adaptive scheme to converge in mean scales linearly with respect to the number of sensor/relay nodes.

Recent attention in quickest change detection in the multisensor setting has been on the case where the densities of the observations change at the same instant at all the sensors due to the disruption. In this work, a more general scenario is considered where the change propagates across the sensors, and its propagation can be modeled as a Markov process. A centralized, Bayesian version of this problem is considered, with a fusion center that has perfect information about the observations anda prioriknowledge of the statistics of the change process. The problem of minimizing the average detection delay subject to false alarm constraints is formulated in a dynamic programming framework. Insights into the structure of the optimal stopping rule are presented. In the limiting case of rare disruptions, it is shown that the structure of the optimal test reduces to thresholding thea posterioriprobability of the hypothesis that no change has happened. Under a certain condition on the Kullback-Leibler (K-L) divergence between the post- and the pre-change densities, it is established that the threshold test is asymptotically optimal (in the vanishing false alarm probability regime). It is shown via numerical studies that thislow-complexitythreshold test results in a substantial improvement in performance overnaivetests such as a single-sensor test or a test that incorrectly assumes that the change propagates instantaneously.

We consider constrained minimization of a sum of convex functions over a convex and compact set, when each component function is known only to a specific agent in a time-varying peer to peer network. We study an iterative optimization algorithm in which each agent obtains a weighted average of its own iterate with the iterates of its neighbors, updates the average using the subgradient of its local function and then projects onto the constraint set to generate the new iterate. We obtain error bounds on the limit of the function value when a constant stepsize is used.

We consider the uplink power control problem where mobile users in different cells are communicating with their base stations. We formulate the power control problem as the minimization of a sum of convex functions. Each component function depends on the channel coefficients from all the mobile users to a specific base station and is assumed to be known only to that base station (only CSIR). We then view the power control problem as a distributed optimization problem that is to be solved by the base stations and propose convergent, distributed and iterative power control algorithms. These algorithms require each base station to communicate with the base stations in its neighboring cells in each iteration and are hence non-autonomous. Since the base stations are connected through a wired backbone the communication overhead is not an issue. The convergence of the algorithms is shown theoretically and also verified through numerical simulations.

Codebooks based on random vector quantization (RVQ) are popular in limited feedback beamforming applications over MIMO channels because of their low-complexity design properties. The goal of this work is on understanding the performance of an ensemble of RVQ codebooks as a function of the number of bits of feedback (B), antenna dimensions, and spatial correlation. We analyze the case of correlated MIMO channels and arbitrary choice of B. Towards this goal, we first study the distribution function of weighted norms of isotropically distributed beamforming vectors. From this, we compute the received SNR loss and mutual information loss of a B-bit RVQ scheme relative to a perfect channel information benchmark. Our computation reveals the following: (i) The loss terms are a product of two factors. The first factor, which is also common to analysis of i.i.d. channels, decays as B increases at the rate 2-B/(Nt-1)where Ntis the number of transmit antennas; (ii) The second factor reflects the condition number of the channel. A channel that minimizes/maximizes the condition number on average also minimizes/maximizes the performance loss, respectively. Such behavior is typical of channels that correspond to rich (i.i.d.) spatial scattering, and poor (rank-1 channels) spatial scattering, respectively.

Attention in quickest change detection in the multi-sensor setting has been on the case where the densities of observations change at the same instant at all the sensors due to the disruption. In this work, a more general change process scenario is studied where the change propagates across the sensors, and its propagation can be modeled as a Markov process. A centralized, Bayesian version of this problem is considered, with a fusion center that has perfect information about the observations and a priori knowledge of the statistics of the change process. Insights into the structure of the optimal stopping rule are presented, that minimizes average detection delay subject to false alarm constraints. In the limiting case of rare disruptions, it is shown that this test structure reduces to a threshold rule. The asymptotic optimality (in the vanishing false alarm regime) of this threshold test is established under a certain condition on the Kullback-Leibler (K-L) divergence between the post- and the pre-change densities. In the special case of near-instantaneous change propagation across the sensors, this condition reduces to the mild condition that the K-L divergence be positive. Numerical studies show that this low-complexity threshold test results in a substantial improvement in performance over naive tests such as a single-sensor test or a test that incorrectly assumes that the change propagates instantaneously.

We study the problem of robust quickest change detection where the pre-change and post-change distributions are not known exactly but belong to known uncertainty classes of distributions. Both Bayesian and minimax versions of the quickest change detection problem are considered. When the uncertainty classes satisfy some specific conditions, we identify least favorable distributions (LFD's) from the uncertainty classes, and show that the detection rule designed for the LFD's is optimal in a minimax sense. The condition is similar to that required for the existence of LFD's for the robust hypothesis testing problem studied by Huber.

The support vector machine (SVM) has emerged as one of the most popular approaches to classification and supervised learning. It is a flexible approach for solving the problems posed in these areas, but the approach is not easily adapted to noisy data in which absolute discrimination is not possible. We address this issue in this paper by returning to the statistical setting. The main contribution is the introduction of a statistical support vector machine (SSVM) that captures all of the desirable features of the SVM, along with desirable statistical features of the classical likelihood ratio test. In particular, we establish the following: (i) The SSVM can be designed so that it forms a continuous function of the data, yet also approximates the potentially discontinuous log likelihood ratio test. (ii) Extension to universal detection is developed, in which only one hypothesis is labeled (a semi-supervised learning problem). (iii) The SSVM generalizes the robust hypothesis testing problem based on a moment class. Motivation for the approach and analysis are each based on ideas from information theory. A detailed performance analysis is provided in the special case of i.i.d. observations. This research was partially supported by NSF under grant CCF 07-29031, by UTRC, Motorola, and by the DARPA ITMANET program. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF, UTRC, Motorola, or DARPA.

Establishing the capacity region of a Gaussian interference network is an open problem in information theory. Recent progress on this problem has led to the characterization of the capacity region of a general two-user Gaussian interference channel within one bit. In this paper, we develop new, improved outer bounds on the capacity region. Using these bounds, we show thattreatinginterferenceasnoiseachieves thesumcapacityof the two-user Gaussian interference channel in alow-interferenceregime, where the interference parameters are below certain thresholds. We then generalize our techniques and results to Gaussian interference networks with more than two users. In particular, we demonstrate that the total interference threshold, below which treating interference as noise achieves the sum capacity, increases with the number of users.

Recent attention on correlated multi-input multi-output systems has centered around the case of imperfect channel or statistical information at the transmitter. The focus of this work is on correlated channels with arbitrary antenna array geometry and spacings, a coherent receiver, and imperfect statistical knowledge at the transmitter. Leveraging a recently proposed channel modeling paradigm that exploits processing in the angular domain, we first elucidate the structure of the optimal schemes when 'genie-aided' perfect statistical information is available at the transmitter. In the low-S N R case, we then show that the beamforming scheme that is optimal when perfect statistical information is available does not degrade smoothly with imperfections in the statistical information. We then go on to show that there exists a certain low-complexity beamforming approach which, while being sub-optimal in the genie-aided case, is robust to statistical feedback as well as the dynamics of its evolution.

Genie based arguments are used to derive new outer bounds on the sum capacity of the two user, symmetric three user, one-to-many and many-to-one Gaussian interference channels. Using these bounds, it is shown that treating interference as noise achieves the sum capacity in a low interference regime, where the interference parameters are below certain thresholds.

The focus of this paper is on spatial precoding in correlated multi-antenna channels where the number of independent data-streams can be adapted to trade off the data rate with the transmitter complexity. A structured precoding scheme is proposed, where the precoder structure evolves fairly slowly at a rate comparable with the statistical evolution of the channel, and in addition, enjoys low-complexity. A particular case of the proposed scheme, semiunitary precoding, is shown to be near- optimal in matched channels where the dominant eigenvalues of the transmit covariance matrix are well-conditioned and their number equals the number of independent data-streams, and the receive covariance matrix is also well-conditioned. In mismatched channels where the above conditions do not hold, it is shown that the loss in performance with semiunitary precoding when compared with a perfect channel information benchmark is substantial. This loss can be mitigated via limited feedback techniques that provide partial channel information to the transmitter. We also develop matching metrics that capture the degree of matching of a channel to the precoder structure continuously, and allow ordering two matrix channels in terms of their mutual information or error probability performance.

Space-time codes leverage the availability of multiple antennas to enhance the reliability of communication over wireless channels. While space-time codes have initially been designed with a focus on open-loop systems, recent technological advances have enabled the possibility of low-rate feedback from the receiver to the transmitter. The focus of this paper is on the implications of this feedback in a single-user multi-antenna system with a general model for spatial correlation. We assume a limited feedback model, that is, a coherent receiver and statistical knowledge at both the ends, along with B bits of error-free quantized channel information at the transmitter. We study space-time coding with a family of linear dispersion (LD) codes that meet an additional orthogonality constraint so as to ensure low-complexity decoding. Our results show that, when the number of bits of feedback (B) is small, a space-time coding scheme that is equivalent to beamforming and does not code across time is optimal in a weak sense in that it maximizes the average received SNR. As B increases, this weak optimality transitions to optimality in a strong sense that is characterized by the maximization of average mutual information. Thus, from a system designer's perspective, our work suggests that beamforming may not only be attractive from a low-complexity viewpoint, but also from an information-theoretic viewpoint.

The design of space-time codes for frequency flat, spatially correlated MIMO fading channels is considered. The focus of the paper is on the class of space-time block codes known as linear dispersion (LD) codes, introduced by Hassibi and Hochwald. The LD codes are optimized with respect to the mutual information between the inputs to the space-time encoder and the output of the channel. The use of the mutual information as both a design criterion and a performance measure is justified by allowing soft decisions at the output of the space-time decoder. A spatial Fourier (virtual) representation of the channel is exploited to allow for the analysis of MIMO channels with quite general fading statistics. Conditions, known as generalized orthogonal conditions (GOC's), are derived for an LD code to achieve an upper bound on the mutual information, with the understanding that LD codes that achieve the upper bound, if they exist, are optimal. Explicit code constructions and properties of the optimal power allocation schemes are also derived. In particular, it is shown that optimal LD codes correspond to beamforming to a single virtual transmit angle at low SNR, and a necessary and sufficient condition for beamforming to be optimal is provided. Due to the nature of the code construction, it is further observed that the optimal LD codes can be designed to adapt to the statistics of different scattering environments. Finally, numerical results are provided to illustrate the optimal code design for three examples of sparse scattering environments. The performance of the optimal LD codes for these scattering environments is compared with that of LD codes designed assuming the i.i.d. Rayleigh fading (rich scattering) model, and it is shown that the optimal LD codes perform significantly better. The optimal LD codes are also compared to beamforming LD codes and it is shown that beamforming is nearly optimal over a range of SNR's of interest.

The design of spatio-temporal power allocation schemes is considered for space-time coding over spatially correlated multiple-input multiple-output (MIMO) channels. The focus is on linear dispersion (LD) space-time codes that are constructed to maximize the mutual information between the input of the space-time encoder and the output of the channel. While perfect channel state information (CSI) is assumed at the receiver, three cases are considered for the CSI at the transmitter: 1) perfect CSI is available, 2) only statistical CSI is available, and 3) partial CSI in the form of a B-bit quantized channel information along with the statistical information is available. In all the three cases, it is shown that the optimal temporal power allocation is uniform. The optimal spatial power allocation for the case where only statistical CSI is available was studied previously in [1] where it was shown to be a nontrivial function of the spatial correlation. Here, the cases of perfect and partial CSI are studied. For the perfect CSI case, it is shown that it is optimal to excite only one spatial mode. For the partial and statistical CSI cases, the optimal allocation excites multiple modes, in general. However, it is attractive to use a low-complexity scheme that excites only the dominant spatial mode. We show that this low-complexity scheme is near-optimal in two settings: 1) large receive antenna asymptotics, and 2) for fixed antenna dimensions, when the transmit and receive covariance matrices are ill- and well-conditioned, respectively. Based on the optimal schemes for the extreme cases of perfect and statistical CSI, low-complexity spatial power allocation for the case of partial CSI is considered. Simulation results indicate that even in this case, exciting one spatial mode leads to a minimal loss in performance over the optimal spatial power allocation scheme.

We consider a network of spatially distributed sensors deployed to track the intensity of a diffusing source whose location is fixed, but unknown. The sensors make discrete time concentration measurements and communicate them to a fusion center. We propose a recursive algorithm that can be used at the fusion center, which takes in the latest concentration measurements as input and produces an estimate for the source location and latest intensity as the output. The performance of the algorithm is verified through simulations.

One of the main requirements of cognitive radio systems is the ability to reliably detect the presence of licensed primary transmissions. Previous works on the problem of detection for cognitive radio have suggested the necessity of user cooperation in order to be able to detect at the really low signal- to-noise ratios experienced in practical situations. We consider a system of cognitive radio users who cooperate with each other in trying to detect licensed transmissions. Assuming that the cooperating nodes use identical energy detectors, we model the received signals as correlated log-normal random variables and study the problem of fusing the decisions made by the individual nodes. We design a linear-quadratic (LQ) fusion strategy based on a deflection criterion for this problem, that takes into account the correlation between the nodes. Our simulation results show that the LQ detector significantly outperforms the counting rule, which is the fusion rule that is obtained by ignoring the correlation.

With partial channel state information (CSI) at the transmitter, the design of space-time codes for frequency flat, spatially correlated MIMO fading channels is considered. The focus of the paper is on the class of space-time block codes known as linear dispersion (LD) codes, introduced by Hassibi and Hochwald. For perfect CSI at the transmitter, the LD codes are optimized with respect to the instantaneous mutual information between the inputs to the space-time encoder and the output of the channel. An equivalent optimization problem is proposed and can that be solved by standard convex optimization algorithms. It is then conjectured that the LD codes obtained by maximizing the instantaneous mutual information converge to that obtained from maximizing the averaged mutual information in the large antenna asymptote. Based on the insights drawn from the conjecture, a limited feedback scheme for LD codes is proposed assuming a common codebook at the transmitter and receiver. The numerical result for a scattering environment suggests that the proposed feedback scheme achieves high performance at low complexity.

We consider a spatially correlated multi-user communication system with Ntantennas at the base station (BS), U users (Ntof whom are serviced), and each user with a single antenna. While the users are assumed to know their channels perfectly, the BS has neither instantaneous channel state information (CSI) nor the spatial statistics corresponding to any of the users. We consider a limited feedback model where each user conveys B bits of partial channel information to the BS. Due to the lack of statistical information at the BS, a codebook based on random vector quantization (RVQ) and tailored to uncorrected Rayleigh fading is used in signaling. Our first contribution is to characterize the impact of spatial correlation (in particular, the eigenvalues of the transmit covariance matrix) on the performance of an RVQ scheme. We also show that spatial correlation has significant consequences on practical aspects of limited feedback systems like storage and construction of codebooks. While independent RVQ codebooks have to be generated for the different users in the i.i.d. case, under certain relaxed assumptions on the correlation, the same codebook can be reused across all the users. This is because the spatial signature induced by the correlation can be exploited to distinguish the quantizers of different users.

The optimal input covariance matrix Q that achieves the ergodic capacity under the coherent assumption in a point-to-point, multi-antenna setting is a function of the spatial correlation and the transmit SNR. While the eigenvectors of Q can be characterized in closed-form for many realistic correlation models, the eigenvalues have to be determined numerically. However, it is well-known that the rank of Q is a non-decreasing function of SNR. Motivated by this fact, in this work, we study communication with a low-complexity family of input covariance matrices that are characterized by their rank, assuming uniform power allocation over the smaller-dimensional eigen-space. We quantify the impact of spatial correlation on the M-th transition-SNR which is defined as the smallest SNR at which rank-M transmission becomes optimal.

A peak-power-limited single-antenna block-stationary Gaussian fading channel is studied, where neither the transmitter nor the receiver knows the channel state information, but both know the channel statistics. This model subsumes most previously studied Gaussian fading models. The asymptotic channel capacity in the high signal-to-noise ratio (SNR) regime is first computed, and it is shown that the behavior of the channel capacity depends critically on the channel model. For the special case where the fading process is symbol-by-symbol stationary, it is shown that the codeword length must scale at least logarithmically with SNR in order to guarantee that the communication rate can grow logarithmically with SNR with decoding error probability bounded away from one. An expression for the capacity per unit energy is also derived. Furthermore, it is shown that the capacity per unit energy is achievable using temporal ON-OFF signaling with optimally allocated ON symbols, where the optimal ON-symbol allocation scheme may depend on the peak power constraint.

The capacity regions are investigated for two relay broadcast channels (RBCs), where relay links are incorporated into two-user broadcast channels to support user cooperation. In the first channel, the partially cooperative RBC, only one user in the system acts as a relay. An achievable rate region is derived based on the relay using the decode-and-forward scheme. An outer bound on the capacity region is derived and is shown to be tighter than the cut-set bound. For the special case where the partially cooperative RBC is degraded, the achievable rate region is shown to be the capacity region. Two Gaussian cases of the partially cooperative RBC are studied. For the system where the additive white Gaussian noise (AWGN) term at one receiver is a degraded version of the other, which we refer to as the D-AWGN partially cooperative RBC, the capacity region is established. For the system where the AWGN term at one receiver is independent of the other, which we refer to as the AWGN partially cooperative RBC, inner and outer bounds on the capacity region are derived and are shown to be close. Furthermore, it is shown that feedback does not increase the capacity region for the degraded partially cooperative RBC, but that it improves the capacity region for the nondegraded version. In particular, feedback improves the capacity region for the AWGN partially cooperative RBC. In the second channel model being studied in the paper, the fully cooperative RBC, both users can act as relay nodes. All the results for the partially cooperative RBC are correspondingly generalized to the fully cooperative RBC. In particular, capacity regions are established for the degraded and D-AWGN fully cooperative RBCs. The capacity region is also established for the fully cooperative RBC with feedback. It is further shown that the AWGN fully cooperative RBC has a larger achievable rate region than its partially cooperative counterpart. The results illustrate that relaying and user cooperation are powerful techniques for improving the capacity of broadcast channels

Resource allocation is investigated for fading relay channels under separate power constraints at the source and relay nodes. As a basic information-theoretic model for fading relay channels, the parallel relay channel is first studied, which consists of multiple independent three-terminal relay channels as subchannels. Lower and upper bounds on the capacity are derived, and are shown to match, and thus establish the capacity for the parallel relay channel with degraded subchannels. This capacity theorem is further demonstrated via the Gaussian parallel relay channel with degraded subchannels, for which the synchronized and asynchronized capacities are obtained. The capacity-achieving power allocation at the source and relay nodes among the subchannels is partially characterized for the synchronized case and fully characterized for the asynchronized case. The fading relay channel is then studied, which is based on the three-terminal relay channel with each communication link being corrupted by a multiplicative fading gain coefficient as well as an additive Gaussian noise term. For each link, the fading state information is assumed to be known at both the transmitter and the receiver. The source and relay nodes are allowed to allocate their power adaptively according to the instantaneous channel state information. The source and relay nodes are assumed to be subject to separate power constraints. For both the full-duplex and half-duplex cases, power allocations that maximize the achievable rates are obtained. In the half-duplex case, the power allocation needs to be jointly optimized with the channel resource (time and bandwidth) allocation between the two orthogonal channels over which the relay node transmits and receives. Capacities are established for fading relay channels that satisfy certain conditions.

A dynamic-user model for centralized wireless networks is studied, where users arrive with a certain file size and depart when the file is served by a central server. Although the exact analysis of dynamic-user systems can be complicated, it is shown that an approximate analysis can be performed in a time-scale separation regime where the file size is much larger than the time scale of service process fluctuation. A first-order approximation result is derived that shows that when file sizes are large, a complicated service process can be replaced by a simple constant-rate service process. The accuracy of the approximation is further improved through a second order approximation result that incorporates the effect of service variability. Variability in the service process is shown to reduce the effective service rate, leading to a quantification of the conventional heuristic that service variability degrades system performance

We study the problem of tracking an object that is moving randomly through a dense network of wireless sensors. We assume that each sensor has a limited range for detecting the presence of the object, and that the network is sufficiently dense so that the sensors cover the area of interest. In order to conserve energy the sensors may be put into a sleep mode with a timer that determines the sleep duration. We assume that a sensor that is asleep cannot be communicated with or woken up. Thus the sleep duration needs to be determined at the time the sensor goes to sleep based on all the information available to the sensor. The objective is to track the location of the object to within the accuracy of the range of the sensor. However, having sleeping sensors in the network could result in tracking errors, and hence there is a tradeoff between the energy savings and the tracking error that results from the sleeping actions at the sensors. We consider the design of sleeping policies that optimize this tradeoff

We consider a peak-power-limited single-antenna block-stationary Gaussian fading channel where neither the transmitter nor the receiver knows the channel state information, but both know the channel statistics. We compute the asymptotic channel capacity in the high SNR regime. A fundamental interplay between the codeword length, communication rate, and decoding error probability is revealed. We also derive an expression for the capacity per unit energy

A detection problem in sensor networks is considered, where the sensor nodes are placed on a line and receive partial information about their environment. The nodes transmit a summary of their observations over a noisy communication channel to a fusion center for the purpose of detection. The observations at the sensors are samples of a spatial stochastic process, which is one of two possible signals corrupted by Gaussian noise. Two cases are considered: one where the signal is deterministic under each hypothesis, and the other where the signal is a correlated Gaussian process under each hypothesis. The nodes are assumed to be subject to a power density constraint, i.e., the power per unit distance is fixed, so that the power per node decreases linearly with the node density. Under these constraints, the central question that is addressed is: how dense should the sensor array be, i.e., is it better to use a few high-cost, high-power nodes or to have many low-cost, low-power nodes? An answer to this question is obtained by resorting to an asymptotic analysis where the number of nodes is large. In this asymptotic regime, the Gaumlrtner-Ellis theorem and similar large-deviation theory results are used to study the impact of node density on system performance. For the deterministic signal case, it is shown that performance improves monotonically with sensor density. For the stochastic signal case, a finite sensor density is shown to be optimal

A binary decentralized detection problem is studied in which a collection of wireless sensor nodes provides relevant information about their environment to a fusion center. The observations at the nodes are samples of a finite state Markov process under each hypothesis. The nodes transmit their data to a fusion center over a multiple access channel. Upon reception of the information, the fusion center selects one of the two possible hypotheses. It is assumed that the sensor system is constrained by the capacity of the multiple access channel over which the sensor nodes are transmitting. Thus, as the node density increases, the sensor observations get more correlated, and, furthermore, fewer bits can be transmitted by each sensor node. A framework is presented in this paper for deriving design guidelines relating sensor density to system performance under a total communication constraint. The framework is based on large deviation theory applied to the asymptotic regime where the number of sensor nodes is large. This framework is applied to a specific example to compare the gains offered by having a higher node density with the benefits of getting detailed information from each sensor.

The ergodic capacity of Ricean MIMO (multiple-input multiple-output) fading channels is investigated in this paper, based on a virtual (Fourier) channel representation. Coherent reception is assumed at the receiver. The Ricean statistics are due to a line-of-sight (LOS) path joining the transmitter and receiver. In the virtual domain, this LOS path corresponds to a single entry in the virtual channel matrix. The optimal input distribution of the correlated Ricean MIMO channel in the virtual domain has a diagonal covariance matrix structure, the same as in the Rayleigh fading MIMO case. Our method is used to get a tight lower bound and upper bound on the ergodic capacity. Further, the same analysis is used to obtain an approximate optimal input distribution analytically, in place of the usual Monte Carlo based numerical optimization methods.

There is significant interest in battery-powered sensor networks to be used for detection in a wide variety of applications, from surveillance and security to health and environmental monitoring. Severe energy and bandwidth constraints at each sensor node demand system-level approaches to design that consider detection performance jointly with system-resource constraints. Our approach is to formulate detection problems with constraints on the expected cost arising from transmission (sensor nodes to a fusion node) and measurement (at each sensor node) to address some of the system-level costs in a sensor network. For a given resource constraint, we find that randomization over the choice of measurement and over the choice of when to transmit achieves the best performance (in a Bayesian, Neyman-Pearson, and Ali-Silvey sense). To facilitate design, we describe performance criteria in the send/no-send transmission scenario, where the joint optimization over the sensor nodes decouples into optimization at each sensor node.

A Gaussian orthogonal relay model is investigated, where the source transmits to the relay and destination in channel 1, and the relay transmits to the destination in channel 2, with channels 1 and 2 being orthogonalized in the time-frequency plane in order to satisfy practical constraints. The total available channel resource (time and bandwidth) is split into the two orthogonal channels, and the resource allocation to the two channels is considered to be a design parameter that needs to be optimized. The main focus of the analysis is on the case where the source-to-relay link is better than the source-to-destination link, which is the usual scenario encountered in practice. A lower bound on the capacity (achievable rate) is derived, and optimized over the parameter /spl theta/, which represents the fraction of the resource assigned to channel 1. It is shown that the lower bound achieves the max-flow min-cut upper bound at the optimizing /spl theta/, the common value thus being the capacity of the channel at the optimizing /spl theta/. Furthermore, it is shown that when the relay-to-destination signal-to-noise ratio (SNR) is less than a certain threshold, the capacity at the optimizing /spl theta/ is also the maximum capacity of the channel over all possible resource allocation parameters /spl theta/. Finally, the achievable rates for optimal and equal resource allocations are compared, and it is shown that optimizing the resource allocation yields significant performance gains.

The capacity of the multiple-input multiple-output (MIMO) wireless channel with uniform linear arrays (ULAs) of antennas at the transmitter and receiver is investigated. It is assumed that the receiver knows the channel perfectly but that the transmitter knows only the channel statistics. The analysis is carried out using an equivalent virtual representation of the channel that is obtained via a spatial discrete Fourier transform. A key property of the virtual representation that is exploited is that the components of virtual channel matrix are approximately independent. With this approximation, the virtual representation allows for a general capacity analysis without the common simplifying assumptions of Gaussian statistics and product-form correlation (Kronecker model) for the channel matrix elements. A deterministic line-of-sight (LOS) component in the channel is also easily incorporated in much of the analysis. It is shown that in the virtual domain, the capacity-achieving input vector consists of independent zero-mean proper-complex Gaussian entries, whose variances can be computed numerically using standard convex programming algorithms based on the channel statistics. Furthermore, in the asymptotic regime of low signal-to-noise ratio (SNR), it is shown that beamforming along one virtual transmit angle is asymptotically optimal. Necessary and sufficient conditions for the optimality of beamforming, and the value of the corresponding optimal virtual angle, are also derived based on only the second moments of the virtual channel coefficients. Numerical results indicate that beamforming may be close to optimum even at moderate values of SNR for sparse scattering environments. Finally, the capacity is investigated in the asymptotic regime where the numbers of receive and transmit antennas go to infinity, with their ratio being kept constant. Using a result of Girko, an expression for the asymptotic capacity scaling with the number of antennas is obtained in terms

We study a binary decentralized detection problem in which a set of sensor nodes provides partial information about the state of nature to a fusion center. Sensor nodes have access to conditionally independent observations, given the state of nature, and they transmit their data over separate wireless channels. The communication link between each node and the fusion center is subject to fading, with certain nodes possibly having much better connections than others. Upon reception of the information, the fusion center attempts to accurately reconstruct the state of nature. Large deviation theory is employed to obtain design guidelines for wireless sensor networks with a large number of nodes. The normalized Chernoff information is shown to be an appropriate performance metric to compare prospective sensor nodes. For the specific example of binary sensor nodes sending data over Rayleigh fading channels, the performance loss due to fading is found to be small.

A binary decentralized detection problem in which sensor nodes provide partial information about their environment to a fusion center is studied. The nodes have access to conditionally independent observations and transmit a summary of their own data over wireless channels. Upon reception of the information, the fusion center attempts to accurately reconstruct the state of nature. The communication link between each node and the fusion center is modeled as a fading channel corrupted by additive noise. Channel state information is available at the fusion center and at the sensor nodes. Large deviation theory is used to show that having identical sensor nodes is asymptotically optimal. Algorithms in which each sensor node selects a signaling/coding schemes based on the quality of its channel are studied.

The capacity of two broadcast systems with relay links is studied in this paper. Both of these systems are extensions of two users degraded broadcast channels, which achieves a rate region of channels and includes the capacity region of original broadcast channel. We then consider another system, the dumb relay broadcast channel, where an additional relay node is introduced into the two users degraded broadcast channel that assists both user. This relay node does not have its own information from the source, and hence is referred to as dumb relay node. From the results an achievable rate region for this channel is derived and is shown to include that for the cooperative broadcast channel.

A robust hypothesis testing framework is introduced in which candidate hypotheses are characterized by moment classes. It is shown that there exists a test sequence that is asymptotically optimal in the min-max sense, and that it is expressed as a comparison of a log-linear combination of the constraint functions to a predetermined threshold.

This paper outlines interesting applications of large-deviation theory and asymptotic analysis to the design of wireless sensor networks. Sensor networks are envisioned to contain a large amount of wireless nodes. As such, asymptotic regimes where the number of nodes becomes large are important tools in identifying good design rules for future sensor systems. Through a simple example, we show how the Gartner-Ellis theorem can be used to study the impact of density on overall performance in resource constrained systems. Specifically, we consider the problem where sensor nodes receive partial information about their environment, and then send a summary of their observations to a fusion center for the purpose of detection. Each node transmits its own data on a noisy communication channel. Observations are assumed to become increasingly correlated as sensor nodes are placed in close proximity. It is found that high node density performs well even when observations from adjacent sensors are highly correlated. Furthermore, the tools presented in this paper can be employed for a more complete analysis of the tradeoff between resource allocation, system complexity, and overall performance in wireless sensor networks.

Many problems in information theory can be distilled to an optimization problem over a space of probability distributions. The most important examples are in communication theory, where it is necessary to maximize mutual information in order to compute channel capacity, and the classical hypothesis testing problem in which an optimal test is based on the maximization of divergence. Two general classes of optimization problems are considered in this paper: convex and linear programs, where the constraint set is defined by a finite number of moment constraints.

In this paper, we study a binary decentralized detection problem in which a set of sensor nodes provides partial information about the state of nature to a fusion center. Sensor nodes have access to conditionally independent and identically distributed observations, given the state of nature, and transmit their data over a wireless channel. Upon reception of the information, the fusion center attempts to accurately reconstruct the state of nature. Specifically, we extend existing asymptotic results about large sensor networks to the case where the network is subject to a joint power constraint, and where the communication channel from each sensor node to the fusion center is corrupted by additive noise. Large deviation theory is used to show that having identical sensor nodes, i.e., each node using the same transmission scheme, is asymptotically optimal. Furthermore, a performance metric by which sensor node candidates can be compared is established. We supplement the theory with examples to illustrate how the results derived in this paper apply to the design of practical sensing systems.

The capacity of noncoherent time-selective Rayleigh-fading channels is studied under various models for the variations in time. The study includes both single-input and single-output (SISO) and multiple-input and multiple-output (MIMO) systems. A block-fading model is first considered where the channel changes correlatively over each block period of length T, and independently across blocks. The predictability of the channel is characterized through the rank Q of the correlation matrix of the vector of channel gains in each block. This model includes, as special cases, the standard block-fading model where the channel remains constant over block periods (Q=1), and models where the fading process has finite differential entropy rate (Q=T). The capacity is initially studied for long block lengths and some straightforward but interesting asymptotes are established. For the case where Q is kept fixed as T/spl rarr//spl infin/, it is shown that the noncoherent capacity converges to the coherent capacity. For the case where both T,Q/spl rarr//spl infin/, with Q/T being held constant, a bound on the capacity loss due to channel unpredictability is established. The more interesting scenario of large signal-to-noise ratio (SNR) is then explored in detail. For SISO systems, useful upper and lower bounds on the large SNR asymptotic capacity are derived, and it is shown that the capacity grows logarithmically with SNR with a slope of T-Q/spl rarr/T, for Q

The use of multiple antennas at the transmitter and the receiver is considered for the uplink of cellular communication systems. The achievable spectral efficiency in bits/s/Hz is used as the criterion for comparing various design choices. The focus is on wideband code-division multiple-access (CDMA) systems when the receiver uses the matched-filter or the minimum mean-squared error detector, followed by single-user decoders. The spreading sequences of the CDMA system are assumed to be random across the users, but could be dependent across the transmit antennas of each user. Using analytical results in the large system asymptote, guidelines are provided for the sequence design across the transmit antennas and for choosing the number of antennas. In addition, comparisons are made between (random) CDMA and orthogonal multiaccess with multiple antennas. It is shown that CDMA, even with single-user decoding, can outperform orthogonal multiaccess when the number of receive antennas is sufficiently large.

The control of transmit power has been recognized as an essential requirement in the design of cellular code-division multiple-access (CDMA) systems. Indeed, power control allows for mobile users to share radio resources equitably and efficiently in a multicell environment. Much of the work on power control for CDMA systems found in the literature assumes a quasi-static channel model, i.e., the channel gains of the users are assumed to be constant over a sufficiently long period of time for the control algorithm to converge. In this paper, the design of dynamic power control algorithms for CDMA systems is considered without the quasi-static channel restriction. The design problem is posed as a tradeoff between the desire for users to maximize their individual quality of service and the need to minimize interference to other users. The dynamic nature of the wireless channel for mobile users is incorporated in the problem definition. Based on a cost minimization framework, an optimal multiuser solution is derived. The multiuser solution is shown to decouple, and effectively converge, to a single-user solution in the large system asymptote, where the number of users and the spreading factor both go to infinity with their ratio kept constant. In a numerical study, the performance of a simple threshold policy is shown to be near that of the optimal single-user policy. This offers support to the threshold decision rules that are employed in current cellular CDMA systems.

The optimal detection procedure for detecting changes in independent and identically distributed sequences (i.i.d.) in a Bayesian setting was derived by Shiryaev in the nineteen sixties. However, the analysis of the performance of this procedure in terms of the average detection delay and false alarm probability has been an open problem. In this paper, we investigate the performance of Shiryaev's procedure in an asymptotic setting where the false alarm probability goes to zero. The asymptotic study is performed not only in. the i.d.d. case where the Shiryaev's procedure is optimal but also in a general, non-i.i.d. case. In the latter case, we show that Shiryaev's procedure is asymptotically optimum under mild conditions. We also show that the two popular non-Bayesian detection procedures, namely the Page and Shiryaev-Roberts-Pollak procedures, are not optimal (even asymptotically) under the Bayesian criterion. The results of this study are shown to be especially important in studying the asymptotics of decentralized quickest change detection procedures.

The key to reliable communication is a fundamental understanding of the interaction between the signal space and the channel. In time- and frequency-selective multi-antenna (space-time) fading channels this interaction happens in time, frequency and space. In this paper we propose a four-dimensional Karhunen-Loeve-like Fourier series representation for space-time channels that captures the essence of such interaction and exposes the intrinsic degrees of freedom in the channel. The four dimensions are: time, frequency and the two spatial dimensions at the transmitter and receiver. The key signal space parameters are the signaling duration, bandwidth and the two array apertures. The corresponding channel parameters are the delay, Doppler and the two angular spreads associated with the scattering environment. The representation induces a virtual partitioning of propagation paths in time, frequency and space that reveals their contribution to channel capacity and diversity. It also exposes fundamental dependencies between time, frequency and space thereby revealing the essential independent degrees of freedom in the channel.

General definitions of spreading and coding are given based on the notion of Shannon bandwidth introduced by Massey (1994), with the goal of distinguishing these operations for signaling with bandwidth redundancy. These definitions are shown to lead to a separation result: every bandwidth redundancy scheme can be expressed as a concatenation of coding followed by spreading. The coding-spreading tradeoff problem is then studied for a code division multiple access (CDMA) system in which the receiver processes the received signal by using a user-separating front-end, which feeds into autonomous single-user decoders. Under the single-user decoding setting, it is established that the linear minimum mean square error (LMMSE) front-end multiuser detector is optimum among all front-ends that are constrained to use only spreading information. Also, conditions are given for the single-user decoders to ignore spreading information without losing optimality. An example illustrating the coding-spreading tradeoff optimization for a direct sequence CDMA system with random spreading is given. Single-cell and multicell scenarios are considered in the optimization, and a comparison is made of the spectral efficiencies that can be achieved with the conventional matched filter and LMMSE front-ends.

The analysis of linear minimum mean-square error (MMSE) detection in a band-limited code-division multiple-access (CDMA) system that employs random spreading sequences is considered. The key features of the analysis are that the users are allowed to be completely asynchronous, and that the chip waveform is assumed to be the ideal Nyquist sinc function. It is shown that the asymptotic signal-to-interference ratio (SIR) at the detector output is the same as that in an equivalent chip-synchronous system. It is hence been established that synchronous analyses of linear MMSE detection can provide useful guidelines for the performance in asynchronous band-limited systems.

The problem of generating discrete sufficient statistics for signal processing in code-division multiple-access (CDMA) systems is considered in the context of underlying channel bandwidth restrictions. Discretization schemes are identified for (approximately) bandlimited CDMA systems, and a notion of approximate sufficiency is introduced. The role of chip-matched filtering in generating accurate discrete statistics is explored. The impact of approximate sufficiency on performance is studied in three cases: conventional matched filter (MF) detection, minimum mean-squared-error detection, and delay acquisition. It is shown that for waveforms limited to a chip interval, sampling the chip-MF output at the chip rate can lead to a significant degradation in performance. Then, with equal bandwidth and equal rate constraints, the performance with different chip waveforms is compared. In all three cases above, it is demonstrated that multichip waveforms that approximate Nyquist sine pulses achieve the best performance, with the commonly used rectangular chip pulse being severely inferior. However, the results also indicate that it is possible to approach the best performance with well-designed chip waveforms limited to a chip interval, as long as the chip-MF output is sampled above the Nyquist rate.

A general approach is presented for analyzing the performance of digital signaling with multichannel reception on correlated fading channels. The approach is based on: (i) exploiting the complex Gaussian model for the joint distribution of the fading on the multiple channels; and (ii) applying recent results on the unified performance analysis of digital signaling on fading channels using alternative representations of the Q(/spl middot/) and related functions. Numerical results that illustrate the effect of correlation on the diversity gain from multichannel reception are also presented.

This paper analyzes the performance of the linear parallel interference cancellation (LPIC) multiuser detector in a synchronous multiuser communication scenario with binary signaling, nonorthogonal multiple access interference, and an additive white Gaussian noise channel. The LPIC detector has been considered in the literature lately due to its low computational complexity, potential for good performance under certain operating conditions, and close connections to the decorrelating detector. In this paper, we compare the performance of the two-stage LPIC detector to the original multistage detector proposed by Varanasi and Aazhang (1990, 1991) for CDMA systems. The general M-stage LPIC detector is compared to the conventional matched filter detector to describe operating conditions where the matched filter detector outperforms the LPIC detector in terms of error probability at any stage M. Analytical results are presented that show that the LPIC detector may exhibit divergent error probability performance under certain operating conditions and may actually yield error probabilities greater than 0.5 in some cases. Asymptotic results are presented for the case where the number of LPIC stages goes to infinity. Implications of the prior results for code division multiple access (CDMA) systems with random binary spreading sequences are discussed in the "large-system" scenario. Our results are intended to analytically corroborate the simulation evidence of other authors and to provide cautionary guidelines concerning the application of LPIC detector to CDMA communication systems.

A decentralized formulation of the quickest change detection problem is studied, where the distributions of the observations at all of the sensors in the system change at the time of disruption, and the sensors communicate with a common fusion center. A Bayesian setting is considered in which a priori knowledge of the change time distribution is available. The observations are assumed to be independent from sensor to sensor, conditioned on the change hypothesis. An optimal solution to the problem is derived under a quasi-classical information structure, where each sensor retains only its messages from the past (restricted local memory), and receives feedback from the fusion center about the past messages of the other sensors (full feedback). A technique for implementation of the optimal solution is given, and the solution is extended to the situation where a priori change time distribution information is not available. The structure of the optimal solution is then used to arrive at a simple suboptimal policy that does not require any past massage information. Numerical examples are given, which illustrate that the optimal solution offers little improvement over the suboptimal one, i.e., that feedback from the fusion center cannot be exploited to improve performance.

The problem of estimating the propagation delay of a new user in a coded band-limited DS/CDMA system in the presence of multiple access interference (MAI) is considered. MAI-resistant acquisition schemes are developed for a general CDMA system without the constraint that the spreading sequences of the users repeat every symbol period. It is assumed that the spreading sequences and delays of the interfering users are known. However, knowledge of their amplitudes, which would need estimation, is not assumed, and their unreliable code-symbol estimates are not used. Under this scenario, acquisition schemes are derived based on the maximum-likelihood (ML) criterion. The performance of an approximation to the ML scheme is analyzed using Gaussian approximations and by assuming that the chip boundaries of the new user are known a priori. Simulations show that the analysis is reasonably accurate for parameters in the realm of practical interest.

The design of hard handoff algorithms based on optimizing the tradeoff between link quality and rate of handoffs is considered. For handoff algorithms based on this criterion, adaptation is precisely defined in terms of remaining on a locus of desirable operating points as system parameters (such as mobile velocity) change. A rule based on a linear cost criterion is used to select desirable operating points. For this rule, it is shown that the optimal handoff algorithm, which is impractical, is easily adapted by fixing a single tradeoff parameter at an appropriate value. The same adaptation property is shown to hold for an easily implementable approximation to the optimal algorithm, the locally optimal (LO) handoff algorithm. This is in contrast to the poor adaptation of hysteresis based approaches which require lookup tables for adaptation. Practical estimators for all relevant system parameters based on a short window of pilot signal strength measurements are also discussed. It is shown that the LO algorithm adapts well when these simple estimators are used. A hysteresis-threshold approximation to the adaptive LO algorithm is also developed.

The scenario considered is one where a single new user is to be acquired on the reverse link by the base station, and where the channel parameters of the interfering users are known. Following a minimum mean squared error (MMSE) strategy for suppressing the multiaccess interference, the parameter estimation problem is posed in a maximum likelihood framework, To reduce complexity, the solution is implemented in two stages: first, the estimated tap delays are restricted to be at chip spacings; second, the number of taps is reduced by allowing for arbitrary spacing between them. The performance of the proposed techniques is studied through numerical simulations. It is shown that significant gains can be obtained by exploiting the structure of the interference and acquiring the channel parameters jointly.

For pt. I see ibid. vol.45, p.2448-61, 1999. We proved in pt.I that two specific constructions of multihypothesis sequential tests, which we refer to as multihypothesis sequential probability ratio tests (MSPRTs), are asymptotically optimal as the decision risks (or error probabilities) go to zero. The MSPRTs asymptotically minimize not only the expected sample size but also any positive moment of the stopping time distribution, under very general statistical models for the observations. In this paper, based on nonlinear renewal theory we find accurate asymptotic approximations (up to a vanishing term) for the expected sample size that take into account the "overshoot" over the boundaries of decision statistics. The approximations are derived for the scenario where the hypotheses are simple, the observations are independent and identically distributed (i.i.d.) according to one of the underlying distributions, and the decision risks go to zero. Simulation results for practical examples show that these approximations are fairly accurate not only for large but also for moderate sample sizes. The asymptotic results given here complete the analysis initiated by Baum and Veeravalli (1994), where first-order asymptotics were obtained for the expected sample size under a specific restriction on the Kullback-Leibler distances between the hypotheses.

The problem of sequential testing of multiple hypotheses is considered, and two candidate sequential test procedures are studied. Both tests are multihypothesis versions of the binary sequential probability ratio test (SPRT), and are referred to as MSPRTs. The first test is motivated by Bayesian optimality arguments, while the second corresponds to a generalized likelihood ratio test. It is shown that both MSPRTs are asymptotically optimal relative not only to the expected sample size but also to any positive moment of the stopping time distribution, when the error probabilities or, more generally, risks associated with incorrect decisions are small. The results are first derived for the discrete-time case of independent and identically distributed (i.i.d.) observations and simple hypotheses. They are then extended to general, possibly continuous-time, statistical models that may include correlated and nonhomogeneous observation processes. It also demonstrated that the results can be extended to hypothesis testing problems with nuisance parameters, where the composite hypotheses, due to nuisance parameters, can be reduced to simple ones by using the principle of invariance. These results provide a complete generalization of the results given by Veeravalli and Baum (see ibid., vol.41, p.1994-97, 1995), where it was shown that the quasi-Bayesian MSPRT is asymptotically efficient with respect to the expected sample size for i.i.d. observations.

Previous work on estimating the performance of hard handoff algorithms has been based on Monte-Carlo simulations or asymptotic approximations. A new analysis technique for evaluating the performance of handoff algorithms is introduced. This technique may be used to accurately estimate the performance of both optimal and suboptimal handoff algorithms. Specifically, the technique allows for the calculation of an upper bound on handoff performance without the need for storing or simulating the complicated optimal solution.

A technique is presented for jointly optimizing the signaling in the two directions of transmission on a twisted-pair communications channel. It is then applied to twisted-pair channel models with monotonic channel response and crosstalk transfer functions. While the signaling strategy presented in this paper can achieve only a lower bound on the true channel capacity, it is a significant improvement over existing signaling schemes. In particular, in contrast with existing schemes, the maximum information rate for the joint signaling strategy increases without bound as the signal-to-noise ratio (SNR) approaches infinity. It is also shown through numerical results that the proposed signaling strategy generalizes naturally to more practical nonmonotonic twisted-pair channel models incorporating bridge taps and other nonidealities. Finally, the form of the optimal signaling strategy suggests a relatively straightforward implementation using multicarrier modulation.

The design of handoff algorithms for cellular communication systems based on mobile signal strength measurements is considered. The design problem is posed as an optimization to obtain the best tradeoff between expected number of service failures and expected number of handoffs, where a service failure is defined to be the event that the signal strength falls below a level required for satisfactory service to the subscriber. Based on dynamic programming arguments, an optimal solution is obtained which, though impractical, can be used as a benchmark in the comparison of suboptimal schemes. A simple, locally optimal handoff algorithm is derived from the optimal solution. Simulation results show that the locally optimal algorithm outperforms the hysteresis algorithm and is competitive with a hysteresis-threshold algorithm proposed by Zhang and Holtzman (see IEEE 44th Veh. Tech. Conf., p.82, 1994). A straightforward technique for adapting the locally optimal algorithm to changing environments is suggested.

A sequential multihypothesis test known as the M-ary sequential probability ratio test (MSPRT) is generalized to account for nonuniform decision costs. Bounds on error probabilities and asymptotic expressions for the stopping time and error probabilities are given. A key result of this correspondence is a proof that the generalized MSPRT is asymptotically efficient.

The sequential testing of more than two hypotheses has important applications in direct-sequence spread spectrum signal acquisition, multiple-resolution-element radar, and other areas. A useful sequential test which we term the MSPRT is studied in this paper. The test is shown to be a generalization of the sequential probability ratio test. Under Bayesian assumptions, it is argued that the MSPRT approximates the much more complicated optimal test when error probabilities are small and expected stopping times are large. Bounds on error probabilities are derived, and asymptotic expressions for the stopping time and error probabilities are given. A design procedure is presented for determining the parameters of the MSPRT. Two examples involving Gaussian densities are included, and comparisons are made between simulation results and asymptotic expressions. Comparisons with Bayesian fixed sample size tests are also made, and it is found that the MSPRT requires two to three times fewer samples on average.>

Decentralized detection problems are studied where the sensor distributions are not specified completely. The sensor distributions are assumed to belong to known uncertainty classes. It is shown for a broad class of such problems that a set of least favorable distributions exists for minimax robust testing between the hypotheses. It is hence established that the corresponding minimax robust tests are solutions to simple decentralized detection problems for which the sensor distributions are specified to be the least favorable distributions.>

A decentralized sequential detection problem is considered in which each one of a set of sensors receives a sequence of observations about the hypothesis. Each sensor sends a sequence of summary messages to the fusion center where a sequential test is carried out to determine the true hypothesis. A Bayesian framework for this problem is introduced, and for the case when the information structure in the system is quasi-classical, it is shown that the problem is tractable. A detailed analysis of this case is presented, along with some numerical results.>