Reliable communication of data in modern wireless systems requires accurate channel state information (CSI). Sounding Reference Signal (SRS) based CSI acquisition enables the estimation of the channel between the base station and user equipment through the uplink transmission of known SRS by the user equipment to the base station. However, limited SRS resources and limited Signal to Noise Ratio (SNR) coverage for which SRS-based CSI acquisition can be performed renders the acquisition of CSI challenging. We propose an approach to perform sparse non-uniform SRS resource allocation and use a masked auto-encoder with a vision transformer backbone to reconstruct full band channel from partial sub-band information. Experiments on data emulating transmission over CDL-A, B, and C channels demonstrate that the proposed method can achieve state-of-the-art normalized mean square error (NMSE) using only 25% of the band information. This translates to a four fold increase in SRS resource capacity and 6dB improvement in SRS coverage under current 5G NR specifications.

MOTIVATION: Oncoviruses, pathogens known to cause or increase the risk of cancer, include both common viruses such as human papillomaviruses and rarer pathogens such as human T-lymphotropic viruses. Computational methods for detecting viral DNA from data acquired by modern DNA sequencing technologies have enabled studies of the association between oncoviruses and cancers. Those studies are rendered particularly challenging when multiple species of oncovirus are present in a tumor sample. In such scenarios, merely detecting the presence of a sequencing read of viral origin is insufficiently informative-instead, a more precise characterization of the viral content in the sample is required. RESULTS: We address this need with NextVir, to our knowledge the first multi-class viral classification framework that adapts genomic foundation models to detecting and classifying sequencing reads of oncoviral origin. Specifically, NextVir explores several foundation models-DNABERT-S, Nucelotide Transformer, and HyenaDNA-and efficiently fine-tunes them to enable accurate identification of the sequencing reads' origin. The results demonstrate superior performance of the proposed framework over existing deep learning methods and suggest downstream potential for foundational models in genomics.

Motivated by high resource costs of centralized machine learning schemes as well as data privacy concerns, federated learning (FL) emerged as an efficient alternative that relies on aggregating locally trained models rather than collecting clients' potentially private data. In practice, available resources and data distributions vary from one client to another, creating an inherent system heterogeneity that leads to deterioration of the performance of conventional FL algorithms. In this work, we present a federated quantization-based self-supervised learning scheme (Fed-QSSL) designed to address heterogeneity in FL systems. At clients' side, to tackle data heterogeneity we leverage distributed self-supervised learning while utilizing low-bit quantization to satisfy constraints imposed by local infrastructure and limited communication resources. At server's side, Fed-QSSL deploys de-quantization, weighted aggregation and re-quantization, ultimately creating models personalized to both data distribution as well as specific infrastructure of each client's device. We validated the proposed algorithm on real world datasets, demonstrating its efficacy, and theoretically analyzed impact of low-bit training on the convergence and robustness of the learned models.

While federated learning (FL) systems often utilize quan-tization to battle communication and computational bottle-necks, they have heretofore been limited to deploying fixed-precision quantization schemes. Meanwhile, the concept of mixed-precision quantization (MPQ), where different layers of a deep learning model are assigned varying bit-width, remains unexplored in the FL settings. We present a novel FL algorithm, FedMPQ, which introduces mixed-precision quantization to resource-heterogeneous FL systems. Specifically, local models, quantized so as to satisfy bit-width constraint, are trained by optimizing an objective function that includes a regularization term which promotes reduction of precision in some of the layers without significant performance degradation. The server collects local model updates, de-quantizes them into full-precision models, and then aggregates them into a global model. To initialize the next round of local training, the server relies on the information learned in the previous training round to customize bit-width assignments of the models delivered to different clients. In extensive benchmarking experiments on several model architectures and different datasets in both iid and non-iid settings, FedMPQ outperformed the baseline FL schemes that utilize fixed-precision quantization while in-curring only a minor computational overhead on the par-ticipating devices.

Gradient inversion (GI) attacks present a threat to the privacy of clients in federated learning (FL) by aiming to enable reconstruction of the clients’ data from communicated model updates. A number of such techniques attempts to accelerate data recovery by first reconstructing labels of the samples used in local training. However, existing label extraction methods make strong assumptions that typically do not hold in realistic FL settings. In this paper we present a novel label recovery scheme, Recovering Labels from Local Updates (RLU), which provides near-perfect accuracy when attacking untrained (most vulnerable) models. More significantly, RLU achieves high performance even in realistic real-world settings where the clients in an FL system run multiple local epochs, train on heterogeneous data, and deploy various optimizers to minimize different objective functions. Specifically, RLU estimates labels by solving a least-square problem that emerges from the analysis of the correlation between labels of the data points used in a training round and the resulting update of the output layer. The experimental results on several datasets, architectures, and data heterogeneity scenarios demonstrate that the proposed method consistently outperforms existing baselines, and helps improve quality of the reconstructed images in GI attacks in terms of both PSNR and LPIPS.

We consider a hierarchical inference system with multiple clients connected to a server via a shared communication resource. When necessary, clients with low-accuracy machine learning models can offload classification tasks to a server for processing on a high-accuracy model. We propose a distributed online offloading algorithm which maximizes the accuracy subject to a shared resource utilization constraint thus indirectly realizing accuracy-delay tradeoffs possible given an underlying network scheduler. The proposed algorithm, named Lyapunov-EXP4, introduces a loss structure based on Lyapunov-drift minimization techniques to the bandits with expert advice framework. We prove that the algorithm converges to a near-optimal threshold policy on the confidence of the clients’ local inference without prior knowledge of the system’s statistics and efficiently solves a constrained bandit problem with sublinear regret. We further consider settings where clients may employ multiple thresholds, allowing more aggressive optimization of overall accuracy at a possible loss in fairness. Extensive simulation results on real and synthetic data demonstrate convergence of Lyapunov-EXP4, and show the accuracy-delay-fairness tradeoffs achievable in such systems.

Statistical heterogeneity of data present at client devices in a federated learning (FL) system renders the training of a global model in such systems difficult. Particularly challenging are the settings where due to communication resource constraints only a small fraction of clients can participate in any given round of FL. Recent approaches to training a global model in FL systems with non-IID data have focused on developing client selection methods that aim to sample clients with more informative updates of the model. However, existing client selection techniques either introduce significant computation overhead or perform well only in the scenarios where clients have data with similar heterogeneity profiles. In this paper, we propose HiCS-FL (Federated Learning via Hierarchical Clustered Sampling), a novel client selection method in which the server estimates statistical heterogeneity of a client's data using the client’s update of the network’s output layer and relies on this information to cluster and sample the clients. We analyze the ability of the proposed techniques to compare heterogeneity of different datasets, and characterize convergence of the training process that deploys the introduced client selection method. Extensive experimental results demonstrate that in non-IID settings HiCS-FL achieves faster convergence than state-of-the-art FL client selection schemes. Notably, HiCS-FL drastically reduces computation cost compared to existing selection schemes and is adaptable to different heterogeneity scenarios.

We study non-convex optimization problems where the data is distributed across nodes of a time-varying directed network; this describes dynamic settings in which the communication between network nodes is affected by delays or link failures. The network nodes, which can access only their local objectives and query a stochastic first-order oracle for the gradient estimates, collaborate by exchanging messages with their neighbors to minimize a global objective function. We propose an algorithm for non-convex optimization problems in such settings that leverages stochastic gradient descent with momentum and gradient tracking. We further prove, by analyzing dynamic network systems with gradient acceleration, that the oracle complexity of the proposed algorithm is $\mathcal{O}\left( {1/{\varepsilon ^{1.5}}} \right)$. The results demonstrate superior performance of the proposed framework compared to state-of-the-art related methods used in a variety of machine learning tasks.

