BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Venugopal V. Veeravalli

Venugopal V. Veeravalli appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITmath.STStatistics Theoryeess.SPMachine Learningmath.OCmath.PRGenomicsApplicationsComputationData Structures and AlgorithmsMultiagent SystemsNetworking and Internet ArchitectureQuantitative MethodsSystems and Control

Catalog footprint

What is connected

39works
16topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

39 published item(s)

preprint2024arXiv

Robust Multi-Hypothesis Testing with Moment Constrained Uncertainty Sets

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 samples. 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 using finite samples from the alphabet. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Adaptive Step-Size Methods for Compressed SGD

Compressed Stochastic Gradient Descent (SGD) algorithms have been recently proposed to address the communication bottleneck in distributed and decentralized optimization problems, such as those that arise in federated machine learning. Existing compressed SGD algorithms assume the use of non-adaptive step-sizes(constant or diminishing) to provide theoretical convergence guarantees. Typically, the step-sizes are fine-tuned in practice to the dataset and the learning algorithm to provide good empirical performance. Such fine-tuning might be impractical in many learning scenarios, and it is therefore of interest to study compressed SGD using adaptive step-sizes. Motivated by prior work on adaptive step-size methods for SGD to train neural networks efficiently in the uncompressed setting, we develop an adaptive step-size method for compressed SGD. In particular, we introduce a scaling technique for the descent step in compressed SGD, 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 also show through simulation examples that without this scaling, the algorithm can fail to converge. We present experimental results on deep neural networks for real-world datasets, and compare the performance of our proposed algorithm with previously proposed compressed SGD methods in literature, and demonstrate improved performance on ResNet-18, ResNet-34 and DenseNet architectures for CIFAR-100 and CIFAR-10 datasets at various levels of compression.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quickest Change Detection in the Presence of Transient Adversarial Attacks

We study a monitoring system in which the distributions of sensors' observations change from a nominal distribution to an abnormal distribution in response to an adversary's presence. The system uses the quickest change detection procedure, the Shewhart rule, to detect the adversary that uses its resources to affect the abnormal distribution, so as to hide its presence. The metric of interest is the probability of missed detection within a predefined number of time-slots after the changepoint. Assuming that the adversary's resource constraints are known to the detector, we find the number of required sensors to make the worst-case probability of missed detection less than an acceptable level. The distributions of observations are assumed to be Gaussian, and the presence of the adversary affects their mean. We also provide simulation results to support our analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Dynamic Spectrum Access using Stochastic Multi-User Bandits

A stochastic multi-user multi-armed bandit framework is used to develop algorithms for uncoordinated spectrum access. In contrast to prior work, it is assumed that rewards can be non-zero even under collisions, thus allowing for the number of users to be greater than the number of channels. The proposed algorithm consists of an estimation phase and an allocation phase. It is shown that if every user adopts the algorithm, the system wide regret is order-optimal of order $O(\log T)$ over a time-horizon of duration $T$. The regret guarantees hold for both the cases where the number of users is greater than or less than the number of channels. The algorithm is extended to the dynamic case where the number of users in the system evolves over time, and is shown to lead to sub-linear regret.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Non-Parametric Quickest Detection of a Change in the Mean of an Observation Sequence

We study the problem of quickest detection of a change in the mean of an observation sequence, under the assumption that both the pre- and post-change distributions have bounded support. We first study the case where the pre-change distribution is known, and then study the extension where only the mean and variance of the pre-change distribution are known. In both cases, no knowledge of the post-change distribution is assumed other than that it has bounded support. For the case where the pre-change distribution is known, we derive a test that asymptotically minimizes the worst-case detection delay over all post-change distributions, as the false alarm rate goes to zero. We then study the limiting form of the optimal test as the gap between the pre- and post-change means goes to zero, which we call the Mean-Change Test (MCT). We show that the MCT can be designed with only knowledge of the mean and variance of the pre-change distribution. We validate our analysis through numerical results for detecting a change in the mean of a beta distribution. We also demonstrate the use of the MCT for pandemic monitoring.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Resource Allocation in NOMA-based Self-Organizing Networks using Stochastic Multi-Armed Bandits