Federated learning (FL) enables distribution of machine learning workloads from the cloud to resource-limited edge devices. Unfortunately, current deep networks remain not only too compute-heavy for inference and training on edge devices, but also too large for communicating updates over bandwidth-constrained networks. In this paper, we develop, implement, and experimentally validate a novel FL framework termed Federated Dynamic Sparse Training (FedDST) by which complex neural networks can be deployed and trained with substantially improved efficiency in both on-device computation and in-network communication. At the core of FedDST is a dynamic process that extracts and trains sparse sub-networks from the target full network. With this scheme, "two birds are killed with one stone:'' instead of full models, each client performs efficient training of its own sparse networks, and only sparse networks are transmitted between devices and the cloud. Furthermore, our results reveal that the dynamic sparsity during FL training more flexibly accommodates local heterogeneity in FL agents than the fixed, shared sparse masks. Moreover, dynamic sparsity naturally introduces an "in-time self-ensembling effect'' into the training dynamics, and improves the FL performance even over dense training. In a realistic and challenging non i.i.d. FL setting, FedDST consistently outperforms competing algorithms in our experiments: for instance, at any fixed upload data cap on non-iid CIFAR-10, it gains an impressive accuracy advantage of 10% over FedAvgM when given the same upload data cap; the accuracy gap remains 3% even when FedAvgM is given 2 times the upload data cap, further demonstrating efficacy of FedDST. Code is available at: https://github.com/bibikar/feddst.

Federated learning (FL) is an emerging collaborative machine learning (ML) framework that enables training of predictive models in a distributed fashion where the communication among the participating nodes are facilitated by a central server. To deal with the communication bottleneck at the server, decentralized FL (DFL) methods advocate rely on local communication of nodes with their neighbors according to a specific communication network. In DFL, it is common algorithmic practice to have nodes interleave (local) gradient descent iterations with gossip (i.e., averaging over the network) steps. As the size of the ML models grows, the limited communication bandwidth among the nodes does not permit communication of full-precision messages; hence, it is becoming increasingly common to require that messages belossy, compressedversions of the local parameters. The requirement of communicating compressed messages gives rise to the important question:given a fixed communication budget, what should be our communication strategy to minimize the (training) loss as much as possible?In this article, we explore this direction, and show that in such compressed DFL settings, there are benefits to havingmultiplegossip steps between subsequent gradient iterations, even when the cost of doing so is appropriately accounted for, e.g., by means of reducing the precision of compressed information. In particular, we show that having${\mathcal O}(\log \frac{1}{\epsilon })$gradient iterations with constant step size - and${\mathcal O}(\log \frac{1}{\epsilon })$gossip steps between every pair of these iterations - enables convergence to within$\epsilon$of the optimal value for a class of non-convex problems that arise in the training of deep learning models, namely, smooth non-convex objectives satisfying Polyak-Łojasiewicz condition. Empirically, we show that our proposed scheme bridges the gap between centralized gradient descent and DFL on various machine learning tasks across different network topologies and compression operators.

Identification of the type of communication technology and/or modulation scheme based on detected radio signal are challenging problems encountered in a variety of applications including spectrum allocation and radio interference mitigation. They are rendered difficult due to a growing number of emitter types and varied effects of real-world channels upon the radio signal. Existing spectrum monitoring techniques are capable of acquiring massive amounts of radio and real-time spectrum data using compact sensors deployed in a variety of settings. However, state-of-the-art methods that use such data to classify emitter types and detect communication schemes struggle to achieve required levels of accuracy at a computational efficiency that would allow their implementation on low-cost computational platforms. In this paper, we present a learning framework based on an LSTM denoising auto-encoder designed to automatically extract stable and robust features from noisy radio signals, and infer modulation or technology type using the learned features. The algorithm utilizes a compact neural network architecture readily implemented on a low-cost computational platform while exceeding state-of-the-art accuracy. Results on realistic synthetic as well as over-the-air radio data demonstrate that the proposed framework reliably and efficiently classifies received radio signals, often demonstrating superior performance compared to state-of-the-art methods. Source codes are available athttps://github.com/WuLoli/LSTMDAE.

We consider the problem of decentralized optimization where a collection of agents, each having access to a local cost function, communicate over a time-varying directed network and aim to minimize the sum of those functions. In practice, the amount of information that can be exchanged between the agents is limited due to communication constraints. We propose a communication-efficient algorithm for decentralized convex optimization that rely on sparsification of local updates exchanged between neighboring agents in the network. In directed networks, message sparsification alters column-stochasticity – a property that plays an important role in establishing convergence of decentralized learning tasks. We propose a decentralized optimization scheme that relies on local modification of mixing matrices, and show that it achieves $\mathcal{O}\left( {\frac{{\ln T}}{{\sqrt T }}} \right)$ convergence rate in the considered settings. Experiments validate theoretical results and demonstrate efficacy of the proposed algorithm.

Weak submodular optimization underpins many problems in signal processing and machine learning. For such problems, under a cardinality constraint, a simple greedy algorithm is guaranteed to find a solution with a value no worse than 1 − e−γof the optimal. Given the high cost of queries to large-scale signal processing models, the complexity of GREEDY becomes prohibitive in modern applications. In this work, we study the tradeoff between performance and complexity when one resorts to random sampling strategies to reduce the query complexity of GREEDY. Specifically, we quantify the effect of uniform sampling strategies on the performance through two criteria: (i) the probability of identifying an optimal subset, and (ii) the suboptimality of the solution’s value with respect to the optimal. Building upon this insight, we propose a simple progressive stochastic greedy algorithm, study its approximation guarantees, and consider its applications to dimensionality reduction and feature selection tasks.

Identifying modulation type of a received radio signal is a challenging problem encountered in many applications including radio interference mitigation and spectrum allocation. This problem is rendered challenging by the existence of a large number of modulation schemes and numerous sources of interference. Existing methods for monitoring spectrum readily collect large amounts of radio signals. However, existing state-of-the-art approaches to modulation classification struggle to reach desired levels of accuracy with computational efficiency practically feasible for implementation on low-cost computational platforms. To this end, we propose a learning framework based on an LSTM denoising autoencoder designed to extract robust and stable features from the noisy received signals, and detect the underlying modulation scheme. The method uses a compact architecture that may be implemented on low-cost computational devices while achieving or exceeding state-of-the-art classification accuracy. Experimental results on realistic synthetic and over-the-air radio data show that the proposed framework reliably and efficiently classifies radio signals, and often significantly outperform state-of-the-art approaches.

Pervasive computing applications commonly involve user's personal smartphones collecting data to influence application behavior. Applications are often backed by models that learn from the user's experiences to provide personalized and responsive behavior. While models are often pre-trained on massive datasets, federated learning has gained attention for its ability to train globally shared models on users' private data without requiring the users to share their data directly. However, federated learning requires devices to collaborate via a central server, under the assumption that all users desire to learn the same model. We define a new approach, opportunistic federated learning, in which individual devices belonging to different users seek to learn robust models that are personalized to their user's own experiences. However, instead of learning in isolation, these models opportunistically incorporate the learned experiences of other devices they encounter opportunistically. In this paper, we explore the feasibility and limits of such an approach, culminating in a framework that supports encounter-based pairwise collaborative learning. The use of our opportunistic encounter-based learning amplifies the performance of personalized learning while resisting overfitting to encountered data.

In a variety of problems, a decision-maker is unaware of the loss function associated with a task, yet it has to minimize this unknown loss in order to accomplish the task. Furthermore, the decision-maker’s task may evolve, resulting in a varying loss function. In this setting, we explore sequential decision-making problems modeled by adversarial Markov decision processes, where the loss function may arbitrarily change at every time step. We consider the bandit feedback scenario, where the agent observes only the loss corresponding to its actions. We propose an algorithm, called online relative-entropy policy search with implicit exploration, that achieves a sublinear regret not only in expectation but, more importantly, with high probability. In particular, we prove that by employing an optimistically biased loss estimator, the proposed algorithm achieves a regret of $\tilde{\mathcal{O}}((T|\act||\st|)^{\pp} \sqrt{\tau})$, where $|\st|$ is the number of states, $|\act|$ is the number of actions, $\tau$ is the mixing time, and $T$ is the time horizon. To our knowledge, the proposed algorithm is the first scheme that enjoys such high-probability regret bounds for general adversarial Markov decision processes under the presence of bandit feedback.

We are often interested in clustering objects that evolve over time and identifying solutions to the clustering problem for every time step. Evolutionary clustering provides insight into cluster evolution and temporal changes in cluster memberships while enabling performance superior to that achieved by independently clustering data collected at different time points. In this article we introduce evolutionary affinity propagation (EAP), an evolutionary clustering algorithm that groups data points by exchanging messages on a factor graph. EAP promotes temporal smoothness of the solution to clustering time-evolving data by linking the nodes of the factor graph that are associated with adjacent data snapshots, and introduces consensus nodes to enable cluster tracking and identification of cluster births and deaths. Unlike existing evolutionary clustering methods that require additional processing to approximate the number of clusters or match them across time, EAP determines the number of clusters and tracks them automatically. A comparison with existing methods on simulated and experimental data demonstrates effectiveness of the proposed EAP algorithm.

Reconstructing components of a genomic mixture from data obtained by means of DNA sequencing is a challenging problem encountered in a variety of applications including single individual haplotyping and studies of viral communities. High-throughput DNA sequencing platforms oversample mixture components to provide massive amounts of reads whose relative positions can be determined by mapping the reads to a known reference genome; assembly of the components, however, requires discovery of the reads' origin – an NP-hard problem that the existing methods struggle to solve with the required level of accuracy. In this paper, we present a learning framework based on a graph auto-encoder designed to exploit structural properties of sequencing data. The algorithm is a neural network which essentially trains to ignore sequencing errors and infers the posterior probabilities of the origin of sequencing reads. Mixture components are then reconstructed by finding consensus of the reads determined to originate from the same genomic component. Results on realistic synthetic as well as experimental data demonstrate that the proposed framework reliably assembles haplotypes and reconstructs viral communities, often significantly outperforming state-of-the-art techniques. Source codes, datasets and supplementary document are available at https://github.com/WuLoli/GAEseq.

Haplotype assembly and viral quasispecies reconstruction are challenging tasks concerned with analysis of genomic mixtures using sequencing data. High-throughput sequencing technologies generate enormous amounts of short fragments (reads) which essentially oversample components of a mixture; the representation redundancy enables reconstruction of the components (haplotypes, viral strains). The reconstruction problem, known to be NP-hard, boils down to grouping together reads originating from the same component in a mixture. Existing methods struggle to solve this problem with required level of accuracy and low runtimes; the problem is becoming increasingly more challenging as the number and length of the components increase. This paper proposes a read clustering method based on a convolutional auto-encoder designed to first project sequenced fragments to a low-dimensional space and then estimate the probability of the read origin using learned embedded features. The components are reconstructed by finding consensus sequences that agglomerate reads from the same origin. Mini-batch stochastic gradient descent and dimension reduction of reads allow the proposed method to efficiently deal with massive numbers of long reads. Experiments on simulated, semi-experimental and experimental data demonstrate the ability of the proposed method to accurately reconstruct haplotypes and viral quasispecies, often demonstrating superior performance compared to state-of-the-art methods. Source codes are available at https://github.com/WuLoli/CAECseq.

This paper introduces the MCML approach for empirically studying the learnability of relational properties that can be expressed in the well-known software design language Alloy. A key novelty of MCML is quantification of the performance of and semantic differences among trained machine learning (ML) models, specifically decision trees, with respect to entire (bounded) input spaces, and not just for given training and test datasets (as is the common practice). MCML reduces the quantification problems to the classic complexity theory problem of model counting, and employs state-of-the-art model counters. The results show that relatively simple ML models can achieve surprisingly high performance (accuracy and F1-score) when evaluated in the common setting of using training and test datasets -- even when the training dataset is much smaller than the test dataset -- indicating the seeming simplicity of learning relational properties. However, MCML metrics based on model counting show that the performance can degrade substantially when tested against the entire (bounded) input space, indicating the high complexity of precisely learning these properties, and the usefulness of model counting in quantifying the true performance.

We propose the maximum a posteriori accelerated orthogonal least-squares (MAP-AOLS) algorithm, a novel greedy scheme for accurate reconstruction of a sparse binary signal from its compressed measurements. The algorithm leverages the distributions of the sensing matrix, signal, and noise to find a support set that is optimal in the maximum a posteriori (MAP) sense. This stands in contrast to existing greedy orthogonal least squares (OLS) methods that perform reconstruction without fully exploiting all the available statistical information. In each iteration of the proposed algorithm, the distributions of the sensing matrix, noise, and signal with respect to the support set are used to identify and select the column of the sensing matrix with the largest likelihood ratio of the alternate and null hypotheses. Our extensive simulations demonstrate superiority of MAP-AOLS over existing greedy algorithms with only a minor increase in computational costs. Moreover, the proposed scheme has significantly lower computational complexity than traditional OLS.

An evolutionary self-expressive model for clustering a collection of evolving data points that lie on a union of low-dimensional evolving subspaces is proposed. A parsimonious representation of data points at each time step is learned via a non-convex optimization framework that exploits the self-expressiveness property of the evolving data while taking into account data representation from the preceding time step. The resulting scheme adaptively learns an innovation matrix that captures changes in self-representation of data in consecutive time steps as well as a smoothing parameter reflective of the rate of data evolution. Extensive experiments demonstrate superiority of the proposed framework overs state-of-the-art static subspace clustering algorithms and existing evolutionary clustering schemes.

Accurate path gain models are critical for coverage prediction and radio frequency (RF) planning in wireless communications. In many settings irregular terrain induces blockages and scattering making it difficult to predict the path gain. Current solutions are either computationally expensive or slope-intercept fits that do not capture local deviations due to terrain variation, leading to large prediction errors. We propose to use machine learning to learn path gain based on terrain elevation as features. We implement different neural network architectures with dense and convolutional layers that could include effects difficult to describe with traditional models (e.g. back scatter). We test our framework on an extensive set of measured path gain data and consistently predict with 5 dB Root Mean Squared Error, an 8 dB improvement over traditional slope-intercept solutions.

We study the problem of selecting most informative subset of a large observation set to enable accurate estimation of unknown parameters. This problem arises in a variety of settings in machine learning and signal processing including feature selection, phase retrieval, and target localization. Since for quadratic measurement models the moment matrix of the optimal estimator is generally unknown, majority of prior work resorts to approximation techniques such as linearization of the observation model to optimize the alphabetical optimality criteria of an approximate moment matrix. Conversely, by exploiting a connection to the classical Van Trees’ inequality, we derive new alphabetical optimality criteria without distorting the relational structure of the observation model. We further show that under certain conditions on parameters of the problem these optimality criteria are monotone and (weak) submodular set functions. These results enable us to develop an efficient greedy observation selection algorithm uniquely tailored for quadratic models, and provide theoretical bounds on its achievable utility.

We study the problem of sampling a bandlimited graph signal in the presence of noise, where the objective is to select a node subset of prescribed cardinality that minimizes the signal reconstruction mean squared error (MSE). To that end, we formulate the task at hand as the minimization of MSE subject to binary constraints, and approximate the resulting NP-hard problem via semidefinite programming (SDP) relaxation. Moreover, we provide an alternative formulation based on maximizing a monotone weak submodular function and propose a randomized-greedy algorithm to find a sub-optimal subset. We then derive a worst-case performance guarantee on the MSE returned by the randomized greedy algorithm for general non-stationary graph signals. The efficacy of the proposed methods is illustrated through numerical simulations on synthetic and realworld graphs. Notably, the randomized greedy algorithm yields an order-of-magnitude speedup over state-of-the-art greedy sampling schemes, while incurring only a marginal MSE performance loss.