To achieve high data rates and better connectivity in future communication networks, the deployment of different types of access points (APs) is underway. In order to limit human intervention and reduce costs, the APs are expected to be equipped with self-organizing capabilities. Moreover, due to the spectrum crunch, frequency reuse among the deployed APs is inevitable, aggravating 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 in future communication networks. With the aim of reducing ICI in a SON, this paper proposes a novel solution for the uncoordinated channel and power allocation problems. Based on the multi-player multi-armed bandit (MAB) framework, the proposed technique does not require any communication or coordination 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 (NOMA) is used to allow 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 of O(log^2 T ), which is validated by simulation results. Extensive numerical results also reveal that the proposed technique significantly outperforms the well-known upper confidence bound (UCB) algorithm, by achieving more than a twofold increase in the energy efficiency.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quickest Detection of Growing Dynamic Anomalies in Networks

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 a different set 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 by 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 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quickest Detection of Moving Anomalies in Sensor Networks

The problem of sequentially detecting a moving anomaly which affects different parts of a sensor network with time is studied. Each network sensor is characterized by a non-anomalous and anomalous distribution, governing the generation of sensor data. Initially, the observations of each sensor are generated according to the corresponding non-anomalous distribution. After some unknown but deterministic time instant, a moving anomaly emerges, affecting different sets of sensors as time progresses. As a result, the observations of the affected sensors are generated according to the corresponding anomalous distribution. Our goal is to design a stopping procedure to detect the emergence of the anomaly as quickly as possible, subject to constraints on the frequency of false alarms. The problem is studied in a quickest change detection framework where it is assumed that the evolution of the anomaly is unknown but deterministic. To this end, we propose a modification of Lorden's worst average detection delay metric to account for the trajectory of the anomaly that maximizes the detection delay of a candidate detection procedure. We establish that a Cumulative Sum-type test solves the resulting sequential detection problem exactly when the sensors are homogeneous. For the case of heterogeneous sensors, the proposed detection scheme can be modified to provide a first-order asymptotically optimal algorithm. We conclude by presenting numerical simulations to validate our theoretical analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust Mean Estimation in High Dimensions via $\ell_0$ Minimization