Motivation: As RNA viruses mutate and adapt to environmental changes, often developing resistance to anti-viral vaccines and drugs, they form an ensemble of viral strains--a viral quasispecies. While high-throughput sequencing (HTS) has enabled in-depth studies of viral quasispecies, sequencing errors and limited read lengths render the problem of reconstructing the strains and estimating their spectrum challenging. Inference of viral quasispecies is difficult due to generally non-uniform frequencies of the strains, and is further exacerbated when the genetic distances between the strains are small. Results: This paper presents TenSQR, an algorithm that utilizes tensor factorization framework to analyze HTS data and reconstruct viral quasispecies characterized by highly uneven frequencies of its components. Fundamentally, TenSQR performs clustering with successive data removal to infer strains in a quasispecies in order from the most to the least abundant one; every time a strain is inferred, sequencing reads generated from that strain are removed from the dataset. The proposed successive strain reconstruction and data removal enables discovery of rare strains in a population and facilitates detection of deletions in such strains. Results on simulated datasets demonstrate that TenSQR can reconstruct full-length strains having widely different abundances, generally outperforming state-of-the-art methods at diversities 1-10% and detecting long deletions even in rare strains. A study on a real HIV-1 dataset demonstrates that TenSQR outperforms competing methods in experimental settings as well. Finally, we apply TenSQR to analyze a Zika virus sample and reconstruct the full-length strains it contains. Availability and implementation: TenSQR is available at https://github.com/SoYeonA/TenSQR. Supplementary information: Supplementary data are available at Bioinformatics online.

Fast and accurate performance estimation is a key challenge in modern system design. Recently, machine learning-based approaches have emerged that allow predicting the performance of an application on a target platform from executions on a different host. However, existing approaches rely on expensive instrumentation that requires source code to be available. We propose a novel sampling-based, binary-level cross-platform prediction method that accurately predicts performance of a workload on a target by relying on various performance statistics sampled on a host using built-in hardware counters. In our proposed framework, samples acquired from the host and target do not satisfy straightforward one-to-one correspondence that characterizes prior instrumentation-based approaches. The resulting alignment problem is NP-hard; to solve it efficiently, we develop a stochastic dynamic coupling (SDC) algorithm which, under mild assumptions, with high probability closely approximates optimal alignment. The prediction model constructed using SDC-aligned samples achieves on average 96.5% accuracy for 45 benchmarks at speeds of over 3 GIPS. At similar accuracies, this is up to 6× faster than instrumentation-based prediction, and approximately twice the speed of executing the same applications natively on our ARM target.

Evolutionary affinity propagation, an evolutionary clustering algorithm that groups data points by exchanging messages on a factor graph, is proposed. The algorithm promotes temporal smoothness of the clustering solutions at distinct temporal snapshots by linking variable nodes of the graph across time, and is capable of detecting cluster births and deaths. Unlike most existing evolutionary clustering methods that require additional processing in order to approximate the number of clusters, evolutionary affinity propagation determines the number of clusters automatically. A comparison with existing methods on simulated and experimental data demonstrates accuracy and robustness of the proposed framework.

We study the problem of approximating a partially observed matrix by a product of two low-rank matrices where the data as well as the factors are constrained to be binary. This computationally challenging task is motivated by the single individual haplotyping problem which attracted considerable attention in computational biology and is of critical importance for personalized medicine applications. We analyze a binary-constrained variant of the alternating minimization algorithm for solving the aforementioned problem in the scenario where the matrices are rank-one, establish its performance and convergence properties, and in doing so provide the first theoretical guarantees for haplotype reconstruction expressed in terms of the minimum error-correction score. Sample complexity required for reconstruction is derived and experiments are performed on both synthetic and real datasets, demonstrating superiority of the proposed framework over competing methods.

We present an algorithm, referred to as Branch and Bound Least-Squares (BBLS), for the recovery of sparse signals from a few linear combinations of their entries. Sparse signal reconstruction is readily cast as the problem of finding a sparse solution to an underdetermined system of linear equations. To solve it, BBLS employs an efficient search strategy of traversing a tree whose nodes represent the columns of the coefficient matrix and selects a subset of those columns by relying on Orthogonal Least-Squares (OLS) procedure. We state sufficient conditions under which in noise-free settings BBLS with high probability constructs a tree path which corresponds to the true support of the unknown sparse signal. Moreover, we empirically demonstrate that BBLS provides performance superior to that of existing algorithms in terms of accuracy, running time, or both. In the scenarios where the columns of the coefficient matrix are characterized by high correlation, BBLS is particularly beneficial and significantly outperforms existing methods.

This paper studies the haplotype assembly problem from an information-theoretic perspective. In the human genome, a haplotype is a sequence of nucleotide bases on a chromosome that differ from the bases in the corresponding positions on the other chromosome in a homologous pair. Haplotype sequences can conveniently be represented by binary strings, which enable us to transform the bioinformatics problem of haplotype assembly into an equivalent information-theoretic problem. Information about the order of bases in a genome is readily inferred using short reads provided by high-throughput DNA sequencing technologies. Performing haplotype assembly is challenging due to limited lengths of the reads and the presence of sequencing errors. In this paper, the recovery of the target pair of haplotype sequences using short reads is transformed into an equivalent joint source-channel coding problem. Two binary messages, representing haplotypes and chromosome memberships of reads, are encoded and transmitted over a channel with erasures and errors, where the channel model reflects salient features of high-throughput sequencing. The focus of this paper is on determining the required number of reads for reliable haplotype reconstruction. For the error-free reading case, erasure decoding is shown to be one of the optimal algorithms enabling reliable haplotype assembly. For the erroneous reading case, spectral partitioning is proved to be an efficient algorithm with orderwise optimal bounds.

In matrix decomposition problems, one often seeks to represent a data matrix by the product of two matrices - one capturing meaningful information contained in the data and the other specifying how this information is combined to generate the data matrix. We consider matrix decomposition that arises in haplotype assembly, an important problem in genomics. The observed matrix contains noisy samples of the product of an informative matrix with rows having entries from a finite alphabet and a matrix with rows that are standard unit basis. Structurally-constrained gradient descent algorithm for finding the two aforementioned matrices is proposed and its convergence is analyzed. Simulation results demonstrate superior accuracy and speed of the proposed method compared to state-of-the-art haplotype assembly techniques.

High-throughput DNA sequencing technologies allow fast and affordable sequencing of individual genomes and thus enable unprecedented studies of genetic variations. Information about variations in the genome of an individual is provided by haplotypes, ordered collections of single nucleotide polymorphisms. Knowledge of haplotypes is instrumental in finding genes associated with diseases, drug development, and evolutionary studies. Haplotype assembly from high-throughput sequencing data is challenging due to errors and limited lengths of sequencing reads. The key observation made in this paper is that the minimum error-correction formulation of the haplotype assembly problem is identical to the task of deciphering a coded message received over a noisy channel-a classical problem in the mature field of communication theory. Exploiting this connection, we develop novel haplotype assembly schemes that rely on the bit-flipping and belief propagation algorithms often used in communication systems. The latter algorithm is then adapted to the haplotype assembly of polyploids. We demonstrate on both simulated and experimental data that the proposed algorithms compare favorably with state-of-the-art haplotype assembly methods in terms of accuracy, while being scalable and computationally efficient.

Wireless network sensors today are deployed geographically in a random manner and are subjected to disturbances caused by natural forces, thereby necessitating real time and accurate estimation of the sensors' locations. In this paper, we consider wireless sensor self-localization problem where sensors are deployed according to a Poisson point process. We model such sensor networks under realistic assumptions about the wireless channel and measurement updates. We propose a novel distributed and sequential algorithm based on inter-node exchange of information for estimating sensor locations and analyze their performance through numerical simulations.

BACKGROUND: Genetic variations predispose individuals to hereditary diseases, play important role in the development of complex diseases, and impact drug metabolism. The full information about the DNA variations in the genome of an individual is given by haplotypes, the ordered lists of single nucleotide polymorphisms (SNPs) located on chromosomes. Affordable high-throughput DNA sequencing technologies enable routine acquisition of data needed for the assembly of single individual haplotypes. However, state-of-the-art high-throughput sequencing platforms generate data that is erroneous, which induces uncertainty in the SNP and genotype calling procedures and, ultimately, adversely affect the accuracy of haplotyping. When inferring haplotype phase information, the vast majority of the existing techniques for haplotype assembly assume that the genotype information is correct. This motivates the development of methods capable of joint genotype calling and haplotype assembly. RESULTS: We present a haplotype assembly algorithm, ParticleHap, that relies on a probabilistic description of the sequencing data to jointly infer genotypes and assemble the most likely haplotypes. Our method employs a deterministic sequential Monte Carlo algorithm that associates single nucleotide polymorphisms with haplotypes by exhaustively exploring all possible extensions of the partial haplotypes. The algorithm relies on genotype likelihoods rather than on often erroneously called genotypes, thus ensuring a more accurate assembly of the haplotypes. Results on both the 1000 Genomes Project experimental data as well as simulation studies demonstrate that the proposed approach enables highly accurate solutions to the haplotype assembly problem while being computationally efficient and scalable, generally outperforming existing methods in terms of both accuracy and speed. CONCLUSIONS: The developed probabilistic framework and sequential Monte Carlo algorithm enable joint haplotype assembly and genotyping in a computationally efficient manner. Our results demonstrate fast and highly accurate haplotype assembly aided by the re-examination of erroneously called genotypes. A C code implementation of ParticleHap will be available for download from https://sites.google.com/site/asynoeun/particlehap.

Soft-constraint semi-supervised affinity propagation (SCSSAP) adds supervision to the affinity propagation (AP) clustering algorithm without strictly enforcing instance-level constraints. Constraint violations lead to an adjustment of the AP similarity matrix at every iteration of the proposed algorithm and to addition of a penalty to the objective function. This formulation is particularly advantageous in the presence of noisy labels or noisy constraints since the penalty parameter of SCSSAP can be tuned to express our confidence in instance-level constraints. When the constraints are noiseless, SCSSAP outperforms unsupervised AP and performs at least as well as the previously proposed semi-supervised AP and constrained expectation maximization. In the presence of label and constraint noise, SCSSAP results in a more accurate clustering than either of the aforementioned established algorithms. Finally, we present an extension of SCSSAP which incorporates metric learning in the optimization objective and can further improve the performance of clustering.

This paper studies the haplotype assembly problem from an information-theoretic perspective. A haplotype is a sequence of nucleotide bases on a chromosome, often conveniently represented by a binary string, that differ from the bases in the corresponding positions on the other chromosome in a homologous pair. Information about the order of bases in a genome is readily inferred using short reads provided by high-throughput DNA sequencing technologies. Associating reads that cover variant positions with specific chromosomes in a homologous pairs, which enables haplotype assembly, is challenging due to limited lengths of the reads and presence of sequencing errors. In this paper, the recovery of the target pair of haplotype sequences using short reads is rephrased as a joint source-channel coding problem. Two messages, representing haplotypes and chromosome memberships of reads, are encoded and transmitted over a channel with erasures and errors, where the channel model reflects salient features of high-throughput sequencing. The focus of this paper is on determining the required number of reads for reliable haplotype reconstruction, and both the necessary and sufficient conditions are presented with order-wise optimal bounds.

Sparse integer least-squares problems come up in a wide range of applications including wireless communications and genomics. The sphere decoding algorithm can find near-optimal solution to these problems with reduced average complexity if the knowledge of sparsity of the unknown vector is used in decoding. In this paper, we formulate a sphere decoding approach that relies on the ℓ0-norm constraint on the unknown vector to solve sparse integer least-squares problems. The expected complexity of this algorithm is derived analytically for sparse alphabets associated with common applications such as sparse channel estimation and validated via simulations. The results indicate superior performance and speed compared to the classical sphere decoding algorithm.

In order to determine an individual's DNA sequence, sequencing platforms often employ shotgun sequencing where multiple identical copies of the DNA strand of interest are randomly fragmented and then the nucleotide content of the short fragments is determined. Assembly of the long DNA strand from short fragments is a computationally challenging task that has attracted significant amount of attention in recent years. We formulate reference-guided assembly as the inference problem on a bipartite graph and solve it using a message-passing algorithm. The message-passing algorithm does not need to rely on the quality score information which expresses reliability of the short reads. To assess the performance of the proposed methodology, we derive an expression for the probability of error of a genie-aided MAP consensus scheme. Simulation results on a Neisseria meningitidis data set demonstrate that the proposed message-passing algorithm performs close to the idealistic MAP consensus scheme.

BACKGROUND: Next-generation DNA sequencing platforms are capable of generating millions of reads in a matter of days at rapidly reducing costs. Despite its proliferation and technological improvements, the performance of next-generation sequencing remains adversely affected by the imperfections in the underlying biochemical and signal acquisition procedures. To this end, various techniques, including statistical methods, are used to improve read lengths and accuracy of these systems. Development of high performing base calling algorithms that are computationally efficient and scalable is an ongoing challenge. RESULTS: We develop model-based statistical methods for fast and accurate base calling in Illumina's next-generation sequencing platforms. In particular, we propose a computationally tractable parametric model which enables dynamic programming formulation of the base calling problem. Forward-backward and soft-output Viterbi algorithms are developed, and their performance and complexity are investigated and compared with the existing state-of-the-art base calling methods for this platform. A C code implementation of our algorithm named Softy can be downloaded from https://sourceforge.net/projects/dynamicprog. CONCLUSION: We demonstrate high accuracy and speed of the proposed methods on reads obtained using Illumina's Genome Analyzer II and HiSeq2000. In addition to performing reliable and fast base calling, the developed algorithms enable incorporation of prior knowledge which can be utilized for parameter estimation and is potentially beneficial in various downstream applications.

MOTIVATION: Next-generation DNA sequencing platforms are becoming increasingly cost-effective and capable of providing enormous number of reads in a relatively short time. However, their accuracy and read lengths are still lagging behind those of conventional Sanger sequencing method. Performance of next-generation sequencing platforms is fundamentally limited by various imperfections in the sequencing-by-synthesis and signal acquisition processes. This drives the search for accurate, scalable and computationally tractable base calling algorithms capable of accounting for such imperfections. RESULTS: Relying on a statistical model of the sequencing-by-synthesis process and signal acquisition procedure, we develop a computationally efficient base calling method for Illumina's sequencing technology (specifically, Genome Analyzer II platform). Parameters of the model are estimated via a fast unsupervised online learning scheme, which uses the generalized expectation-maximization algorithm and requires only 3 s of running time per tile (on an Intel i7 machine @3.07GHz, single core)-a three orders of magnitude speed-up over existing parametric model-based methods. To minimize the latency between the end of the sequencing run and the generation of the base calling reports, we develop a fast online scalable decoding algorithm, which requires only 9 s/tile and achieves significantly lower error rates than the Illumina's base calling software. Moreover, it is demonstrated that the proposed online parameter estimation scheme efficiently computes tile-dependent parameters, which can thereafter be provided to the base calling algorithm, resulting in significant improvements over previously developed base calling methods for the considered platform in terms of performance, time/complexity and latency. AVAILABILITY: A C code implementation of our algorithm can be downloaded from http://www.cerc.utexas.edu/OnlineCall/.