We study the robust mean estimation problem in high dimensions, where $α<0.5$ fraction of the data points can be arbitrarily corrupted. Motivated by compressive sensing, we formulate the robust mean estimation problem as the minimization of the $\ell_0$-`norm' of the outlier indicator vector, under second moment constraints on the inlier data points. We prove that the global minimum of this objective is order optimal for the robust mean estimation problem, and we propose a general framework for minimizing the objective. We further leverage the $\ell_1$ and $\ell_p$ $(0<p<1)$, minimization techniques in compressive sensing to provide computationally tractable solutions to the $\ell_0$ minimization problem. Both synthetic and real data experiments demonstrate that the proposed algorithms significantly outperform state-of-the-art robust mean estimation methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tightening Mutual Information Based Bounds on Generalization Error

An information-theoretic upper bound on the generalization error of supervised learning algorithms is derived. The bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm. The bound is derived under more general conditions on the loss function than in existing studies; nevertheless, it provides a tighter characterization of the generalization error. Examples of learning algorithms are provided to demonstrate the the tightness of the bound, and to show that it has a broad 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. Finally, it is demonstrated that, unlike existing bounds, which are difficult to compute and evaluate empirically, the proposed bound can be estimated easily in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Data-driven Voltage Regulation in Radial Power Distribution Systems

In this paper, we develop a data-driven voltage regulation framework for distributed energy resources (DERs) in a balanced radial power distribution system. The objective is to determine optimal DER power injections that minimize the voltage deviations from a desirable voltage range without knowing a complete power distribution system model a priori. The nonlinear relationship between the voltage magnitudes and the power injections in the power distribution system is approximated by a linear model, the parameters of which---referred to as the voltage sensitivities---can be computed directly using information on the topology and the line parameters. Assuming the knowledge of feasible topology configurations and distribution line resistance-to-reactance ratios, the true topology configuration and corresponding line parameters can be estimated effectively using a few sets of measurements on voltage magnitudes and power injections. Using the estimated voltage sensitivities, the optimal DER power injections can be readily determined by solving a convex optimization problem. The proposed framework is intrinsically adaptive to changes in system conditions such as unknown topology reconfiguration due to its data-driven nature. The effectiveness and efficiency of the proposed framework is validated via numerical simulations on the IEEE 123-bus distribution test feeder.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Linear-Complexity Exponentially-Consistent Tests for Universal Outlying Sequence Detection

The problem of universal outlying sequence detection is studied, where the goal is to detect outlying sequences among $M$ sequences of samples. A sequence is considered as outlying 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, we are interested in identifying all the outlying sequences without knowing the underlying generating distributions. In this paper, a class of tests based on distribution clustering is proposed. These tests are shown to be exponentially consistent with linear time complexity in $M$. Numerical results demonstrate that our clustering-based tests achieve similar performance to existing tests, while being considerably more computationally efficient.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Detecting Sparse Mixtures: Rate of Decay of Error Probability

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 via the likelihood ratio test. 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 $χ^2$-divergence rather than the Kullback-Leibler divergence for "weak" signals and can be independent of divergence for "strong" signals. Our contribution is the first characterization of the rate of decay of the error probability for this problem for both the false alarm and miss probabilities.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Adaptive Sequential Optimization with Applications to Machine Learning

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Universal Outlying sequence detection For Continuous Observations

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 $π$, but otherwise unknown. A universal test based on KL divergence is built to approximate the maximum likelihood test, with known $π$ and unknown $μ$. A data-dependent partitions based KL divergence estimator is employed. Such a KL divergence estimator is further shown to converge to its true value exponentially fast when the density ratio satisfies $0<K_1\leq \frac{dμ}{dπ}\leq K_2$, where $K_1$ and $K_2$ are positive constants, and this further implies that the test is exponentially consistent. The performance of the test is compared with that of a recently introduced test for this problem based on the machine learning approach of maximum mean discrepancy (MMD). We identify regimes in which the KL divergence based test is better than the MMD based test.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Data-Efficient Minimax Quickest Change Detection with Composite Post-Change Distribution

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 some 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 the additional condition that either the post-change family of distributions is finite, or both the pre- and post-change distributions belong to a one parameter exponential family, it is shown that the proposed algorithm is asymptotically optimal, uniformly for all possible post-change distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Flexible Backhaul Design and Degrees of Freedom for Linear Interference Networks

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 (4B-1)/(4B), 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 is shown to apply for more general locally connected and two-dimensional networks.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Universal Outlier Hypothesis Testing

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). It is shown that the generalized likelihood test is universally exponentially consistent under various settings. The achievable error exponent is also characterized. In the other settings, it is also shown that there cannot exist any universally exponentially consistent test.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Universal Scheme for Optimal Search and Stop

The problem of universal search and stop using an adaptive search policy is considered. When the target location is searched, the observation is distributed according to the target distribution, otherwise it is distributed according to the absence distribution. A universal sequential scheme for search and stop is proposed using only the knowledge of the absence distribution, and its asymptotic performance is analyzed. The universal test is shown to yield a vanishing error probability, and to achieve the optimal reliability when the target is present, universally for every target distribution. Consequently, it is established that the knowledge of the target distribution is only useful for improving the reliability for detecting a missing target. It is also shown that a multiplicative gain for the search reliability equal to the number of searched locations is achieved by allowing adaptivity in the search.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Universal Sequential Outlier Hypothesis Testing

Universal outlier hypothesis testing is studied in a sequential setting. Multiple observation sequences are collected, a small subset of which are outliers. A sequence is considered an outlier if the observations in that sequence are generated by an "outlier" distribution, distinct from a common "typical" distribution governing the majority of the sequences. Apart from being distinct, the outlier and typical distributions can be arbitrarily close. The goal is to design a universal test to best discern all the outlier sequences. A universal test with the flavor of the repeated significance test is proposed and its asymptotic performance is characterized under various universal settings. The proposed test is shown to be universally consistent. For the model with identical outliers, the test is shown to be asymptotically optimal universally when the number of outliers is the largest possible and with the typical distribution being known, and its asymptotic performance otherwise is also characterized. An extension of the findings to the model with multiple distinct outliers is also discussed. In all cases, it is shown that the asymptotic performance guarantees for the proposed test when neither the outlier nor typical distribution is known converge to those when the typical distribution is known.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Controlled Sensing for Multihypothesis Testing

The problem of multiple hypothesis testing with observation control is considered in both fixed sample size and sequential settings. In the fixed sample size setting, for binary hypothesis testing, the optimal exponent for the maximal error probability corresponds to the maximum Chernoff information over the choice of controls, and a pure stationary open-loop control policy is asymptotically optimal within the larger class of all causal control policies. For multihypothesis testing in the fixed sample size setting, lower and upper bounds on the optimal error exponent are derived. It is also shown through an example with three hypotheses that the optimal causal control policy can be strictly better than the optimal open-loop control policy. In the sequential setting, a test based on earlier work by Chernoff for binary hypothesis testing, is shown to be first-order asymptotically optimal for multihypothesis testing in a strong sense, using the notion of decision making risk in place of the overall probability of error. Another test is also designed to meet hard risk constrains while retaining asymptotic optimality. The role of past information and randomization in designing optimal control policies is discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Dynamic Interference Management

A linear interference network is considered. Long-term fluctuations (shadow fading) in the wireless channel can lead to any link being erased with probability p. Each receiver is interested in one unique message that can be available at M transmitters. In a cellular downlink scenario, the case where M=1 reflects the cell association problem, and the case where M>1 reflects the problem of setting up the backhaul links for Coordinated Multi-Point (CoMP) transmission. In both cases, we analyze Degrees of Freedom (DoF) optimal schemes for the case of no erasures, and propose new schemes with better average DoF performance at high probabilities of erasure. For M=1, we characterize the average per user DoF, and identify the optimal assignment of messages to transmitters at each value of p. For general values of M, we show that there is no strategy for assigning messages to transmitters in large networks that is optimal for all values of p.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Interference Channels with Coordinated Multi-Point Transmission: Degrees of Freedom, Message Assignment, and Fractional Reuse

Coordinated Multi-Point (CoMP) transmission is an infrastructural enhancement under consideration for next generation wireless networks. In this work, 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 > 1 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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

MCUIUC -- A New Framework for Metagenomic Read Compression

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

MetaPar: Metagenomic Sequence Assembly via Iterative Reclassification

We introduce a parallel algorithmic architecture for metagenomic sequence assembly, termed MetaPar, which allows for significant reductions in assembly time and consequently enables the processing of large genomic datasets on computers with low memory usage. The gist of the approach is to iteratively perform read (re)classification based on phylogenetic marker genes and assembler outputs generated from random subsets of metagenomic reads. Once a sufficiently accurate classification within genera is performed, de novo metagenomic assemblers (such as Velvet or IDBA-UD) or reference based assemblers may be used for contig construction. We analyze the performance of MetaPar on synthetic data consisting of 15 randomly chosen species from the NCBI database through the effective gap and effective coverage metrics.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Data-Efficient Quickest Change Detection in Minimax Settings

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 trade-off 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 work is guided by the insights gained from an earlier study of a Bayesian version of this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Degrees of Freedom (DoF) of Locally Connected Interference Channels with Coordinated Multi-Point (CoMP) Transmission

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. [1] A. Lapidoth, S. Shamai (Shitz) and M. A. Wigger, "A linear interference network with local Side-Information," in Proc. IEEE International Symposium on Information Theory (ISIT), Nice, Jun. 2007.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Ensemble Properties of RVQ-Based Limited-Feedback Beamforming Codebooks

The ensemble properties of Random Vector Quantization (RVQ) codebooks for limited-feedback beamforming in multi-input multi-output (MIMO) systems are studied with the metrics of interest being the received SNR loss and mutual information loss, both relative to a perfect channel state information (CSI) benchmark. The simplest case of unskewed codebooks is 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 ($N_t$), and spatial correlation. In particular, it is established that: i) the loss metrics are a product of two components -- a quantization component and a channel-dependent component; ii) the quantization component, which is also common to analysis of channels with independent and identically distributed (i.i.d.) fading, decays as $B$ increases at the rate $2^{-B/(N_t-1)}$; iii) the channel-dependent component reflects the condition number of the channel. Further, the precise connection between the received 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 optimal 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Optimal Message Assignments for Interference Channels with CoMP Transmission

The degrees of freedom (DoF) number of the fully connected K-user Gaussian interference channel is known to be K/2. In [1], the DoF for the same channel model was studied while allowing each message to be available at its own transmitter as well as M-1 successive transmitters. In particular, it was shown that the DoF gain through cooperation does not scale with the number of users K for a fixed value of M, i.e., the per user DoF number is 1/2 . In this work, we relax the cooperation constraint such that each message can be assigned to M transmitters without imposing further constraints on their location. Under the new constraint, we study properties for different message assignments in terms of the gain in the per user DoF number over that achieved without cooperation. In particular, we show that a local cooperation constraint that confines the transmit set of each message within a o(K) radius cannot achieve a per user DoF number that is greater than 1/2. Moreover, we show that the same conclusion about the per user DoF number holds for any assignment of messages such that each message cannot be available at more than two transmitters. Finally, for the case where M > 2, we do not know whether a per user DoF number that is greater than 1/2 is achievable. However, we identify a candidate class of message assignments that could potentially lead to a positive answer. [1] V. S. Annapureddy, A. El Gamal, and V. V. Veervalli, "Degrees of Freedom of Interference Channels with CoMP Transmission and Reception," Submitted to IEEE Trans. Inf. Theory, Sep. 2011

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Strategies for Communication and Remote Estimation with an Energy Harvesting Sensor

We consider a remote estimation problem with an energy harvesting sensor and a remote estimator. The sensor observes the state of a discrete-time source which may be a finite state Markov chain or a multi-dimensional linear Gaussian system. It harvests energy from its environment (say, for example, through a solar cell) and uses this energy for the purpose of communicating with the estimator. Due to the randomness of energy available for communication, the sensor may not be able to communicate all the time. The sensor may also want to save its energy for future communications. The estimator relies on messages communicated by the sensor to produce real-time estimates of the source state. We consider the problem of finding a communication scheduling strategy for the sensor and an estimation strategy for the estimator that jointly minimize an expected sum of communication and distortion costs over a finite time horizon. Our goal of joint optimization leads to a decentralized decision-making problem. By viewing the problem from the estimator's perspective, we obtain a dynamic programming characterization for the decentralized decision-making problem that involves optimization over functions. Under some symmetry assumptions on the source statistics and the distortion metric, we show that an optimal communication strategy is described by easily computable thresholds and that the optimal estimate is a simple function of the most recently received sensor observation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quickest Change Detection

The problem of detecting changes in the statistical properties of a stochastic system and time series arises in various branches of science and engineering. It has a wide spectrum of important applications ranging from machine monitoring to biomedical signal processing. In all of these applications the observations being monitored undergo a change in distribution in response to a change or anomaly in the environment, and the goal is to detect the change as quickly as possibly, subject to false alarm constraints. In this chapter, two formulations of the quickest change detection problem, Bayesian and minimax, are introduced, and optimal or asymptotically optimal solutions to these formulations are discussed. Then some generalizations and extensions of the quickest change detection problem are described. The chapter is concluded with a discussion of applications and open issues.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Data-Efficient Quickest Change Detection with On-Off Observation Control

In this paper we extend the Shiryaev's quickest change detection formulation by also accounting for the cost of observations used before the change point. The observation cost is captured through the average number of observations used in the detection process before the change occurs. The objective is to select an on-off observation control policy, that decides whether or not to take a given observation, along with the stopping time at which the change is declared, so as to minimize the average detection delay, subject to constraints on both the probability of false alarm and the observation cost. By considering a Lagrangian relaxation of the constraint problem, and using dynamic programming arguments, we obtain an \textit{a posteriori} probability based two-threshold algorithm that is a generalized version of the classical Shiryaev algorithm. We provide an asymptotic analysis of the two-threshold algorithm and show that the algorithm is asymptotically optimal, i.e., the performance of the two-threshold algorithm approaches that of the Shiryaev algorithm, for a fixed observation cost, as the probability of false alarm goes to zero. We also show, using simulations, that the two-threshold algorithm has good observation cost-delay trade-off curves, and provides significant reduction in observation cost as compared to the naive approach of fractional sampling, where samples are skipped randomly. Our analysis reveals that, for practical choices of constraints, the two thresholds can be set independent of each other: one based on the constraint of false alarm and another based on the observation cost constraint alone.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Degrees of Freedom of Interference Channels with CoMP Transmission and Reception

We study the Degrees of Freedom (DoF) of the K-user interference channel with coordinated multi-point (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 is greater than or equal to K+1. For the general case, we derive an outer bound that states that the DoF is bounded above by the ceiling of (K+M_t+M_r-2)/2. 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 . The achievability proofs are based on the notion of algebraic independence from algebraic geometry.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Minimax Robust Quickest Change Detection

The popular criteria of optimality for quickest change detection procedures are the Lorden criterion, the Shiryaev-Roberts-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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Sensor Management for Tracking in Sensor Networks

We study the problem of tracking an object moving through a network of wireless sensors. In order to conserve energy, the sensors may be put into a sleep mode with a timer that determines their sleep duration. It is assumed that an asleep sensor cannot be communicated with or woken up, and hence the sleep duration needs to be determined at the time the sensor goes to sleep based on all the information available to the sensor. Having sleeping sensors in the network could result in degraded tracking performance, therefore, there is a tradeoff between energy usage and tracking performance. We design sleeping policies that attempt to optimize this tradeoff and characterize their performance. As an extension to our previous work in this area [1], we consider generalized models for object movement, object sensing, and tracking cost. For discrete state spaces and continuous Gaussian observations, we derive a lower bound on the optimal energy-tracking tradeoff. It is shown that in the low tracking error regime, the generated policies approach the derived lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Sensor Scheduling for Energy-Efficient Target Tracking in Sensor Networks

In this paper we study the problem of tracking an object moving randomly through a network of wireless sensors. Our objective is to devise strategies for scheduling the sensors to optimize the tradeoff between tracking performance and energy consumption. We cast the scheduling problem as a Partially Observable Markov Decision Process (POMDP), where the control actions correspond to the set of sensors to activate at each time step. Using a bottom-up approach, we consider different sensing, motion and cost models with increasing levels of difficulty. At the first level, the sensing regions of the different sensors do not overlap and the target is only observed within the sensing range of an active sensor. Then, we consider sensors with overlapping sensing range such that the tracking error, and hence the actions of the different sensors, are tightly coupled. Finally, we consider scenarios wherein the target locations and sensors' observations assume values on continuous spaces. Exact solutions are generally intractable even for the simplest models due to the dimensionality of the information and action spaces. Hence, we devise approximate solution techniques, and in some cases derive lower bounds on the optimal tradeoff curves. The generated scheduling policies, albeit suboptimal, often provide close-to-optimal energy-tracking tradeoffs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Sum Capacity of MIMO Interference Channels in the Low Interference Regime

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.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Quickest Change Detection of a Markov Process Across a Sensor Array

Recent attention in quickest change detection in the multi-sensor 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, with a fusion center that has perfect information about the observations and a priori knowledge of the statistics of the change process, is considered. The problem of minimizing the average detection delay subject to false alarm constraints is formulated as a partially observable Markov decision process (POMDP). Insights into the structure of the optimal stopping rule are presented. In the limiting case of rare disruptions, we show that the structure of the optimal test reduces to thresholding the a posteriori probability of the hypothesis that no change has happened. We establish the asymptotic optimality (in the vanishing false alarm probability regime) of this threshold test 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 wrongly assumes that the change propagates instantaneously.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Capacity Results for Block-Stationary Gaussian Fading Channels with a Peak Power Constraint

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. This model subsumes most previously studied Gaussian fading models. We first compute the asymptotic channel capacity in the high SNR regime and show that the behavior of channel capacity depends critically on the channel model. For the special case where the fading process is symbol-by-symbol stationary, we also reveal a fundamental interplay between the codeword length, communication rate, and decoding error probability. Specifically, we show that the codeword length must scale with SNR in order to guarantee that the communication rate can grow logarithmically with SNR with bounded decoding error probability, and we find a necessary condition for the growth rate of the codeword length. We also derive an expression for the capacity per unit energy. Furthermore, we show 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.

0 citations0 reviewsNo code linkedOpen access