BACKGROUND: Next-generation sequencing systems are capable of rapid and cost-effective DNA sequencing, thus enabling routine sequencing tasks and taking us one step closer to personalized medicine. Accuracy and lengths of their reads, however, are yet to surpass those provided by the conventional Sanger sequencing method. This motivates the search for computationally efficient algorithms capable of reliable and accurate detection of the order of nucleotides in short DNA fragments from the acquired data. RESULTS: In this paper, we consider Illumina's sequencing-by-synthesis platform which relies on reversible terminator chemistry and describe the acquired signal by reformulating its mathematical model as a Hidden Markov Model. Relying on this model and sequential Monte Carlo methods, we develop a parameter estimation and base calling scheme called ParticleCall. ParticleCall is tested on a data set obtained by sequencing phiX174 bacteriophage using Illumina's Genome Analyzer II. The results show that the developed base calling scheme is significantly more computationally efficient than the best performing unsupervised method currently available, while achieving the same accuracy. CONCLUSIONS: The proposed ParticleCall provides more accurate calls than the Illumina's base calling algorithm, Bustard. At the same time, ParticleCall is significantly more computationally efficient than other recent schemes with similar performance, rendering it more feasible for high-throughput sequencing data analysis. Improvement of base calling accuracy will have immediate beneficial effects on the performance of downstream applications such as SNP and genotype calling.

We develop distributed algorithms for efficient spectrum access strategies in cognitive radio relay networks. In our setup, primary users permit secondary users access to the resource (spectrum) as long as they consent to aiding the primary users as relays in addition to transmitting their own data. Given a pool of primary and secondary users, we desire to optimize overall network utility by determining the best configuration/pairing of secondary users with primary users. This optimization can be stated in a form similar to the maximum weighted matching problem. Given such formulation, we develop an algorithm based on affinity propagation technique that is completely distributed in its structure. We demonstrate the convergence of the developed algorithm and show that it performs close to the optimal centralized scheme.

Performance of DNA sequencing-by-synthesis systems is fundamentally limited by the stochastic nature of the under lying biochemical process. We develop a novel graphical representation of sequencing-by-synthesis which allows for computationally efficient base-calling via message-passing algorithms. Computational studies indicate that the proposed message-passing technique outperforms existing base-calling methods.

This paper applies affinity propagation (AP) to develop distributed solutions for routing over networks. AP is a message passing algorithm for unsupervised learning. This paper demonstrates that AP can be generalized and applied to a wide class of problems in networking. In particular, AP can be used to develop distributed routing mechanisms for networks. Simulation results demonstrate that the proposed schemes compare favorably with the existing methods.

Estimation of the amounts of target molecules in real-time affinity-based biosensors is studied. The problem is mapped to inferring the parameters of a temporally sampled diffusion process. To solve it, we rely on a sequential Monte Carlo algorithm which generates particles using transition density of the diffusion process. The transition density is not available in a closed form and is thus approximated using Hermite polynomial expansion. Simulations and experimental results demonstrate effectiveness of the proposed scheme, and show that it outperforms competing techniques.

A new class of message-passing algorithms for motif finding is presented. Motif finding is the problem of identifying a collection of common subsequences within a given set of DNA sequences. It can be cast as an integer linear program (ILP). Message-passing techniques are a computationally efficient alternative to the often infeasible combinatorial solutions to the ILP. We introduce a new graphical representation of the ILP formulation of the problem, and use it to develop new message-passing algorithms for motif finding. Simulation results demonstrate that the new algorithms have better performance and convergence properties than the previously proposed solutions.

We consider the state estimation problem in distributed nonlinear systems with bandwidth constraints. In particular, we focus on the sensor networks with limited communication between the sensor nodes and the fusion center. Two practical bandwidth-saving methods are considered: (1) recursive filtering with quantized innovations, and (2) compressive sampling of sparse signals. For both scenarios, Rao-Blackwellized unscented Kalman filter (RBUKF) based methods are developed. The simulation results demonstrate that the proposed algorithms closely track the original signal.

Gene regulatory networks are highly complex dynamical systems of biomolecular components - genes, mRNA, proteins. These components interact with each other and through those interactions determine gene expression levels, i.e., determine the rate of gene transcription to mRNA and, consequently, the rate of mRNA translation to proteins. In this paper, a particle filter with MCMC move step is employed for the estimation of parameters in a gene regulatory network modeled by a chemical Langevin equation. Simulations demonstrate that the proposed technique outperforms previously considered methods.

In sequencing-by-synthesis systems, determining the order of nucleotides of a DNA fragment can be cast as an ML sequence detection (MLSD) problem. Solving it via exhaustive search is prohibitive even for relatively short DNA sequences. Symbol-by-symbol and partial-MLSD solutions are computationally feasible but sacrifice the optimal performance. In this paper, we modify the so-called sphere decoding algorithm to efficiently solve the MLSD problem in sequencing-by-synthesis systems. We analyze the expected complexity of the algorithm, and demonstrate via simulations that it significantly outperforms heuristic techniques.

Estimation of the DNA copy number in a given biological sample is an important problem in genomics. Quantitative polymerase chain reaction (qPCR) systems detect the target DNA molecules by amplifying their number through a series of thermal cycles and measuring the amount of created amplicons in each cycle. Ideally, the number of target molecules doubles at the end of each cycle. However, in practice, due to biochemical noise the efficiency of the qPCR reaction - defined as the fraction of the target molecules which are successfully copied during a cycle - is always less than1. In this paper, we formulate the problem of the joint maximum-likelihood estimation of the qPCR efficiency and the initial DNA copy number. Then, we analytically determine the limits of performance of qPCR by deriving the Cramer-Rao lower bound on the mean-square estimation error. As indicated by simulation studies, the performance of the proposed estimator is superior compared to competing statistical approaches. The proposed approach is validated using experimental data.

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary andq-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined overFq(e.g. Reed- Solomon codes) and transmitted overq-ary symmetric channels is derived and used in the analysis. We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed.

Conventional fluorescent-based microarrays acquire data after the hybridization phase. During this phase, the target analytes bind to the capturing probes on the array and, by the end of it, supposedly reach a steady state. Therefore, conventional microarrays attempt to detect and quantify the targets with a single data point taken in the steady-state. On the other hand, a novel technique, the so-called real-time microarray, capable of recording the kinetics of hybridization in fluorescent-based microarrays has recently been proposed in (Hassibi, 2007). The richness of the information obtained therein promises higher signal-to-noise ratio, smaller estimation error, and broader assay detection dynamic range compared to conventional microarrays. In the current paper, we develop a probabilistic model for real-time microarrays and describe a procedure for the estimation of target amounts therein. Moreover, leveraging on system identification ideas, we propose a novel technique for the elimination of cross-hybridization.

DNA microarrays comprising tens of thousands of probe spots are currently being employed to test multitude of targets in a single experiment. Typically, each microarray spot contains a large number of copies of a single probe designed to capture a single target, and hence collects only a single data point. This is a wasteful use of the sensing resources in comparative DNA microarray experiments, where a test sample is measured relative to a reference sample. Since only a small fraction of the total number of genes represented by the two samples is differentially expressed, a vast number of probe spots will not provide any useful information. To this end we consider an alternative design, the so-called compressed microarrays, wherein each spot is a composite of several different probes and the total number of spots is potentially much smaller than the number of targets being tested. Fewer spots directly translates to significantly lower costs due to cheaper array manufacturing, simpler image acquisition and processing, and smaller amount of genomic material needed for experiments. To recover signals from compressed microarray measurements, we leverage ideas from compressive sampling. Moreover, we propose an algorithm which has far less computational complexity than the widely-used linear-programming-based methods, and can also recover signals with less sparsity.

In multi-antenna communication systems, channel information is often not known at the receiver. To fully exploit bandwidth resources of the system and ensure practical feasibility of the receiver, channel parameters are often estimated blindly and then employed in the design of signal detection algorithms. Instead of separating channel estimation from signal detection, in this paper we focus on the joint channel estimation and signal detection problem in a single-input multiple-output (SIMO) system. It is well known that finding solution to this optimization requires solving an integer maximization of a quadratic form and is, in general, an NP hard problem. To solve it, we propose an approximate algorithm based on the semi-definite program (SDP) relaxation. We derive a bound on the pairwise probability of error (PEP) of the proposed algorithm and show that, the algorithm achieves the same diversity as the exact maximum-likelihood (ML) decoder. The computed PEP implies that, over a wide range of system parameters, the proposed algorithm requires moderate increase in the signal-to-noise ratio (SNR) in order to achieve performance comparable to that of the ML decoder but with often significantly lower complexity.

Estimation of DNA copy number in a given biological sample is an extremely important problem in genomics. This problem is especially challenging when the number of the DNA strands is minuscule, which is often the case in applications such as pathogen and genetic mutation detection. A recently developed technique, real-time polymerase chain reaction (PCR), amplifies the number of initial target molecules by replicating them through a series of thermal cycles. Ideally, the number of target molecules doubles at the end of each cycle. However, in practice, due to biochemical noise the efficiency of the PCR reaction, defined as the fraction of target molecules which are successfully copied during a cycle, is always less than 1. In this paper, we formulate the problem of joint maximum-likelihood estimation of the PCR efficiency and the initial DNA copy number. As indicated by simulation studies, the performance of the proposed estimator is superior with respect to competing statistical approaches. Moreover, we compute the Cramer-Rao lower bound on the mean-square estimation error.

In multi-antenna communication systems, channel information is often not known at the receiver. To fully exploit the bandwidth resources of the system and ensure the practical feasibility of the receiver, the channel parameters are often estimated and then employed in the design of signal detection algorithms. However, sometimes communication can occur in the environment where learning the channel coefficients becomes infeasible. In this paper we consider the problem of maximum-likelihood (ML)-detection in single-input multiple-output (SIMO) systems when the channel information is completely unavailable at the receiver and when employed signalling at the transmitter is q-PSK. It is well known that finding the solution to this optimization requires solving an integer maximization of a quadratic form and is, in general, an NP hard problem. To solve it, we propose an approximate algorithm based on the semi-definite program (SDP) relaxation. We derive a bound on the pairwise probability of error (PEP) of the proposed algorithm and show that, the algorithm achieves the same diversity as the exact maximum-likelihood (ML) decoder. Furthermore, we prove that in the limit of large system dimension this bound differs from the corresponding one in the exact ML case by at most 3.92 dB if the transmitted symbols are from 2 or 4-PSK constellations and by at most 2.55 dB if the transmitted symbols are from 8-PSK constellation. This suggests that the proposed algorithm requires moderate increase in the signal-to-noise ratio (SNR) in order to achieve performance comparable to that of the ML decoder but with often significantly lower complexity.

In many communication applications, maximum-likelihood decoding reduces to solving an integer least-squares problem which is NP hard in the worst-case. On the other hand, it has recently been shown that, over a wide range of dimensions and SNR, the sphere decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. In earlier work, we targeted these two regimes attempting to find faster algorithms by pruning the search tree beyond what is done in the standard sphere decoder. The search tree is pruned by computing lower bounds on the possible optimal solution as we proceed to go down the tree. A trade-off between the computational complexity required to compute the lower bound and the size of the pruned tree is readily observed: the more effort we spend in computing a tight lower bound, the more branches that can be eliminated in the tree. Thus, even though it is possible to prune the search tree (and hence the number of points visited) by several orders of magnitude, this may be offset by the computations required to perform the pruning. In this paper, we propose a computationally efficient lower bound which requires solving a single semi-definite program (SDP) at the top of the search tree; the solution to the SDP is then used to deduce the lower bounds on the optimal solution on all levels of the search tree. Simulation results indicate significant improvement in the computational complexity of the proposed algorithm over the standard sphere decoding

The sum rate capacity of the multi-antenna Gaussian broadcast channel has recently been computed. However, the search for computationally efficient practical schemes that achieve it is still in progress. When the channel state information is fully available at the transmitter, the dirty paper coding (DPC) technique is known to achieve the maximal throughput, but is computationally infeasible. In this paper, we analyze the asymptotic behavior of one of its alternatives - the recently suggested so-called vector perturbation technique. We show that for a square channel, where the number of users is large and equal to the number of transmit antennas, its sum rate approaches that of the DPC technique. More precisely, we show that at both low and high signal-to-noise ratio (SNR), the scheme under consideration is asymptotically optimal. Furthermore, we obtain similar results in the case where the number of users is much larger than the number of transmit antennas

DNA microarray technology relies on the hybridization process which is stochastic in nature. Probabilistic cross-hybridization of non-specific targets, as well as the shot-noise originating from specific targets binding, are among the many obstacles for achieving high accuracy in DNA microarray analysis. In this paper, we use statistical model of hybridization and cross-hybridization processes to derive a lower bound (viz., the Cramer-Rao bound) on the minimum mean-square error of the target concentrations estimation. A preliminary study of the Cramer-Rao bound for estimating the target concentrations suggests that, in some regimes, cross-hybridization may, in fact, be beneficial - a result with potential ramifications for probe design, which is currently focused on minimizing cross-hybridization

The performance of sphere decoding of block codes over a variety of channels is investigated. We derive a tight bound on the performance of maximum likelihood decoding of linear codes on q-ary symmetric channels. We use this result to bound the performance of q-ary hard decision sphere decoders. We also derive a tight bound on the performance of soft decision sphere decoders on the AWGN channel for BPSK and M-PSK modulated block codes. The performance of soft decision sphere decoding of arbitrary finite lattices or block codes is also analyzed

The maximum-likelihood (ML) sequence detection problem for channels with memory is investigated. The Viterbi algorithm (VA) provides an exact solution. Its computational complexity is linear in the length of the transmitted sequence, but exponential in the channel memory length. On the other hand, the sphere decoding (SD) algorithm also solves the ML detection problem exactly, and has expected complexity which is a low-degree polynomial (often cubic) in the length of the transmitted sequence over a wide range of signal-to-noise ratios. We combine the sphere-constrained search strategy of SD with the dynamic programming principles of the VA. The resulting algorithm has the worst-case complexity determined by the VA, but often significantly lower expected complexity

The sum rate capacity of the multi-antenna broadcast channel has recently been computed. However, the search for efficient practical schemes that achieve it is still ongoing. In this paper, we focus on schemes with linear preprocessing of the transmitted data. We propose two criteria for the preceding matrix design: one maximizing the sum rate and the other maximizing the minimum rate among all users. The latter problem is shown to be quasiconvex and is solved exactly via a bisection method. In addition to preceding, we employ a signal scaling scheme that minimizes the average bit-error-rate (BER). The signal scaling scheme is posed as a convex optimization problem, and thus can be solved exactly via efficient interior-point methods. In terms of the achievable sum rate, the proposed technique significantly outperforms traditional channel inversion methods, while having comparable (in fact, often superior) BER performance

In wireless communication systems, channel state information is often assumed to be available at the receiver. Traditionally, a training sequence is used to obtain the estimate of the channel. Alternatively, the channel can be identified using known properties of the transmitted signal. However, the computational effort required to find the joint ML solution to the symbol detection and channel estimation problem increases exponentially with the dimension of the problem. To significantly reduce this computational effort, we formulate the joint ML estimation and detection as an integer least-squares problem, and show that for a wide range of signal-to-noise ratios (SNR) and problem dimensions it can be solved via sphere decoding with expected complexity comparable to the complexity of heuristic techniques

In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem which is NP hard in the worst-case. However, as has recently been shown, over a wide range of dimensions and SNRs, the sphere decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. We target these two regimes and attempt to find faster algorithms by pruning the search tree beyond what is done in the standard sphere decoder. The search tree is pruned by computing lower bounds on the possible optimal solution as we proceed down the tree. We observe a trade-off between the computational complexity required to compute the lower bound and the size of the pruned tree: the more effort spent computing a tight lower bound, the more branches that can be eliminated in the tree. Thus, even though it is possible to prune the search tree (and hence the number of points visited) by several orders of magnitude, this may be offset by the computations required to perform the pruning. All of which suggests the need for computationally-efficient tight lower bounds. We present three different lower bounds (based on spherical-relaxation, polytope-relaxation and duality), simulate their performances and discuss their relative merits.

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We derive tight upper bounds on the performance of sphere decoding of linear block codes. The performance of soft-decision sphere decoding on AWGN channels as well as that of hard-decision sphere decoding on binary symmetric channels is analyzed.

The sum rate capacity of the multi-antenna broadcast channel has recently been computed. However, the search for efficient practical schemes that achieve it is still ongoing. In this paper, we focus on schemes with linear preprocessing of the transmitted data. We propose two criteria for precoding matrix design, one maximizing the sum rate and the other maximizing the minimum rate among all users. The latter problem is shown to be quasiconvex and is solved exactly via the bisection method. In addition to precoding, we employ a signal scaling scheme that minimizes average bit-error-rate (BER). The signal scaling scheme is posed as a convex optimization problem, and thus can be solved exactly via efficient interior-point methods. In terms of achievable sum rate, the proposed technique significantly outperforms traditional channel inversion methods, while having comparable (in fact, often superior) BER performance.

Maximum-likelihood (ML) decoding of linear block codes on a symmetric channel is studied. Exact ML decoding is known to be computationally difficult. We propose an algorithm that finds the exact solution to the ML decoding problem by performing a depth-first search on a tree. The tree is designed from the code generator matrix and pruned based on the statistics of the channel noise. The complexity of the algorithm is a random variable. We characterize the complexity by means of its first moment, which for binary symmetric channels we find in closed-form. The obtained results indicate that the expected complexity of the algorithm is low over a wide range of system parameters.

In recent years, soft iterative decoding techniques have been shown to greatly improve the bit error rate performance of various communication systems. For multiantenna systems employing space-time codes, however, it is not clear what is the best way to obtain the soft information required of the iterative scheme with low complexity. In this paper, we propose a modification of the Fincke-Pohst (sphere decoding) algorithm to estimate the maximum a posteriori probability of the received symbol sequence. The new algorithm solves a nonlinear integer least squares problem and, over a wide range of rates and signal-to-noise ratios, has polynomial-time complexity. Performance of the algorithm, combined with convolutional, turbo, and low-density parity check codes, is demonstrated on several multiantenna channels. The results for systems that employ space-time modulation schemes seem to indicate that the best performing schemes are those that support the highest mutual information between the transmitted and received signals, rather than the best diversity gain.

In wireless communication systems, channel state information is often assumed to be available at the receiver. Traditionally, a training sequence is used to obtain the estimate of the channel. Alternatively, the channel can be identified using known properties of the transmitted signal. However, the computational effort required to find the joint ML solution to the symbol detection and channel estimation problem increases exponentially with the dimension of the problem. To significantly reduce this computational effort, we formulate the aforementioned problem in a way that makes it possible to solve it via the use of sphere decoding, an algorithm that has polynomial expected complexity. We also provide simulation results and a complexity discussion.

Maximum-likelihood (ML) detection problem for channels with memory is investigated. The Viterbi algorithm provides an elegant solution, but is computationally inefficient when employed for detection on long channels. On the other hand, sphere decoding solves the ML detection problem in polynomial expected time over a wide range of SNRs. The sphere-constrained search strategy of sphere decoding is combined with the dynamic programming principles of the Viterbi algorithm. The resulting algorithm has the worst-case complexity of the Viterbi algorithm, but significantly lower expected complexity.

The problem of finding the least-squares solution to a system of linear equations where the unknown vector is comprised of integers, but the matrix coefficient and given vector are comprised of real numbers, arises in many applications: communications, cryptography, GPS, to name a few. The problem is equivalent to finding the closest lattice point to a given point and is known to be NP-hard. In communications applications, however, the given vector is not arbitrary, but rather is an unknown lattice point that has been perturbed by an additive noise vector whose statistical properties are known. Therefore in this paper, rather than dwell on the worst-case complexity of the integer-least-squares problem, we study its expected complexity, averaged over the noise and over the lattice. For the “sphere decoding” algorithm of Fincke and Pohst we find a closed-form expression for the expected complexity and show that for a wide range of noise variances the expected complexity is polynomial, in fact often sub-cubic. Since many communications systems operate at noise levels for which the expected complexity turns out to be polynomial, this suggests that maximum-likelihood decoding, which was hitherto thought to be computationally intractable, can in fact be implemented in realtime—a result with many practical implications.

In recent years, soft iterative decoding techniques have been shown to greatly improve the bit error rate performance of various communication systems. For multiple antenna systems, however, it is not clear what is the best way to obtain the soft-information required of the iterative scheme with low complexity. In this paper, we propose a modification of the Fincke-Pohst (sphere decoder) algorithm to estimate the MAP probability of the received symbol sequence. The new algorithm solves a nonlinear integer leasts-quares problem and, over a wide range of rates and SNRs, has polynomial-time (often cubic) complexity. The performance of the algorithm, combined with convolutional, turbo, and LDPC codes is demonstrated on several multiple antenna channels.

Many communications systems employ training, ie, the transmission of known signals, so that the channel parameters may be learned at the receiver. This has a dual effect: too little training and the channel is improperly learned, too much training and there is no time left for data transmission before the channel changes. We use an information-theoretic approach to find the optimal amount of training for frequency selective channels described by a block-fading model. When the training and data powers are allowed to vary, we show that the optimal number of training symbols is equal to the length of the channel impulse response. When the training and data powers are instead required to be equal, the optimal number of symbols may be larger. We further show that at high SNR training-based schemes are capable of capturing most of the channel capacity, whereas at low SNR they are highly suboptimal.

We study the design of synthesis filters in noisy filter bank systems using an H/sup /spl infin// estimation point of view. The H/sup /spl infin// approach is most promising in situations where the statistical properties of the disturbances (arising from quantization, compression, etc.) in each subband of the filter bank are unknown, or are too difficult to model and analyze. For arbitrary analysis polyphase matrices, standard state-space H/sup /spl infin// techniques can be employed to obtain numerical solutions. When the synthesis filters are restricted to being FIR, as is often the case in practice, the design can be cast as a finite-dimensional semi-definite program. In this case, we can effectively exploit the inherent non-uniqueness of the H/sup /spl infin// solution to optimize for an additional average performance and thus obtain mixed H/sup 2//H/sup /spl infin// optimal FIR synthesis filters.

Portable wireless systems require long battery lifetime while still delivering high performance. The major contribution of this work is combining new it power management(PM) and it power control (PC) algorithms to trade off performance for power consumption at the system level in portable devices. First we present the formulation for the solution of the PM policy optimization based on renewaltheory. Next we present the formulation for power control (PC) of the wireless link that enables us to obtain further energy savings when thesystem is active. Finally, we discuss the measurements obtained for a set of PM and PC algorithms implemented for the WLAN card on a laptop. The PM policy we developed based on our renewal model consumes three times less power as compared to the default PM policy for the WLAN card with still high performance. Power control saves additional 53% in energy at same bit error rate. With both power control and power management algorithms in place, we observe on average a factor of six in power savings.

We study the design of synthesis filters in noisy filter bank systems using an H/sup /spl infin// point of view. For unitary analysis polyphase matrices we obtain an explicit expression for the minimum achievable disturbance attenuation. Numerical examples and comparisons with existing methods are also included.