The Gaussian process (GP) is a Bayesian non-parametric paradigm that is widely adopted for uncertainty quantification (UQ) in a number of safety-critical applications, including robotics, healthcare, as well as surveillance. The consistency of the resulting uncertainty values however, hinges on the premise that the learning function conforms to the properties specified by the GP model, such as smoothness, periodicity and more, which may not be satisfied in practice, especially with data arriving on the fly. To combat against such model mis-specification, we propose to wed the GP with the prevailing conformal prediction (CP), a distribution-free post-processing framework that produces prediction sets with a provably valid coverage under the sole assumption of data exchangeability. However, this assumption is usually violated in the online setting, where a prediction set is sought before revealing the true label. To ensure long-term coverage guarantee, we will adpatively set the key threshold parameter based on the feedback whether the true label falls inside the prediction set. Numerical results demonstrate the merits of the online GP-CP approach relative to existing alternatives in the long-term coverage performance.

Targeting solutions over ‘flat’ regions of the loss landscape, sharpness-aware minimization (SAM) has emerged as a powerful tool to improve generalizability of deep neural network based learning. While several SAM variants have been developed to this end, a unifying approach that also guides principled algorithm design has been elusive. This contribution leverages preconditioning (pre) to unify SAM variants and provide not only unifying convergence analysis, but also valuable insights. Building upon preSAM, a novel algorithm termed infoSAM is introduced to address the so-called adversarial model degradation issue in SAM by adjusting gradients depending on noise estimates. Extensive numerical tests demonstrate the superiority of infoSAM across various benchmarks.

Low-Rank Adaptation (LoRA) lowers the computational and memory overhead of fine-tuning large models by updating a low-dimensional subspace of the pre-trained weight matrix. Albeit efficient, LoRA exhibits suboptimal convergence and noticeable performance degradation, due to inconsistent and imbalanced weight updates induced by its nonunique low-rank factorizations. To overcome these limitations, this article identifies the optimal low-rank factorization per step that minimizes an upper bound on the loss. The resultant refactored low-rank adaptation (RefLoRA) method promotes a flatter loss landscape, along with consistent and balanced weight updates, thus speeding up stable convergence. Extensive experiments evaluate RefLoRA on natural language understanding, and commonsense reasoning tasks with popular large language models including DeBERTaV3, LLaMA-7B, LLaMA2-7B and LLaMA3-8B. The numerical tests corroborate that RefLoRA converges faster, outperforms various benchmarks, and enjoys negligible computational overhead compared to state-of-the-art LoRA variants.

Using a subset of observed network links, high-order link prediction (HOLP) infers missing hyperedges, that is links connecting three or more nodes. HOLP emerges in several applications, but existing approaches have not dealt with the associated predictor’s performance. To overcome this limitation, the present contribution develops a Bayesian approach and the relevant predictive distributions that quantify model uncertainty. Gaussian processes model the dependence of each node to the remaining nodes. These nonparametric models yield predictive distributions, which are fused across nodes by means of a pseudo-likelihood based criterion. Performance is quantified by proper measures of dispersion, which are associated with the predictive distributions. Tests on benchmark datasets demonstrate the benefits of the novel approach.

Utilizing task-invariant prior knowledge extracted from related tasks, meta-learning is a principled framework that empowers learning a new task especially when data records are limited. A fundamental challenge in meta-learning is how to quickly "adapt" the extracted prior in order to train a task-specific model within a few optimization steps. Existing approaches deal with this challenge using a preconditioner that enhances convergence of the per-task training process. Though effective in representing locally a quadratic training loss, these simple linear preconditioners can hardly capture complex loss geometries. The present contribution addresses this limitation by learning a nonlinear mirror map, which induces a versatile distance metric to enable capturing and optimizing a wide range of loss geometries, hence facilitating the per-task training. Numerical tests on few-shot learning datasets demonstrate the superior expressiveness and convergence of the advocated approach.

Relying on prior knowledge accumulated from related tasks, meta-learning offers a powerful approach to learning a novel task from a limited number of training data. Recent approaches use a family of prior probability density functions or recurrent neural network models, whose parameters can be optimized by utilizing labeled data from the observed tasks. While these approaches have appealing empirical performance, expressiveness of their prior is relatively low, which limits generalization and interpretation of meta-learning. Aiming at expressive yet meaningful priors, this contribution puts forth a novel prior representation model that leverages the notion of algorithm unrolling. The key idea is to unroll the proximal gradient descent steps, where learnable piecewise linear functions are developed to approximate the desired proximal operators within *tight* theoretical error bounds established for both smooth and non-smooth proximal functions. The resultant multi-block neural network not only broadens the scope of learnable priors, but also enhances interpretability from an optimization viewpoint. Numerical tests conducted on few-shot learning datasets demonstrate markedly improved performance with flexible, visualizable, and understandable priors.

Meta-learning empowers data-hungry deep neural networks to rapidly learn from merely a few samples, which is especially appealing to tasks with small datasets. Critical in this context is the *prior knowledge* accumulated from related tasks. Existing meta-learning approaches typically rely on preselected priors, such as a Gaussian probability density function (pdf). The limited expressiveness of such priors however, hinders the enhanced performance of the trained model when dealing with tasks having exceedingly scarce data. Targeting improved expressiveness, this contribution introduces a *data-driven* prior that optimally fits the provided tasks using a novel non-injective change-of-variable (NCoV) model. Unlike preselected prior pdfs with fixed shapes, the advocated NCoV model can effectively approximate a considerably wide range of pdfs. Moreover, compared to conventional change-of-variable models, the introduced NCoV exhibits augmented expressiveness for pdf modeling, especially in high-dimensional spaces. Theoretical analysis underscores the appealing universal approximation capacity of the NCoV model. Numerical experiments conducted on three few-shot learning datasets validate the superiority of data-driven priors over the prespecified ones, showcasing its pronounced effectiveness when dealing with extremely limited data resources.

The advent of diverse frequency bands in 5G networks has promoted measurement studies focused on 5G signal propagation, aiming to understand its pathloss, coverage, and channel quality characteristics. Nonetheless, conducting a thorough 5G measurement campaign is markedly laborious given the large number of samples that must be collected. To alleviate this burden, the present contribution leverages principled active learning (AL) methods to prudently select only a few, yet most informative locations to collect samples. The core idea is to rely on a Gaussian Process (GP) model to efficiently extrapolate measurements throughout the coverage area. Specifically, an ensemble (E) of GP models is adopted that not only provides a rich learning function space, but also quantifies uncertainty, and can offer accurate predictions. Building on this EGP model, a suite of acquisition functions (AFs) are advocated to query new locations on-the-fly. To account for realistic scenaria, the proposed AFs are augmented with a novel distance-based AL rule that selects informative samples, while penalizing queries at long distances. Numerical tests on 5G data generated by the Sionna simulator and on real urban and suburban datasets, showcase the merits of the novel EGP-AL approaches.

Recent years have witnessed the emergence of mobile edge computing (MEC), on the premise of a cost-effective enhancement in the computational ability of hardware-constrained wireless devices (WDs) comprising the Internet of Things (IoT). In a general multi-server multi-user MEC system, each WD has a computational task to execute and has to select binary (off)loading decisions, along with the analog-amplitude resource allocation variables in an online manner, with the goal of minimizing the overall energy-delay cost (EDC) with dynamic system states. While past works typically rely on the explicit expression of the EDC function, the present contribution considers a practical setting, where in lieu of system state information, the EDC function is not available in analytical form, and instead only the function values at queried points are revealed. Towards tackling such a challenging online combinatorial problem with only bandit information, novel Bayesian optimization (BO) based approaches are put forth by leveraging the multi-armed bandit (MAB) framework. Per time slot, the discrete offloading decisions are first obtained via the MAB method, and the analog resource allocation variables are subsequently optimized using the BO selection rule. By exploiting both temporal and contextual information, two novel BO approaches, termed time-varying BO and contextual time-varying BO, are developed. Numerical tests validate the merits of the proposed BO approaches compared with contemporary benchmarks under different MEC network sizes.

Meta-learning owns unique effectiveness and swiftness in tackling emerging tasks with limited data. Its broad applicability is revealed by viewing it as a bi-level optimization problem. The resultant algorithmic viewpoint however, faces scalability issues when the inner-level optimization relies on gradient-based iterations. Implicit differentiation has been considered to alleviate this challenge, but it is restricted to an isotropic Gaussian prior, and only favors deterministic meta-learning approaches. This work markedly mitigates the scalability bottleneck by cross-fertilizing the benefits of implicit differentiation to probabilistic Bayesian meta-learning. The novel implicit Bayesian meta-learning (iBaML) method not only broadens the scope of learnable priors, but also quantifies the associated uncertainty. Furthermore, the ultimate complexity is well controlled regardless of the inner-level optimization trajectory. Analytical error bounds are established to demonstrate the precision and efficiency of the generalized implicit gradient over the explicit one. Extensive numerical tests are also carried out to empirically validate the performance of the proposed method.

Higher-order link prediction (HOLP) seeks missing links capturing dependencies among three or more network nodes. Predicting high-order links (HOLs) can for instance reveal hyperlinks in the structure of drug substance and metabolic networks. Existing methods either make restrictive assumptions regarding the emergence of HOLs, or, they rely on reduced dimensionality models of limited expressiveness. To overcome these limitations, the HOLP approach developed here leverages distribution similarities across embeddings as captured by a learnable probability metric. The intuition underpinning the novel approach is that sets of nodes whose embeddings are less similar in distribution, are less likely to be connected by a HOL. Specifically, nonlinear dimensionality reduction is effected through a Gaussian process latent variable model that yields nodal embeddings, and also learns a data-driven similarity function (kernel). This kernel forms the core of a maximum mean discrepancy probability metric. Tests on benchmark datasets illustrate the potential of the proposed approach.

Optimizing a black-box function that is expensive to evaluate emerges in a gamut of machine learning and artificial intelligence applications including drug discovery, policy optimization in robotics, and hyperparameter tuning of learning models to list a few. Bayesian optimization (BO) provides a principled framework to find the global optimum of such functions using a limited number of function evaluations. BO relies on a statistical surrogate model to actively select new query points, that is typically captured by a Gaussian process (GP). Unlike most existing approaches that hinge on a single GP surrogate model with a pre-selected kernel function that may confine the expressiveness of the sought function especially under the limited evaluation budget, the present work puts forth a weighted ensemble of GPs as a surrogate model. Building on the advocated Gaussian mixture (GM) posterior, the EGP framework adapts to the most fitted surrogate model as data arrive on-the-fly, offering a richer function space. For the acquisition of next evaluation points, the EGP-based posterior is coupled with an adaptive expected improvement (EI) criterion to balance exploration and exploitation of the search space. Numerical tests on a set of benchmark synthetic functions and two robotic tasks, demonstrate the impressive benefits of the proposed approach.

Assessing set-membership and evaluating distances to the related set boundary are problems of widespread interest, and can often be computationally challenging. Seeking efficient learning models for such tasks, this paper deals with voltage stability margin prediction for power systems. Supervised training of such models is conventionally hard due to high-dimensional feature space, and a cumbersome label-generation process. Nevertheless, one may find related easy auxiliary tasks, such as voltage stability verification, that can aid in training for the hard task. This paper develops a novel approach for such settings by leveraging transfer learning. A Gaussian process-based learning model is efficiently trained using learning- and physics-based auxiliary tasks. Numerical tests demonstrate markedly improved performance that is harnessed alongside the benefit of uncertainty quantification to suit the needs of the considered application.

Over-the-air federated learning (OTA-FL) is a communication-effective approach for achieving distributed learning tasks. In this paper, we aim to enhance OTA-FL by seamlessly combining sensing into the communication-computation integrated system. Our research reveals that the wireless waveform used to convey OTA-FL parameters possesses inherent properties that make it well-suited for sensing, thanks to its remarkable auto-correlation characteristics. By leveraging the OTA-FL learning statistics, i.e., means and variances of local gradients in each training round, the sensing results can be embedded therein without the need for additional time or frequency resources. Finally, by considering the imperfections of learning statistics that are neglected in the prior works, we end up with an optimized the transceiver design to maximize the OTA-FL performance. Simulations validate that the proposed method not only achieves outstanding sensing performance but also significantly lowers the learning error bound.

Sharpness-aware minimization (SAM) has well documented merits in enhancing generalization of deep neural networks, even without sizable data augmentation. Embracing the geometry of the loss function, where neighborhoods of 'flat minima' heighten generalization ability, SAM seeks 'flat valleys' by minimizing the maximum loss caused by an *adversary* perturbing parameters within the neighborhood. Although critical to account for sharpness of the loss function, such an '*over-friendly* adversary' can curtail the outmost level of generalization. The novel approach of this contribution fosters stabilization of adversaries through *variance suppression* (VaSSO) to avoid such friendliness. VaSSO's *provable* stability safeguards its numerical improvement over SAM in model-agnostic tasks, including image classification and machine translation. In addition, experiments confirm that VaSSO endows SAM with robustness against high levels of label noise. Code is available at https://github.com/BingcongLi/VaSSO.

Belonging to the family of Bayesian nonparametrics, Gaussian process (GP) based approaches have well-documented merits not only in learning over a rich class of nonlinear functions, but also in quantifying the associated uncertainty. However, most GP methods rely on a single preselected kernel function, which may fall short in characterizing data samples that arrive sequentially in time-critical applications. To enable online kernel adaptation, the present work advocates an incremental ensemble (IE-) GP framework, where an EGP assembler employs an ensemble of GP learners, each having a unique kernel belonging to a prescribed kernel dictionary. With each GP expert leveraging the random feature-based approximation to perform online prediction and model update with scalability, the EGP assembler capitalizes on data-adaptive weights to synthesize the per-expert predictions. Further, the novel IE-GP is generalized to accommodate time-varying functions by modeling structured dynamics at the EGP assembler and within each GP learner. To benchmark the performance of IE-GP and its dynamic variant in the adversarial setting where the modeling assumptions are violated, rigorous performance analysis has been conducted via the notion of regret, as the norm in online convex optimization. Last but not the least, online unsupervised learning for dimensionality reduction is explored under the novel IE-GP framework. Synthetic and real data tests demonstrate the effectiveness of the proposed schemes.

Bayesian optimization (BO) has well-documented merits for optimizing black-box functions with an expensive evaluation cost. Such functions emerge in applications as diverse as hyperparameter tuning, drug discovery, and robotics. BO hinges on a Bayesian surrogate model to sequentially select query points so as to balance exploration with exploitation of the search space. Most existing works rely on a single Gaussian process (GP) based surrogate model, where the kernel function form is typically preselected using domain knowledge. To bypass such a design process, this paper leverages an ensemble (E) of GPs to adaptively select the surrogate model fit on-the-fly, yielding a GP mixture posterior with enhanced expressiveness for the sought function. Acquisition of the next evaluation input using this EGP-based function posterior is then enabled by Thompson sampling (TS) that requires no additional design parameters. To endow function sampling with scalability, random feature-based kernel approximation is leveraged per GP model. The novel EGP-TS readily accommodates parallel operation. To further establish convergence of the proposed EGP-TS to the global optimum, analysis is conducted based on the notion of Bayesian regret for both sequential and parallel settings. Tests on synthetic functions and real-world applications showcase the merits of the proposed method.

Simultaneous wireless information and power transfer (SWIPT) is a prospective technology that can handle the energy consumption and communication requirements in the Internet of Things. Resonant beam SWIPT (RB-SWIPT) scheme utilizes narrow optical beam as carrier and with spatially separated resonator structure, which can support high power and high rate SWIPT for mobile devices. However, the performance of original RB-SWIPT systems is limited by returning beam interference and transmission loss. In this paper, we propose a RB-SWIPT scheme for transmission-enhanced and anti-interference. The telescope internal modulator (TIM) and second harmonic generator (SHG) are adopted in the proposed system. The TIM can compress beams to reduce the transmission loss. The SHG can generate frequency-doubled beams to avoid interference. To evaluate the proposed system, we establish mathematical models to depict the beam transmission, energy conversion, electric power output and data receiving. Numerical results illustrate that the proposed system can achieve 18 bit/s/Hz spectral efficiency and deliver 8 W power over 100 m distance.

Graph convolutional networks (GCNs) have well-documented performance in various graph learning tasks, but their analysis is still at its infancy. Graph scattering transforms (GSTs) offer training-free deep GCN models that extract features from graph data, and are amenable to generalization and stability analyses. The price paid by GSTs is exponential complexity in space and time that increases with the number of layers. This discourages deployment of GSTs when a deep architecture is needed. The present work addresses the complexity limitation of GSTs by introducing an efficient so-termed pruned (p)GST approach. The resultant pruning algorithm is guided by a graph-spectrum-inspired criterion, and retains informative scattering features on-the-fly while bypassing the exponential complexity associated with GSTs. Stability of the novel pGSTs is also established when the input graph data or the network structure are perturbed. Furthermore, the sensitivity of pGST to random and localized signal perturbations is investigated analytically and experimentally. Numerical tests showcase that pGST performs comparably to the baseline GST at considerable computational savings. Furthermore, pGST achieves comparable performance to state-of-the-art GCNs in graph and 3D point cloud classification tasks. Upon analyzing the pGST pruning patterns, it is shown that graph data in different domains call for different network architectures, and that the pruning algorithm may be employed to guide the design choices for contemporary GCNs.

This paper focuses on communication-efficient federated learning problem, and develops a novel distributed quantized gradient approach, which is characterized by adaptive communications of the quantized gradients. Specifically, the federated learning builds upon the server-worker infrastructure, where the workers calculate local gradients and upload them to the server; then the server obtain the global gradient by aggregating all the local gradients and utilizes it to update the model parameter. The key idea to save communications from the worker to the server is to quantize gradients as well as skip less informative quantized gradient communications by reusing previous gradients. Quantizing and skipping result in 'lazy' worker-server communications, which justifies the term Lazily Aggregated Quantized (LAQ) gradient. Theoretically, the LAQ algorithm achieves the same linear convergence as the gradient descent in the strongly convex case, while effecting major savings in the communication in terms of transmitted bits and communication rounds. Empirically, extensive experiments using realistic data corroborate a significant communication reduction compared with state-of-the-art gradient- and stochastic gradient-based algorithms.

Ensemble learning, the machine learning paradigm where multiple models are combined, has exhibited promising perfomance in a variety of tasks. The present work focuses on unsupervised ensemble classification. The term unsupervised refers to the ensemble combiner who has no knowledge of the ground-truth labels that each classifier has been trained on. While most prior works on unsupervised ensemble classification are designed for independent and identically distributed (i.i.d.) data, the present work introduces an unsupervised scheme for learning from ensembles of classifiers in the presence of data dependencies. Two types of data dependencies are considered: sequential data and networked data whose dependencies are captured by a graph. For both, novel moment matching and Expectation-Maximization algorithms are developed. Performance of these algorithms is evaluated on synthetic and real datasets, which indicate that knowledge of data dependencies in the meta-learner is beneficial for the unsupervised ensemble classification task.

Aiming at convex optimization under structural constraints, this work introduces and analyzes a variant of the Frank Wolfe (FW) algorithm termed ExtraFW. The distinct feature of ExtraFW is the pair of gradients leveraged per iteration, thanks to which the decision variable is updated in a prediction-correction (PC) format. Relying on no problem dependent parameters in the step sizes, the convergence rate of ExtraFW for general convex problems is shown to be ${\cal O}(\frac{1}{k})$, which is optimal in the sense of matching the lower bound on the number of solved FW subproblems. However, the merit of ExtraFW is its faster rate ${\cal O}\big(\frac{1}{k^2} \big)$ on a class of machine learning problems. Compared with other parameter-free FW variants that have faster rates on the same problems, ExtraFW has improved rates and fine-grained analysis thanks to its PC update. Numerical tests on binary classification with different sparsity-promoting constraints demonstrate that the empirical performance of ExtraFW is significantly better than FW, and even faster than Nesterov's accelerated gradient on certain datasets. For matrix completion, ExtraFW enjoys smaller optimality gap, and lower rank than FW.

This paper studies the adversarial graphical contextual bandits, a variant of adversarial multi-armed bandits that leverage two categories of the most common side information: contexts and side observations. In this setting, a learning agent repeatedly chooses from a set of K actions after being presented with a d-dimensional context vector. The agent not only incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures, which are encoded as a series of feedback graphs. This setting models a variety of applications in social networks, where both contexts and graph-structured side observations are available. Two efficient algorithms are developed based on EXP3. Under mild conditions, our analysis shows that for undirected feedback graphs the first algorithm, EXP3-LGC-U, achieves a sub-linear regret with respect to the time horizon and the average independence number of the feedback graphs. A slightly weaker result is presented for the directed graph setting as well. The second algorithm, EXP3-LGC-IX, is developed for a special class of problems, for which the regret is the same for both directed as well as undirected feedback graphs. Numerical tests corroborate the efficiency of proposed algorithms.

Value function approximation is a crucial module for policy evaluation in reinforcement learning when the state space is large or continuous. The present paper revisits policy evaluation via temporal-difference (TD) learning from the Gaussian process (GP) perspective. Leveraging random features to approximate the GP prior, an online scalable (OS) approach, termed OS-GPTD, is developed to estimate the value function for a given policy by observing a sequence of state-reward pairs. To benchmark the performance of OS-GPTD even in the adversarial setting, where the modeling assumptions are violated, complementary worst-case analyses are performed. The cumulative Bellman error, as well as the long-term reward prediction error, are upper bounded relative to their counterparts from a fixed value function estimator with the entire state-reward trajectory in hindsight. Performance of the novel OS-GPTD is evaluated on two benchmark problems.

The present paper develops a graph-based sampling and consensus (GraphSAC) approach to effectively detect anomalous nodes in large-scale graphs. GraphSAC randomly draws sub-sets of nodes, and relies on graph-aware criteria to judiciously filter out sets contaminated by anomalous nodes, before employing a semi-supervised learning (SSL) module to estimate nominal label distributions per node. These learned nominal distributions are minimally affected by the anomalous nodes, and hence can be directly adopted for anomaly detection. The per-draw complexity grows linearly with the number of edges, which implies efficient SSL, while draws can be run in parallel, thereby ensuring scalability to large graphs. GraphSAC is tested under different anomaly generation models based on random walks, as well as contemporary adversarial attacks for graph data. Experiments with real-world graphs show-case the advantage of GraphSAC relative to state-of-the-art alternatives.

Gaussian process latent variable models (GPLVMs) are powerful, yet computationally heavy tools for nonlinear dimensionality reduction. Existing scalable variants utilize low- rank kernel matrix approximants that in essence subsample the embedding space. This work develops an efficient online approach based on random features by replacing spatial with spectral subsampling. The novel approach bypasses the need for optimizing over spatial samples, without sacrificing performance. Different from GPLVM, whose performance depends on the choice of the kernel, the proposed algorithm relies on an ensemble of kernels - what allows adaptation to a wide range of operating environments. It further allows for initial exploration of a richer function space, relative to methods adhering to a single fixed kernel, followed by sequential contraction of the search space as more data become available. Tests on benchmark datasets demonstrate the effectiveness of the proposed method.

Graph-guided semi-supervised learning (SSL) is a major task emerging in a gamut of network science applications. However, most SSL approaches rely on deterministic similarity metrics for prediction, thus providing only point estimates of the sought function. To allow for uncertainty quantification, which is of utmost importance in safety-critical applications, this work tackles the SSL task in a Gaussian process (GP) based Bayesian framework to propagate the distribution of nonparametric function estimates. Specifically, an incremental learning scenario is considered, where prediction of the desired value of a new node per iteration is followed by processing the corresponding nodal observation. Capitalizing on random features for scalability, an ensemble of GP experts is employed, each associated with a unique kernel from a known dictionary, to choose the fitted kernel combination in a graph- and data-adaptive fashion, thus bypassing the need for offline model training. Experiments with synthetic and real data showcase the merits of the proposed approach.

The present work addresses the problem of adversarial attacks in unsupervised ensemble or crowdsourcing classification tasks. Under certain conditions, it is shown, both analytically and through numerical tests, that spammers cause the most damage with respect to classification performance. To curb their effect, a novel spectral algorithm for spammer detection that utilizes second-order statistics of annotators, is developed and preliminary results on synthetic and real data showcase the potential of this approach.

Relying on a conditional gradient based iteration, the Frank-Wolfe (FW) algorithm has been a popular solver of constrained convex optimization problems in signal processing and machine learning, thanks to its low complexity. The present contribution broadens its scope by replacing the gradient per FW subproblem with a weighted average of gradients. This generalization speeds up the convergence of FW by alleviating its zigzag behavior. A geometric interpretation for the averaged gradients is provided, and convergence guarantees are established for three different weight combinations. Numerical comparison shows the effectiveness of the proposed methods.

Despite its successes in various machine learning and data science tasks, crowdsourcing can be susceptible to attacks from dedicated adversaries. This work investigates the effects of adversaries on crowdsourced classification, under the popular Dawid and Skene model. The adversaries are allowed to deviate arbitrarily from the considered crowdsourcing model, and may potentially cooperate. To address this scenario, we develop an approach that leverages the structure of second-order moments of annotator responses, to identify large numbers of adversaries, and mitigate their impact on the crowdsourcing task. The potential of the proposed approach is empirically demonstrated on synthetic and real crowdsourcing datasets.

Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projection-based methods, momentum cannot improve the convergence rate of FW, in general. This limitation motivates the present work, which deals with heavy ball momentum, and its impact to FW. Specifically, it is established that heavy ball offers a unifying perspective on the primal-dual (PD) convergence, and enjoys a tighter \textit{per iteration} PD error rate, for multiple choices of step sizes, where PD error can serve as the stopping criterion in practice. In addition, it is asserted that restart, a scheme typically employed jointly with Nesterov's momentum, can further tighten this PD error bound. Numerical results demonstrate the usefulness of heavy ball momentum in FW iterations.

In this article, we present an advanced coherent receiver for the IEEE 802.15.4 offset quadrature phase-shift keying (OQPSK) physical layer and provide an open-source implementation in the GNU Radio framework. Simulation and field test results show that the proposed receiver achieves about 11-dB power gain over an existing GNU Radio receiver, which treats OQPSK as minimum-shift-keying (MSK) for low-complexity processing. While suitable modules can be added to the MSK-based receiver for performance enhancement, the proposed receiver still maintains a 6-dB power gain. The proposed coherent receiver is attractive for IoT applications where a powerful software-defined-radio (SDR)-based gateway is deployed to interact with various sensors.

Resonant beam communications (RBCom) is capable of providing wide bandwidth when using light as the carrier. Besides, the RBCom system possesses the characteristics of mobility, high signal-to-noise ratio (SNR), and multiplexing. Nevertheless, the channel of the RBCom system is distinct from other light communication technologies due to the echo interference issue. In this article, we reveal the mechanism of the echo interference and propose the method to eliminate the interference. Moreover, we present an exemplary design based on frequency shifting and optical filtering, along with its mathematic model and performance analysis. The numerical evaluation shows that the channel capacity is greater than 15 b/s/Hz.

Node embedding is the task of extracting informative and descriptive features over the nodes of a graph. The importance of node embedding for graph analytics as well as learning tasks, such as node classification, link prediction, and community detection, has led to a growing interest and a number of recent advances. Nonetheless, node embedding faces several major challenges. Practical embedding methods have to deal with real-world graphs that arise from different domains, with inherently diverse underlying processes as well as similarity structures and metrics. On the other hand, similar to principal component analysis in feature vector spaces, node embedding is an inherently unsupervised task. Lacking metadata for validation, practical schemes motivate standardization and limited use of tunable hyperparameters. Finally, node embedding methods must be scalable in order to cope with large-scale real-world graphs of networks with ever-increasing size. The present work puts forth an adaptive node embedding framework that adjusts the embedding process to a given underlying graph, in a fully unsupervised manner. This is achieved by leveraging the notion of a tunable node similarity matrix that assigns weights on multihop paths. The design of multihop similarities ensures that the resultant embeddings also inherit interpretable spectral properties. The proposed model is thoroughly investigated, interpreted, and numerically evaluated using stochastic block models. Moreover, an unsupervised algorithm is developed for training the model parameters effieciently. Extensive node classification, link prediction, and clustering experiments are carried out on many real-world graphs from various domains, along with comparisons with state-of-the-art scalable and unsupervised node embedding alternatives. The proposed method enjoys superior performance in many cases, while also yielding interpretable information on the underlying graph structure.

Joint analysis of data from multiple information repositories facilitates uncovering the underlying structure in heterogeneous datasets. Single and coupled matrix-tensor factorization (CMTF) has been widely used in this context for imputation-based recommendation from ratings, social network, and other user-item data. When this side information is in the form of item-item correlation matrices or graphs, existing CMTF algorithms may fall short. Alleviating current limitations, we introduce a novel model coined coupled graph-tensor factorization (CGTF) that judiciously accounts for graph-related side information. The CGTF model has the potential to overcome practical challenges, such as missing slabs from the tensor and/or missing rows/columns from the correlation matrices. A novel alternating direction method of multipliers (ADMM) is also developed that recovers the nonnegative factors of CGTF. Our algorithm enjoys closed-form updates that result in reduced computational complexity and allow for convergence claims. A novel direction is further explored by employing the interpretable factors to detect graph communities having the tensor as side information. The resulting community detection approach is successful even when some links in the graphs are missing. Results with real data sets corroborate the merits of the proposed methods relative to state-of-the-art competing factorization techniques in providing recommendations and detecting communities.

The main theme of this work is a unifying algorithm, \textbf{L}oop\textbf{L}ess \textbf{S}ARAH (L2S) for problems formulated as summation of $n$ individual loss functions. L2S broadens a recently developed variance reduction method known as SARAH. To find an $\epsilon$-accurate solution, L2S enjoys a complexity of ${\cal O}\big( (n+\kappa) \ln (1/\epsilon)\big)$ for strongly convex problems. For convex problems, when adopting an $n$-dependent step size, the complexity of L2S is ${\cal O}(n+ \sqrt{n}/\epsilon)$; while for more frequently adopted $n$-independent step size, the complexity is ${\cal O}(n+ n/\epsilon)$. Distinct from SARAH, our theoretical findings support an $n$-independent step size in convex problems without extra assumptions. For nonconvex problems, the complexity of L2S is ${\cal O}(n+ \sqrt{n}/\epsilon)$. Our numerical tests on neural networks suggest that L2S can have better generalization properties than SARAH. Along with L2S, our side results include the linear convergence of the last iteration for SARAH in strongly convex problems.

Combining benefits of kernels with Bayesian models, Gaussian process (GP) based approaches have well-documented merits not only in learning over a rich class of nonlinear functions, but also quantifying the associated uncertainty. While most GP approaches rely on a single preselected prior, the present work employs a weighted ensemble of GP priors, each having a unique covariance (kernel) belonging to a prescribed kernel dictionary – which leads to a richer space of learning functions. Leveraging kernel approximants formed by spectral features for scalability, an online interactive ensemble (OI-E) GP framework is developed to jointly learn the sought function, and for the first time select interactively the EGP kernel on-the-fly. Performance of OI-EGP is benchmarked by the best fixed function estimator via regret analysis. Furthermore, the novel OI-EGP is adapted to accommodate dynamic learning functions. Synthetic and real data tests demonstrate the effectiveness of the proposed schemes.

Motivated by the emerging use of multi-agent reinforcement learning (MARL) in engineering applications such as networked robotics, swarming drones, and sensor networks, we investigate the policy evaluation problem in a fully decentralized setting, using temporal-difference (TD) learning with linear function approximation to handle large state spaces in practice. The goal of the group of agents is to collaboratively learn the value function of a given policy from locally private rewards observed in a shared environment, through exchanging local estimates with neighbors. Despite their simplicity and widespread use, our theoretical understanding of such decentralized TD learning algorithms remains limited. Existing results were obtained based on i.i.d. data samples, or by imposing an ‘additional’ projection step to control the ‘gradient’ bias incurred by the Markovian observations. In this paper, we provide a finite-time analysis of the fully decentralized TD(0) learning under both i.i.d. as well as Markovian samples, and prove that all local estimates converge linearly to a small neighborhood of the optimum. The resultant error bounds are the first of its type—in the sense that they hold under the most practical assumptions—which is made possible by means of a novel multi-step Lyapunov approach.

Inspired by the widespread use of Q-learning algorithms in reinforcement learning (RL), this present paper studies a class of biased stochastic approximation (SA) procedures under an ‘ergodic-like’ assumption on the underlying stochastic noise sequence. Leveraging a \emph{multistep Lyapunov function} that looks ahead to several future updates to accommodate the gradient bias, we prove a general result on the convergence of the iterates, and use it to derive finite-time bounds on the mean-square error in the case of constant stepsizes. This novel viewpoint renders the finite-time analysis of \emph{biased SA} algorithms under a broad family of stochastic perturbations possible. For direct comparison with past works, we also demonstrate these bounds by applying them to Q-learning with linear function approximation, under the realistic Markov chain observation model. The resultant finite-time error bound for Q-learning is \emph{the first of its kind}, in the sense that it holds: i) for the unmodified version (i.e., without making any modifications to the updates), and ii), for Markov chains starting from any initial distribution, at least one of which has to be violated for existing results to be applicable.

Link prediction is one of the core problems in network and data science with widespread applications. While predicting pairwise nodal interactions (links) in network data has been investigated extensively, predicting higher-order interactions (higher-order links) is still not fully understood. Several approaches have been advocated to predict such higher-order interactions, but no principled method has been put forth to tackle this challenge so far. Cross-fertilizing ideas from Volterra series and linear structural equation models, the present paper introduces self-driven graph Volterra models that can capture higher-order interactions among nodal observables available in networked data. The novel model is validated for the higher-order link prediction task using real interaction data from social networks.

The interconnection of social, email, and media platforms enables adversaries to manipulate networked data and promote their malicious intents. This paper introduces graph neural network architectures that are robust to perturbed networked data. The novel network utilizes a randomization layer that performs link-dithering (LD) by adding or removing links with probabilities selected to boost robustness. The resultant link-dithered auxiliary graphs are leveraged by an adaptive (A)GCN that performs SSL. The proposed robust LD-AGCN achieves performance gains relative to GCNs under perturbed network data.

In this paper, we revisit the problem of minimizing a convex function f(x) with Lipschitz continuous gradient via accelerated gradient methods (AGM). To do so, we consider the so-called estimate sequence (ES), a useful analysis tool for establishing the convergence of AGM. We develop a generalized ES to support Lipschitz continuous gradient on any norm, given the importance of considering non-Euclidian norms in optimization. Traditionally, ES consists of a sequence of quadratic functions that serves as surrogate functions of f(x). However, such quadratic functions preclude the possibility of supporting Lipschitz continuous gradient defined w.r.t. non-Euclidian norms. Hence, an extension of such a powerful tool to the non-Euclidian norm setting is so much needed. Such extension is accomplished through a simple yet nontrivial modification of the standard ES. Further, our analysis provides insights of how acceleration is achieved and interpretability of the involved parameters in ES. Finally, numerical tests demonstrate the convergence benefits of taking non-Euclidean norms into account.

Semi-supervised learning (SSL) of dynamic processes over graphs is encountered in several applications of network science. Most of the existing approaches are unable to handle graphs with multiple relations, which arise in various real-world networks. This work deals with SSL of dynamic processes over multi-relational graphs (MRGs). Towards this end, a structured dynamical model is introduced to capture the spatio-temporal nature of dynamic graph processes, and incorporate contributions from multiple relations of the graph in a probabilistic fashion. Given nodal samples over a subset of nodes and the MRG, the expectation-maximization (EM) algorithm is adapted to extrapolate nodal features over unobserved nodes, and infer the contributions from the multiple relations in the MRG simultaneously. Experiments with real data showcase the merits of the proposed approach.

In this work, we consider the distributed optimization problem using networked computing machines. Specifically, we are interested in solving this problem using the alternating direction method of multipliers (ADMM) while accounting for edge weights. Existing works focus on star graphs and use simple heuristics for other types of graphs. The present work shows that the optimal edge weights design is equivalent to the preconditioning matrix of ADMM that leads to the fastest convergence speed. Based on a tight convergence rate of ADMM, we show that the preconditioning matrix of general graphs can be found by minimizing the ratio of the largest and smallest nonzero eigenvalue of the graph Laplacian. Numerical experiments show that preconditioned ADMM converges much faster to a certain accuracy with less communication rounds, and exemplify the robustness to topology changes of the underlying network.

Wireless and wireline networks, such as Internet, cellular, and content delivery networks are to serve end-user file requests proactively. To this aim, by storing anticipated highly popular files during off-peak periods, and fetching them to end-users during on-peak instances, these networks smoothen out the load fluctuations on the back-haul links. In this context, several practical networks comprise a parent caching node connected to multiple leaf nodes to serve end-user file requests. To model the two-way interactive influence between caching decisions at the parent and leaf nodes, a reinforcement learning formulation is put forth in this work. Furthermore, to endow with scalability so that the algorithm can effectively handle the curse of dimensionality, a deep reinforcement learning approach is also developed. Our novel caching policy relies on a deep Q-network to enforce the parent node with ability to learn-and-adapt to unknown policies of leaf nodes as well as spatio-temporal dynamic evolution of file requests, results in remarkable caching performance, as corroborated through numerical tests.

The present work introduces a simple scheme for active classification of data using unsupervised ensembles of classifiers. Uncertainty sampling, with different uncertainty measures, is evaluated for data selection, while an online expectation maximization algorithm is derived to estimate model parameters on-the-fly. Preliminary tests on real data showcase the potential of the novel approach.

This contribution deals with distributed finite-sum optimization for learning over networks in the presence of malicious Byzantine attacks. To cope with such attacks, resilient approaches so far combine stochastic gradient descent (SGD) with different robust aggregation rules. However, the sizeable SGD-induced gradient noise makes it challenging to distinguish malicious messages sent by the Byzantine attackers from noisy stochastic gradients sent by the friendly workers. This motivates gradient noise reduction as a means of robustifying SGD in the presence of Byzantine attacks. To this end, the present work puts forth a Byzantine attack resilient distributed (Byrd-) SAGA approach for learning tasks involving finite-sum optimization over networks. Rather than the mean employed by distributed SAGA, the novel Byrd-SAGA relies on the geometric median to aggregate the corrected stochastic gradients sent by the workers. When less than half of the workers are Byzantine attackers, the robustness of geometric median to outliers enables Byrd-SAGA to achieve provable linear convergence to a neighborhood of the optimal solution, where the size of neighborhood is determined by the number of Byzantine workers. Numerical tests demonstrate the robustness of Byrd-SAGA to various Byzantine attacks, as well as the merits of Byrd-SAGA over Byzantine-resilient SGD.

To perform any meaningful optimization task, distribution grid operators need to know the topology of their grids. Although power grid topology identification and verification has been recently studied, discovering instantaneous interplay among subsets of buses, also known as higher-order interactions in recent literature, has not yet been addressed. The system operator can benefit from having this knowledge when re-configuring the grid in real time, to minimize power losses, balance loads, alleviate faults, or for scheduled maintenance. Establishing a connection between the celebrated exact distribution flow equations and the so-called self-driven graph Volterra model, this paper puts forth a nonlinear topology identification algorithm, that is able to reveal both the edge connections as well as their higher-order interactions. Preliminary numerical tests using real data on a 47-bus distribution grid showcase the merits of the proposed scheme relative to existing alternatives.

The variance reduction class of algorithms including the representative ones, SVRG and SARAH, have well documented merits for empirical risk minimization problems. However, they require grid search to tune parameters (step size and the number of iterations per inner loop) for optimal performance. This work introduces ‘almost tune-free’ SVRG and SARAH schemes equipped with i) Barzilai-Borwein (BB) step sizes; ii) averaging; and, iii) the inner loop length adjusted to the BB step sizes. In particular, SVRG, SARAH, and their BB variants are first reexamined through an ‘estimate sequence’ lens to enable new averaging methods that tighten their convergence rates theoretically, and improve their performance empirically when the step size or the inner loop length is chosen large. Then a simple yet effective means to adjust the number of iterations per inner loop is developed to enhance the merits of the proposed averaging schemes and BB step sizes. Numerical tests corroborate the proposed methods.

The present contribution deals with decentralized policy evaluation in multi-agent Markov decision processes using temporal-difference (TD) methods with linear function approximation for scalability. The agents cooperate to estimate the value function of such a process by observing continual state transitions of a shared environment over the graph of interconnected nodes (agents), along with locally private rewards. Different from existing consensus-type TD algorithms, the approach here develops a simple decentralized TD tracker by wedding TD learning with gradient tracking techniques. The non-asymptotic properties of the novel TD tracker are established for both independent and identically distributed (i.i.d.) as well as Markovian transitions through a unifying multistep Lyapunov analysis. In contrast to the prior art, the novel algorithm forgoes the limiting error bounds on the number of agents, which endows it with performance comparable to that of centralized TD methods that are the sharpest known to date.

Wireless energy transfer (WET) has recently emerged as an appealing solution for power supplying mobile/Internet of Things (IoT) devices. As an enabling WET technology, resonant beam charging (RBC) is well documented for its long-range, high-power, and safe “WiFi-like” mobile power supply. To provide high-quality wireless charging services for multiple users in a given region, we formulate a deployment problem of multiple RBC transmitters for balancing the charging fairness and quality of charging service. Based on the RBC transmitter's coverage model and receiver's charging/discharging model, a genetic algorithm (GA)-based scheme and a particle swarm optimization (PSO)-based scheme are put forth to resolve the above issue. Moreover, we present a scheduling method to evaluate the performance of the proposed algorithms. The numerical results corroborate that the optimized deployment schemes outperform uniform and random deployment in 10%-20% charging efficiency improvement.

Optimization underpins many of the challenges that science and technology face on a daily basis. Recent years have witnessed a major shift from traditional optimization paradigms grounded on batch algorithms for medium-scale problems to challenging dynamic, time-varying, and even huge-size settings. This is driven by technological transformations that converted infrastructural and social platforms into complex and dynamic networked systems with even pervasive sensing and computing capabilities. This article reviews a broad class of state-of-the-art algorithms for time-varying optimization, with an eye to performing both algorithmic development and performance analysis. It offers a comprehensive overview of available tools and methods and unveils open challenges in application domains of broad range of interest. The real-world examples presented include smart power systems, robotics, machine learning, and data analytics, highlighting domain-specific issues and solutions. The ultimate goal is to exemplify wide engineering relevance of analytical tools and pertinent theoretical foundations.

Prior information can be incorporated in matrix completion to improve estimation accuracy and extrapolate the missing entries. Reproducing kernel Hilbert spaces provide tools to leverage the said prior information, and derive more reliable algorithms. This paper analyzes the generalization error of such approaches, and presents numerical tests confirming the theoretical results.

In this paper, we propose a class of robust stochastic subgradient methods for distributed learning from heterogeneous datasets at presence of an unknown number of Byzantine workers. The Byzantine workers, during the learning process, may send arbitrary incorrect messages to the master due to data corruptions, communication failures or malicious attacks, and consequently bias the learned model. The key to the proposed methods is a regularization term incorporated with the objective function so as to robustify the learning task and mitigate the negative effects of Byzantine attacks. The resultant subgradient-based algorithms are termed Byzantine-Robust Stochastic Aggregation methods, justifying our acronym RSA used henceforth. In contrast to most of the existing algorithms, RSA does not rely on the assumption that the data are independent and identically distributed (i.i.d.) on the workers, and hence fits for a wider class of applications. Theoretically, we show that: i) RSA converges to a near-optimal solution with the learning error dependent on the number of Byzantine workers; ii) the convergence rate of RSA under Byzantine attacks is the same as that of the stochastic gradient descent method, which is free of Byzantine attacks. Numerically, experiments on real dataset corroborate the competitive performance of RSA and a complexity reduction compared to the state-of-the-art alternatives.

This paper deals with bandit online learning, where feedback of unknown delay can emerge in non-stochastic multi-armed bandit (MAB) and bandit convex optimization (BCO) settings. MAB and BCO require only values of the objective function to become available through feedback, and are used to estimate the gradient appearing in the corresponding iterative algorithms. Since the challenging case of feedback with unknown delays prevents one from constructing the sought gradient estimates, existing MAB and BCO algorithms become intractable. Delayed exploration, exploitation, and exponential (DEXP3) iterations, along with delayed bandit gradient descent (DBGD) iterations are developed for MAB and BCO with unknown delays, respectively. Based on a unifying analysis framework, it is established that both DEXP3 and DBGD guarantee an $\tilde{\cal O}\big( \sqrt{K(T+D)} \big)$ regret, where $D$ denotes the delay accumulated over $T$ slots, and $K$ represents the number of arms in MAB or the dimension of decision variables in BCO. Numerical tests using both synthetic and real data validate DEXP3 and DBGD.

Multiview canonical correlation analysis (MCCA) looks for shared low-dimensional representations hidden in multiple transformations of common source signals. Existing MCCA approaches do not exploit the geometry of common sources, which can be either given a priori, or constructed from do- main knowledge. In this paper, a novel graph-regularized (G) MCCA is developed to account for such geometry-bearing in- formation via graph regularization in the classical maximum- variance MCCA model. GMCCA minimizes the distance between the sought canonical variables and the common sources, while incorporating the graph-induced prior of these sources. To capture nonlinear dependencies, GMCCA is fur- ther broadened to the graph-regularized kernel (GK) MCCA. Numerical tests using real datasets document the merits of G(K)MCCA in comparison with competing alternatives.

The era of "data deluge" has sparked the interest in graph-based learning methods in a number of disciplines such as sociology, biology, neuroscience, or engineering. In this paper, we introduce a graph recurrent neural network (GRNN) for scalable semi-supervised learning from multi-relational data. Key aspects of the novel GRNN architecture are the use of multi-relational graphs, the dynamic adaptation to the different relations via learnable weights, and the consideration of graph-based regularizers to promote smoothness and alleviate over-parametrization. Our ultimate goal is to design a powerful learning architecture able to: discover complex and highly non-linear data associations, combine (and select) multiple types of relations, and scale gracefully with respect to the size of the graph. Numerical tests with real datasets corroborate the design goals and illustrate the performance gains relative to competing alternatives.

Channel-gain cartography relies on sensor measurements to construct maps providing the attenuation profile between arbitrary transmitter-receiver locations. State-of-the-art on this subject includes tomography-based approaches, where shadowing effects are modeled by the weighted integral of a spatial loss field (SLF) that captures the propagation environment. To learn SLFs exhibiting statistical heterogeneity induced by spatially diverse propagation environments, the present work develops a Bayesian approach comprising a piecewise homogeneous SLF with an underlying hidden Markov random field model. Built on a variational Bayes scheme, the novel approach yields efficient field estimators at affordable complexity. In addition, a data-adaptive sensor selection algorithm is developed to collect informative measurements for effective learning of the SLF. Numerical tests demonstrate the capabilities of the novel approach.

Next-generation communication networks are envisioned to extensively utilize storage-enabled caching units to alleviate unfavorable surges of data traffic by pro-actively storing anticipated highly popular contents across geographically distributed storage devices during off-peak periods. This resource pre-allocation is envisioned not only to improve network efficiency, but also to increase user satisfaction. In this context, the present paper designs optimal caching schemes for distributed caching scenarios. In particular, we look at networks where a central node (base station) communicates with a number of "regular" nodes (users or pico base stations) equipped with local storage infrastructure. Given the spatio-temporal dynamics of content popularities, and the decentralized nature of our setup, the problem boils down to select what, when and where to cache. To address this problem, we define fetching and caching prices that vary across contents, time and space, and formulate a global optimization problem which aggregates the costs across those three domains. The resultant optimization is solved using decomposition and dynamic programming techniques, and a reduced-complexity algorithm is finally proposed. Preliminary simulations illustrating the behavior of our algorithm are finally presented.

Despite their well-documented learning capabilities in clean environments, deep convolutional neural networks (CNNs) are extremely fragile in adversarial settings, where carefully crafted perturbations created by an attacker can easily disrupt the task at hand. Numerous methods have been proposed for designing effective attacks, while the design of effective defense schemes is still an open area. This work leverages randomization-based defense schemes to introduce a sampling mechanism for strong and efficient defense. To this end, sampling is proposed to take place over the matricized mid-layer data in the neural network, and the sampling probabilities are systematically obtained via variance minimization. The proposed defense only requires adding sampling blocks to the network in the inference phase without extra overhead in the training. In addition, it can be utilized on any pre-trained network without altering the weights. Numerical tests corroborate the improved defense against various attack schemes in comparison with state-of-the-art randomized defenses.

State forecasting plays a critical role in power system monitoring, by offering system awareness even ahead of the time horizon, enhancing system observability, and providing efficient identification of the grid topology and link parameter changes. However, available approaches relying on linear estimators or single-hidden-layer feed-forward neural networks (FNNs), cannot capture long-term nonlinear dependencies in the voltage time series, and lead to suboptimal performance. To bypass these hurdles, this paper advocates deep recurrent neural networks (RNNs) for power system state forecasting. Deep RNNs capture long-term dependencies, and are easy to implement. By also leveraging the physics behind power systems, a novel architecture based on prox-linear nets (RPLN) is further developed for state forecasting based on past measurements. Simulated tests show improved performance of the proposed RNN and RPLN predictors when compared to FNN and vector autoregression based alternatives.

The present paper develops a novel aggregated gradient approach for distributed machine learning that adaptively compresses the gradient communication. The key idea is to first quantize the computed gradients, and then skip less informative quantized gradient communications by reusing outdated gradients. Quantizing and skipping result in 'lazy' worker-server communications, which justifies the term Lazily Aggregated Quantized gradient that is henceforth abbreviated as LAQ. Our LAQ can provably attain the same linear convergence rate as the gradient descent in the strongly convex case, while effecting major savings in the communication overhead both in transmitted bits as well as in communication rounds. Empirically, experiments with real data corroborate a significant communication reduction compared to existing gradient- and stochastic gradient-based algorithms.

This paper introduces PerDif; a novel framework for learning personalized diffusions over item-to-item graphs for top-n recommendation. PerDif learns the teleportation probabilities of a time-inhomogeneous random walk with restarts capturing a user-specific underlying item exploration process. Such an approach can lead to significant improvements in recommendation accuracy, while also providing useful information about the users in the system. Per-user fitting can be performed in parallel and very efficiently even in large-scale settings. A comprehensive set of experiments on real-world datasets demonstrate the scalability as well as the qualitative merits of the proposed framework. PerDif achieves high recommendation accuracy, outperforming state-of-the-art competing approaches---including several recently proposed methods relying on deep neural networks.

BACKGROUND: Gene networks in living cells can change depending on various conditions such as caused by different environments, tissue types, disease states, and development stages. Identifying the differential changes in gene networks is very important to understand molecular basis of various biological process. While existing algorithms can be used to infer two gene networks separately from gene expression data under two different conditions, and then to identify network changes, such an approach does not exploit the similarity between two gene networks, and it is thus suboptimal. A desirable approach would be clearly to infer two gene networks jointly, which can yield improved estimates of network changes. RESULTS: In this paper, we developed a proximal gradient algorithm for differential network (ProGAdNet) inference, that jointly infers two gene networks under different conditions and then identifies changes in the network structure. Computer simulations demonstrated that our ProGAdNet outperformed existing algorithms in terms of inference accuracy, and was much faster than a similar approach for joint inference of gene networks. Gene expression data of breast tumors and normal tissues in the TCGA database were analyzed with our ProGAdNet, and revealed that 268 genes were involved in the changed network edges. Gene set enrichment analysis identified a significant number of gene sets related to breast cancer or other types of cancer that are enriched in this set of 268 genes. Network analysis of the kidney cancer data in the TCGA database with ProGAdNet also identified a set of genes involved in network changes, and the majority of the top genes identified have been reported in the literature to be implicated in kidney cancer. These results corroborated that the gene sets identified by ProGAdNet were very informative about the cancer disease status. A software package implementing the ProGAdNet, computer simulations, and real data analysis is available as Additional file 1. CONCLUSION: With its superior performance over existing algorithms, ProGAdNet provides a valuable tool for finding changes in gene networks, which may aid the discovery of gene-gene interactions changed under different conditions.

This paper deals with online convex optimization involving both time-varying loss functions, and time-varying constraints. The loss functions are not fully accessible to the learner, and instead only the function values (also known as bandit feedback) are revealed at queried points. The constraints are revealed after making decisions, and can be instantaneously violated, yet they must be satisfied in the long term. This setting fits nicely the emerging online network tasks such as fog computing in the Internet-of-Things, where online decisions must flexibly adapt to the changing user preferences (loss functions), and the temporally unpredictable availability of resources (constraints). Tailored for such human-in-the-loop systems where the loss functions are hard to model, a family of online bandit saddle-point (BanSaP) schemes are developed, which adaptively adjust the online operations based on (possibly multiple) bandit feedback of the loss functions, and the changing environment. Performance here is assessed by: 1) dynamic regret that generalizes the widely used static regret and 2) fit that captures the accumulated amount of constraint violations. Specifically, BanSaP is proved to simultaneously yield sublinear dynamic regret and fit, provided that the best dynamic solutions vary slowly over time. Numerical tests in fog computation offloading tasks corroborate that our proposed BanSaP approach offers competitive performance relative to existing approaches that are based on gradient feedback.

Internet of Things (IoT) is powering up smart cities by connecting all kinds of electronic devices. The power supply problem of IoT devices constitutes a major challenge in current IoT development, due to the poor battery endurance as well as the troublesome cable deployment. The wireless power transfer (WPT) technology has recently emerged as a promising solution. Yet, existing WPT advances cannot support free and mobile charging like Wi-Fi communications. To this end, the concept of mobile energy transfer (MET) is proposed, which relies critically on a resonant beam charging (RBC) technology. The adaptive (A) RBC technology builds on RBC, but aims at improving the charging efficiency by charging devices at device preferred current and voltage levels adaptively. A mobile ARBC scheme is developed relying on an adaptive source power control. Extensive numerical simulations using a 1000-mAh Li-ion battery show that the mobile ARBC outperforms simple charging schemes, such as the constant power charging, the profile-adaptive charging, and the distance-adaptive charging in saving energy.

Kernel-based methods exhibit well-documented performance in various nonlinear learning tasks. Most of them rely on a preselected kernel, whose prudent choice presumes task-specific prior information. Especially when the latter is not available, multi-kernel learning has gained popularity thanks to its flexibility in choosing kernels from a prescribed kernel dictionary. Leveraging the random feature approximation and its recent orthogonality-promoting variant, the present contribution develops a scalable multi-kernel learning scheme (termed Raker) to obtain the sought nonlinear learning function `on the fly,' first for static environments. To further boost performance in dynamic environments, an adaptive multi-kernel learning scheme (termed AdaRaker) is developed. AdaRaker accounts not only for data-driven learning of kernel combination, but also for the unknown dynamics. Performance is analyzed in terms of both static and dynamic regrets. AdaRaker is uniquely capable of tracking nonlinear learning functions in environments with unknown dynamics, and with with analytic performance guarantees Tests with synthetic and real datasets are carried out to showcase the effectiveness of the novel algorithms.

Small base stations (SBs) of fifth-generation (5G) cellular networks are envisioned to have storage devices to locally serve requests for reusable and popular contents by caching them at the edge of the network, close to the end users. The ultimate goal is to smartly utilize a limited storage capacity to serve locally contents that are frequently requested instead of fetching them from the cloud, contributing to a better overall network performance and service experience. To enable the SBs with efficient fetch-cache decision-making schemes operating in dynamic settings, this paper introduces simple but flexible generic time-varying fetching and caching costs, which are then used to formulate a constrained minimization of the aggregate cost across files and time. Since caching decisions per time slot influence the content availability in future slots, the novel formulation for optimal fetch-cache decisions falls into the class of dynamic programming. Under this generic formulation, first by considering stationary distributions for the costs as well as file popularities, an efficient reinforcement learning-based solver known as value iteration algorithm can be used to solve the emerging optimization problem. Later, it is shown that practical limitations on cache capacity can be handled using a particular instance of this generic dynamic pricing formulation. Under this setting, to provide a light-weight online solver for the corresponding optimization, the well-known reinforcement learning algorithm, Q-learning, is employed to find optimal fetch-cache decisions. Numerical tests corroborating the merits of the proposed approach wrap up the paper.

In the envisioned smart grid, high penetration of uncertain renewables, unpredictable participation of (industrial) customers, and purposeful manipulation of smart meter readings, all highlight the need for accurate, fast, and robust power system state estimation (PSSE). Nonetheless, most real-time data available in the current and upcoming transmission/distribution systems are nonlinear in power system states (i.e., nodal voltage phasors). Scalable approaches to dealing with PSSE tasks undergo a paradigm shift toward addressing the unique modeling and computational challenges associated with those nonlinear measurements. In this study, we provide a contemporary overview of PSSE and describe the current state of the art in the nonlinear weighted least-squares and least-absolutevalue PSSE. To benchmark the performance of unbiased estimators, the Cramér-Rao lower bound is developed. Accounting for cyber attacks, new corruption models are introduced, and robust PSSE approaches are outlined as well. Finally, distribution system state estimation is discussed along with its current challenges. Simulation tests corroborate the effectiveness of the developed algorithms as well as the practical merits of the theory.

Internet of Things (IoT) envisions an intelligent infrastructure of networked smart devices offering task-specific monitoring and control services. The unique features of IoT include extreme heterogeneity, massive number of devices, and unpredictable dynamics partially due to human interaction. These call for foundational innovations in network design and management. Ideally, it should allow efficient adaptation to changing environments, and low-cost implementation scalable to a massive number of devices, subject to stringent latency constraints. To this end, the overarching goal of this paper is to outline a unified framework for online learning and management policies in IoT through joint advances in communication, networking, learning, and optimization. From the network architecture vantage point, the unified framework leverages a promising fog architecture that enables smart devices to have proximity access to cloud functionalities at the network edge, along the cloud-to-things continuum. From the algorithmic perspective, key innovations target online approaches adaptive to different degrees of nonstationarity in IoT dynamics, and their scalable model-free implementation under limited feedback that motivates blind or bandit approaches. The proposed framework aspires to offer a stepping stone that leads to systematic designs and analysis of task-specific learning and management schemes for IoT, along with a host of new research directions to build on.

Network Function Virtualization (NFV) can cost-efficiently provide network services by running different virtual network functions (VNFs) at different virtual machines (VMs) in a correct order. This can result in strong couplings between the decisions of the VMs on the placement and operations of VNFs. This paper presents a new fully decentralized online approach for optimal placement and operations of VNFs. Building on a new stochastic dual gradient method, our approach decouples the real-time decisions of VMs, asymptotically minimizes the time-average cost of NFV, and stabilizes the backlogs of network services with a cost-backlog tradeoff of [ε, 1/ε], for any ε > 0. Our approach can be relaxed into multiple timescales to have VNFs (re)placed at a larger timescale and hence alleviate service interruptions. While proved to preserve the asymptotic optimality, the larger timescale can slow down the optimal placement of VNFs. A learn-and-adapt strategy is further designed to speed the placement up with an improved tradeoff [ε, log2(ε)/ε]. Numerical results show that the proposed method is able to reduce the time-average cost of NFV by 23 percent and reduce the queue length (or delay) by 74 percent, as compared to existing benchmarks.

Kernel-based methods exhibit well-documented performance in various nonlinear learning tasks. Most of them rely on a preselected kernel, whose prudent choice presumes task-specific prior information. To cope with this limitation, multi-kernel learning has gained popularity thanks to its flexibility in choosing kernels from a prescribed kernel dictionary. Leveraging the random feature approximation and its recent orthogonality-promoting variant, the present contribution develops an online multi-kernel learning scheme to infer the intended nonlinear function ‘on the fly.’ To further boost performance in non-stationary environments, an adaptive multi-kernel learning scheme is developed with affordable computation and memory complexity. Performance is analyzed in terms of both static and dynamic regret. To our best knowledge, AdaRaker is the first algorithm that can optimally track nonlinear functions in non-stationary settings with strong theoretical guarantees. Numerical tests on real datasets are carried out to showcase the effectiveness of the proposed algorithms.

Diffusion-based classifiers such as those relying on the Personalized PageRank and the Heat kernel, enjoy remarkable classification accuracy at modest computational requirements. Their performance however is affected by the extent to which the chosen diffusion captures a typically unknown label propagation mechanism, that can be specific to the underlying graph, and potentially different for each class. The present work introduces a disciplined, data-efficient approach to learning class-specific diffusion functions adapted to the underlying network topology. The novel learning approach leverages the notion of "landing probabilities" of class-specific random walks, which can be computed efficiently, thereby ensuring scalability to large graphs. This is supported by rigorous analysis of the properties of the model as well as the proposed algorithms. Classification tests on real networks demonstrate that adapting the diffusion function to the given graph and observed labels, significantly improves the performance over fixed diffusions; reaching-and many times surpassing-the classification accuracy of computationally heavier state-of-the-art competing methods, that rely on node embeddings and deep neural networks.

The present work introduces methods for sampling and inference for the purpose of semi-supervised classification over the nodes of a graph. The graph may be given or constructed using similarity measures among nodal features. Leveraging the graph for classification builds on the premise that relation among nodes can be modeled via stationary distributions of a certain class of random walks. The proposed classifier builds on existing scalable random-walk-based methods and improves accuracy and robustness by automatically adjusting a set of parameters to the graph and label distribution at hand. Furthermore, a sampling strategy tailored to random-walk-based classifiers is introduced. Numerical tests on benchmark synthetic and real labeled graphs demonstrate the performance of the proposed sampling and inference methods in terms of classification accuracy.

This paper focuses on the online fog computing tasks in the Internet-of-Things (IoT), where online decisions must flexibly adapt to the changing user preferences (loss functions), and the temporally unpredictable availability of resources (constraints). Tailored for such human-in-the-loop systems where the loss functions are hard to model, a family of bandit online saddle-point (BanSP) schemes are developed, which adaptively adjust the online operations based on (possibly multiple) bandit feedback of the loss functions, and the changing environment. Performance here is assessed by: i) dynamic regret that generalizes the widely used static regret; and, ii) fit that captures the accumulated amount of constraint violations. Specifically, BanSP is proved to simultaneously yield sub-linear dynamic regret and fit, provided that the best dynamic solutions vary slowly over time. Numerical tests on fog computing tasks corroborate that BanSP offers desired performance under such limited information.

Channel gain cartography relies on sensor measurements to construct maps providing the attenuation profile between arbitrary transmitter-receiver locations. Existing approaches capitalize on tomographic models, where shadowing is the weighted integral of a spatial loss field (SLF) depending on the propagation environment. Currently, the SLF is learned via regularization methods tailored to the propagation environment. However, the effectiveness of existing approaches remains unclear especially when the propagation environment involves heterogeneous characteristics. To cope with this, the present work considers a piecewise homogeneous SLF with a hidden Markov random field (MRF) model under the Bayesian framework. Efficient field estimators are obtained by using samples from Markov chain Monte Carlo (MCMC). Furthermore, an uncertainty sampling algorithm is developed to adaptively collect measurements. Real data tests demonstrate the capabilities of the novel approach.

The Alternating Directions Methods of Multipliers (ADMM) has witnessed a resurgence of interest over the past few years fueled by the ever increasing demand for scalable optimization techniques to tackle real-world statistical learning problems. However, despite its success in several application settings the applicability of the traditional centralized ADMM is limited by its communication requirement to a global fusion center, which might not be always feasible. Its decentralized variant D-CADMM, on the other hand, while it alleviates this need, it does so at the expense of significantly slower convergence in cases of adverse underlying network topologies. To address the aforementioned limitations, in this work we consider the presence of multiple fusion centers and we propose a unifying framework that allows leveraging the structure of the communication network to accelerate the decentralized ADMM even in cases where it is not practical to resort to its fully centralized counterpart. We prove the linear convergence rate of the proposed approach and we verify its promising performance by carrying out numerical tests on both real and synthetic networks.

In next generation cellular networks (5G) the access points (APs) are anticipated to be equipped with storage devices to serve locally requests for reusable popular contents by caching them at the edge of the network. The ultimate goal is to shift part of the load on the back-haul links from on-peak to off-peak periods, contributing to a better overall network performance and service experience. In order to enable the APs with efficient (optimal) fetch-cache decision making schemes able to work in dynamic settings, we introduce simple but flexible generic time-varying fetching and caching costs, which are then used to formulate a constrained minimization of the aggregate cost across files and time. Since caching decisions in every time slot influence the content availability in future instants, the novel formulation for optimal fetch-cache decisions falls into the class of dynamic programming, for which efficient reinforcement-learning-based solvers are proposed. The performance of our algorithms is assessed via numerical tests, and discussions on the inherent fetching-versus-caching trade-off are provided.

Kernel-based methods have well-appreciated performance in various nonlinear learning tasks. Most of them rely on a preselected kernel, whose prudent choice presumes task-specific prior information. To cope with this limitation, multi-kernel learning has gained popularity thanks to its flexibility in choosing kernels from a prescribed kernel dictionary. Leveraging the random feature approximation and its recent orthogonality-promoting variant, the present contribution develops an online multi-kernel learning scheme to infer the intended nonlinear function `on the fly.' Performance analysis shows that the novel algorithm can afford sublinear regret. Numerical tests on real datasets are carried out to showcase the effectiveness of the proposed algorithms.

Principal component analysis (PCA) has well-documented merits for data extraction and dimensionality reduction. PCA deals with a single dataset at a time, and it is challenged when it comes to analyzing multiple datasets. Yet in certain setups, one wishes to extract the most significant information of one dataset relative to other datasets. Specifically, the interest may be on identifying or extracting features that are specific to a single target dataset but not the others. This paper presents a novel approach for such so-termed discriminative data analysis, and establishes its optimality in the least-squares sense under suitable assumptions. The criterion reveals linear combinations of variables by maximizing the ratio of the variance of the target data to that of the remainders. The novel approach solves a generalized eigenvalue problem by performing SVD just once. Numerical tests using synthetic and real datasets showcase the merits of the proposed approach relative to its competing alternatives.

Segmentation of ventricles from cardiac magnetic resonance (MR) images is a key step to obtaining clinical parameters useful for prognosis of cardiac pathologies. To improve upon the performance of existing fully convolutional network (FCN) based automatic right ventricle (RV) segmentation approaches, a multi-task deep neural network (DNN) architecture is proposed. The multi-task model can employ any FCN as a building block, allows for leveraging shared features between different tasks, and can be efficiently trained end-to-end. Specifically, a multi-task U-net is developed and implemented using the Tensorflow framework. Numerical tests on real datasets showcase the merits of the proposed approach and in particular its ability to offer improved segmentation performance for small-size RVs.

This paper presents a new class of gradient methods for distributed machine learning that adaptively skip the gradient calculations to learn with reduced communication and computation. Simple rules are designed to detect slowly-varying gradients and, therefore, trigger the reuse of outdated gradients. The resultant gradient-based algorithms are termed Lazily Aggregated Gradient --- justifying our acronym LAG used henceforth. Theoretically, the merits of this contribution are: i) the convergence rate is the same as batch gradient descent in strongly-convex, convex, and nonconvex cases; and, ii) if the distributed datasets are heterogeneous (quantified by certain measurable constants), the communication rounds needed to achieve a targeted accuracy are reduced thanks to the adaptive reuse of lagged gradients. Numerical experiments on both synthetic and real data corroborate a significant communication reduction compared to alternatives.

Internet of Things (IoT) is featured with its seamless connectivity of billions of smart devices, which offer different functionalities and serve various personalized tasks. To meet the task-specific requirements such as latency and privacy, the fog computing emerges to extend cloud computing services to the edge of the Internet backbone. This paper deals withonline fog computingemerging in IoT, where the goal is to balance computation and communication at fog networks on-the-fly to minimize service latency. Due to heterogeneous devices and human participation in IoT, the online decisions here need to flexibly adapt to the temporally unpredictable user demands and availability of fog resources. By generalizing the classic online convex optimization (OCO) framework, the low-latency fog computing task is first formulated as an OCO problem involving both time-varying loss functions and time-varying constraints. These constraints are revealed after making decisions, and allow instantaneous violations yet they must be satisfied in the long term. Tailored for heterogeneous tasks in IoT, a “thing-adaptive” online saddle-point (TAOSP) scheme is developed, which automatically adjusts the stepsize to offer desirabletask-specificlearning rates. It is established that without prior knowledge of the time-varying parameters, TAOSP simultaneously yields near-optimality and feasibility, provided that the best dynamic solutions vary slowly over time. Numerical tests corroborate that our novel approach outperforms the state-of-the-art in minimizing network latency.

Identifying graph topologies as well as processes evolving over graphs emerge in various applications involving gene-regulatory, brain, power, and social networks, to name a few. Key graph-aware learning tasks include regression, classification, subspace clustering, anomaly identification, interpolation, extrapolation, and dimensionality reduction. Scalable approaches to deal with such high-dimensional tasks experience a paradigm shift to address the unique modeling and computational challenges associated with data-driven sciences. Albeit simple and tractable, linear time-invariant models are limited since they are incapable of handling generally evolving topologies, as well as nonlinear and dynamic dependencies between nodal processes. To this end, the main goal of this paper is to outline overarching advances, and develop a principled framework to capture nonlinearities through kernels, which are judiciously chosen from a preselected dictionary to optimally fit the data. The framework encompasses and leverages (non) linear counterparts of partial correlation and partial Granger causality, as well as (non)linear structural equations and vector autoregressions, along with attributes such as low rank, sparsity, and smoothness to capture even directional dependencies with abrupt change points, as well as time-evolving processes over possibly time-evolving topologies. The overarching approach inherits the versatility and generality of kernel-based methods, and lends itself to batch and computationally affordable online learning algorithms, which include novel Kalman filters over graphs. Real data experiments highlight the impact of the nonlinear and dynamic models on consumer and financial networks, as well as gene-regulatory and functional connectivity brain networks, where connectivity patterns revealed exhibit discernible differences relative to existing approaches.

This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector x from a system of quadratic equations of the form yi= |〈ai, x〉|2, where ai's are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adapts the amplitude based empirical loss function and proceeds in two stages. In the first stage, we introduce an orthogonality-promoting initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable truncated generalized gradient iterations, which are able to handle the rather challenging nonconvex and nonsmooth amplitude based objective function. In particular, when vectors x and ai's are real valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.

By performing fog computing, a device can offload delay-tolerant computationally demanding tasks to its peers for processing, and the results can be returned and aggregated. In distributed wireless networks, the challenges of fog computing include lack of central coordination, selfish behaviors of devices, and multi-hop signaling delays, which can result in outdated network knowledge and prevent effective cooperations beyond one hop. This paper presents a new approach to enable cooperations of N selfish devices over multiple hops, where selfish behaviors are discouraged by a tit-for-tat mechanism. The titfor-tat incentive of a device is designed to be the gap between the helps (in terms of energy) the device has received and offered; and indicates how much help the device can offer at the next time slot. The tit-for-tat incentives can be evaluated at every device by having all devices broadcast how much help they offered in the past time slot, and used by all devices to schedule task offloading and processing. The approach achieves asymptotic optimality in a fully distributed fashion with a timecomplexity of less than O(N2). The optimality loss resulting from multi-hop signaling delays and consequently outdated titfor-tat incentives is proved to asymptotically diminish. Simulation results show that our approach substantially reduces the timeaverage energy consumption of the state of the art by 50% and accommodates more tasks, by engaging devices hops away under multi-hop delays.

Decoupling network services from underlying hardware, network function virtualization (NFV) is expected to significantly improve agility and reduce network cost. However, network services, sequences of network functions, need to be processed in specific orders at specific types of virtual machines (VMs), which couples decisions of VMs on processing or routing network services. Built on a new stochastic dual gradient method, our approach suppresses the couplings, minimizes the time-average cost of NFV, stabilizes queues at VMs, and reduces the backlogs of unprocessed services through online learning and adaptation. Asymptotically optimal decisions are instantly generated at individual VMs, with a cost-delay tradeoff [ε,log2(ε)/√ε]. Numerical results show that the proposed method is able to reduce the time-average cost of NFV by 30% and reduce the queue length (or delay) by 83%, as compared to existing non-stochastic approaches.

Granger causality based approaches are popular in unveiling directed interactions among brain regions. The present work advocates a multi-kernel based nonlinear model for obtaining the effective connectivity between brain regions, by wedding the merits of partial correlation in undirected topology identification with the ability of partial Granger causality (PGC) to estimate edge directionality. The premise is that existing linear PGC approaches may be inadequate for capturing certain dependencies, whereas available nonlinear connectivity models lack data adaptability that multi-kernel learning methods can offer. The proposed approach is tested on both synthetic and real resting-state fMRI data, with the former illustrating the gains in directed edge presence detection performance, as compared to existing PGC methods, and with the latter highlighting differences in the estimated test statistics.

Crowdsourcing approaches rely on the collection of multiple individuals to solve problems that require analysis of large data sets in a timely accurate manner. The inexperience of participants or annotators motivates well robust techniques. Focusing on clustering setups, the data provided by all annotators is suitably modeled here as a mixture of Gaussian components plus a uniformly distributed random variable to capture outliers. The proposed algorithm is based on the expectation-maximization algorithm and allows for soft assignments of data to clusters, to rate annotators according to their performance, and to estimate the number of Gaussian components in the non-Gaussian/Gaussian mixture model, in a jointly manner.

Linear structural vector autoregressive models constitute a generalization of structural equation models (SEMs) and vector autoregressive (VAR) models, two popular approaches for topology inference of directed graphs. Although simple and tractable, linear SVARMs seldom capture nonlinearities that are inherent to complex systems, such as the human brain. To this end, the present paper advocates kernel-based nonlinear SVARMs, and develops an efficient sparsity-promoting least-squares estimator to learn the hidden topology. Numerical tests on real electrocorticographic (ECoG) data from an Epilepsy study corroborate the efficacy of the novel approach.

A linear-time algorithm termed SPARse Truncated Amplitude flow (SPARTA) is developed for the phase retrieval (PR) of sparse signals. Upon formulating the sparse PR as a non-convex empirical loss minimization task, SPARTA emerges as an iterative solver consisting of two components: s1) a sparse orthogonality-promoting initialization leveraging support recovery and principal component analysis; and, s2) a series of refinements by hard thresholding based truncated gradient iterations. SPARTA is simple, scalable, and fast. It recovers any k-sparse n-dimensional signal (k ≪ n) of large enough minimum (in modulus) nonzero entries from about k2log n measurements with high probability; this is achieved at computational complexity of order k2n log n, improving upon the state-of-the-art by at least a factor of k. SPARTA is robust against bounded additive noise. Simulated tests corroborate the merits of SPARTA relative to existing alternatives.

The deluge of networked big data motivates the development of computation- and communication-efficient network information processing algorithms. In this paper, we propose two data-adaptive censoring strategies that significantly reduce the computation and communication costs of the distributed recursive least-squares (D-RLS) algorithm. Through introducing a cost function that underrates the importance of those observations with small innovations, we develop the first censoring strategy based on the alternating minimization algorithm and the stochastic Newton method. It saves computation when a datum is censored. The computation and communication costs are further reduced by the second censoring strategy, which prohibits a node updating and transmitting its local estimate to neighbors when its current innovation is less than a threshold. For both strategies, a simple criterion for selecting the threshold of innovation is given so as to reach a target ratio of data reduction. The proposed censored D-RLS algorithms guarantee convergence to the optimal argument in the mean-square deviation sense. Numerical experiments validate the effectiveness of the proposed algorithms.

The task of community detection over complex networks is of paramount importance in a multitude of applications. The present work puts forward a top-to-bottom community identification approach, termed DC-EgoTen, in which an egonet-tensor (EgoTen) based algorithm is developed in a divide-and-conquer (DC) fashion for breaking the network into smaller subgraphs, out of which the underlying communities progressively emerge. In particular, each step of DC-EgoTen forms a multi-dimensional egonet-based representation of the graph, whose induced structure enables casting the task of overlapping community identification as a constrained PARAFAC decomposition. Thanks to the higher representational capacity of tensors, the novel egonet-based representation improves the quality of detected communities by capturing multi-hop connectivity patterns of the network. In addition, the top-to-bottom approach ensures successive refinement of identified communities, so that the desired resolution is achieved. Synthetic as well as real-world tests corroborate the effectiveness of DC-EgoTen.

This paper deals with finding an $n$-dimensional solution $\bm{x}$ to a system of quadratic equations $y_i=|\langle\bm{a}_i,\bm{x}\rangle|^2$, $1\le i \le m$, which in general is known to be NP-hard. We put forth a novel procedure, that starts with a \emph{weighted maximal correlation initialization} obtainable with a few power iterations, followed by successive refinements based on \emph{iteratively reweighted gradient-type iterations}. The novel techniques distinguish themselves from prior works by the inclusion of a fresh (re)weighting regularization. For certain random measurement models, the proposed procedure returns the true solution $\bm{x}$ with high probability in time proportional to reading the data $\{(\bm{a}_i;y_i)\}_{1\le i \le m}$, provided that the number $m$ of equations is some constant $c>0$ times the number $n$ of unknowns, that is, $m\ge cn$. Empirically, the upshots of this contribution are: i) perfect signal recovery in the high-dimensional regime given only an \emph{information-theoretic limit number} of equations; and, ii) (near-)optimal statistical accuracy in the presence of additive noise. Extensive numerical tests using both synthetic data and real images corroborate its improved signal recovery performance and computational efficiency relative to state-of-the-art approaches.

Mobile edge computing is of particular interest to Internet of Things (IoT), where inexpensive simple devices can get complex tasks offloaded to and processed at powerful infrastructure. Scheduling is challenging due to stochastic task arrivals and wireless channels, congested air interface, and more prominently, prohibitive feedbacks from thousands of devices. In this paper, we generate asymptotically optimal schedules tolerant to out-of-date network knowledge, thereby relieving stringent requirements on feedbacks. A perturbed Lyapunov function is designed to stochastically maximize a network utility balancing throughput and fairness. A knapsack problem is solved per slot for the optimal schedule, provided up-to-date knowledge on the data and energy backlogs of all devices. The knapsack problem is relaxed to accommodate out-of-date network states. Encapsulating the optimal schedule under up-to-date network knowledge, the solution under partial out-of-date knowledge preserves asymptotic optimality, and allows devices to self-nominate for feedback. Corroborated by simulations, our approach is able to dramatically reduce feedbacks at no cost of optimality. The number of devices that need to feed back is reduced to less than 60 out of a total of 5000 IoT devices.

Contemporary cloud networks are being challenged by the rapid increase of user demands and growing concerns about global warming, due to their substantial energy consumption. This requires future data centers to be both energy efficient and sustainable, which calls for leveraging cutting-edge features and the flexibility provided by the modern smart grids. To fulfill those goals, this paper puts forward a systematic approach to designing energy-aware traffic-efficient geographicalload balancing schemesfor data-center networks that are not only optimal, but also computationally efficient and amenable todistributedimplementation. Under this comprehensive approach, workload and power balancing schemes are designed jointly across the network, both delay-tolerant andinteractive workloadsare accommodated, novel smart-grid features such as energy storage units are incorporated to cope with renewables, andincentive pricingmechanisms are adopted in the design. To further account for the spatio-temporal variation of demands, energy prices and renewables, the task is formulated as a two-timescale stochastic optimization. Leveraging dual stochastic approximation and the fast iterative shrinkage-thresholding algorithm (FISTA), the proposed optimization is decomposed across time slots (first-stage) and data centers (second-stage). While the resultant online algorithm is strictly feasible and provably optimal under a Markovian assumption for the underlying random processes, extensive numerical tests further demonstrate that it also works well in real-data scenarios, where the underlying randomness is highly correlated across time.

Channel gain cartography aims at inferring the channel gains between two arbitrary points in space based on the measurements (samples) of the gains collected by a set of radios deployed in the area. Channel gain maps are useful for various sensing and resource allocation tasks essential for the operation of cognitive radio networks. In this paper, the channel gains are modeled as the tomographic accumulations of an underlying spatial loss field (SLF), which captures the attenuation in the signal strength due to the obstacles in the propagation path. In order to estimate the map accurately with a relatively small number of measurements, the SLF is postulated to have a low-rank structure possibly with sparse deviations. Efficient batch and online algorithms are derived for the resulting map reconstruction problem. Comprehensive tests with both synthetic and real data sets corroborate that the algorithms can accurately reveal the structure of the propagation medium, and produce the desired channel gain maps.

In this paper, a novel two-scale stochastic control framework is put forth for smart-grid powered coordinated multi-point (CoMP) systems. Taking into account renewable energy sources (RES), dynamic pricing, two-way energy trading facilities and imperfect energy storage devices, the energy management task is formulated as an infinite-horizon optimization problem minimizing the time-averaged energy transaction cost, subject to the users' quality of service (QoS) requirements. Leveraging the Lyapunov optimization approach and the stochastic subgradient method, a two-scale online control (TS-OC) approach is developed to make online control decisions at two timescales. It is analytically established that the TS-OC is capable of yielding a feasible and asymptotically near-optimal solution.

In an age of exponentially increasing data generation, performing inference tasks by utilizing the available information in its entirety is not always an affordable option. The present paper puts forth approaches to render tracking of large-scale dynamic processes affordable, by processing a reduced number of data. Two distinct methods are introduced for reducing the number of data involved per time step. The first method builds on reduction using low-complexity random projections, while the second performs censoring for data-adaptive measurement selection. Simulations on synthetic data, compare the proposed methods with competing alternatives, and corroborate their efficacy in terms of estimation accuracy over complexity reduction.

An infinite time-horizon resource allocation problem is formulated to maximize the time-averaged multi-input multi-output (MIMO) downlink throughput, subject to a time-averaged energy cost budget. By using the advanced time decoupling technique, a novel stochastic subgradient based online control (SGOC) approach is developed for the resultant smart-grid powered communication system. It is analytically established that even without a-priori knowledge of the underlying random processes, the proposed online algorithm is capable of yielding a feasible and asymptotically optimal solution.

A systematic framework is put forth in this paper to integrate renewable energy sources (RES), distributed storage units, cooling facilities, as well as dynamic pricing into the workload and energy management tasks for a data center network. To cope with RES uncertainty, the resource allocation task is formulated as a robust optimization problem minimizing the worst-case net cost. The resulting problem is reformulated as a convex program, and then solved in a distributed fashion using the dual decomposition approach. Numerical tests demonstrate the performance gain of the proposed approach over the existing alternative.

Partial correlations (PCs) of functional magnetic resonance imaging (fMRI) time series play a principal role in revealing connectivity of brain networks. To explore nonlinear behavior of the blood-oxygen-level dependent signal, the present work postulates a kernel-based nonlinear connectivity model based on which it obtains topology revealing PCs. Instead of relying on a single predefined kernel, a data-driven approach is advocated to learn the combination of multiple kernel functions that optimizes the data fit. Synthetically generated data based on both a dynamic causal and a linear model are used to validate the proposed approach in resting-state fMRI scenarios, highlighting the gains in edge detection performance when compared with the popular linear PC method. Tests on real fMRI data demonstrate that connectivity patterns revealed by linear and nonlinear models are different.

Big data applications demand efficient solvers capable of providing accurate solutions to large-scale problems at affordable computational costs. Processing data sequentially, online algorithms offer attractive means to deal with massive data sets. However, they may incur prohibitive complexity in high-dimensional scenarios if the entire data set is processed. It is therefore necessary to confine computations to an informative subset. While existing approaches have focused on selecting a prescribed fraction of the available data vectors, the present paper capitalizes on this degree of freedom to accelerate the convergence of a generic class of online algorithms in terms of processing time/computational resources by balancing the required burden with a metric of how informative each datum is. The proposed method is illustrated in a linear regression setting, and simulations corroborate the superior convergence rate of the recursive least-squares algorithm when the novel data selection is effected.

Variabilities of renewable energy sources critically challenge contemporary power distribution grids. Depending on grid conditions, solar energy may have to be curtailed to comply with network limitations. On the other hand, smart inverters installed with solar panels enable for reactive power support at fast response rates. Existing energy management schemes may not efficiently integrate intermittent generation. Inherent operational flexibilities, such as flexible voltage regulation margins and instantaneous inverter or distribution line overloading could be judiciously exploited. To that end, an ergodic energy management framework is put forth calling for joint control of active and reactive power using smart inverters. Although tighter operational constraints are enforced in an average sense, looser margins are satisfied at all times. A stochastic dual subgradient solver is devised using an approximate linearized grid model. The algorithm is distribution free, and enjoys provable convergence. Numerical tests on a 56-bus distribution feeder demonstrate that the novel scheme yields lower energy cost upon its deterministic counterpart.

We study the problem of high-dimensional covariance matrix estimation from partial observations. We consider covariance matrices modeled as Kronecker products of matrix factors, and rely on observations with missing values. In the absence of missing data, observation vectors are assumed to be i.i.d multivariate Gaussian. In particular, we propose a new procedure computationally affordable in high dimension to extend an existing permuted rank-penalized least-squares method to the case of missing data. Our approach is applicable to a large variety of missing data mechanisms, whether the process generating missing values is random or not, and does not require imputation techniques. We introduce a novel unbiased estimator and characterize its convergence rate to the true covariance matrix measured by the spectral norm of a permutation operator. We establish a tight outer bound on the square error of our estimate, and elucidate consequences of missing values on the estimation performance. Different schemes are compared by numerical simulations in order to test our proposed estimator.

This paper puts forth a novel algorithm, termed \emph{truncated generalized gradient flow} (TGGF), to solve for $\bm{x}\in\mathbb{R}^n/\mathbb{C}^n$ a system of $m$ quadratic equations $y_i=|\langle\bm{a}_i,\bm{x}\rangle|^2$, $i=1,2,\ldots,m$, which even for $\left\{\bm{a}_i\in\mathbb{R}^n/\mathbb{C}^n\right\}_{i=1}^m$ random is known to be \emph{NP-hard} in general. We prove that as soon as the number of equations $m$ is on the order of the number of unknowns $n$, TGGF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with the time required to read the data $\left\{\left(\bm{a}_i;\,y_i\right)\right\}_{i=1}^m$. Specifically, TGGF proceeds in two stages: s1) A novel \emph{orthogonality-promoting} initialization that is obtained with simple power iterations; and, s2) a refinement of the initial estimate by successive updates of scalable \emph{truncated generalized gradient iterations}. The former is in sharp contrast to the existing spectral initializations, while the latter handles the rather challenging nonconvex and nonsmooth \emph{amplitude-based} cost function. Numerical tests demonstrate that: i) The novel orthogonality-promoting initialization method returns more accurate and robust estimates relative to its spectral counterparts; and ii) even with the same initialization, our refinement/truncation outperforms Wirtinger-based alternatives, all corroborating the superior performance of TGGF over state-of-the-art algorithms.

A large number of geo-distributed data centers begin to surge in the era of data deluge and information explosion. To meet the growing demand in massive data processing, the infrastructure of future data centers must be energy-efficient and sustainable. Facing this challenge, a systematic framework is put forth in this paper to integrate renewable energy sources (RES), distributed storage units, cooling facilities, as well as dynamic pricing into the workload and energy management tasks of a data center network. To cope with RES uncertainty, the resource allocation task is formulated as a robust optimization problem minimizing the worst-case net cost. Compared with existing stochastic optimization methods, the proposed approach entails a deterministic uncertainty set where generated RES reside, thus can be readily obtained in practice. It is further shown that the problem can be cast as a convex program, and then solved in a distributed fashion using the dual decomposition method. By exploiting the spatio-temporal diversity of local temperature, workload demand, energy prices, and renewable availability, the proposed approach outperforms existing alternatives, as corroborated by extensive numerical tests performed using real data.

Benefiting from technological advances in the smart grid era, next-generation multi-input multi-output (MIMO) communication systems are expected to be powered by renewable energy sources (RES) integrated in the distribution grid, thus realizing the vision of “green communications.” However, penetration of renewables introduces variabilities in the traditional power system, making RES benefits achievable only after appropriately mitigating their inherently high variability, which challenges existing resource allocation strategies. Aligned with this goal, an infinite time-horizon resource allocation problem is formulated to maximize the time-average MIMO downlink throughput, subject to a time-average energy cost budget. By using the advanced time decoupling technique, a novel stochastic subgradient-based online control approach is developed for the resultant smart-grid powered communication system. It is established analytically that even without a priori knowledge of the independently and identically distributed (i.i.d.) processes involved such as channel coefficients, renewables, and electricity prices, the proposed online control algorithm is still able to yield a feasible and asymptotically optimal solution. Numerical results further demonstrate that the proposed algorithm also works well in non-i.i.d. scenarios, where the underlying randomness is highly correlated over time.

Due to increasing threats of global warming and climate change concerns, green wireless communications have recently drawn intense attention toward reducing carbon emissions. Aligned with this goal, the present paper deals with dynamic energy management for smart-grid powered coordinated multipoint (CoMP) transmissions. To address the intrinsic variability of renewable energy sources, a novel energy transaction mechanism is introduced for grid-connected base stations that are also equipped with an energy storage unit. Aiming to minimize the expected energy transaction cost while guaranteeing the worst-case users’ quality of service, an infinite-horizon optimization problem is formulated to obtain the optimal downlink transmit beamformers that are robust to channel uncertainties. Capitalizing on the virtual-queue-based relaxation technique and the stochastic dual-subgradient method, an efficient online algorithm is developed yielding a feasible and asymptotically optimal solution. Numerical tests with synthetic and real data corroborate the analytical performance claims and highlight the merits of the novel approach.

Mapping origin-destination (OD) network traffic is pivotal for network management and proactive security tasks. However, lack of sufficient flow-level measurements as well as potential anomalies pose major challenges towards this goal. Leveraging the spatiotemporal correlation of nominal traffic, and the sparse nature of anomalies, this paper brings forth a novel framework to map out nominal and anomalous traffic, which treats jointly important network monitoring tasks including traffic estimation, anomaly detection, and traffic interpolation. To this end, a convex program is first formulated with nuclear and l1-norm regularization to effect sparsity and low rank for the nominal and anomalous traffic with only the link counts and a small subset of OD-flow counts. Analysis and simulations confirm that the proposed estimator can exactly recover sufficiently low-dimensional nominal traffic and sporadic anomalies so long as the routing paths are sufficiently “spread-out” across the network, and an adequate amount of flow counts are randomly sampled. The results offer valuable insights about data acquisition strategies and network scenaria giving rise to accurate traffic estimation. For practical networks where the aforementioned conditions are possibly violated, the inherent spatiotemporal traffic patterns are taken into account by adopting a Bayesian approach along with a bilinear characterization of the nuclear and l1 norms. The resultant nonconvex program involves quadratic regularizers with correlation matrices, learned systematically from (cyclo)stationary historical data. Alternating-minimization based algorithms with provable convergence are also developed to procure the estimates. Insightful tests with synthetic and real Internet data corroborate the effectiveness of the novel schemes.

Optimal resource management for smart grid powered multi-input multi-output (MIMO) systems is of great importance for future green wireless communications. A novel framework is put forth to account for the stochastic renewable energy sources (RES), dynamic energy prices, as well as random wireless channels. Based on practical models, the resource allocation task is formulated as an optimization problem that aims at maximizing the weighted sum-rate of the MIMO broadcast channels. A two-way transaction mechanism and storage units are introduced to accommodate the RES variability. In addition to system operating constraints, a budget threshold is imposed on the worst-case energy transaction cost due to the possibly adversarial nature. Capitalizing on the uplink-downlink duality and the Lagrangian relaxation-based subgradient method, an efficient algorithm is developed to obtain the optimal strategy. Generalizations to the setups of time-varying channels and ON-OFF transmissions are also discussed. Numerical results are provided to corroborate the merits of the novel approaches.

Multicell cooperative processing with limited backhaul traffic is studied for cellular uplinks. Aiming at reduced backhaul overhead, a sparse multicell linear receive-filter design problem is formulated. Both unstructured distributed cooperation and clustered cooperation, in which base station groups are formed for tight cooperation, are considered. Dynamic clustered cooperation, where the sparse equalizer and the cooperation clusters are jointly determined, is solved via alternating minimization based on spectral clustering and group-sparse regression. Furthermore, decentralized implementations of both unstructured and clustered cooperation schemes are developed for scalability, robustness, and computational efficiency. Extensive numerical tests verify the efficacy of the proposed methods.

The paper deals with dynamic energy management for smart-grid powered coordinated multi-point (CoMP) transmissions. Aiming to minimize the expected energy transaction cost while guaranteeing the worst-case users' quality of service (QoS), an infinite-horizon optimization problem is formulated to obtain the optimal downlink transmit beamformers that are robust to channel uncertainties. Capitalizing on the virtual-queue based relaxation technique and the stochastic dual-subgradient method, an efficient online algorithm is developed in this context. Without a-priori knowledge of any statistics of the underlying random processes, it is rigorously established that the proposed algorithm is able to yield a feasible and asymptotically optimal solution.

Complex phenomena involving pairwise interactions in natural and man-made settings can be well-represented by networks. Besides statistical and computational analyses on such networks, visualization plays a crucial role towards effectively conveying “at-a-glance” structural properties such as node hierarchy. However, most graph embedding algorithms developed for network visualization are ill-equipped to cope with the sheer volume of data generated by modern networks that encompass online social interactions, the Internet, or the world-wide web. Motivated by the emergence of nonlinear manifold learning approaches for dimensionality reduction, this paper puts forth a novel scheme for embedding graphs using kernel matrices defined on graphs. In particular, a kernelized version of local linear embedding is devised for computation of reconstruction weights. Unlike contemporary approaches, the developed embedding algorithm entails low-cost, parallelizable, and closed-form updates that can easily scale to big network data. Furthermore, it turns out that inclusion of embedding constraints to emphasize centrality structure can be accomplished at minimal extra computational cost. Experimental results on Watts-Strogatz small-world networks demonstrate the efficacy of the novel approach.

Albeit being in the big data era, a significant percentage of data accrued can be overlooked while maintaining reasonable quality of statistical inference at affordable complexity. By capitalizing on data redundancy, interval censoring is leveraged here to cope with the scarcity of resources needed for data exchanging, storing, and processing. By appropriately modifying least-squares regression, first- and second-order algorithms with complementary strengths that operate on censored data are developed for large-scale regressions. Theoretical analysis and simulated tests corroborate their efficacy relative to contemporary competing alternatives.

This work proposes a spectrum cartography algorithm used for learning the power spectrum distribution over a wide frequency band across a given geographic area. Motivated by low-complexity sensing hardware and stringent communication constraints, compressed and quantized measurements are considered. Setting out from a nonparametric regression framework, it is shown that a sensible approach leads to a support vector machine formulation. The simulated tests verify that accurate spectrum maps can be constructed using a simple sensing architecture with significant savings in the feedback.

Stochastic algorithms to allocate resources across different layers in an underlay multi-hop cognitive radio with primary and secondary users are presented. The algorithms aim to maximize the utility of the secondary users, while adhering to average interfering power constraints and accounting for the presence of imperfections in the state information. Interference among secondary users is modeled using a binary conflict graph, so that close-by secondary devices cannot transmit simultaneously. The optimal resource allocation dictates the power transmitted by each user, the rates at the transport, network and physical level, and the links to be activated. The design is casted as a nonlinear constrained optimization, and the solution is obtained using stochastic dual decomposition. Nu- merical experiments validate the theoretical claims.

A framework is introduced to integrate renewable energy sources (RES) and dynamic pricing capabilities of the smart grid into beamforming designs for coordinated multipoint (CoMP) downlink communication systems. To this end, novel models are put forth to account for harvesting, storage of nondispatchable RES, time-varying energy pricing, and stochastic wireless channels. Building on these models, robust energy management and transmit-beamforming designs are developed to minimize the worst-case energy cost subject to the worst-case user QoS guarantees for the CoMP downlink. Leveraging pertinent tools, this task is formulated as a convex problem. A Lagrange dual-based subgradient iteration is then employed to find the desired optimal energy-management strategy and transmit-beamforming vectors. Numerical results are provided to demonstrate the merits of the proposed robust designs.

Many real-world processes evolve in cascades over networks, whose topologies are often unobservable and change over time. However, the so-termed adoption times when for instance blogs mention popular news items are typically known, and are implicitly dependent on the underlying network. To infer the network topology, a dynamic structural equation model is adopted to capture the relationship between observed adoption times and the unknown edge weights, while accounting also for external (non-topological) perturbations. Assuming a slowly time-varying topology and leveraging the sparse connectivity inherent to social networks, edge weights are estimated by minimizing a sparsity-regularized exponentially-weighted least-squares criterion. To this end, a solver is developed by leveraging (pseudo) real-time sparsity-promoting proximal gradient iterations. Numerical tests with real cascades of online media demonstrate the effectiveness of the novel algorithm in unveiling sparse dynamically-evolving topologies.

This work examines a sparse dictionary learning task - that of fitting a collection of data points, arranged as columns of a matrix, to a union of low-dimensional linear subspaces - in settings where only highly quantized (single bit) observations of the data matrix entries are available. We analyze a complexity penalized maximum likelihood estimation strategy, and obtain finite-sample bounds for the average per-element squared approximation error of the estimate produced by our approach. Our results are reminiscent of traditional parametric estimation tasks - we show here that despite the highly-quantized observations, the normalized per-element estimation error is bounded by the ratio between the number of “degrees of freedom” of the matrix and its dimension.

Advanced data analytics are undoubtedly needed to enable the envisioned smart grid functionalities. Towards that goal, modern statistical learning tools are developed for day-ahead electricity market inference. Congestion patterns are modeled as rank-one components in the matrix of spatio-temporal prices. The new kernel-based predictor is regularized by the square root of the nuclear norm of the sought matrix. Such a regularizer not only promotes low-rank solutions, but it also facilitates a systematic kernel selection methodology. The non-convex optimization problem involved is efficiently driven to a stationary point following a block successive upper bound minimization approach. Numerical tests on real high-dimensional market data corroborate the interpretative merits and the computational efficiency of the novel method.

Power system state estimation (PSSE) constitutes a crucial prerequisite for reliable operation of the power grid. A key challenge for accurate PSSE is the inherent nonlinearity of SCADA measurements in the system states. Recent proposals for static PSSE tackle this issue by exploiting hidden convexity structure and solving a semidefinite programming (SDP) relaxation. In this work, an online PSSE algorithm based on SDP relaxation is proposed, which enjoys a similar convexity advantage, while capitalizing on past measurements as well for improved performance. An online convex optimization technique is adopted to derive an efficient algorithm with strong performance guarantees. Numerical tests verify the efficacy of the proposed approach.

Applications involving large-scale dictionary learning tasks motivate well online optimization algorithms for generally non-convex and non-smooth problems. In this big data context, the present paper develops an online learning framework by jointly leveraging the stochastic approximation paradigm with first-order acceleration schemes. The generally non-convex objective evaluated online at the resultant iterates enjoys quadratic rate of convergence. The generality of the novel approach is demonstrated in two online learning applications: (i) Online linear regression using the total least-squares approach; and, (ii) a semi-supervised dictionary learning approach to network-wide link load tracking and imputation of real data with missing entries. In both cases, numerical tests highlight the potential of the proposed online framework for big data network analytics.

A cross-layer resource allocation scheme for underlay multi-hop cognitive radio networks is formulated, in the presence of uncertain propagation gains and locations of primary users (PUs). Secondary network design variables are optimized under long-term probability-of-interference constraints, by exploiting channel statistics and maps that pinpoint areas where PU receivers are likely to reside. These maps are tracked using a Bayesian approach, based on 1-bit messages - here refereed to as "interference tweet" - broadcasted by the PU system whenever a communication disruption occurs due to interference. Although nonconvex, the problem has zero duality gap, and it is optimally solved using a Lagrangian dual approach. Numerical experiments demonstrate the ability of the proposed scheme to localize PU receivers, as well as the performance gains enabled by this minimal primary-secondary interplay.

Path delays in IP networks are important metrics, required by network operators for assessment, planning, and fault diagnosis. Monitoring delays of all source-destination pairs in a large network are, however, challenging and wasteful of resources. This paper advocates a spatio-temporal Kalman filtering approach to construct network-wide delay maps using measurements on only a few paths. The proposed network cartography framework allows efficient tracking and prediction of delays by relying on both topological as well as historical data. Optimal paths for delay measurement are selected in an online fashion by leveraging the notion of submodularity. The resulting predictor is optimal in the class of linear predictors, and outperforms competing alternatives on real-world data sets.

Spatio-temporal spectrum prediction algorithms for cognitive radios (CRs) are developed using the framework of dictionary learning and compressive sensing. The interference power levels at each CR node locations are predicted using the measurements from a subset of CR nodes without a priori knowledge on the primary transmitters. Batch and online alternatives are presented, where the online algorithm features low complexity and memory requirements. Numerical tests verify the performance of the proposed novel methods.

Visual rendering of graphs is a key task in the mapping of complex network data. Although most graph drawing algorithms emphasize aesthetic appeal, certain applications such as travel-time maps place more importance on visualization of structural network properties. The present paper advocates a graph embedding approach with centrality considerations to comply with node hierarchy. The problem is formulated as one of constrained multi-dimensional scaling (MDS), and it is solved via block coordinate descent iterations with successive approximations and guaranteed convergence to a KKT point. In addition, a regularization term enforcing graph smoothness is incorporated with the goal of reducing edge crossings. Experimental results demonstrate that the algorithm converges, and can be used to efficiently embed large graphs on the order of thousands of nodes.

A novel regularizer capturing the tensor rank is introduced in this paper as the key enabler for completion of three-way data arrays with missing entries. The novel regularized imputation approach induces sparsity in the factors of the tensor's PARAFAC decomposition, thus reducing its rank. The focus is on count processes which emerge in diverse applications ranging from genomics to computer and social networking. Based on Poisson count data, a maximum aposteriori (MAP) estimator is developed using the Kullback-Leibler divergence criterion. This probabilistic approach also facilitates incorporation of correlated priors regularizing the rank, while endowing the tensor imputation method with extra smoothing and prediction capabilities. Tests on simulated and real datasets corroborate the sparsifying regularization effect, and demonstrate recovery of 15% missing RNA-sequencing data with an inference error of -12dB.

Accurate estimation of origin-to-destination (OD) traffic flows provides valuable input for network management tasks. However, lack of flow-level observations as well as intentional and unintentional anomalies pose major challenges toward achieving this goal. Leveraging the low intrinsic-dimensionality of OD flows and the sparse nature of anomalies, this paper proposes a convex program with nuclear-norm and ℓ1-norm regularization terms to estimate the nominal and anomalous traffic components, using a small subset of (possibly anomalous) flow counts in addition to link counts. Analysis and simulations confirm that the said estimator can exactly recover sufficiently low-dimensional nominal traffic and sparse enough anomalies when the routing matrix is column-incoherent, and an adequate amount of flow counts are randomly sampled. The results offer valuable insights about the measurement types and network scenaria giving rise to accurate traffic estimation. Tests with real Internet data corroborate the effectiveness of the novel estimator.

Extracting latent low-dimensional structure from high-dimensional data is of paramount importance in timely inference tasks encountered with `Big Data' analytics. However, increasingly noisy, heterogeneous, and incomplete datasets as well as the need for real-time processing pose major challenges towards achieving this goal. In this context, the fresh look advocated here permeates benefits from rank minimization to track low-dimensional subspaces from incomplete data. Leveraging the low-dimensionality of the subspace sought, a novel estimator is proposed based on an exponentially-weighted least-squares criterion regularized with the nuclear norm. After recasting the non-separable nuclear norm into a form amenable to online optimization, a real-time algorithm is developed and its convergence established under simplifying technical assumptions. The novel subspace tracker can asymptotically offer the well-documented performance guarantees of the batch nuclear-norm regularized estimator. Simulated tests with real Internet data confirm the efficacy of the proposed algorithm in tracking the traffic subspace, and its superior performance relative to state-of-the-art alternatives.

Conventional spectrum sensing schemes can detect active transmitters but not passive receivers, which have to be nevertheless protected from excessive interference whenever their bands are reused. In this paper, a resource allocation scheme for underlay cognitive radios is formulated, taking into account uncertainty of both propagation gains and locations of incumbent receivers. The performance of orthogonal access by secondary users is maximized under average interference constraints, using channel statistics and maps that pin-point areas where primary receivers are likely to reside. These maps are tracked using a Bayesian approach, based on a 1-bit message sent by the primary system whenever a communication disruption occurs due to interference.

The present paper introduces a novel online asset allocation strategy which accounts for the sensitivity of Markowitz-inspired portfolios to low-quality estimates of the mean and the correlation matrix of stock returns. The proposed methodology builds upon the total least-squares (TLS) criterion regularized with sparsity attributes, and the ability to incorporate additional convex constraints on the portfolio vector. To solve such an optimization task, the present paper draws from the rich family of splitting algorithms to construct a novel online splitting algorithm with computational complexity that scales linearly with the number of unknowns. Real-world financial data are utilized to demonstrate the potential of the proposed technique.

Integrating genetic perturbations with gene expression data not only improves accuracy of regulatory network topology inference, but also enables learning of causal regulatory relations between genes. Although a number of methods have been developed to integrate both types of data, the desiderata of efficient and powerful algorithms still remains. In this paper, sparse structural equation models (SEMs) are employed to integrate both gene expression data and cis-expression quantitative trait loci (cis-eQTL), for modeling gene regulatory networks in accordance with biological evidence about genes regulating or being regulated by a small number of genes. A systematic inference method named sparsity-aware maximum likelihood (SML) is developed for SEM estimation. Using simulated directed acyclic or cyclic networks, the SML performance is compared with that of two state-of-the-art algorithms: the adaptive Lasso (AL) based scheme, and the QTL-directed dependency graph (QDG) method. Computer simulations demonstrate that the novel SML algorithm offers significantly better performance than the AL-based and QDG algorithms across all sample sizes from 100 to 1,000, in terms of detection power and false discovery rate, in all the cases tested that include acyclic or cyclic networks of 10, 30 and 300 genes. The SML method is further applied to infer a network of 39 human genes that are related to the immune function and are chosen to have a reliable eQTL per gene. The resulting network consists of 9 genes and 13 edges. Most of the edges represent interactions reasonably expected from experimental evidence, while the remaining may just indicate the emergence of new interactions. The sparse SEM and efficient SML algorithm provide an effective means of exploiting both gene expression and perturbation data to infer gene regulatory networks. An open-source computer program implementing the SML algorithm is freely available upon request.

Given the noiseless superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, the goal of this paper is to establish deterministic conditions under which exact recovery of the low-rank and sparse components becomes possible. This fundamental identifiability issue arises with traffic anomaly detection in backbone networks, and subsumes compressed sensing as well as the timely low-rank plus sparse matrix recovery tasks encountered in matrix decomposition problems. Leveraging the ability of l1and nuclear norms to recover sparse and low-rank matrices, a convex program is formulated to estimate the unknowns. Analysis and simulations confirm that the said convex program can recover the unknowns for sufficiently low-rank and sparse enough components, along with a compression matrix possessing an isometry property when restricted to operate on sparse vectors. When the low-rank, sparse, and compression matrices are drawn from certain random ensembles, it is established that exact recovery is possible with high probability. First-order algorithms are developed to solve the nonsmooth convex optimization problem with provable iteration complexity guarantees. Insightful tests with synthetic and real network data corroborate the effectiveness of the novel approach in unveiling traffic anomalies across flows and time, and its ability to outperform existing alternatives.

A resource allocation problem for a cognitive radio base station (CR-BS) communicating with multiple CR mobile stations (MSs) is considered in the downlink, which relies on orthogonal frequency-division multiple access (OFDMA). To protect the incumbent primary user (PU) system operating over the same frequency band, the interference inflicted to the PU receiver must be regulated. Since the channel gain estimates from the CR-BS to the PU receiver are typically uncertain in practice, a robust interference power constraint is advocated. Although the latter translates to a second-order cone constraint, the overall optimization problem for joint transmit-power and subcarrier allocation is non-convex, and coupled over all subcarriers in general. To circumvent the resulting computational hurdle, a tight polyhedral approximation of the second-order cone is employed. Practical finite-alphabet constellations are adopted and total weighted achievable rate is maximized. It is shown that a near-optimal solution can be obtained based on the Lagrangian dual.

A resource allocation task for the uplink of OFDMA-based cognitive radio (CR) systems is considered. The weighted sum-rate is maximized over subcarrier assignment as well as over power loading per CR user, while protecting primary user (PU) systems. However, due to the lack of explicit support from PU systems, the channels from CR users to the PU may not be accurately acquired. Thus, the PU interference constraint is posed as a chance constraint, for which conservative convex approximation is employed for tractability. In particular, to mitigate the combinatorial complexity incurred for optimal subcarrier assignment, a separable structure is pursued, and the dual decomposition method is adopted to obtain near-optimal solutions. Numerical tests verify that the proposed algorithms yield higher weighted sum-rate at lower computational complexity than a benchmark algorithm.

Recent advances in metering technology, deregulation of the energy market, rapid penetration of renewables, and the smart grid vision for situational awareness, all call for a system-wide power system state estimation (PSSE). On the other hand, complexity of an interconnected power grid, privacy policies of local authorities, and vulnerability concerns preclude a centralized estimator. In this context, several possible manifestations of PSSE are treated in the present paper under a unified and systematic framework. Building on the alternating direction method of multipliers, a novel decentralized PSSE approach is developed. The obtained algorithm waives local observability concerns, leverages existing software, while requiring local system operators exchange minimal information only across tie lines. Numerical tests on two commonly used benchmarks, namely IEEE 14- and 118-bus power grids, show that the desired statistical accuracy is attained within 5-10 inter-area exchanges.

Standard sparse decomposition (with applications in many different areas including compressive sampling) amounts to finding the minimum ℓ0-norm solution of an underdetermined system of linear equations. In this decomposition, all atoms are treated `uniformly' for being included or not in the decomposition. However, one may wish to weigh more or less certain atoms, or, assign higher costs to some other atoms to be included in the decomposition. This can happen for example when there is prior information available on each atom. This motivates generalizing the notion of minimal ℓ0-norm solution to that of minimal weighted ℓ0-norm solution. On the other hand, relaxing weighted ℓ0-norm via the weighted ℓ1-norm is challenging. This paper deals with minimal weighted ℓ0-norm solutions of underdetermined linear systems, provides conditions for their uniqueness, and develops an algorithm for their estimation.

A distributed belief propagation protocol is developed to carry inference and decoding tasks using wireless sensor networks with high-dimensional, correlated observations. Statistical dependencies are modeled using factor graphs. The overall a-posteriori probability is factored so that its factor graph representation can be mapped to the actual communication network. Sum-product message passing updates over the graphical model can thus be mapped to messages among sensors. As an application scenario, distributed spectrum sensing is considered. Simulated tests show that exploiting the correlation present among sensor observations can considerably improve sensing performance.

A novel approach to multi-hop routing for cognitive random access is developed under channel gain uncertainty constraints. Motivated by the inherent randomness of the propagation medium, the novel routing strategy leverages pairwise decoding probabilities to randomly route packets to neighboring nodes. The resultant cross-layer optimization framework not only provides optimal routes in a well-defined sense, but also yields transmission probabilities and transmit-powers, thus enabling cognizant adaptation of networking, medium access, and physical layer parameters to the operational environment. The relevant optimization problem is non-convex and hence hard to solve in general. Nevertheless, a successive convex approximation approach is employed to efficiently find a Karush-Kuhn-Tucker solution. Enticingly, the fresh look advocated here permeates benefits also to conventional multi-hop random access networks in the presence of channel uncertainty.

This paper deals with the resource allocation task for the uplink of OFDMA-based cognitive radio (CR) systems. A weighted sum-rate maximization problem is formulated to optimize the subcarrier assignment as well as the power loading per CR user, while protecting the primary user (PU) systems. Since the CR-to-PU channels may not be accurately acquired, the PU interference constraint is cast as a chance constraint. Consequently, a convex conservative approximation of the chance constraint is employed for tractability reasons. In particular, to mitigate the combinatorial complexity incurred for optimal subcarrier assignment, a separable structure is pursued, and the dual decomposition method is employed to obtain a near-optimal solver. The resultant algorithm is tested via simulated tests.

Beamforming for multi-input multi-output (MIMO) cognitive networks is considered in the presence of channel uncertainty induced by errors in estimating cognitive-to-primary channels. A robust beamforming problem is formulated to optimize an appropriate cognitive radio network-wide performance metric, while enforcing protection of the primary system. In spite of the non-convexity of the resultant optimization problem, a block coordinate ascent algorithm is developed with provable convergence to a stationary point. Enticingly, the novel scheme also lends itself naturally to a distributed implementation. Numerical results are reported to corroborate the analytical findings.

To account for the randomness of propagation channels and interference levels in hierarchical spectrum sharing, a novel approach to multihop routing is introduced for cognitive random access networks, whereby packets are randomly routed according to outage probabilities. Leveraging channel and interference level statistics, the resultant cross-layer optimization framework provides optimal routes, transmission probabilities, and transmit-powers, thus enabling cognizant adaptation of routing, medium access, and physical layer parameters to the propagation environment. The associated optimization problem is non-convex, and hence hard to solve in general. Nevertheless, a successive convex approximation approach is adopted to efficiently find a Karush-Kuhn-Tucker solution. Augmented Lagrangian and primal decomposition methods are employed to develop a distributed algorithm, which also lends itself to online implementation. Enticingly, the fresh look advocated here permeates benefits also to conventional multihop wireless networks in the presence of channel uncertainty.

Efficient design of cognitive radios (CRs) calls for secondary users implementing adaptive resource allocation schemes that exploit knowledge of the channel state information (CSI), while at the same time limiting interference to the primary system. This paper introduces stochastic resource allocation algorithms for both interweave (also known as overlay) and underlay cognitive radio paradigms. The algorithms are designed to maximize the weighted sum-rate of orthogonally transmitting secondary users under average-power and probabilistic interference constraints. The latter are formulated either as short- or as long-term constraints, and guarantee that the probability of secondary transmissions interfering with primary receivers stays below a certain pre-specified level. When the resultant optimization problem is non-convex, it exhibits zero-duality gap and thus, due to a favorable structure in the dual domain, it can be solved efficiently. The optimal schemes leverage CSI of the primary and secondary networks, as well as the Lagrange multipliers associated with the constraints. Analysis and simulated tests confirm the merits of the novel algorithms in: i) accommodating time-varying settings through stochastic approximation iterations; and ii) coping with imperfect CSI.

A network-compressive transmission protocol is developed in which correlated sensor observations belonging to a finite alphabet are linearly combined as they traverse the network on their way to a sink node. Statistical dependencies are modeled using factor graphs. The sum-product algorithm is run under different modeling assumptions to estimate the maximum a posteriori set of observations given the compressed measurements at the sink node. Error exponents are derived for cyclic and acyclic factor graphs using the method of types, showing that observations can be recovered with arbitrarily low probability of error as the network size grows. Simulated tests corroborate the theoretical claims.

Graphical models are useful for capturing interdependencies of statistical variables in various fields. Estimating parameters describing sparse graphical models of stationary multivariate data is a major task in areas as diverse as biostatistics, econometrics, social networks, and climate data analysis. Even though time series in these applications are often non stationary, revealing interdependencies through sparse graphs has not advanced as rapidly, because estimating such time varying models is challenged by the curse of dimensionality and the associated complexity which is prohibitive. The goal of this paper is to introduce novel algorithms for joint segmentation and estimation of sparse, piecewise stationary, graphical models. The crux of the proposed approach is application of dynamic programming in conjunction with cost functions regularized with terms promoting the right form of sparsity in the right application domain. As a result, complexity of the novel schemes scales gracefully with the problem dimension.

A nonparametric version of the basis pursuit method is developed for field estimation. The underlying model entails known bases, weighted by generic functions to be estimated from the field's noisy samples. A novel field estimator is developed based on a regularized variational least-squares (LS) criterion that yields estimates spanned by thin-plate splines. Robustness considerations motivate well the adoption of an overcomplete set of basis functions, together with a sparsity-promoting regularization term, which endows the estimator with the ability to select a few of these bases that "better" explain the data. This parsimonious field representation becomes possible because the sparsity-aware spline-based method of this paper induces a group-Lasso estimator of the thin-plate spline basis expansion coefficients. The novel spline-based approach to basis pursuit is motivated by a spectrum cartography application, in which a set of sensing cognitive radios collaborate to estimate the distribution of RF power in space and frequency. Simulated tests corroborate that the estimated power spectrum density atlas yields the desired RF state awareness, since the maps reveal spatial locations where idle frequency bands can be reused for transmission, even when fading and shadowing effects are pronounced.

Clustering is a basic task in a variety of machine learning applications. Partitioning a set of input vectors into compact, well separated subsets can be severely affected by the presence of model incompatible inputs called outliers. The present paper develops robust clustering algorithms for jointly partitioning the data and identifying the outliers. The novel approach relies on translating scarcity of outliers to sparsity in a judiciously defined domain, to robustify three widely used clustering schemes: hard K-means, fuzzy K-means, and probabilistic clustering. Cluster centers and assignments are iteratively updated in closed form. The developed outlier aware algorithms are guaranteed to converge, while their computational complexity is of the same order as their outlier-agnostic counterparts. Preliminary simulations validate the analytical claims.

The recent upsurge of research toward compressive sampling and parsimonious signal representations hinges on signals being sparse, either naturally, or, after projecting them on a proper basis. The present paper introduces a neat link between sparsity and a fundamental aspect of statistical inference, namely that of robustness against outliers, even when the signals involved are not sparse. It is argued that controlling sparsity of model residuals leads to statistical learning algorithms that are computationally affordable and universally robust to outlier models. Analysis, comparisons, and corroborating simulations focus on robustifying linear regression, but succinct overview of other areas is provided to highlight universality of the novel framework.

A weighted sum-rate maximization problem is considered for an access point (AP) allocating resources to wireless cognitive radios (CRs) communicating using orthogonal frequency-division multiple access (OFDMA). To protect the incumbent primary user (PU) system operating over the same frequency band, the interference inflicted to the PU receiver must be regulated. Since the channel gain estimates from the AP to the PU receiver may well be inaccurate in practice, a probabilistic interference power constraint is adopted. Although the latter translates to a second-order cone constraint, the overall optimization problem for joint transmit-power and subcarrier allocation is non-convex, and coupled over all subcarriers in general. To circumvent this hurdle, a tight polyhedral approximation of the second-order cone is employed. A near-optimal solution can then be efficiently obtained using the dual method.

Efficient design of cognitive radio networks calls for secondary users implementing adaptive resource allocation, which requires knowledge of the channel state information in order to limit interference inflicted to primary users. In this context, the present paper develops stochastic resource allocation algorithms maximizing the sum-rate of secondary users while adhering to "average power" and "probability of interference" constraints. These constraints guarantee that the probability of the secondary network interfering with the primary one stays below a pre-specified level. The optimal schemes turn out to be a function of the quality of the secondary network links, the activity of the primary users, and the associated Lagrange multipliers. The focus is on algorithms that: i) use stochastic approximation tools to estimate the multipliers; and ii) are able to cope with imperfections in the information of the primary network state.

Nonparametric methods are widely applicable to statistical learning problems, since they rely on a few modeling assumptions. In this context, the fresh look advocated here permeates benefits from variable selection and compressive sampling, to robustify nonparametric regression against outliers. A variational counterpart to least-trimmed squares regression is shown closely related to an ℓ0-(pseudo)norm-regularized estimator, that encourages sparsity in a vector explicitly modeling the outliers. This connection suggests efficient (approximate) solvers based on convex relaxation, which lead naturally to a variational M-type estimator equivalent to Lasso. Outliers are identified by judiciously tuning regularization parameters, which amounts to controlling the sparsity of the outlier vector along the whole robustification path of Lasso solutions. An improved estimator with reduced bias is obtained after replacing the ℓ0-(pseudo)norm with a nonconvex surrogate, as corroborated via simulated tests on robust thin-plate smoothing splines.

Sparsity in the eigenspace of signal covariance matrices is exploited in this paper for compression and denoising. Dimensionality reduction (DR) and quantization modules present in many practical compression schemes such as transform codecs, are redesigned to utilize such forms of sparsity and achieve improved reconstruction performance compared to existing alternatives. Relying on training data that may be noisy a novel sparsity-cognizant linear DR scheme is developed to exploit covariance-domain sparsity and form noise resilient estimates of the principal covariance eigen-basis. Norm-one regularization is used to effect sparsity, while the corresponding minimization problems are solved efficiently via coordinate decent. If data are noisy the sparsity-aware eigenspace estimator can recover a subset of the unknown signal subspace basis support when the noise power is sufficiently low. In the noiseless case the novel estimator is asymptotically normal, and the probability to identify the principal eigenspace support asymptotically approaches one.

Solving linear regression problems based on the total least-squares (TLS) criterion has well-documented merits in various applications, where perturbations appear both in the data vector as well as in the regression matrix. Weighted and structured generalizations of the TLS approach are further motivated in several signal processing and system identification related problems. On the other hand, modern compressive sampling and variable selection algorithms account for perturbations of the data vector, but not those affecting the regression matrix. The present paper addresses also the latter by introducing a weighted and structured sparse (S-) TLS formulation to exploit a priori knowledge on both types of perturbations, and on the sparsity of the unknown vector. The resultant novel approach is further able to cope with sparse, under-determined errors-in-variables models with structured and correlated perturbations, while allowing for efficient sub-optimum solvers. Simulated tests demonstrate the approach, and especially its ability to reliably recover the support of unknown sparse vectors.

Cognitive radio (CR) networks can re-use the RF spectrum licensed to the primary user (PU) network by carefully controlling the interference to the PUs. However, due to lack of explicit support from the PU system, CR sensing algorithms often face difficulty in acquiring CR-to-PU channels accurately. Moreover, the sensing algorithms cannot detect silent PU receivers, which nevertheless have to be protected. In order to achieve aggressive spectrum re-use even in such challenging scenarios, a CR power control problem with probabilistic interference constraints is formulated. Both log-normal shadowing and small-scale fading uncertainties are taken into account through suitable approximations. In particular, a weighted sum-rate maximization problem is considered, whose Karush-Kuhn-Tucker points are obtained via sequential geometric programming. Numerical tests verify the performance of our novel approach.

Joint optimization of network coding and Aloha-based medium access control (MAC) for multi-hop wireless networks is considered. The multicast throughput with a power consumption-related penalty is maximized subject to flow conservation and MAC achievable rate constraints to obtain the optimal transmission probabilities. The relevant optimization problem is inherently non-convex and hence difficult to solve even in a centralized manner. A successive convex approximation technique is employed to obtain a Karush-Kuhn-Tucker solution. A separable problem structure is obtained and the dual decomposition technique is adopted to develop a distributed solution. The algorithm is thus applicable to large networks, and amenable to online implementation. Numerical tests verify performance and complexity advantages of the proposed approach over existing designs. A network simulation with implementation of random linear network coding shows performance very close to the one theoretically designed.

The number of active users in code-division multiple access (CDMA) systems is often much lower than the spreading gain. The present paper exploits fruitfully this a priori information to improve performance of multiuser detectors. A low-activity factor manifests itself in a sparse symbol vector with entries drawn from a finite alphabet that is augmented by the zero symbol to capture user inactivity. The non-equiprobable symbols of the augmented alphabet motivate a sparsity-exploiting maximum a posteriori probability (S-MAP) criterion, which is shown to yield a cost comprising the ℓ2least-squares error penalized by the p-th norm of the wanted symbol vector (p = 0, 1, 2). Related optimization problems appear in variable selection (shrinkage) schemes developed for linear regression, as well as in the emerging field of compressive sampling (CS). The contribution of this work to such sparse CDMA systems is a gamut of sparsity-exploiting multiuser detectors trading off performance for complexity requirements. From the vantage point of CS and the least-absolute shrinkage selection operator (Lasso) spectrum of applications, the contribution amounts to sparsity-exploiting algorithms when the entries of the wanted signal vector adhere to finite-alphabet constraints.

Maximization of the weighted sum-rate of secondary users (SUs) possibly equipped with multiantenna transmitters and receivers is considered in the context of cognitive radio (CR) networks with coexisting primary users (PUs). The total interference power received at the primary receiver is constrained to maintain reliable communication for the PU. An interference channel configuration is considered for ad hoc networking, where the receivers treat the interference from undesired transmitters as noise. Without the CR constraint, a convergent distributed algorithm is developed to obtain (at least) a locally optimal solution. With the CR constraint, a semidistributed algorithm is introduced. An alternative centralized algorithm based on geometric programming and network duality is also developed. Numerical results show the efficacy of the proposed algorithms. The novel approach is flexible to accommodate modifications aiming at interference alignment. However, the stand-alone weighted sum-rate optimal schemes proposed here have merits over interference-alignment alternatives especially for practical SNR values.

Resource allocation issues are investigated in this paper for multiuser wireless transmissions based on orthogonal frequency division multiplexing (OFDM). Relying on convex and stochastic optimization tools, the novel approach to resource allocation includes: i) development of jointly optimal subcarrier, power, and rate allocation for weighted sum-average-rate maximization; ii) judicious formulation and derivation of the optimal resource allocation for maximizing the utility of average user rates; and iii) development of the stochastic resource allocation schemes, and rigorous proof of their convergence and optimality. Simulations are also provided to demonstrate the merits of the novel schemes.

A cross-layer design along with an optimal resource allocation framework is formulated for wireless fading networks, where the nodes are allowed to perform network coding. The aim is to jointly optimize end-to-end transport-layer rates, network code design variables, broadcast link flows, link capacities, average power consumption, and short-term power allocation policies. As in the routing paradigm where nodes simply forward packets, the cross-layer optimization problem with network coding is nonconvex in general. It is proved, however, that with network coding, dual decomposition for multicast is optimal so long as the fading at each wireless link is a continuous random variable. This lends itself to provably convergent subgradient algorithms, which not only admit a layered-architecture interpretation, but also optimally integrate network coding in the protocol stack. The dual algorithm is also paired with a scheme that yields near-optimal network design variables, namely multicast end-to-end rates, network code design quantities, flows over the broadcast links, link capacities, and average power consumption. Finally, an asynchronous subgradient method is developed, whereby the dual updates at the physical layer can be affordably performed with a certain delay with respect to the resource allocation tasks in upper layers. This attractive feature is motivated by the complexity of the physical-layer subproblem and is an adaptation of the subgradient method suitable for network control.

Cognitive radio (CR) networks can re-use the RF spectrum licensed to a primary user (PU) network, provided that the interference inflicted to the PUs is carefully controlled. However, due to lack of explicit cooperation between CR and PU systems, it is often difficult for CRs to acquire CR-to-PU channels accurately. In fact, if the PU receivers are off, the sensing algorithms cannot obtain the channels for the PU receivers, although they have to be protected nevertheless. In order to achieve aggressive spectrum re-use even in such challenging scenarios, power control algorithms that take channel uncertainty into account are developed. Both log-normal shadowing and small-scale fading effects are considered through suitable approximations. Accounting for the latter, centralized network utility maximization (NUM) problems are formulated, and their Karush-Kuhn-Tucker points are obtained via sequential geometric programming. For the case where CR-to-CR channels are also uncertain, a novel outage probability-based NUM formulation is proposed, and its solution method developed in a unified fashion. Numerical tests verify the performance merits of the novel design.

Cognitive radios (CRs) are capable of sensing the RF spectrum to identify idle bands dynamically, and transmit opportunistically so as not to interfere with cohabiting primary users (PUs) over the same bands. In this work, spectrum sensing algorithms for CRs that support quality-of-service (QoS) traffic are investigated. Multiple bands are sensed in parallel to reduce the sensing delay, while ensuring a fixed minimum rate for CR transmissions with a given outage probability. Interference constraints are also imposed to protect PU transmissions. Both fixed sample size (FSS) as well as sequential sensing algorithms are developed to minimize the sensing delay. In the sequential sensing case, a bank of sequential probability ratio tests (SPRTs) are run in parallel to detect PU presence in all bands concurrently. Notably, the parameters for the detectors can be obtained via convex optimization. Numerical tests demonstrate that sequential sensing yields average sensing delays significantly smaller than those of FSS sensing.

Physical-layer network coding over wireless networks can provide considerable throughput gains with respect to traditional cooperative relaying strategies at no loss of diversity gain. In this paper, a novel cooperation protocol is developed based on complex-field wireless network coding. Sources transmit efficiently information symbols linearly combined with symbols from other sources. Different from existing wireless network coding protocols, transmissions are not restricted to binary symbols, and do not have to be received simultaneously. In a network with N sources, the developed protocol can achieve throughput up to approximately 1/N symbols per source per channel use, as well as diversity of order N. To deal with decoding errors at sources, selective- and adaptive-forwarding protocols are also developed at no loss of diversity gain. Analytical results corroborated by simulated tests show considerable performance gains with respect to distributed space-time coding, and bit-level network coding protocols.

Spectrum sensing algorithms are developed for cognitive radios to support real-time traffic. Multiple bands are sensed in parallel to reduce sensing delay, while meeting a minimum rate requirement with a prescribed outage probability. Interference constraints are also imposed to protect primary user (PU) transmissions. Both fixed sample size (FSS) and sequential sensing algorithms are developed. In the FSS sensing, a series of convex feasibility problems are solved to minimize sensing delay. In the sequential case, a bank of sequential probability ratio tests (SPRTs) is employed to detect PU presence, where the detector parameters are optimized via convex optimization. Numerical tests demonstrate that the (average) sensing delay of sequential sensing is considerably smaller than that of FSS sensing.

Although time-domain oversampling of the received baseband signal is common for single-carrier transmissions, the counterpart of frequency-domain oversampling is rarely used for multicarrier transmissions. In this paper, we explore frequency-domain oversampling to improve the system performance of zero-padded OFDM transmissions over underwater acoustic channels with large Doppler spread. We use a signal design that enables separate sparse channel estimation and data detection, rendering a low complexity receiver. Based on both simulation and experimental results, we observe that the receiver with frequency-domain oversampling outperforms the conventional one considerably in channels with moderate and large Doppler spreads, and the gain increases as the Doppler spread increases. Although a raised-cosine pulse-shaping window can be used to improve the system performance relative to a rectangular window at the expense of data rate reduction, the performance gain is much less than that brought by frequency-domain oversampling in the considered OFDM system for Doppler spread channels.

Frequency hopping (FH) signals have well-documented merits for commercial and military applications due to their near-far resistance and robustness to jamming. Estimating FH signal parameters (e.g., hopping instants, carriers, and amplitudes) is an important and challenging problem, but optimum estimation incurs an unrealistic computational burden. The spectrogram has long been the nonparametric estimation workhorse in this context, followed by line spectra refinement. The problem is that hop timing estimates derived from the spectrogram are coarse and unreliable, thus severely limiting performance. In this paper we take a fresh look at this problem, based on sparse linear regression (SLR). At any point in time, there are only few active carriers; and carrier hopping is rare for slow FH. Using a dense frequency grid, we formulate the problem as under-determined linear regression with a dual sparsity penalty, and develop an exact solution using the alternating direction method of multipliers (ADMoM). Simulations demonstrate that the developed technique outperforms spectrogram-based methods, especially with regards to hop timing estimation, which is the crux of the problem.

The least-absolute shrinkage and selection operator (Lasso) is a popular tool for joint estimation and continuous variable selection, especially well-suited for the under-determined but sparse linear regression problems. This paper develops an algorithm to estimate the regression coefficients via Lasso when the training data is distributed across different agents, and their communication to a central processing unit is prohibited for e.g., communication cost or privacy reasons. The novel distributed algorithm is obtained after reformulating the Lasso into a separable form, which is iteratively minimized using the alternating-direction method of multipliers so as to gain the desired degree of parallelization. The per agent estimate updates are given by simple soft-thresholding operations, and inter-agent communication overhead remains at affordable level. Without exchanging elements from the different training sets, the local estimates provably consent to the global Lasso solution, i.e., the fit that would be obtained if the entire data set were centrally available. Numerical experiments corroborate the convergence and global optimality of the proposed distributed scheme.

A distributed set-membership-constrained particle filter (SMCPF) is developed for decentralized tracking applications using wireless sensor networks. Unlike existing PF alternatives, SMC-PF offers reduced overhead for inter-sensor communications because it requires only particle weights to be exchanged among sensors, instead of raw measurements or parameters of a Gaussian mixture model. SMC-PF relies on a novel distributed adaptation scheme based on successive set intersections that can afford reduced number of particles without sacrificing performance. Conditions are provided to quantify the variance reduction of the SMC-PF-based state estimator. Simulations corroborate the ability of the SMCPF to considerably outperform the bootstrap PF for a fixed number of particles.

This paper deals with clustering of spatially distributed data using wireless sensor networks. A distributed low-complexity clustering algorithm is developed that requires one-hop communications among neighboring nodes only, without local data exchanges. The algorithm alternates iterations over the variables of a consensus-based version of the global clustering problem. Using stability theory for time-varying and time-invariant systems, the distributed clustering algorithm is shown to be bounded-input bounded-output stable with an output arbitrarily close to a fixed point of the algorithm. For distributed hard K-means clustering, convergence to a local minimum of the centralized problem is guaranteed. Numerical examples confirm the merits of the algorithm and its stability analysis.

A sequential cooperative spectrum sensing algorithm is developed for multi-channel cognitive radio (CR) systems. Each CR quantizes the local observations to a single-bit datum per sample per channel, and relays the data sequentially to the fusion center for joint decision. The optimal trade-off between the sensing time and the sensing reliability is sought with the objective of maximizing the overall throughput of the CR system under prescribed “collision” probability constraints. A constrained dynamic programming formulation is developed and a reduced-complexity approximate solution is derived. Numerical tests verify the efficacy of cooperation and sequential processing for spectrum sensing.

Efficient design of wireless networks requires implementation of cross-layer algorithms that exploit channel state information. Capitalizing on convex optimization and stochastic approximation tools, this paper develops a stochastic algorithm that allocates resources at network, link, and physical layers so that a sum-utility of the average end-to-end rates is maximized. Focus is placed on networks where interference is strong and nodes transmit orthogonally over a set of parallel channels. Convergence of the developed stochastic schemes is characterized, and the average queue delays are obtained in closed form.

Co-clustering can be viewed as a two-way (bilinear) factorization of a large data matrix into dense/uniform and possibly overlapping sub-matrix factors (co-clusters). This combinatorially complex problem emerges in several applications, including behavior inference tasks encountered with social networks. Existing co-clustering schemes do not exploit the fact that overlapping factors are often sparse, meaning that their dimension is considerably smaller than that of the data matrix. Based on plaid models which allow for overlapping submatrices, the present paper develops a sparsity-cognizant overlapping co-clustering (SOC) approach. Numerical tests demonstrate the ability of the novel SOC scheme to globally detect multiple overlapping co-clusters, outperforming the original plaid model algorithms which rely on greedy search and ignore sparsity.

This paper develops algorithms to train linear support vector machines (SVMs) when training data are distributed across different nodes and their communication to a centralized node is prohibited due to, for example, communication overhead or privacy reasons. To accomplish this goal, the centralized linear SVM problem is cast as the solution of coupled decentralized convex optimization subproblems with consensus constraints on the parameters defining the classifier. Using the method of multipliers, distributed training algorithms are derived that do not exchange elements from the training set among nodes. The communications overhead of the novel approach is fixed and fully determined by the topology of the network instead of being determined by the size of the training sets as it is the case for existing incremental approaches. An online algorithm where data arrive sequentially to the nodes is also developed. Simulated tests illustrate the performance of the algorithms.

Reproducing a sampled sound field using an array of loudspeakers is a problem with well-appreciated applications to acoustics and ultrasound treatment. Loudspeaker signal design has traditionally relied on (possibly regularized) least-squares (LS) criteria. In many cases however, the desired sound field can be reproduced using only a few loudspeakers, which are sparsely distributed in space. To exploit this feature, the fresh look advocated here permeates benefits from advances in variable selection and compressive sampling to sound field synthesis by formulating a sparse linear regression problem that is solved using the least-absolute shrinkage and selection operator (Lasso). An efficient implementation of the Lasso for the problem at hand is developed based on a coordinate descent iteration. Analysis and simulations demonstrate that Lasso-based sound field reproduction yields better performance than LS especially at high frequencies and for reproduction of under-sampled sound fields. In addition, Lasso-based synthesis enables judicious placement of loudspeaker arrays.

Dynamic spectrum access (DSA) is an integral part of cognitive radio technology aiming at efficient management of the available power and bandwidth resources. The present paper deals with cooperative DSA networks, where collaborating terminals adhere to diverse (maximum and minimum) quality-of-service (QoS) constraints in order to not only effect hierarchies between primary and secondary users but also prevent abusive utilization of the available spectrum. Peer-to-peer networks with co-channel interference are considered in both single- and multi-channel settings. Utilities that are functions of the signal-to-interference-plus-noise ratio (SINR) are employed as QoS metrics. By adjusting their transmit power, users can mitigate the generated interference and also meet the QoS requirements. A novel formulation accounting for heterogeneous QoS requirements is obtained after introducing a suitable relaxation and recasting a constrained sum-utility maximization as a convex optimization problem. The optimality of the relaxation is established under general conditions. Based on this relaxation, an algorithm for optimal power control that is amenable to distributed implementation is developed, and its convergence is established. Numerical tests verify the analytical claims and demonstrate performance gains relative to existing schemes.

A general wireless networking problem is formulated whereby end-to-end user rates, routes, link capacities, transmit-power, frequency, and power resources are jointly optimized across fading states. Even though the resultant optimization problem is generally nonconvex, it is proved that the gap with its Lagrange dual problem is zero, so long as the underlying fading distribution function is continuous. The major implication is that separating the design of wireless networks in layers and per-fading state subproblems can be optimal. Subgradient descent algorithms are further developed to effect an optimal separation in layers and layer interfaces.

Optimal and reduced-complexity near-optimal algorithms are developed for the design of wireless networks in the presence of fading. The physical layer is interference-limited, whereby network terminals treat interference as noise. Optimal wireless network design amounts to joint optimization of application-level rates, routes, link capacities, power consumption, and power allocation across frequency tones, neighboring terminals, and fading states. The present contribution shows how recent results establishing the optimality of layered architectures can be realized in practice by developing physical layer resource allocation algorithms that are seamlessly integrated into layered architectures without loss of optimality. Specifically, the provably convergent algorithms yield (near-)optimal end-to-end rates, multicommodity flows, link capacities, and average powers. These design variables are obtained offline, and are subsequently used for control during network operation.

This paper deals with distributed demodulation of space-time transmissions of a common message from a multi-antenna access point (AP) to a wireless sensor network. Based on local message exchanges with single-hop neighboring sensors, two algorithms are developed for distributed demodulation. In the first algorithm, sensors consent on the estimated symbols. By relaxing the finite-alphabet constraints on the symbols, the demodulation task is formulated as a distributed convex optimization problem that is solved iteratively using the method of multipliers. Distributed versions of the centralized zero-forcing (ZF) and minimum mean-square error (MMSE) demodulators follow as special cases. In the second algorithm, sensors iteratively reach consensus on the average (cross-) covariances of locally available per-sensor data vectors with the corresponding AP-to-sensor channel matrices, which constitute sufficient statistics for maximum likelihood demodulation. Distributed versions of the sphere decoding algorithm and the ZF/MMSE demodulators are also developed. These algorithms offer distinct merits in terms of error performance and resilience to non-ideal inter-sensor links. In both cases, the per-iteration error performance is analyzed, and the approximate number of iterations needed to attain a prescribed error rate are quantified. Simulated tests verify the analytical claims. Interestingly, only a few consensus iterations (roughly as many as the number of sensors), suffice for the distributed demodulators to approach the performance of their centralized counterparts.

The batch least-absolute shrinkage and selection operator (Lasso) has well-documented merits for estimating sparse signals of interest emerging in various applications, where observations adhere to parsimonious linear regression models. To cope with linearly growing complexity and memory requirements that batch Lasso estimators face when processing observations sequentially, the present paper develops a recursive Lasso algorithm that can also track slowly-varying sparse signals of interest. Performance analysis reveals that recursive Lasso can either estimate consistently the sparse signal's support or its nonzero entries, but not both. This motivates the development of a weighted version of the recursive Lasso scheme with weights obtained from the recursive least-squares (RLS) algorithm. The resultant RLS-weighted Lasso algorithm provably estimates sparse signals consistently. Simulated tests compare competing alternatives and corroborate the performance of the novel algorithms in estimating time-invariant and tracking slow-varying signals under sparsity constraints.

This paper develops near-optimal designs of wireless networks in the presence of fading. The novel approach optimizes jointly application level rates, routes, link capacities, power consumption and physical layer parameters. The physical layer is interference limited with terminals distributing their power budget among frequency tones, neighboring nodes and fading states. The present contribution builds on recent results establishing the optimality of layered architectures and develops physical layer resource allocation algorithms that are seamlessly integrated into layered architectures without loss of optimality.

Dynamic allocation of power, rate and channel access is a critical task in wireless networks. Capitalizing on convex optimization and stochastic approximation tools, this paper develops a stochastic resource allocation algorithm that minimizes average transmit power under individual average rate constraints. Focus is placed on networks where users transmit orthogonally over a set of parallel channels and transmissions are adapted based on quantized channel state information (CSI) allowing even channel statistics to be unknown. Convergence of the developed stochastic scheme is characterized and the average queue delays are obtained in closed form.

A multisource cooperative protocol is developed capable of achieving diversity order up to the number of cooperating users at a high throughput. In this design each source jointly encodes its own new information symbol with the information symbols received from other sources at past instants. Joint encoding is done using linear complex-field coefficients. Throughput analysis shows gains with respect to existing multi-source protocols and approaches the throughput of non-cooperative schemes. Diversity analysis shows that full spatial diversity is achievable. Simulations confirm the analytically established assessments.

Network coding has been shown to improve throughput, minimize delay and economize the energy requirements in wireless networks. This paper presents an algebraic polyphase approach to the wireless linear network coding problem. By modeling wireless nodes as consisting of linear periodic time varying filters, the model incorporates realistic constraints including omni directionality of transmissions, half-duplex operation and interference effects. A rank criterion is introduced, which together with the transmission constraints, constitutes the necessary and sufficient conditions for the existence of a wireless network code.

Network coding in wired networks has been shown to achieve considerable throughput gains relative to traditional routing networks. While the ergodic capacity of wireless multihop networks is unknown, the scaling of capacity with the number of nodes (n) has recently received increasing attention. While existing works mainly focus on networks with n source-destination pairs, this paper deals with capacity scaling in any-to-any wireless links, where each node communicates with all other nodes. Complex field network coding (CFNC) is adopted at the physical layer to allow n nodes exchanging information with simultaneous transmissions from multiple sources. A hierarchical CFNC-based scheme is developed and shown to achieve asymptotically (as n rarr infin) optimal quadratic capacity scaling in a dense network, where the area is fixed and the density of nodes increases. This is possible by dividing the network into many clusters, with each cluster sub-divided into many sub-clusters, hierarchically.

This paper addresses the problem of cooperative localization (CL) under severe communication constraints. Specifically, we present minimum mean square error (MMSE) and maximum a posteriori (MAP) estimators that can process measurements quantized with as little as one bit per measurement. During CL, each robot quantizes and broadcasts its measurements and receives the quantized observations of its teammates. The quantization process is based on the appropriate selection of thresholds, computed using the current state estimates, that minimize the estimation error metric considered. Extensive simulations demonstrate that the proposed Iteratively-Quantized Extended Kalman filter (IQEKF) and the Iteratively Quantized MAP (IQMAP) estimator achieve performance indistinguishable of that of their real-valued counterparts (EKF and MAP, respectively) when using as few as 4 bits for quantizing each robot measurement.

The number of active users in code-division multiple access (CDMA) systems is often much lower than the spreading gain. The present paper exploits fruitfully this a priori information to improve performance of multiuser detectors. A low-activity factor manifests itself in a sparse symbol vector with entries drawn from a finite alphabet that is augmented by the zero symbol to capture user inactivity. The non-equiprobable symbols of the augmented alphabet motivate a sparsity-exploiting maximum a posteriori probability (S-MAP) criterion, which is shown to yield a cost comprising the lscr2least-squares error penalized by the p-th norm of the wanted symbol vector (p = 0; 1; 2). Related optimization problems appear in variable selection (shrinkage) schemes developed for linear regression, as well as in the emerging field of compressive sampling (CS). The contribution of this work to CDMA systems is a gamut of sparsity-embracing multiuser detectors trading off performance for complexity requirements. From the vantage point of CS and the least-absolute shrinkage selection operator (Lasso) spectrum of applications, the contribution amounts to sparsity-exploiting algorithms when the entries of the wanted signal vector adhere to finite-alphabet constraints.

Consider a set of sensors that wish to consent on the message broadcasted by a multi-antenna transmitter in the presence of white-noise jamming. The jammer's interference introduces correlation across receivers and destroys the decomposable form of the maximum-likelihood decoder, thus preventing direct application of known distributed detection algorithms. This paper develops distributed detectors that circumvent this problem. Treating the jammer signal as deterministic, we develop two distributed estimation-decoding algorithms. The first algorithm relies on the generalized likelihood ratio test, whereas the second algorithm relies on semi-definite relaxation techniques and is suitable for large alphabet sizes. Both algorithms feature: (i) distributed implementation requiring only single-hop communications; (ii) no constraints on the network topology so long as it is connected; and (iii) performance close to the optimum centralized detector in the presence of severe jamming.

The present paper develops a decentralized expectation-maximization (EM) algorithm to estimate the parameters of a mixture density model for use in distributed learning tasks performed with data collected at spatially deployed wireless sensors. The E-step in the novel iterative scheme relies on local information available to individual sensors, while during the M-step sensors exchange information only with their one- hop neighbors to reach consensus and eventually percolate the global information needed to estimate the wanted parameters across the wireless sensor network (WSN). Analysis and simulations demonstrate that the resultant consensus-based distributed EM (CB-DEM) algorithm matches well the resource- limited characteristics of WSNs and compares favorably with existing alternatives because it has wider applicability and remains resilient to inter-sensor communication noise.

Transmit-power control is a critical task in cognitive radio (CR) networks. In the present contribution, adherence to hierarchies between primary and secondary users in a peer-to-peer CR network is enabled through distributed power control. Hierarchies are effected by imposing minimum and maximum bounds on a quality-of-service (QoS) metric, such as communication rate. These bounds translate to signal-to-interference-plus-noise ratio (SINR) constraints. Furthermore, a utility function captures each user's satisfaction with the received SINR. The novel power control strategy maximizes the total utility while respecting individual SINR constraints - a task recast as a convex optimization problem under a suitable relaxation. Sufficient conditions, realistic for practical CR networks, are provided to obtain the optimal power allocation from the solution of the relaxed problem. Finally, a low-overhead distributed algorithm for optimal power control is developed, and tested against competing alternatives via simulations.

The present paper deals with dynamic resource management based on quantized channel state information (CSI) for multi-carrier cognitive radio networks comprising primary and secondary wireless users. For each subcarrier, users rely on adaptive modulation, coding and power modes that they select in accordance with the limited-rate feedback they receive from the access point. The access point uses CSI to maximize the sum of generic concave utilities of the individual average rates in the network while respecting rate and power constraints on the primary and secondary users. Using a stochastic dual approach, optimum dual prices are found to optimally allocate resources across users per channel realization without requiring knowledge of the channel distribution.

We consider state estimation of a Markov stochastic process using an ad hoc wireless sensor network (WSN) based on noisy linear observations. Due to power and bandwidth constraints present in resource- limited WSNs, the observations are quantized before transmission. We derive a distributed recursive mean-square error (MSE) optimal quantizer-estimator based on the quantized observations. The resultant Kalman-like algorithm based on quantized observations exhibits MSE performance and computational complexity comparable to the Kalman filter based on un-quantized observations even for 2-3 bits of quantization per observation.

We formulate a frequency-division multiple access (FDMA) networking problem for wireless mobile ad-hoc networks (MANETS) to jointly optimize end-to-end user rates, routes, link capacities, transmitted power, frequency and power allocation across subcarriers and fading states. We show that the resulting non-convex optimization problem has zero duality gap. For some types of FDMA networks this result is exploited to reformulate the original problem into a (computationally tractable) convex optimization problem. We further exploit the lack of duality gap to show that conventional layering can be optimal in FDMA wireless MANETS. Specifically, if we select Lagrange multipliers appropriately, we can decompose the original problem in smaller sub-problems associated with the conventional networking layers. The solution of these per-layer optimization problems coincides with the solution of the originally formulated cross-layer optimization problem.

We deal with consensus-based online estimation and tracking of (non-) stationary signals using ad hoc wireless sensor networks (WSNs). A distributed (D-) least-mean square (LMS) like algorithm is developed, which offers simplicity and flexibility, while it solely relies on single-hop communications among sensors. Starting from a pertinent squared-error cost, we apply the alternating-direction method of multipliers to minimize it in a distributed fashion; and utilize stochastic approximation tools to eliminate the need for a complete statistical characterization of the processes of interest. By resorting to stochastic averaging and perturbed Lyapunov techniques, we further establish that local estimates are exponentially convergent to the true parameter of interest when observations are noise free and linearly related to it. This convergence result is necessary for bounding the estimation error in the presence of noise, and holds not only when regressors are white across time but even when they exhibit temporal correlations. Numerical tests confirm the merits of the novel D-LMS algorithm and its stability analysis.

The challenging task of scheduling multi-user orthogonal frequency-division multiplexed transmissions amounts to jointly optimum allocation of subcarriers, rate and power resources. The optimization problem for deterministic channels reduces to an integer program known to be exponentially complex. Interestingly, the present paper shows that almost surely optimal allocation is possible at low complexity in the wireless setup, provided that the random fading channel has continuous distribution function. Specifically, it is established that the ergodic capacity achieving allocation follows a greedy water-filling scheme with linear complexity in the number of users and subcarriers. The result extends to accommodate fairness through general utility functions and constraints on the minimum average user rates. When the channel distribution is known, the optimal on-line scheme relies on low-complexity provably convergent subgradient iterations to obtain pertinent dual variables off line. To accommodate channel uncertainties, stochastic subgradient iterations provide dual variables on line with guaranteed convergence to their off-line counterparts.

Multi-source relay-based cooperative communications can achieve spatial diversity gains, enhance coverage and potentially increase capacity when multiuser detection is used to effect maximum likelihood demodulation. If considered for large networks, traditional relaying entails loss in spectral efficiency that can be mitigated through network coding at the physical layer. These considerations motivate the complex field network coding (CFNC) approach introduced in this paper. Different from network coding over the Galois field, where wireless throughput is limited as the number of sources increases, CFNC always achieves throughput as high as 1/2 symbol per source per channel use. In addition to improved throughput, CFNC- based relaying achieves full diversity gain regardless of the underlying signal-to-noise-ratio (SNR) and the constellation used. Furthermore, the CFNC approach is general enough to allow for transmissions from sources to a common destination as well as simultaneous information exchanges among sources.

Without being necessary to pack multiple antennas per terminal, cooperation among distributed single-antenna nodes offers resilience to shadowing and can, in principle, enhance the performance of wireless communication networks by exploiting the available space diversity. Enabling the latter however, calls for practically implementable protocols to cope with errors at relay nodes so that simple receiver processing can collect the diversity at the destination. To this end, we derive in this paper a class of strategies whereby decoded bits at relay nodes are scaled in power before being forwarded to the destination. The scale is adapted to the signal-to-noise-ratio (SNR) of the source-relay and the intended relay-destination links. With maximum ratio combining (MRC) at the destination, we prove that such link-adaptive regeneration (LAR) strategies effect the maximum possible diversity while requiring simple channel state information that can be pragmatically acquired at the relay. In addition, LAR exhibits robustness to quantization and feedback errors and leads to efficient use of power both at relay as well as destination nodes. Analysis and corroborating simulations demonstrate that LAR relays are attractive across the practical SNR range; they are universally applicable to multibranch and multi-hop uncoded or coded settings regardless of the underlying constellation; and outperform existing alternatives in terms of error performance, complexity and bandwidth efficiency.

In communication systems employing a serially concatenated cyclic redundancy check (CRC) code along with a convolutional code (CC), erroneous packets after CC decoding are usually discarded. The list Viterbi algorithm (LVA) and the iterative Viterbi algorithm (IVA) are two existing approaches capable of recovering erroneously decoded packets. We here employ a soft decoding algorithm for CC decoding, and introduce several schemes to identify error patterns using the posterior information from the CC soft decoding module. The resultant iterative decoding-detecting (IDD) algorithm improves error performance by iteratively updating the extrinsic information based on the CRC parity check matrix. Assuming errors only happen in unreliable bits characterized by small absolute values of the log-likelihood ratio (LLR), we also develop a partial IDD (P-IDD) alternative which exhibits comparable performance to IDD by updating only a subset of unreliable bits. We further derive a soft-decision syndrome decoding (SDSD) algorithm, which identifies error patterns from a set of binary linear equations derived from CRC syndrome equations. Being noniterative, SDSD is able to estimate error patterns directly from the decoder output. The packet error rate (PER) performance of SDSD is analyzed following the union bound approach on pairwise errors. Simulations indicate that both IDD and IVA are better tailored for single parity check (PC) codes than for CRC codes. SDSD outperforms both IDD and LVA with weak CC and strong CRC. Applicable to AWGN and flat fading channels, our algorithms can also be extended to turbo coded systems.

We consider a two-person zero-sum mutual information game between one jammer (J) and one relay (Rfr) in both nonfading and fading scenarios. Assuming that the source (S) and the destination (D) are unaware of the game, we derive optimal pure or mixed strategies forJand Rfr depending on the link qualities and whether the players are active during theSrarrDchannel training. In nonfading scenarios, when bothJand Rfr have full knowledge of the source signal, linear jamming (LJ) and linear relaying (LR) are shown optimal in the sense of achieving Nash equilibrium. When theSrarrJandSrarrRfr links are noisy, LJ strategies (pure or mixed) are still optimal under LR. In this case, instead of always transmitting with full power as when theSrarrRfr link is perfect, Rfr should adjust the transmit power according to its power constraint and the reliability of the source signal it receives. Furthermore, in fading scenarios, it is optimal forJto jam only with Gaussian noise if it cannot determine the phase difference between its signal and the source signal. When LR is considered with fading, Rfr should forward with full power when theSrarrRfr link is better than the jammedSrarrDlink, and defer forwarding otherwise. Optimal parameters are derived based on exact Nash equilibrium solutions or upper and lower bounds when a closed-form solution cannot be found.

We investigate resource allocation policies for time-division multiple access (TDMA) over fading channels in the power-limited regime. For frequency-flat block-fading channels and transmitters having full channel state information (CSI), we first minimize power under a weighted sum average rate constraint and show that the optimal rate and time allocation policies can be obtained by a greedy water-filling approach with linear complexity in the number of users. Subsequently, we pursue power minimization under individual average rate constraints and establish that the optimal resource allocation also amounts to a greedy water-filling solution. Our approaches not only provide fundamental power limits when each user can support an infinite-size capacity-achieving codebook (continuous rates), but also yield guidelines for practical designs where users can only support a finite set of adaptive modulation and coding modes (discrete rates).

Differential, transmitted reference (TR) and energy detection (ED) based ultra-wideband impulse radios (UWBIR) can collect the rich multipath energy offered by UWB channels with a low-complexity receiver. However, they perform satisfactorily only when the channel induced inter-pulse interference (IPI) is negligible. This can be achieved by appending a guard interval with duration greater than or equal to the channel's delay spread to each frame an operation limiting the maximum achievable data rate. As a remedy, this Letter advocates block transmissions in conjunction with orthogonal spreading sequences to remove the introduced IPI. The resultant scheme requires no channel knowledge besides timing offset and incurs slightly more complexity than non-block alternatives, while it increases the data rate at no cost in error performance. Given a fixed data rate of 25 Mbps, the novel block scheme exhibits about 1.8 dB gain relative to its non-block counterpart in single-user simulated tests.

Emerging applications involving low-cost wireless sensor networks motivate well optimization of multi-user orthogonal frequency-division multiple access (OFDMA) in the power-limited regime. In this context, the present paper relies on limited-rate feedback (LRF) sent from the access point to terminals to minimize the total average transmit-power under individual average rate and error probability constraints. Along with the characterization of optimal bit, power and subcarrier allocation policies based on LRF, suboptimal yet simple schemes are developed for channel quantization. The novel algorithms proceed in two phases: (i) an off-line phase to construct the channel quantizer as well as the rate and power codebooks with moderate complexity; and (ii) an on-line phase to obtain, based on quantized channel state information, the optimum, rate, power and user-subcarrier allocation with linear complexity. Numerical examples corroborate the analytical claims and reveal that significant power savings result even with suboptimal schemes based on practically affordable LRF.

A novel framework was introduced recently for stochastic routing in wireless multihop networks, whereby each node selects a neighbor to forward a packet according to a probability distribution. Generalizing (deterministic) shortest path routing, stochastic routing offers greater flexibility that matches the random nature of wireless links. Consider the pairwise reliability matrix R, whose (i, j)-th entry Rijrepresents the probability that a packet transmitted from the j-th user Ujis correctly received by the i-th user Ui. Using R to capture physical layer aspects of the wireless medium, several rate-oriented stochastic routing formulations can be reduced to centrally solvable convex optimization problems. The present paper, introduces distributed algorithms that find optimal routing probabilities without the burden of collecting R at a central node and then percolating the resulting routing probabilities through network nodes. The resultant schemes are distributed in the sense that: (i) terminal Ujhas access only to the j-th row and column of R; and (ii) Ujinterchanges variables only with those single-hop neighbors having positive probability of decoding its packets. The distributed algorithms are built by recasting the optimization problems and applying dual decomposition techniques. Since iterates obtained via dual decomposition do not always converge to centralized optimal routing probabilities, two known regularization approaches are further invoked, namely the method of multipliers (MoM) and the alternating-direction MoM. Convergence to the optimal routing matrix is then guaranteed under mild conditions. Many rate-oriented optimality criteria of practical interest can be addressed by the distributed framework, including maximization of: (i) the minimum rate; (ii) a weighted sum of rates; (iii) the product of rates; and (iv) the source's rate in a relay network. Robustness of the distributed algorithms is tested with respect to "topological" changes, communication errors and node mobility.

In this paper, we develop a random access scheme which combines the widely used binary exponential backoff (BEB) algorithm with a cross-layer tree algorithm (TA) that relies on successive interference cancellation (SIC) with first success (FS). BEB and SICTA/FS complement each other nicely in enabling the novel protocol to attain a maximum stable throughput (MST) as high as 0.6 without packet loss. Although BEB-SICTA/FS avoids the deadlock problem caused by the error propagation commonly present in successive interference cancellation (SIC) algorithms, it may still suffer from deadlock effects induced by the "level skipping" caused by harsh wireless fading effects. We further develop a novel BEB-SICTA/F1 protocol, which is a modified version of BEB-SICTA/FS. Analysis and simulations demonstrate that this simple modification leads to high-throughput random access while completely avoiding deadlock problems.

We consider joint congestion and contention control for multihop wireless ad hoc networks, where the goal is to find optimal end-to-end source rates at the transport layer and per-link persistence probabilities at the medium access control (MAC) layer to maximize the aggregate source utility. The primal formulation of this problem is non-convex and non-separable. Under certain conditions, by applying appropriate transformations and introducing new variables, we obtain a decoupled and dual-decomposable convex formulation. For general non-logarithmic concave utilities, we develop a novel dual-based distributed algorithm using the subgradient method. In this algorithm, sources at the transport layer adjust their log rates to maximize their net benefits, while links at the MAC layer select transmission probabilities proportional to their conceived contribution to the system reward. The two layers are connected and coordinated by link prices. Our solutions enjoy the benefits of cross-layer optimization while maintaining the simplicity and modularity of the traditional layered architecture.

We deal with energy efficient time-division multiple access over fading channels with finite-rate feedback for use in the power-limited regime. Through FRP from the access point, users acquire quantized channel state information. The goal is to map channel quantization states to adaptive modulation and coding modes and allocate optimally time slots to users so that the average transmit-power is minimized. To this end, we develop a joint quantization and resource allocation approach, which decouples the complicated problem at hand into three minimization sub-problems and relies on a coordinate descent approach to iteratively effect energy efficiency. Numerical results are presented to evaluate the energy savings.

We consider minimizing average transmit-power with finite-rate feedback for coherent communications in a wireless sensor network (WSN). where sensors communicate with a fusion center (FC) using adaptive modulation and coding over a wireless fading channel. By viewing the coherent WSN setup as a distributed space-time multi-input single-output (MISO) system, we develop beamforming and resource allocation strategies and design optimal quantizers when the sensors only have available quantized (Q-) channel state information at the transmitters (CSIT) through a finite-rate feedback channel. Numerical results reveal that our novel design based on Q-CSIT yields significant power savings even for a small number of feedback bits.

We introduce distributed algorithms to find rate-optimal routes based on local knowledge of the pairwise error probability (reliability) matrix. The distributed algorithms are built by (re)-formulating optimization problems amenable to application of dual decomposition techniques. Convergence of our algorithms to the optimal routing matrix is guaranteed under mild conditions. Many rate-optimality criteria of practical interest can be casted in our framework including maximization of: i)worst user's rate; ii) weighted sum of rates; iii) product of rates; and iv) relay network rate. We test robustness of our algorithms to node mobility.

We deal with distributed estimation of deterministic vector parameters using ad hoc wireless sensor networks (WSNs). We cast the decentralized estimation problem as the solution of multiple convex optimization subproblems. Using the method of alternating multipliers we derive algorithms which are decomposable into a set of simpler tasks suitable for distributed implementation. Different from existing alternatives, our approach does not require knowing the desired estimator in closed-form thus allowing for distributed nonlinear estimation. Our algorithms have guaranteed convergence under ideal channel links, while they exhibit noise resilience provably established for the distributed best linear unbiased estimator (BLUE).

The problem of joint channel and carrier frequency offset (CFO) estimation is addressed in the context of multiple-input multiple-output (MIMO) communications using orthogonal space-time-block codes (OSTBCs). A new semiblind method is proposed to jointly estimate the channel matrix and the CFO parameter. Our method blindly estimates the CFO parameter along with a low-dimensional subspace where the channel is located, and then uses a few training blocks to extract the channel parameters from this subspace.

In the emerging paradigm of open spectrum access, cognitive radios dynamically sense the radio-spectrum environment and must rapidly tune their transmitter parameters to efficiently utilize the available spectrum. The unprecedented radio agility envisioned, calls for fast and accurate spectrum sensing over a wide bandwidth, which challenges traditional spectral estimation methods typically operating at or above Nyquist rates. Capitalizing on the sparseness of the signal spectrum in open-access networks, this paper develops compressed sensing techniques tailored for the coarse sensing task of spectrum hole identification. Sub-Nyquist rate samples are utilized to detect and classify frequency bands via a wavelet-based edge detector. Because spectrum location estimation takes priority over fine-scale signal reconstruction, the proposed novel sensing algorithms are robust to noise and can afford reduced sampling rates.

We consider a two-person zero-sum mutual information game between one jammer (J) and one relay (R), in a non-fading scenario. Supposing that the source (S) and the destination (D) are unaware of the game, we derive optimal pure or mixed strategies for J and R depending on the link qualities and whether the players are active during the S rarr D channel training. When both J and R have full knowledge of the source signal, the optimal strategies amount to linear jamming (LJ) and linear relaying (LR), respectively. When the S rarr J and S rarr R links are noisy, LJ strategies (pure or mixed) are still optimal under LR. In this case, instead of always transmitting with full power as when the S rarr R link is perfect, R should adjust transmit-power according to its power constraint and the reliability of the source signal it receives.

Emerging applications involving low-cost wireless sensor networks motivate well optimization of multi-user orthogonal frequency-division multiple access (OFDMA) in the power-limited regime. In this context, the present paper relies on limited- rate feedback (LRF) sent from the access point to terminals to acquire quantized channel state information (CSI) in order to minimize the total average transmit-power under individual average rate and error probability constraints. Specifically, we introduce two suboptimal reduced-complexity schemes to: (i) allocate power, rate and subcarriers across users; and (ii) design accordingly the channel quantizer. The latter relies on the solution of (i) to design equally probable quantization regions per subcarrier and user. Numerical examples corroborate the analytical claims and reveal that the power savings achieved by our reduced-complexity LRF designs are close to those achieved by the optimal solution.

We put forth a unified framework for downlink and uplink scheduling of multiple connections with diverse quality-of-service requirements, where each connection transmits using adaptive modulation and coding over a wireless fading channel. Based on quantized channel state information at the transmitters (Q-CSIT), we derive the information-theoretic optimal downlink and uplink resource allocation/scheduling strategies using tools from convex/nonlinear optimization theory. When the fading statistics are not known a priori, we develop a class of stochastic primal-dual (SPD) algorithms which can dynamically adapt the scheduling policies online. We prove rigorously and confirm by simulations that with affordable complexity, these SPD algorithms asymptotically converge to the optimal scheduling strategies from any initial value.

We deal with energy-efficiency issues and resource allocation policies for time division multi-access (TDMA) over fading channels under average individual rate constraints. Supposing that the channels are frequency-flat block-fading and transmitters have full channel state information (CSI), we minimize power under average individual rate constraints and show that the optimal rate and time allocation policies can be obtained by a gready water-filling strategy. Our approach not only provides fundamental power limits when each user can support an infinite number of capacity-achieving codebooks, but also yields guidelines for practical designs where users can only support a finite number of adaptive modulation and coding (AMC) modes with prescribed symbol error probabilities.

We introduce a novel approach to multi-hop routing in wireless networks. Instead of the usual graph description we characterize the network by the packet delivery ratio matrix whose entries represent the probability that a given node decodes the packet transmitted by any other node. The model lends itself naturally to the formulation of stochastic routing protocols in which packets are randomly routed to neighboring nodes; and routing algorithms search for a matrix of routing probabilities according to properly defined optimality criteria. The goal of the paper is to show that this novel framework offers a useful model to aid in the design of optimal routing algorithms. In particular, it is established that: (i) performance is improved with respect to graph descriptions; and (ii) optimal routes can be obtained as the solution of optimization problems, many of which turn out to be convex and can thus be solved in polynomial time using interior point methods.

We consider joint congestion control and multiuser scheduling in a hybrid wireline and wireless network, where the air interface of wireless links is based on orthogonal frequency division multiplexing (OFDM). For static channels, we formulate this cross-layer design as a network utility maximization (NUM) problem with both wireline and wireless link constraints. The convexity of the problem enables a well-established dual-based approach to decompose it into two subproblems, the transport layer source rate adaptation and the medium access control (MAC) layer multiuser OFDM scheduling, which are connected and coordinated by link prices. While the rate and link price adjustments follow the same fashion as the conventional utility-based congestion control for wireline networks, the key difference is the multiuser OFDM scheduling performed at the wireless access point (AP). Independent from specific utilities used by each source, this scheduling problem always maximizes a wireless link-price-weighted sum throughput (LPWST), which can be solved efficiently by a block-coordinate descent method, resulting in optimal subcarrier assignment and power allocation at the AP. Convergence of the dual-based algorithm is established using the convex optimization theory. To extend our results to dynamic wireless channels, we provide a NUM formulation with long-term average feasible rate region and develop a gradient scheduling algorithm to handle channel variations. Our work represents a systematic cross-design framework for distributed fair resource allocation in a hybrid network with both static and dynamic wireless channels.

In this paper we derive a stochastic primal-dual (SPD) algorithm for downlink/uplink scheduling of multiple connections with rate requirements, where each connection transmits using adaptive modulation and coding over a wireless fading channel. Based on quantized channel state information at the transmitters, we derive the information-theoretic optimal downlink and uplink resource allocation/scheduling strategies. When the fading statistics are not known a priori, we develop an SPD algorithm which can dynamically adapt the scheduling policy online. We established analytically and confirm by simulations that with affordable complexity, this SPD algorithm asymptotically converges to the optimal scheduling strategies from any initial value.

Emerging applications involving low-cost wireless sensor networks motivate well optimization of multi-user orthogonal frequency-division multiple access (OFDMA) in the power-limited regime. In this context, the present paper relies on limited-rate feedback (LRF) sent from the access point to terminals to minimize the total average transmit-power under individual average rate and error probability constraints. The characterization of optimal bit, power and subcarrier allocation policies based on LRF, as well as optimal channel quantization are provided. Numerical examples corroborate the analytical claims and reveal that significant power savings result even with few fed back bits.

A general framework is developed for multi-source cooperation (MSC) protocols to improve diversity and spectral efficiency relative to repetition based alternatives that rely on single-source cooperation. The novel protocols are flexible to balance tradeoffs among diversity, spectral efficiency and decoding-complexity. Users are grouped in clusters and follow a two-phase MSC protocol which involves time division multiple access (TDMA) to separate users within a cluster, and code division multiple access (CDMA) used to separate clusters. An attractive protocol under the general MSC framework relies on distributed complex field coding (DCFC) to enable diversity order equal to the number of users per cluster. Cluster separation based on orthonormal spreading sequences leads to spectral efficiency 1/2. When the number of clusters exceeds the amount of spreading, spectral efficiency can be enhanced without sacrificing diversity, at the expense of controllable increase in complexity. Simulations corroborate our analytical claims

Scheduling amounts to allocating optimally channel, rate and power resources to multiple connections with diverse quality-of-service (QoS) requirements. It constitutes a throughput-critical task at the medium access control layer of today's wireless networks that has been tackled by seemingly unrelated information-theoretic and protocol design approaches. Capitalizing on convex optimization and stochastic approximation tools, the present paper develops a unified framework for channel-aware QoS-guaranteed scheduling protocols for use in adaptive wireless networks whereby multiple terminals are linked through orthogonal fading channels to an access point, and transmissions are (opportunistically) adjusted to the intended channel. The unification encompasses downlink and uplink with time-division or frequency-division duplex operation; full and quantized channel state information comprising a few bits communicated over a limited-rate feedback channel; different types of traffic (best effort, non-real-time, real-time); uniform and optimal power loading; off-line optimal scheduling schemes benchmarking fundamentally achievable rate limits; as well as on-line scheduling algorithms capable of dynamically learning the intended channel statistics and converging to the optimal benchmarks from any initial value. The take-home message offers an important cross-layer design guideline: judiciously developed, yet surprisingly simple, channel-adaptive, on-line schedulers can approach information-theoretic rate limits with QoS guarantees.

We consider decentralized estimation of a noise-corrupted deterministic parameter using a bandwidth-constrained sensor network with a fusion center (FC). Each sensor's noise is additive, zero mean, and independent across sensors. A decentralized estimator is said to be universal if the local sensor quantization rules and the final fusion rule at the FC are independent of sensor noise pdf. Assuming that information rate from each sensor to the FC is constrained to one bit per sample, we derive a Crameacuter-Rao lower bound (CRLB) on the mean-squared error (MSE) performance of a class of rate-constrained universal decentralized estimators. Our results show that if sensor observation noise has finite range in [-U,U], then the minimum MSE performance of any one-bit rate-constrained universal decentralized estimator is at least U2/(4K), where K is the total number sensors. This bound implies that the recently proposed universal decentralized estimators are optimal up to a constant factor of 4

Cooperative communication systems using various relay strategies can achieve spatial diversity gains, enhance coverage, and potentially increase capacity. For the practically attractive decode-and-forward (DF) relay strategy, we derive a high-performance low-complexity coherent demodulator at the destination in the form of a weighted combiner. The weights are selected adaptively to account for the quality of both source-relay-destination and source-destination links. Analysis proves that the novel coherent demodulator can achieve the maximum possible diversity, regardless of the underlying constellation. Its error performance tightly bounds that of maximum-likelihood (ML) demodulation, which provably quantifies the diversity gain of ML detection with DF relaying. Simulations corroborate the analysis and compare the performance of the novel decoder with existing diversity-achieving strategies including analog amplify-and-forward and selective-relaying.

A novel random access protocol combining a tree algorithm (TA) with successive interference cancellation (SIC) has been introduced recently. To mitigate the deadlock problem of SICTA arising in error-prone wireless networks, we put forth a SICTA with first success (SICTA/FS) protocol, which is capable of high throughput while requiring limited-sensing and gaining robustness to errors relative to SICTA.

Ultra-wideband (UWB) radios have received increasing attention recently for their potential to overlay legacy systems, their low-power consumption and low-complexity implementation. Because of the pulsed or duty-cycled nature of the ultra-short transmitted waveforms, timing synchronization and channel estimation pose major, and often conflicting, challenges and requirements. In order to address (or in fact bypass) both tasks, we design and test noncoherent UWB (de)modulation schemes, which remain operational even without timing and channel information. Relying on integrate-and-dump operations of what we term "dirty templates," we first derive a maximum likelihood (ML) optimal noncoherent UWB demodulator. We further establish a conditional ML demodulator with lower complexity. Analysis and simulations show that both can also be applied after (possibly imperfect) timing acquisition. Under the assumption of perfect timing, our noncoherent UWB scheme reduces to a differential UWB system. Our approach can also be adapted to a transmitted reference (TR) UWB system. We show that the resultant robust-to-timing TR (RTTR) approach considerably improves performance of the original TR system in the presence of timing offsets or residual timing acquisition errors

Well appreciated at the physical layer, user cooperation is introduced here as a diversity enabler for wireless random access (RA) at the medium access control sublayer. This is accomplished through a two-phase protocol in which active users start with a low power transmission attempting to reach nearby users and follow up with a high power transmission in cooperation with the users recruited in the first phase. We show that such a cooperative protocol yields a significant increase in throughput. Specifically, we prove that for networks with a large number of users, the throughput of a cooperative wireless RA network operating over Rayleigh-fading links approaches the throughput of an RA network operating over additive white Gaussian noise links—thus justifying the title of the paper. The message borne out of this result is that user cooperation offers a viable choice for migrating diversity benefits to the wireless RA regime, thus bridging the gap to wireline RA networks, without incurring a bandwidth or energy penalty.

Random access is well motivated and has been widely applied when the network traffic is bursty and the expected throughput is not high. The main reason behind relatively low-throughput expectations is that collided packets are typically discarded. In this paper, we develop a novel protocol exploiting successive interference cancellation (SIC) in a tree algorithm (TA), where collided packets are reserved for reuse. Our SICTA protocol can achieve markedly higher maximum stable throughput relative to existing alternatives. Throughput performance is analyzed for general$d$-ary SICTA with both gated and window access. It is shown that the throughput for$d$-ary SICTA with gated access is about$(\ln d)/(d-1)$, and can reach$0.693$for$d=2$. This represents a 40% increase over the renowned first-come-first-serve (FCFS)$0.487$tree algorithm. Delay performance is also analyzed for SICTA with gated access, and numerical results are provided.

In this correspondence, we deal with noncoherent communications over multiple-input-multiple-output (MIMO) wireless links. For a Rayleigh flat block-fading channel with M transmit- and N receive-antennas and a channel coherence interval of length T, it is well known that for TGtM, or, at high signal-to-noise-ratio (SNR) rhoGt1 and Mlesmin{N,lfloorT/2rfloor}, unitary space-time modulation (USTM) is capacity-achieving, but incurs exponential demodulation complexity in T. On the other hand, conventional training-based schemes that rely on known pilot symbols for channel estimation simplify the receiver design, but they induce certain SNR loss. To achieve desirable tradeoffs between performance and complexity, we propose a novel training approach where USTM symbols over a short length Ttau(tauis a small fraction of T, and recovers part of the SNR loss experienced by the conventional training-based schemes. When rhorarrinfin and TgesTtauges2M=2Nrarrinfin, but the ratios alpha=M/T, alpha1=Ttau/T are fixed, we obtain analytical expressions of the asymptotic SNR loss for both the conventional and new training-based approaches, serving as a guideline for practical designs

As sensor nodes are typically powered by nonrenewable batteries, energy efficiency is a critical factor in wireless sensor networks (WSNs). Orthogonal modulations appropriate for the energy-limited WSN setup have been investigated under the assumption that batteries are linear and ideal, but their effectiveness is not guaranteed when more realistic nonlinear battery models are considered. In this paper, based on a general model that integrates typical WSN transmission and reception modules with realistic battery models, we derive two battery power-conserving schemes for two M-ary orthogonal modulations, namely pulse position modulation (PPM) and frequency shift keying (FSK), both tailored for WSNs. Then we analyze and compare the battery power efficiency of PPM and FSK over various wireless channel models. Our results reveal that FSK is more power-efficient than PPM in sparse WSNs, while PPM may outperform FSK in dense WSNs. We also show that in sparse WSNs, the power advantage of FSK over PPM is no more than 3 dB; whereas in very dense WSNs, the power advantage of PPM over FSK can be much more significant as the constellation size M increases.

We consider broadcasting to multiple destinations with uneven quality receivers. Based on their quality of reception, we group destinations in tiers and transmit using hierarchical modulations. These modulations are known to offer a practical means of achieving variable error protection of the broadcasted information to receivers of variable quality. After the initial broadcasting step, tiers successively re-broadcast part of the information they received from tiers of higher-quality to tiers with lower reception capabilities. This multi-tier cooperative broadcasting strategy can accommodate variable rate and error performance for different tiers but requires complex demodulation steps. To cope with this complexity in demodulation, we derive simplified per-tier detection schemes with performance close to maximum-likelihood and ability to collect the diversity provided as symbols propagate through diversified channels across successive broadcastings. Error performance is analyzed and compared to (non)-cooperative broadcasting strategies. Simulations corroborate our theoretical findings.

Combining multi-source cooperation and link- adaptive regenerative techniques, we develop a novel protocol capable of achieving diversity up to the number of cooperating users and larger coding gains without incurring the overhead of cyclic redundancy check (CRC) codes. The resulting protocol can be further optimized to take advantage of the information provided by CRC when available. Simulations confirm our theoretical assessments.

A differential ultra-wideband (UWB) receiver can mitigate the 50% loss in rate and power inherent to conventional transmitted reference (TR) systems, under the assumption that channel induced inter-pulse interference (IPI) is absent or negligible. Consequently, restrictions on minimum frame length and maximum achievable bit rate are imposed. Using orthogonal Walsh-Hadamard sequences to remove IPI at the receiver, we show that the no-IPI condition can be relaxed without penalty in error performance and a small increase in complexity, leading to higher data rates. Assuming that timing has been acquired, error performance of the novel UWB radio is evaluated analytically and via simulations. A multi-user version of the detector is also developed and its performance is compared with multi-user TR.

Motivated by the increasing demand for low-cost low-power wireless sensor networks and related applications, we develop suboptimal but simple bit and power loading algorithms that minimize transmit-power for orthogonal frequency division multiplexing (OFDM) under rate and error probability constraints. Bit and power loading adaptation are based on a quantized version of channel state information (D-CSI) conveyed from the receiver to the transmitter. Our design exploits the correlation among sub-carriers in order to reduce feedback overhead. Numerical examples support our claim that simple suboptimal schemes with a reduced number of feedback bits achieve near-optimal performance while providing significant power savings

We derive and analyze distributed state estimators of dynamical stochastic processes, whereby low communication cost is effected by requiring the transmission of a single bit per observation. Following a Kalman filtering (KF) approach, we develop recursive algorithms for distributed state estimation based on the sign of innovations (SOI). Even though SOI-KF can afford minimal communication overhead, we prove that in terms of performance and complexity it comes very close to the clairvoyant KF which is based on the analog-amplitude observations. Reinforcing our conclusions, we show that the SOI-KF applied to distributed target tracking based on distance only observations yields accurate estimates at low communication cost

We derive linear estimators of stationary random signals based on reduced-dimensionality observations collected at distributed sensors and communicated over wireless fading links to a fusion center, where additive noise is also present. Dimensionality reduction compresses sensor data to meet low-power and bandwidth constraints, while linearity in compression and estimation are well motivated by the limited computing capabilities wireless sensor networks are envisioned to operate with. For uncorrelated sensor data, we develop mean-square error (MSE) optimal estimators in closed-form; while for correlated sensor data, we derive sub-optimal iterative estimators which guarantee convergence at least to a stationary point. Performance analysis and corroborating simulations demonstrate the merits of the novel distributed estimators relative to existing alternatives.

A cross-layer design is developed for quality-of-service (QoS) guaranteed traffic. The proposed design jointly exploits the error-correcting capability of the truncated automatic repeat request (ARQ) protocol at the data link layer and the adaptation ability of the adaptive modulation and coding (AMC) scheme at the physical layer to optimize the system performance. The queuing behavior induced by both the truncated ARQ protocol and the AMC scheme is analyzed with an embedded Markov chain. Analytical expressions for performance metrics such as packet loss rate, throughput and average packet delay are derived. Using these expressions, a constrained optimization problem is solved numerically to jointly determine the retry limit for the truncated ARQ protocol as well as the prescribed packet error rate for the AMC scheme so that the overall system throughput is maximized under the specified QoS constraints.

Differential encoding is known to simplify receiver implementation because it by-passes channel estimation. Relying on linear constellation precoders designed in closed-from for coherent multi-antenna systems, we derive a non-constant modulus space-time differential scheme that enables diversity, does not sacrifice rate, and more interestingly, it allows for constellation designs with many degrees of freedom. Performance merits of this scheme are analyzed and compared with existing differential designs. Simulations corroborate our theoretical findings.

In this paper, we study the achievable rates of practical ultra-wideband (UWB) systems using pulse position modulation (PPM) and transmitted-reference (TR) transceivers. TR obviates the need for complex channel estimation, which is particularly challenging in the context of UWB. Based on an upper bound we derive for the error probability with random coding, we establish that for SNR values of practical interest, PPM-UWB with TR can achieve rates on the order of C(∞) = P/N0(nats/second), where C(∞) denotes the capacity of an AWGN channel in the UWB regime for average received power P and noise power spectrum density N0.

In response to the growing demand for low-cost low-power wireless sensor networks and related applications, we develop bit and power loading algorithms that minimize transmit-power for orthogonal frequency division multiplexing (OFDM) under rate and error probability constraints. Our novel algorithms exploit one of three types of channel state information at the transmitter (CSIT): deterministic (per channel realization) for slow fading links, statistical (channel mean) for fast fading links, and quantized (Q-) CSIT whereby a limited number of bits are fed back from the transmitter to the receiver. By adopting average transmit-power as a distortion metric, a channel quantizer is also designed to obtain a suitable form of Q-CSI. Numerical examples corroborate the analytical claims and reveal that significant power savings result even with a few bits of Q-CSIT.

Recently, error control codes, including convolutional codes, have been used in multi-source cooperation (MSC) networks to provide higher diversity and code rates relative to repetition-based single source cooperation alternatives. For an MSC network with K active users, it has been established that the maximum diversity order is less than K for any error control code with code rate R > 1/K. This paper introduces distributed complex field coding (DCFC) in MSC networks. Theoretical analysis reveals that DCFC-MSC is capable of enabling full diversity order equal to K, at a fixed rate 1/2. Simulations verify that DCFC-MSC can improve system performance markedly.

In communication systems employing a serially concatenated cyclic redundancy check (CRC) code along with a convolutional code (CC), erroneous packets after CC decoding are usually discarded. The list Viterbi algorithm (LVA) and the iterative Viterbi algorithm (IVA) are two existing approaches capable of recovering erroneously decoded packets. We first propose an iterative log-MAP (ILM) algorithm improves error performance by iteratively updating the extrinsic information based on the CRC parity check matrix. We further derive a soft-decision syndrome decoding (SDSD) algorithm, which identifies error patterns from a set of binary linear equations derived from CRC syndrome equations. Being non-iterative, SDSD is able to estimate error patterns directly from the decoder output. The packet error rate (PER) performance of SDSD is analyzed following the union bound approach on pairwise errors. Simulations indicate that SDSD outperforms both ILM and LVA with weak CC and strong CRC. Applicable to AWGN and flat fading channels, our algorithms can also be extended to turbo coded systems.

We investigate energy-efficiency issues and resource allocation policies for time division multi-access (TDMA) over fading channels in the power-limited regime. Supposing that the channels are frequency-flat block-fading and transmitters have full channel state information (CSI), in this paper we minimize power under a weighted sum-rate constraint and show that the optimal rate and time allocation policies can be obtained by water-filling over realizations of convex envelopes of the minima for cost-reward functions. Our approach not only provides fundamental power limits when each user can support an infinite number of capacity-achieving codebooks, but also yields guidelines for practical designs where users can only support a finite number of adaptive modulation and coding (AMC) modes with prescribed symbol error probabilities

We investigate the potential for high throughput when combining random backoff schemes with a robust cross-layer tree algorithm (TA) for wireless random access. We first develop a BEB-SICTA/FS protocol which combines the binary exponential backoff (BEB) algorithm with a recently proposed SICTA/FS protocol saturation throughput analysis of BEB-SICTA/FS motivates the combined protocol herein because: 1) by using the practically feasible SICTA/FS to resolve collisions in a conventional BEB based protocol for wireless random access, we can achieve high throughput; and 2) BEB can sufficiently reduce the collision size and thus enhance the efficiency of SICTA/FS, since SICTA/FS is more efficient when the number of initially collided packets is small. Guided by our analysis, we further put forth a GBEB-SICTA/FS protocol which is capable of higher and more steadfast saturation throughput than BEB-SICTA/FS. Finally, we tailor our protocols for the IEEE 802.16 broadband wireless access (BWA) networks and test their performance through simulations

Emerging applications involving low-cost wireless sensor networks motivate well optimization of orthogonal frequency-division multiplexing (OFDM) in the power-limited regime. To this end, the present paper develops loading algorithms to minimize transmit-power under rate and error probability constraints, using three types of channel state information at the transmitter (CSIT): deterministic (per channel realization) for slow fading links, statistical (channel mean) for fast fading links, and quantized (Q), whereby a limited number of bits are fed back from the transmitter to the receiver. Along with optimal bit and power loading schemes, quantizer designs and reduced complexity alternatives with low feedback overhead are developed to obtain a suite of Q-CSIT-based OFDM transceivers with desirable complexity versus power-consumption tradeoffs. Numerical examples corroborate the analytical claims and reveal that significant power savings result even with a few bits of Q-CSIT

Multicarrier multiple access with channel knowledge and prescribed power at the transmitters is shown to maximize the sum-rate for circulant intersymbol-interference (ISI) channels. A low-complexity iterative algorithm is derived for optimal subcarrier allocation to multiple users, while power is loaded per user by specializing an existing iterative algorithm to circulant ISI channels. It is analytically shown that each subcarrier should be allocated to the user having relatively better subcarrier gain and that different users may share certain subcarriers.

In this letter, we study the achievable rates of practical ultra-wideband (UWB) systems using pulse position modulation (PPM) and transmitted-reference (TR) transceivers. TR obviates the need for complex channel estimation, which is particularly challenging in the context of UWB communications. Based on an upper bound we derive for the error probability with random coding, we establish that for signal-to-noise ratio values of practical interest, PPM-UWB with TR can achieve rates on the order of C(/spl infin/)=P/N/sub 0/ (nats/s), where C(/spl infin/) denotes the capacity of an additive white Gaussian noise channel in the UWB regime for average received power P and noise power spectrum density N/sub 0/.

Hard sphere decoding (HSD) has well-appreciated merits for near-optimal demodulation of multiuser, block single-antenna or multi-antenna transmissions over multi-input multi-output (MIMO) channels. At increased complexity, a soft version of sphere decoding (SD), so-termed list SD (LSD), has been recently applied to coded layered space-time (LST) systems enabling them to approach the capacity of MIMO channels. By introducing a novel bit-level multi-stream coded LST transmitter along with a soft-to-hard conversion at the decoder, we show how to achieve the near-capacity performance of LSD, and even outperform it as the size of the block to be decoded (M) increases. Specifically, for binary real LST codes, we develop exact max-log-based SD schemes with M + 1 HSD steps, and an approximate alternative with only one HSD step to trade off performance for average complexity. These schemes apply directly to the real and imaginary parts of quaternary phase-shift keying signaling, and also to quadrature amplitude modulation signaling after incorporating an appropriate interference estimation and cancellation module. We corroborate our near-optimal soft detection (SoD) algorithms based on HSD (SoD-HSD) with simulations.

Emerging indoor technologies including wireless multimedia and personal area networks (WPANs) entail high-rate systems capable of supporting multiple users (piconets) with variable rates. These requirements motivate the design of multiband (MB) ultra-wideband (UWB) radios for their simplicity in handling pronounced frequency selectivity, agility in coping with interference, scalability in providing multirate operation, and their potentially low cost. Relative to baseband UWB radios, MB-UWB systems have gained popularity in the IEEE standards for short-range wireless links. However, multiple-access (MA) schemes must be designed carefully to harness the diversity benefits provided by the MB-UWB propagation, in a spectrally efficient manner. To this end, we introduce a crossband flexible UWB MA scheme for multipiconet WPANs. The resultant design that we term FLEX-UWB offers resilience to multiuser interference, can conveniently accommodate various spreading alternatives, enables full multipath diversity, and can effect scalable spectral efficiency (from low to medium and high data rates). Simulations confirm the merits of FLEX-UWB radios in comparison with various alternatives

In the above titled paper (ibid., vol. 51, no. 5, pp. 1900-1907, May 05), changes were made to equations on p. 1905.

Synchronization is a performance-critical factor in most communication systems: from classical narrowband and emerging (ultra) wideband (UWB) point-to-point links to cooperative or ad hoc networking, where access must deal with multi-user interference (MUI) and possibly severe intersymbol interference (ISI). For universal applicability to all these scenarios, we develop a blind synchronization and demodulation scheme which relies on intermittent transmission of nonzero mean symbols. These enable MUI- and ISI-resilient timing acquisition via energy detection and low-complexity demodulation by matching to a synchronized aggregate template (SAT). The resultant SAT receiver offers distinct advantages over RAKE, has low-complexity and lends itself naturally to decision-directed enhancements. Its blind operation nicely fits the requirements of multi-user ad hoc access and its ability to handle ISI is particularly attractive for UWB communications. Analytical performance evaluation and simulations testing our novel scheme in UWB settings confirm its high potential for deployment

Within a new paradigm, where wireless user cooperation is viewed as a form of (opportunistic) multipath, we exploit the unique capabilities of direct-sequence spread spectrum transmissions in handling multipath to design a novel spectrally efficient protocol for wireless cooperative networks. We show how and why our proposed system achieves diversity without increasing bandwidth. After analyzing its performance, we deduce that user capacity can be significantly improved with respect to existing third generation cellular systems in the uplink.

Abstract-A multicarrier direct-sequence code-division multiple-access (MC-DS-CDMA) downlink system with linear precoding over a group of subcarriers is considered. This scheme preserves user orthogonality independently of the underlying frequency-selective channel, collects the channel diversity and enables low-complexity decoding. In this context, we examine a local maximum-likelihood (LML) detection technique that searches for the maximum-likelihood (ML) solution in the neighborhood of the output provided by the minimum mean-squared error (MMSE) detector. By exploiting the soft information of the MMSE detector output and the precoder structure, we introduce useful criteria to reduce the computational complexity of the LML search. Simulations illustrate that the LML-MMSE detector with minimum neighborhood size yields considerable BER improvement with respect to MMSE, and outperforms a block decision-feedback equalization (DFE) approach at comparable complexity.

User cooperation can provide spatial transmit diversity gains, enhance coverage and potentially increase capacity. Existing works have focused on two-user cooperative systems with perfect channel state information at the receivers. In this paper, we develop several distributed space-time processing schemes for general N-user cooperative systems, which do not require channel state information at either relays or destination. We prove that full spatial diversity gain can be achieved in such systems. Simulations demonstrate that these cooperative schemes achieve significant performance gain

Transmitter designs based on partial channel state information (CSI) have become increasingly attractive in multi-antenna wireless communication systems. To capture partial CSI statistics at the transmitter, we rely on a channel amplitude information (CAI) model, based on which we aim for maximizing the random channel's average mutual information. Due to the high computational complexity required for such optimal transmissions, we resort to reduced complexity practical schemes and derive necessary and sufficient conditions for these alternatives to achieve maximal average mutual information

We analyze the stability properties of slotted Aloha with capture for random access over fading channels with infinitely-many users. We assume that each user node knows only its own uplink channel gain, and uses this decentralized channel state information (CSI) to perform power control and/or probability control. The maximum stable throughput (MST) for a general capture model is obtained by means of drift analysis on the backlog Markov chain. We then specialize our general result to a signal-to-interference-plus-noise ratio (SINR) capture model. Our analysis shows that if the channels of all users are identical and independently distributed (i.i.d.) with finite means, the system is unstable under any kind of power and probability control mechanism that is based only on decentralized CSI.

Relative to a centralized operation, opportunistic medium access capitalizing on decentralized multiuser diversity in a channel-aware homogeneous slotted Aloha system with analog-amplitude channels has been shown to incur only partial loss in throughput due to contention. In this context, we provide sufficient conditions for stability as well as upper bounds on average queue sizes, and address three equally important questions. The first one is whether there exist decentralized scheduling algorithms for homogeneous users with higher throughputs than available ones. We prove that binary scheduling maximizes the sum-throughput. The second issue pertains to heterogeneous systems where users may have different channel statistics. Here we establish that binary scheduling not only maximizes the sum of the logs of the average throughputs, but also asymptotically guarantees fairness among users. The last issue we address is extending the results to finite state Markov chain (FSMC) channels. We provide a convex formulation of the corresponding throughput optimization problem, and derive a simple binary-like access strategy

Abstract-Closest point algorithms find wide applications in decoding block transmissions encountered with single- or multiuser communication links relying on a single or multiple antennas. Capitalizing on the random channel and noise models typically encountered in wireless communications, the sphere decoding algorithm (SDA) and related complexity-reducing techniques are approached in this paper from a probabilistic perspective. With both theoretical analysis and simulations, combining SDA with detection ordering is justified. A novel probabilistic search algorithm examining potential candidates in a descending probability order is derived and analyzed. Based on probabilistic search and an error-performance-oriented fast stopping criterion, a computationally efficient layered search is developed. Having comparable decoding complexity to the nulling-canceling (NQ algorithm with detection ordering, simulations confirm that the novel layered search achieves considerable error-performance enhancement.

A low-complexity, high performance demodulation algorithm suitable for ultra-wideband impulse radio (UWB-IR) is developed. Capitalizing on the recently proposed acquisition scheme based on dirty templates (TDT), the novel demodulator can cope with unknown timing offsets, unknown time-hopping spreading codes, and unknown multipath channels. Both data-aided (DA) and non-data-aided (NDA) TDT schemes are considered. Performance of the resultant TDT-based demodulator is evaluated and shown to be robust to timing estimation errors. Comparisons are provided with the UWB-RAKE receiver when timing errors are absent. It is asserted that the TDT-based demodulator outperforms the RAKE with limited number of fingers in the medium to high signal-to-noise-ratio (SNR) range. Analytical results are corroborated by simulations.

A novel random access protocol combining a tree algorithm (TA) with successive interference cancellation (SIC) has been introduced recently. By migrating physical layer benefits to the medium access control (MAC) through a cross-layer approach, SICTA can afford stable throughput as high as 0.693. However, SICTA may lead to deadlocks caused by channel fading and error propagation in error-prone wireless networks. To mitigate such effects, we put forth a truncated version of SICTA that we term SICTA/FS (SICTA with first success). We establish using analysis and simulations that while providing high throughput, SICTA/FS is robust to errors, it is easy to implement, and can be readily incorporated to existing standards.

User cooperation can provide spatial transmit diversity gains, enhance coverage and potentially increase capacity. Existing works have focused on two-user cooperative systems with perfect channel state information at the receivers. In this paper, we develop several distributed space-time processing schemes for general TV-user cooperative systems, which do not require channel state information at either relays or destination. We prove that full spatial diversity gain can be achieved in such systems. Simulations demonstrate that these cooperative schemes achieve significant performance gain.

Synchronization is a factor critically affecting performance of ultra-wideband (UWB) communication systems. We develop a blind synchronization and demodulation scheme which relies on intermittent transmission of nonzero mean symbols. These enable multi-user interference (MUI)- and inter-symbol interference (ISI)-resilient timing acquisition via energy detection and low-complexity demodulation by matching to a synchronized aggregate template (SAT). It turns out that the resultant SAT receiver offers distinct advantages over the widely-deployed RAKE receiver. Its blind operation nicely fits the requirements of multi-user ad hoc access and its ability to handle ISI and MUI is attractive for UWB communications. Analytical performance evaluation and simulations testing our novel scheme confirm its high potential for deployment.

Wireless sensor networks deployed to perform surveillance and monitoring tasks have to operate under stringent energy and bandwidth limitations. These motivate well distributed estimation scenarios where sensors quantize and transmit only one, or a few bits per observation, for use in forming parameter estimators of interest. In a companion paper, we developed algorithms and studied interesting tradeoffs that emerge even in the simplest distributed setup of estimating a scalar location parameter in the presence of zero-mean additive white Gaussian noise of known variance. Herein, we derive distributed estimators based on binary observations along with their error-variance performance for unknown noise pdfs.

We consider the problem of simultaneous estimation of the channel state information (CSI) of several transmitters that use orthogonal space-time block codes to communicate with a single receiver. Based on the generalizations of the Capon and MUSIC techniques, we propose two novel algorithms to estimate multi-user MIMO channels. These algorithms estimate the subspace spanned by the user channels blindly and use only a few training blocks to extract the users' CSI from this subspace.

Consider a codebook containing N unit-norm complex vectors in a K-dimensional space. In a number of applications, the codebook that minimizes the maximal cross-correlation amplitude (I/sub max/) is often desirable. Relying on tools from combinatorial design theory, we construct analytically optimal codebooks meeting, in certain cases, Welch's lower bound. When analytical constructions are not available, we develop an efficient numerical search method based on Lloyd's algorithm, which leads to considerable improvement on the achieved I/sub max/ over existing alternatives. We also derive a composite lower bound on the minimum achievable I/sub max/ that is effective for any N.

Cooperative wireless communication systems have attracted much attention in recent years, due to the diversity advantage they can afford. Existing cooperative transmission modalities have been developed in conjunction with fixed-rate multiplexing based on TDMA, CDMA or FDMA. We advocate user cooperation as the method of choice for enabling diversity in wireless random access networks. The specific protocol developed herein exploits the fact that user cooperation can be viewed as a form of multipath, and capitalizes on the suitability of long pseudo-noise (PN) spreading codes for dealing with multipath channels. Analysis and numerical results confirm that throughput increases considerably when random access via spread-spectrum slotted Aloha protocols is aided by user collaboration.

Differential encoding is known to simplify receiver complexity because it by-passes channel estimation. However, over rapidly fading wireless channels, extra transceiver modules are necessary to enable differential transmission. Relying on a basis expansion model for time and frequency selective (doubly-selective) channels, we derive such a generalized block differential (BD) codec that achieves the maximum Doppler and multi-path diversity gains, while affording low-complexity maximum likelihood (ML) decoding. We further show that existing BD systems over frequency-selective or time-selective channels follow as special cases of our novel system. Simulations corroborate our theoretical analysis.

Wireless sensor networks deployed to perform surveillance and monitoring tasks have to operate under stringent energy and bandwidth limitations. These motivate well distributed estimation scenarios where sensors quantize and transmit only one, or a few bits per observation, for use in forming parameter estimators of interest. In a companion paper, we developed algorithms and studied interesting tradeoffs that emerge even in the simplest distributed setup of estimating a scalar location parameter in the presence of zero-mean additive white Gaussian noise of known variance. Herein, we derive distributed estimators based on binary observations along with their fundamental error-variance limits for more pragmatic signal models: i) known univariate but generally non-Gaussian noise probability density functions (pdfs); ii) known noise pdfs with a finite number of unknown parameters; and iii) practical generalizations to multivariate and possibly correlated pdfs. Estimators utilizing either independent or colored binary observations are developed and analyzed. Corroborating simulations present comparisons with the clairvoyant sample-mean estimator based on unquantized sensor observations, and include a motivating application entailing distributed parameter estimation where a WSN is used for habitat monitoring.

Random access Aloha protocols have well documented merits in terms of simplicity and favorable delay-throughput trade-off under moderate bursty traffic loads. Short spreading codes have been used in conjunction with random access to endow Aloha with benefits originating from spread-spectrum communications. Instead of short, symbol-periodic spreading, this paper considers long pseudo-random (PN) packet-periodic sequences in the context of spread-Aloha and establishes that long PN codes increase the maximum stable throughput by reducing the probability of collisions. Relying on a dominant system approach, we analyze the resultant throughput and demonstrate that increasing the PN code length quickly transforms the collision-limited channel to an interference-limited one. In particular, we investigate how throughput depends on user load and packet length. Finally, we discuss synchronization issues and provide corroborating numerical results.

We consider the problem of minimizing the energy needed for data fusion in a large scale sensor network by varying the transmission times assigned to different sensor nodes. The optimal scheduling protocol is derived, based on which, we develop a low-complexity inverse-log scheduling algorithm that achieves near-optimal energy efficiency. To eliminate the communication overhead required by centralized scheduling protocols, we also develop a distributed inverse-log protocol that is applicable to networks with a large number of nodes. Simulations demonstrate that this distributed scheduling protocol achieves substantial energy savings over uniform time division multiple access protocol.

Contention tree algorithms have provable stability properties, and are known to achieve stable throughput as high as 0.487 for the infinite population Poisson model. A common feature in all these random access protocols is that collided packets at the receive-node are always discarded. In this paper, we derive a novel tree algorithm (TA) that we naturally term SICTA because it relies on successive interference cancellation to resolve collided packets. Performance metrics including throughput and delay are analyzed to establish that SICTA outperforms existing contention tree algorithms reaching 0.693 in stable throughput.

Consider a bandwidth constrained sensor network in which a set of distributed sensors and a fusion center (FC) collaborate to estimate an unknown vector. Due to power and cost limitations, each sensor must compress its data in order to minimize the amount of information that need to be communicated to the FC. In this paper, we consider the design of a linear decentralized estimation scheme (DES) whereby each sensor transmits over a noisy channel to the FC a fixed number of real-valued messages which are linear functions of its observations, while the FC linearly combines the received messages to estimate the unknown parameter vector. Assuming each sensor collects data according to a local linear model, we propose to design optimal linear message functions and linear fusion function according to the minimum mean squared error (MMSE) criterion. We show that the resulting design problem is nonconvex and NP-hard in general, and identify two special cases for which the optimal linear DES design problem can be efficiently solved either in closed form or by semi-definite programming (SDP).

Scheduling plays an important role in providing quality of service (QoS) support for multimedia networks. We propose a cross-layer scheduler at the medium access control (MAC) layer for multiple connections with diverse QoS requirements, where each connection employs adaptive modulation and coding (AMC) scheme at the physical (PHY) layer. Each connection is assigned a priority, which is updated dynamically based on its channel and service quality; and the connection with the highest priority is scheduled each time. Our scheduler provides diverse QoS guarantees, uses the wireless bandwidth efficiently and enjoys flexibility, scalability and low implementation complexity. The performance of our scheduler is evaluated via simulations in the IEEE 802.16 standard setting.

Providing guaranteed quality-of-service (QoS) for multimedia applications over wireless fading channels is challenging. To this end, we develop a cross-layer design for multiuser scheduling at the data link layer, with each user employing adaptive modulation and coding (AMC) at the physical layer. By classifying users into: QoS-guaranteed and best-effort users, the proposed scheduler enables prescribed QoS guarantees and efficient bandwidth utilization simultaneously. Furthermore, our cross-layer scheduler enjoys low-complexity implementation and analysis, provides service isolation and scalability, decouples delay from dynamically-scheduled bandwidth, and is backward compatible with existing separate-layer designs. Accuracy of the performance analysis is verified by simulations and pertinent robustness issues are briefly discussed. Numerical examples illustrate the steady-state statistical performance for a single and multiple users, as well as the asymptotic behavior for a large number of users.

We consider point-to-point wireless links with multiple antennas in the presence of interference, and exploit channel's spatial correlation and the temporal covariance of the interference to design multiantenna transmitters. We develop a space-time spreading scheme that maximizes average signal-to-interference-and-noise ratio, and an optimally power-loaded space-time beamforming (STBF) scheme which improves error-probability performance. In order to increase transmission rates, we combine orthogonal space-time block coding with STBF, optimize power loading across beams, and develop low-complexity receivers. Optimal training for least-squares error channel estimation, and STBF for minimum mean-square error channel estimation, are also studied. Our analytical and simulated results corroborate that STBF with optimal power loading can considerably reduce error probability and channel-estimation errors.

Relayed transmissions enable low-power communications among nodes (possibly separated by a large distance) in wireless networks. Since the capacity of general relay channels is unknown, we investigate the achievable rates of relayed transmissions over fading channels for two transmission schemes: the block Markov coded and the time-division multiplexed (TDM) transmissions. The normalized achievable minimum energy per bit required for reliable communications is derived, which also enables optimal power allocation between the source and the relay. The time-sharing factor in TDM transmissions is optimized to improve achievable rates. The region where relayed transmission can provide a lower minimum energy per bit than direct transmission, as well as the optimal relay placement for these two transmission schemes, are also investigated. Numerical results delineate the advantages of relayed, relative to direct, transmissions.

Differential encoding is known to simplify receiver implementation because it by-passes channel estimation. However, over rapidly fading wireless channels, extra transceiver modules are necessary to enable differential transmission. Relying on a basis expansion model for time and frequency selective (doubly selective) channels, we derive such a generalized block-differential (BD) codec and prove that it achieves maximum Doppler and multipath diversity gains, while affording low-complexity maximum-likelihood decoding. We further show that existing BD systems over frequency-selective or time-selective channels follow as special cases of our novel system. Simulations using the widely accepted Jakes' model corroborate our theoretical analysis.

We design pilot-symbol-assisted modulation for carrier frequency offset (CFO) and channel estimation in orthogonal frequency-division multiplexing transmissions over multi-input multi-output frequency-selective fading channels. The CFO and channel-estimation tasks rely on null-subcarrier and nonzero pilot symbols that we insert and hop from block to block. Because we separate CFO and channel estimation from symbol detection, the novel training patterns lead to further decoupled CFO and channel estimators. The performance of our algorithms is investigated analytically, and then compared with an existing approach by simulations.

Adaptive modulation has the potential to increase system throughput considerably by adapting transmission parameters to the time-varying channel characteristics. Crucial to adaptive systems is the requirement of a feedback channel, that is often capable of carrying only a limited number of bits. Under such a bandwidth-constrained feedback link, we aim to optimize a multiantenna system based on transmit beamforming and adaptive modulation, where the transmit power, the signal constellation, the beamforming direction, and the feedback strategy, are designed jointly. Our proposed nested iterative approach leads to an approximate, yet practical, solution. Simulation results demonstrate considerable improvement in transmission rate, as the number of feedback bits increases.

Ultra-wideband (UWB) technology for indoor wireless communications promises high data rates with low-complexity transceivers. Rapid timing synchronization constitutes a major challenge in realizing these promises. In this paper, we establish a novel synchronization criterion that we term "timing with dirty templates" (TDT), based on which we develop and test timing algorithms in both data-aided (DA) and nondata-aided modes. For the DA mode, we design a training pattern, which turns out to not only speed up synchronization, but also enable timing in a multiuser environment. Based on simple integrate-and-dump operations over the symbol duration, our TDT algorithms remain operational in practical UWB settings. They are also readily applicable to narrowband systems when intersymbol interference is avoided. Simulations confirm performance improvement of TDT relative to existing alternatives in terms of mean square error and bit-error rate.

Relying on a kurtosis-type criterion, we develop a low-complexity blind carrier frequency offset (CFO) estimator for orthogonal frequency-division multiplexing (OFDM) systems. We demonstrate analytically how identifiability and performance of this blind CFO estimator depend on the channel's frequency selectivity and the input distribution. We show that this approach can be applied to blind CFO estimation in multi-input multi-output and multiuser OFDM systems. The issues of channel nulls, multiuser interference, and effects of multiple antennas are addressed analytically, and tested via simulations.

We consider the problem of minimizing the energy needed for data fusion in a sensor network by varying the transmission times assigned to different sensor nodes. The optimal scheduling protocol is derived, based on which we develop a low-complexity inverse-log scheduling (ILS) algorithm that achieves near-optimal energy efficiency. To eliminate the communication overhead required by centralized scheduling protocols, we further derive a distributed inverse-log protocol that is applicable to networks with a large number of nodes. Focusing on large-scale networks with high total data rates, we analyze the energy consumption of the ILS. Our analysis reveals how its energy gain over traditional time-division multiple access depends on the channel and the data-length variations among different nodes.

We start by identifying a relatively efficient version of sphere decoding algorithm (SDA) that performs exact maximum-likelihood (ML) decoding. We develop novel algorithms based on an improved increasing radius search (IIRS), which offer error performance and decoding complexity between two extremes: the ML receiver and the nulling-canceling (NC) receiver with detection ordering. With appropriate choices of parameters, our IIRS offers the flexibility to trade error performance for complexity. We provide design intuitions and guidelines, analytical parameter specifications, and a semianalytical error-performance analysis. Simulations illustrate that IIRS achieves considerable complexity reduction, while maintaining performance close to ML.

Consider a codebook containing N unit-norm complex vectors in a K-dimensional space. In a number of applications, the codebook that minimizes the maximal cross-correlation amplitude (I/sub max/) is often desirable. Relying on tools from combinatorial number theory, we construct analytically optimal codebooks meeting, in certain cases, the Welch lower bound. When analytical constructions are not available, we develop an efficient numerical search method based on a generalized Lloyd algorithm, which leads to considerable improvement on the achieved I/sub max/ over existing alternatives. We also derive a composite lower bound on the minimum achievable I/sub max/ that is effective for any codebook size N.

Adaptive modulation requires channel state information (CSI), which can be acquired at the receiver by inserting pilot symbols in the transmitted signal. We first analyze the effect linear minimum mean square error (MMSE) channel estimation and prediction errors have on bit-error rate (BER). Based on this analysis, we develop adaptive pilot symbol assisted modulation (PSAM) schemes that account for both channel estimation and prediction errors to meet a target BER. While pilot symbols facilitate channel acquisition, they consume part of transmitted power and bandwidth, which in turn, reduces spectral efficiency. With imperfect (and thus, partial) CSI available at the transmitter and receiver, two questions arise naturally: how often should pilot symbols be transmitted, and how much power should be allocated to pilot symbols. We address these two questions by optimizing pilot parameters to maximize spectral efficiency.

Assuming there are always sufficient data waiting to be transmitted, adaptive modulation and coding (AMC) schemes at the physical layer have been traditionally designed separately from higher layers. However, this assumption is not always valid when queuing effects are taken into account at the data link layer. In this paper, we analyze the joint effects of finite-length queuing and AMC for transmissions over wireless links. We present a general analytical procedure, and derive the packet loss rate, the average throughput, and the average spectral efficiency (ASE) of AMC. Guided by our performance analysis, we introduce a cross-layer design, which optimizes the target packet error rate of AMC at the physical layer, to minimize thpacket loss rate and maximize the average throughput, when combined with a finite-length queue at the data link layer. Numerical results illustrate the dependence of system performance on various parameters, and quantify the performance gain due to cross-layer optimization. Our focus is on the single user case, but we also discuss briefly possible applications to multiuser scenarios.

High data rates give rise to frequency-selective propagation effects. Space-time multiplexing and/or coding offer attractive means of combating fading and boosting capacity of multi-antenna communications. As the number of antennas increases, channel estimation becomes challenging because the number of unknowns increases, and the power is split at the transmitter. Optimal training sequences have been designed for flat-fading multi-antenna systems or for frequency-selective single transmit antenna systems. We design a low-complexity optimal training scheme for block transmissions over frequency-selective channels with multiple antennas. The optimality in designing our training schemes consists of maximizing a lower bound on the ergodic (average) capacity that is shown to be equivalent to minimizing the mean square error of the linear channel estimator. Simulation results confirm our theoretical analysis that applies to both single- and multicarrier transmissions.

Cooperative diversity (CD) networks have been receiving a lot of attention recently as a distributed means of improving error performance and capacity. For sufficiently large signal-to-noise ratio (SNR), this paper derives the average symbol error probability (SEP) for analog forwarding CD links. The resulting expressions are general as they hold for an arbitrary number of cooperating branches, arbitrary number of cooperating hops per branch, and various channel fading models. Their simplicity provides valuable insights to the performance of CD networks and suggests means of optimizing them. Besides revealing the diversity, they clearly show from where this advantage comes from and prove that presence of diversity does not depend on the specific (e.g., Rayleigh) fading distribution. Finally, they explain how diversity is improved in multihop CD networks.

Realizing the great potential of impulse radio communications depends critically on the success of timing acquisition. To this end, optimum data-aided (DA) timing offset estimators are derived in this paper based on the maximum likelihood (ML) criterion. Specifically, generalized likelihood ratio tests (GLRTs) are employed to detect an ultrawideband (UWB) waveform propagating through dense multipath and to estimate the associated timing and channel parameters in closed form. Capitalizing on the pulse repetition pattern, the GLRT boils down to an amplitude estimation problem, based on which closed-form timing acquisition estimates can be obtained without invoking any line search. The proposed algorithms only employ digital samples collected at a low symbol rate, thus reducing considerably the implementation complexity and acquisition time. Analytical acquisition performance bounds and corroborating simulations are also provided.

The overall system efficiency of impulse radio communications relies critically on judicious allocation of transmission resources, a portion of which should be used to ensure successful timing acquisition. In data-aided mode, optimum timing offset estimation depends not only on the mechanism used for energy capture and the acquisition algorithm employed to recover timing information, but also on the training sequence (TS) pattern from which the timing information is to be extracted. Furthermore, the transmission resources used for timing have to be balanced with that for conveying information messages in order to strike desirable tradeoffs between timing accuracy and information rate. In Part I of this paper, data-aided timing offset estimation is derived based on the maximum likelihood (ML) criterion, where only symbol-rate samples are needed for low-complexity receiver processing. To minimize the mean-square timing errors of these ML synchronizers while at the same time maximizing the average system capacity, TS design and transmit power allocation are investigated in this paper. The optimum training pattern and the number, placement, and power distribution between training and information-bearing symbols are formulated as a resource allocation optimization problem whose solution optimizes system-level performance with the minimum amount of resources consumed.

Relay links are expected to play a critical role in the design of wireless networks. This paper investigates the energy efficiency of relay communications in the low-power regime under two different scenarios: when the relay has unlimited power supply and when it has limited power supply. A system with a source node, a destination node, and a single relay operating in the time division duplex (TDD) mode was considered. Analysis and simulations are used to compare the energy required for transmitting one information bit in three different relay schemes: amplify and forward (AnF), decode and forward (DnF), and block Markov coding (BMC). Relative merits of these relay schemes in comparison with direct transmissions (direct Tx) are discussed. The optimal allocation of power and transmission time between source and relay is also studied.

Power loading algorithms improve the data rates of orthogonal frequency division multiplexing (OFDM) systems. However, they require the transmitter to have perfect channel state information, which is impossible in most wireless systems. We investigate the effects of imperfect (and thus partial) channel feedback on the throughput of OFDM systems. Two channel uncertainty models are studied: 1) the ergodic model, where average rate is the figure of merit and 2) the quasi-static model, where outage rate is relevant. Rate-power allocation algorithms are developed. The throughput achieved by these algorithms and the effects of channel multipath are investigated analytically and with simulations.

Layered space-time (LST) transmissions employing continuous phase modulations (CPM) are well motivated for both bandwidth- and power-limited multiantenna communications. However, one of the major challenges for LST-CPM is the high complexity it incurs with maximum likelihood (ML) detection. In this paper, we develop reduced complexity LST-CPM receivers. First, we consider single antenna systems. Specifically, we study a reduced complexity Viterbi receiver for binary CPM. Based on this design, we introduce differential encoding for a class of CPM signals and analyze its performance gain both theoretically and with simulations. Second, we focus on multiantenna LST systems with minimum shift-keying (MSK)-type modulations. With group nulling-canceling (NC) and low-complexity linear equalization, we convert a coded multiuser detection problem into an uncoded one with small equalization loss. We also find that the combination of sphere decoding with hard-decision iterative processing is effective in boosting performance with a controllable complexity increase. Both analytical and simulated performance confirm that the novel LST-MSK receiver exhibits markedly improved performance relative to conventional NC detectors with moderate complexity increase.

Providing guaranteed quality of service (QoS) with efficient bandwidth utilization over wireless fading channels is challenging. In this paper, we derive the throughput, the packet loss rate and the average delay of an end-to-end wireless link, where the transmitter relies on adaptive modulation and coding (AMC) at the physical layer while accounting for finite-length buffer effects at the data link layer. Guided by our cross-layer performance analysis, we develop a simple procedure to determine the minimal required bandwidth, which guarantees the prescribed QoS over the wireless link.

We develop a model for decentralized opportunistic transmissions of a finite (n) user slotted ALOHA system that relies on decentralized channel state information (D-CSI). D-CSI refers to each user node having access only to its own uplink channel gain. Every user adapts both rate and re-transmission probability to D-CSI in every slot. Due to the variable transmission rate from slot to slot, incoming packets with fixed length are re-assembled to deliver as many bits as possible per slot. By modeling the number of bits in queues as a discrete Markov chain, we analyze the stability region and the maximum stable throughput (MST). In addition, we derive a decentralized opportunistic scheme and show that it achieves a fraction (1-1/n)/sup n-1/ of its centralized counterpart's throughput, where (1-1/n)/sup n-1/ is a factor due to the inherent contention in random access.

Within a new paradigm, where wireless user cooperation is viewed as a form of (opportunistic) multipath, we exploit the unique capabilities of direct-sequence spread spectrum transmissions in handling multipath to design a novel spectrally efficient protocol for wireless cooperative networks. We show how and why our proposed system achieves diversity without increasing bandwidth. After analyzing its performance, we deduce that user capacity can be significantly improved with respect to existing third generation cellular systems in the uplink. This is particularly interesting since our scheme can be readily integrated in such networks without major changes in the existing standards.

Realizing the benefits of ultra-wideband (UWB) communications hinges critically on judicious pulse shape design to enable UWB spectral mask compatibility, and co-existence with and adaptation to other wireless devices. To this end, we propose a convex optimization based waveform design method for UWB radios. By casting the pulse design problem as a (convex) semidefinite program (SDP) over the pulse autocorrelation, globally optimal waveform designs can be efficiently obtained. While the focus of this paper is on the design of waveforms that optimally utilize the bandwidth and power allowed by the spectral mask, the flexibility of the SDP framework also allows the optimization of several other system objectives.

Ultra-wideband (UWB) radio is gaining increasing attention thanks to its attractive features that include low-power low-complexity baseband operation and ample multipath diversity. Realization of its potential, however, faces the challenge of low-complexity high-performance timing acquisition. In this paper, we develop a blind timing acquisition algorithm for frame-level synchronization. Relying on simple integrate-and-dump operations over one symbol duration, our algorithm exploits the rich multipath diversity enabled by UWB transmissions. It outperforms existing blind algorithms and has comparable performance to data-aided ones. Equally attractive is its applicability to UWB links with or without time hopping (TH), over frequency-flat or multipath channels. It is also worth stressing that our "dirty" template based scheme is able to achieve timing synchronization at any desirable resolution and is readily applicable to non-UWB systems, so long as intersymbol interference is absent.

Demand for high data rate leads to frequency-selective propagation effects, whereas carrier frequency-offsets and Doppler effects induced by mobility introduce time-selectivity in wireless links. These fading channels, once acquired, offer joint multipath-Doppler diversity gains. In addition, space-time multiplexing and/or coding offer attractive means of combating fading, and boosting capacity of multi-antenna communications. As the number of antennas increases, channel estimation becomes challenging because the number of unknowns increases, and the power is split at the transmitter. Optimal training sequences have so far been designed for flat-fading and frequency-selective multi-antenna systems. In this paper, we design a low complexity optimal training scheme for block transmissions over time-and frequency (a.k.a. doubly)- selective channels with multiple antennas. The optimality in designing our training schemes consists of maximizing a lower bound on the ergodic (average) capacity that is shown to be equivalent to minimizing the mean-square error of the linear channel estimator. Simulation results confirm our theoretical analysis which applies to both single- and multi-carrier transmissions.

We investigate the information regularity and identifiability of the blind source separation problem with constant modulus constraints on the sources. We demonstrate that the information regularity (existence of a finite Cramer-Rao bound) is closely related to local identifiability. Sufficient and necessary conditions for local identifiability are derived. We also study the conditions under which unique (global) identifiability is guaranteed within the inherently unresolvable ambiguities on phase rotation and source permutation. Both sufficient and necessary conditions are obtained.

We study a wireless access system with adaptive modulation and coding (AMC) at the physical layer, finite-length queuing at the data link layer and a TCP protocol at the transport layer. We analyze the end-to-end TCP performance via a fixed-point procedure that effectively couples TCP with the AMC-based wireless link. Guided by the performance analysis, we present a simple cross-layer design, which optimizes the target packet error rate in AMC at the physical layer, so that the TCP throughput at the transport layer is maximized.

Channels with long impulse response often arise in high-rate digital transmissions due to severe multipath. This necessitates sophisticated equalization at the receiver. On the other hand, exploiting the available multipath diversity improves bit error performance. To collect the full multipath diversity, computationally cumbersome maximum likelihood sequence estimation (MLSE) is required. Although the Viterbi algorithm (VA) for MLSE is more efficient than the exhaustive ML search, its complexity increases exponentially with the channel length, which varies with the propagation environment. Since the computational power of the receiver is limited, VA becomes infeasible for long channels. In this paper, we develop a transmission capable of handling relatively long channels. The transmitter controls the computational complexity of MLSE at the receiver by periodically inserting zeros within information-bearing symbols, depending on the channel length and the computational power of the receiver. The optimal MLSE with reduced complexity becomes available at the expense of reduced data rate.

Cooperative diversity (CD) networks have been receiving a lot of attention recently as a distributed means of improving error performance and capacity. This paper derives the average symbol error probability (SEP) for amplify and forward CD links. The resulting expressions are general as they hold for an arbitrary number of cooperating branches, arbitrary number of cooperating hops per branch, and many channel fading models. Their simplicity provides valuable insights to the performance of CD networks and allows their optimization. Besides revealing the diversity advantage, they clearly show from where this advantage comes from and prove that the diversity advantage holds independently of the channel fading model. Finally, explain how diversity is improved in multihop CD networks.

Linear precoding is a well known effective technique to boost the performance of orthogonal frequency-division multiplexing (OFDM) systems. A drawback of linearly precoded OFDM (LP-OFDM) systems is the high computational complexity required by maximum-likelihood (ML) detection, which is mandatory to capture all the channel diversity. Conversely, low-complexity techniques, such as the linear minimum mean-squared error (MMSE) detection, suffer from nonnegligible performance loss with respect to the ML performance. This paper proposes a detection technique that performs a local ML (LML) search in the neighborhood of the output provided by the MMSE detector. The trade-off between performance and complexity of the proposed LML-MMSE detector, which fall between the ones of the MMSE and ML detectors, can be nicely adjusted by appropriately setting the neighborhood size. Simulation results show that the LML-MMSE detector with minimum neighborhood size outperforms a block decision-feedback equalization (DFE) approach, while preserving a similar complexity.

The overall system efficiency of impulse radio communications relies critically on judicious allocation of transmission resources, a portion of which should be used to ensure successful timing acquisition. Data-aided timing offset estimation has been derived by the authors based on the maximum likelihood (ML) criterion, where only symbol-rate samples are needed for low-complexity receiver processing. To minimize the mean-square timing errors of these ML synchronizers while at the same time maximizing the average system capacity, the training sequence design and the transmit power allocation are investigated in this paper. The optimum training pattern, as well as the number, placement, and power allocation of training vs. information-bearing symbols, are formulated as a resource allocation optimization problem, whose solution offers the optimum system-level performance with the minimum amount of resources consumed.

Relay links are expected to play a critical role in the design of wireless networks. In this paper, we investigate the energy efficiency of relay communications under two different scenarios: when the relay has unlimited and when it has limited power supply. Relative merits of these relay schemes in comparison with direct transmissions are discussed.

Wired-wireless multimedia networks require diverse quality-of-service (QoS) support. To this end, it is essential to rely on QoS metrics pertinent to wireless links. In this paper, we develop a cross-layer model for adaptive wireless links, which enables derivation of the desired QoS metrics analytically from the typical wireless parameters across the hardware-radio layer, the physical layer and the data link layer. We illustrate the advantages of our model: generality, simplicity, scalability and backward compatibility. Finally, we outline its applications to power control, TCP, UDP and bandwidth scheduling in wireless networks.

As low power, low cost and longevity of transceivers are major requirements in wireless sensor networks, optimizing their design under energy constraints is of paramount importance. To this end, we develop quantizers under strict energy constraints to effect optimal reconstruction at the fusion center. Propagation, modulation, as well as transmitter and receiver structures are jointly accounted for using a binary symmetric channel model. We first optimize quantization for reconstructing a single sensor's measurement. Optimal number of quantization levels and optimal energy allocation across bits are derived. We then consider multiple sensors collaborating to estimate a deterministic parameter in noise. Similarly, optimum energy allocation and optimum number of quantization bits are derived analytically and tested with simulated examples.

Hard sphere-decoding (SD) has well appreciated merits for near-optimal demodulation of multiuser, block single-antenna, or, multiantenna transmissions over multiinput multioutput (MIMO) channels. At increased complexity, a soft version of SD, so termed list SD (LSD), has been recently applied to coded layered space-time (LST) systems enabling them to approach MIMO channel capacity. By introducing a novel bit-level multistream LST transmitter along with a soft-to-hard decoder conversion, we show how to achieve the near-capacity performance of LSD at reduced complexity, and even outperform it as the size of the block to be decoded (M) increases. Specifically, for binary real LST codes we develop exact max-log based SD schemes with average complexity O(M/sup 4/), and various approximate alternatives trading-off performance for average complexity down to O(M/sup 3/). These schemes apply directly to the real and imaginary parts of QPSK signalling, and also to QAM signalling after incorporating an appropriate interference estimation and cancellation module. We corroborate our reduced-complexity near-optimal soft SD algorithms with simulations.

We analyze the stability properties of slotted Aloha with capture for random access over fading channels when the number of users is very large. We consider the most commonly used power capture model, namely the one based on signal-to-interference-plus-noise ratio (SINK). Existing works have shown that for this model the capture capability alone can stabilize the slotted Aloha when the distribution of the received user power satisfies certain conditions. However, our analysis shows that as long as the received powers of all the users are independent and identically distributed with finite mean, the system is unstable. We further establish that power or probability control based on decentralized channel state information (CSI) can not render an infinite-user system stable.

This work first identifies the most efficient version of the sphere decoding algorithms (SDA) We then develop a novel SDA based on an improved increasing radius search (IIRS), which essentially achieves maximum likelihood (ML) error performance with considerable complexity reduction and provides both design intuition and analytical parameter specification. A probabilistic trimming approach, which exploits both channel realizations and the noise distribution is also introduced. Simulations confirm our claims on both the IIRS and the probabilistic trimming aspects.

In the presence of frequency-selective multipath fading channels, code-division multiple access (CDMA) suffers from multiuser interference (MUI) and intersymbol interference (ISI); but when properly designed, it enjoys multipath diversity. Orthogonal frequency-division multiple access (OFDMA) is MUI-free, but it does not enable the available channel diversity without employing error-control coding. On the other hand, coded OFDMA may achieve lower diversity than a CDMA system employing the same error-control codes. In this paper, we merge the advantages of OFDMA and CDMA to minimize MUI effects, and also enable the maximum available diversity for every user. In our group orthogonal multicarrier CDMA (GO-MC-CDMA) scheme, groups of users share a set of subcarriers. By judiciously choosing group subcarriers, we guarantee that every user transmits with maximum diversity. MUI is only present among users in the same group, and is suppressed via multiuser detection, which becomes practically feasible because we assign a small number of users per group. Performance is analyzed, and simulations are carried out to illustrate the merits of GO-MC-CDMA relative to existing alternatives.

Frequency-selective channels can be converted to a set of flat-fading subchannels by employing orthogonal frequency-division multiplexing (OFDM). Conventional differential encoding on each subchannel, however, suffers from loss of multipath diversity, and a very high peak-to-average power ratio (PAPR), which causes undesirable nonlinear effects. To mitigate these effects, we design a block differential encoding scheme over the subchannels that preserves multipath diversity, and in addition, results in constant modulus transmitted symbols. This property is shown to ensure that the PAPR of the continuous-time transmitted waveform is reduced by a large factor. The maximum-likelihood decoder for the proposed scheme, conditioned on the current and previous received block, is shown to have linear complexity in the number of subcarriers. The constant modulus scheme will yield good bit-error rate performance with full rate only if short blocks are used. However, one may mitigate this problem by relaxing the constant modulus requirement. We show that in a practical OFDM system, we can group the subcarriers into shorter subblocks in a certain manner, and apply the constant modulus technique to each subblock. Thus, we improve diversity at a very low decoder complexity, and at the same time, we introduce an upper bound on the discrete-time PAPR, which, in turn, may lead to appreciable reduction in continuous-time PAPR, depending on the system parameters. Finally, in situations where we can sacrifice rate, additional complex field coding may be used to exploit the multipath diversity provided by channels longer than those the simple scheme can handle.

Frequency-shift keying (FSK) is a popular modulation scheme in power-limited communication links. This paper introduces space-time FSK (ST-FSK), which does not require any channel state information at the transmitter and the receiver, as in conventional noncoherent FSK. ST-FSK can be viewed as a special unitary ST modulation design. However, ST-FSK has a number of advantages over existing unitary ST modulation designs. ST-FSK is easier to design, and enjoys lower decoding complexity. Furthermore, ST-FSK guarantees full diversity. Finally, ST-FSK can be adopted in the digital as well as in the analog domain, and merges very naturally with frequency-hopping multiple access. As expected, all these advantages come at the cost of a decrease in spectral efficiency.

Rapidly fading channels provide Doppler-induced diversity, but are also challenging to estimate. To bypass channel estimation, we derive two novel block differential (BD) codecs. Relying on a basis expansion model for time-varying channels, our differential designs are easy to implement, and can achieve the maximum possible Doppler diversity. The first design (BD-I) relies on a time-frequency duality, based on which we convert a time-varying channel into multiple frequency-selective channels, and subsequently into multiple flat-fading channels using orthogonal frequency-division multiplexing. Combined with a group partitioning scheme, BD-I offers flexibility to trade off decoding complexity with performance. Our second block differential design (BD-II) improves the bandwidth efficiency of BD-I at the price of increased complexity at the receiver, which relies on decision-feedback decoding. Simulation results corroborate our theoretical analysis, and compare with competing alternatives.

We compare two block transmission systems over frequency-selective fading channels: orthogonal frequency-division multiplexing (OFDM) versus single-carrier modulated blocks with zero padding (ZP). We first compare their peak-to-average power ratio (PAR) and the corresponding power amplifier backoff for phase-shift keying or quadrature amplitude modulation. Then, we study the effects of carrier frequency offset on their performance and throughput. We further compare the performance and complexity of uncoded and coded transmissions over random dispersive channels, including Rayleigh fading channels, as well as practical HIPERLAN/2 indoor and outdoor channels. We establish that unlike OFDM, uncoded block transmissions with ZP enjoy maximum diversity and coding gains within the class of linearly precoded block transmissions. Analysis and computer simulations confirm the considerable edge of ZP-only in terms of PAR, robustness to carrier frequency offset, and uncoded performance, at the price of slightly increased complexity. In the coded case, ZP is preferable when the code rate is high (e.g., 3/4), while coded OFDM is to be preferred in terms of both performance and complexity when the code rate is low (e.g., 1/2) and the error-correcting capability is enhanced. As ZP block transmissions can approximate serial single-carrier systems as well, the scope of the present comparison is broader.

Ultra-wideband (UWB) transmissions have well-documented advantages for low-power, peer-to-peer, and multiple-access communications. Space-time coding (STC), on the other hand, has gained popularity as an effective means of boosting rates and performance. Existing UWB transmitters rely on a single antenna, while ST coders have mostly focused on digital linearly modulated transmissions. In this paper, we develop ST codes for analog (and possibly nonlinearly) modulated multiantenna UWB systems. We show that the resulting analog system is able to collect not only the spatial diversity, but also the multipath diversity inherited by the dense multipath channel, with either coherent or noncoherent reception. Simulations confirm a considerable increase in both bit-error rate performance and immunity against timing jitter, when wedding STC with UWB transmissions.

The location, number, and power of pilot symbols embedded in multicarrier block transmissions over rapidly fading channels, are important design parameters affecting not only channel estimation performance, but also channel capacity. Considering orthogonal frequency-division multiplexing (OFDM) systems with decoupled information-bearing symbols from pilot symbols transmitted over wireless frequency-selective Rayleigh-fading channels, we show that equispaced and equipowered pilot symbols are optimal in terms of minimizing the mean-square channel estimation error. We also design the number of pilots, and the power distributed between information bearing and pilot symbols, using as criterion a lower bound on the average capacity. Numerical results corroborate our theoretical findings.

We derive analytical expressions for the probability density function (pdf) of the random mutual information between transmitted and received vector signals of a random space-time independent and identically distributed (i.i.d.) multiple-input multiple-output (MIMO) channel, assuming that the transmitted signals from the multiple antennas are Gaussian i.i.d.. We show that this pdf can be well approximated by a Gaussian distribution, and such a Gaussian approximation is based on expressions for the given pdfs mean and variance that we derive. We prove that at high signal-to-noise ratio (SNR), every factor of 2 increase in SNR leads to an increase in outage rate in the amount of min(M,N) bits, where M and N denote the number of transmit and receive antennas, respectively. A simple expression for the moment generating function (MGF) of the mutual information pdf is also provided, based on which we establish normality of the pdf, when both M and N are large, and the SNR is large.

We construct unitary noncoherent space-time constellations, which can be considered as a concatenation of a training block with an orthogonal design. With a simple construction, our constellations are easy to design, enjoy full antenna diversity, allow for a simplified maximum-likelihood (ML) detector, and achieve error performance comparable to existing designs that rely on computer search. To exploit the constellation structures and improve coding gains, we further pursue a trellis-coded modulation (TCM) approach. Based on the sequence pairwise error analysis, we identify two simple parameters to quantify the asymptotic error performance, which enables us to compare among different TCM schemes or uncoded alternatives.

We analyze the average symbol error rate (SER) of M-PSK and M-QAM modulations with transmit antenna selection diversity (SD) and receive generalized selection combining (GSC) in Rayleigh fading channels. SER formulas are derived in closed form, and numerical results show that transmit SD and receive GSC are flexible to tradeoff performance for complexity.

We developed a cross-layer design which combines adaptive modulation and coding at the physical layer with a truncated automatic repeat request protocol at the data link layer, in order to maximize spectral efficiency under prescribed delay and error performance constraints. We derive the achieved spectral efficiency in closed-form for transmissions over Nakagami-m block fading channels. Numerical results reveal that retransmissions at the data link layer relieve stringent error control requirements at the physical layer, and thereby enable considerable spectral efficiency gain. This gain is comparable with that offered by diversity, provided that the maximum number of transmissions per packet equals the diversity order. Diminishing returns on spectral efficiency, that result when increasing the maximum number of retransmissions, suggest that a small number of retransmissions offers a desirable delay-throughput tradeoff, in practice.

Fair queueing (FQ) algorithms, which have been proposed for quality of service (QoS) wireline/wireless networking, rely on the fundamental idea that the service rate allocated to each user is proportional to a positive weight. Targeting wireless data networks with a multicode CDMA-based physical layer, we develop FQ with time-varying weight assignment in order to minimize the queueing delays of mobile users. Applying dynamic programming, we design a computationally efficient algorithm which produces the optimal service rates while obeying 1) constraints imposed by the underlying physical layer and 2) QoS requirements. Furthermore, we study how information about the underlying channel quality can be incorporated into the scheduler to improve network performance. Simulations illustrate the merits of our designs.

We combine error-control coding with linear precoding (LP) for flat-fading channels, as well as for wireless orthogonal frequency-division multiplexing transmissions through frequency-selective fading channels. The performance is analyzed and compared with the corresponding error-control-coded system without precoding. By wedding LP with conventional error-control coding, the diversity order becomes equal to the error-control code's minimum Hamming distance times the precoder size. We also derive a low-complexity turbo-decoding algorithm for joint coded-precoded transmissions. We analyze the decoding complexity and compare it with an error-control-coded system without LP. Extensive simulations with convolutional and turbo codes for HiperLan/2 channels support the analysis and demonstrate superior performance of the proposed system.

Ultrawideband (UWB) transmissions induce pronounced frequency-selective fading effects in their multipath propagation. Multipath diversity gains can be collected to enhance performance, provided that the underlying channel can be estimated at the receiver. To this end, we develop a novel pilot waveform assisted modulation (PWAM) scheme that is tailored for UWB communications. We select our PWAM parameters by jointly optimizing channel estimation performance and information rate. The resulting transmitter design maximizes the average capacity, which is shown to be equivalent to minimizing the mean-square channel estimation error, and thereby achieves the Crame/spl acute/r-Rao lower bound. Application of PWAM to practical UWB systems is promising because it entails simple integrate-and-dump operations at the frame rate. Equally important, it offers a flexible UWB channel estimator, capable of striking desirable rate-performance tradeoffs depending on the channel coherence time.

Adaptive modulation improves the system throughput considerably by matching transmitter parameters to time-varying wireless fading channels. Crucial to adaptive modulation is the quality of channel state information at the transmitter. In this paper, we first present a channel predictor based on pilot symbol assisted modulation for multiple-input multiple-output Rayleigh fading channels. We then analyze the impact of the channel prediction error on the bit error rate performance of a transmit-beamformer with adaptive modulation that treats the predicted channels as perfect. Our numerical results reveal the critical value of the normalized prediction error, below which the predicted channels can be treated as perfect by the adaptive modulator; otherwise, explicit consideration of the channel imperfection must be accounted for at the transmitter.

Adaptive modulation has the potential to increase the system throughput significantly by matching transmitter parameters to time-varying channel conditions. However, adaptive modulation schemes that rely on perfect channel state information (CSI) are sensitive to CSI imperfections induced by estimation errors and feedback delays. In this paper, we design adaptive modulation schemes for multiantenna transmissions based on partial CSI, that models the spatial fading channels as Gaussian random variables with nonzero mean and white covariance, conditioned on feedback information. Based on a two-dimensional beamformer, our proposed transmitter optimally adapts the basis beams, the power allocation between two beams, and the signal constellation, to maximize the transmission rate, while maintaining a target bit-error rate. Adaptive trellis-coded multiantenna modulation is also investigated. Numerical results demonstrate the rate improvement, and illustrate an interesting tradeoff that emerges between feedback quality and hardware complexity.

A so-termed chip-interleaved block-spread (CIBS) code division multiple access (CDMA) system has been introduced for cellular applications in the presence of frequency selective multipath channels. In both uplink and downlink operation, CIBS-CDMA achieves multiuser-interference (MUI) free reception within each cell. This paper focuses on the cellular downlink configuration and compares CIBS-CDMA against the conventional direct-sequence (DS) CDMA system, which relies on a chip equalizer to restore code orthogonality and, subsequently, suppresses MUI by despreading. We provide a unifying framework for both systems and investigate their performance in the presence of intercell interference and soft-handoff operation. Extensive comparisons from load, performance, complexity, and flexibility perspectives illustrate the merits, along with the disadvantages, of CIBS-CDMA over DS-CDMA, and reveal its potential for future wireless systems.

Abstract A full‐diversity full‐rate (FDFR) multi‐antenna system was developed recently, enabling uncoded layered space‐time (LST) transmissions to achieve full‐diversity (Nt) and full‐rate (Ntsymbols per channel use) simultaneously, for any number of transmit antennasNtand receive antennasNr. In this paper, we investigate the performance of a coded FDFR design obtained by concatenating an error control coding (ECC) module and FDFR module with a random interleaver in between. Turbo decoding is performed at the receiver. WithRcdenoting the ECC rate,dminthe minimum Hamming distance of the ECC, andMthe constellation size, an overall transfer rate ofRcNtlog2Mbits per channel use and a full diversity orderdminNtNrare achieved. Different ECC choices are considered. Approximate analysis reveals that multi‐stream ECC and single‐stream ECC make no difference when convolutional codes with long frame length and near‐optimal MIMO decoding schemes are adopted. Without sacrificing rate, the coded FDFR system improves error performance compared with coded V‐BLAST, when relatively weak codes are used. AsNrincreases, even strong codes such as rate 1/2 turbo codes can benefit from FDFR. Specifically, 1.5–2 dB gain over coded V‐BLAST is obtained in a 2 × 2 antenna setup when convolutional codes or rate 3/4 turbo codes are used; 0.5 dB gain is offered in a 2 × 5 setup when rate 1/2 turbo codes are used. Coded FDFR also outperforms a 16‐QAM Alamouti coded scheme by 1 dB when convolutional codes are used. The price paid is increased complexity. Copyright © 2004 John Wiley & Sons, Ltd.

We design pilot symbol assisted modulation for carrier frequency offset (CFO) and channel estimation in orthogonal frequency division multiplexing (OFDM) transmissions over multiinput multioutput (MIMO) frequency-selective fading channels. By separating CFO and channel estimation from symbol detection, the novel training patterns lead to low-complexity CFO and channel estimators. The performance of our algorithms is investigated analytically, and then compared with an existing approach by simulations.

The unique advantages of ultrawideband (UWB) technology are somewhat encumbered by its stringent timing tolerances. To help to appreciate how critical timing offset estimation is for UWB, the bit-error-rate (BER) sensitivity to timing offsets is investigated in this paper for correlation-based UWB receivers. Focusing on UWB transmissions with time hopping, the BER expressions are derived for various operating conditions and system setups, including AWGN and frequency flat channels, dense multipath fading channels, and various receiver types including sliding correlators and RAKE combiners. It is demonstrated through analyses that time-hopping based multiple access systems exhibit little tolerance to acquisition errors, while the energy capture capability of a RAKE combiner can be severely compromised by mistiming.

Rapid timing acquisition with low complexity constitutes a major challenge in realizing the high potential ultra wideband (UWB) technology promises for indoor wireless communications. We design and test such a timing acquisition algorithm based on training symbols. Relying on a judiciously designed preamble, our algorithm achieves clock synchronization at the receiver using simple integrate-and-dump operations over the symbol duration. Analysis and simulations confirm that with a small number of training symbols, our scheme brings bit-error-rate (BER) performance close to that corresponding to the case with perfect timing.

Power loading algorithms improve the data rates of OFDM systems. However, they require the transmitter to have perfect channel state information, which is impossible in most wireless systems. We investigate the effects of imperfect (and thus partial) channel feedback on the achievable rates of OFDM systems. Two cases are studied: i) ergodic channels, where average rate is the figure of merit; and ii) quasistatic channels, where the outage rate is relevant. Power loading algorithms and the effects of channel multipath are investigated analytically and with simulations.

While the knowledge of each channel realization is not available in a system with differential space-time modulation, channel correlation can be easily estimated without training at the receiver, and exploited by the transmitter to enhance the error probability performance. We develop a transmission scheme that combines transmit-beamforming with differential space-time modulation based on orthogonal space-time block coding. Error probability is analyzed for both correlated and independent channels. Based on the error probability analysis, we derive power loading coefficients to improve performance.

Summary form only given. Ultra-wideband (UWB) refers to bandwidths in excess of 2 GHz, whose utilization by radar systems dates back to the late '60s. The renewed and rapidly growing interest for UWB was sparked by the spectral mask released by FCC in February 2002, and is well motivated by the attractive features UWB brings to commercial communications: low-power carrier-free transmissions, ample multipath diversity, enhanced penetration capability, low-complexity transceivers, ability to overlay existing systems, and a potential for increase in capacity. This article outlines features and challenges unique to UWB, with emphasis on timely signal processing issues that focus on synchronization, channel estimation, multiple access, and suppression of interference UWB systems cause to (and suffer from) co-existing narrowband systems. Application areas include shortrange indoor wireless links at home, and in the workplace for low-cost multimedia communications and storage, as well as secure connectivity for ranging, and covert communications.

Rapidly fading channels provide Doppler-induced diversity, but are also challenging to estimate. To by-pass channel estimation, we derive a novel block differential codec. Relying on a basis expansion model for time-varying channels, our block differential design is easy to implement, and achieves the maximum possible Doppler diversity. Simulation results corroborate our theoretical analysis.

Standardized wireless transmissions include fixed-size fragments per packet. Relying on this structure, we develop two schemes for distributing redundancy across fragments, in order to improve performance of packet transmissions over frequency-selective fading channels. We prove that both schemes guarantee symbol detectability, which implies that they both enable the full multipath diversity. We test their relative merits, and compare them with competing alternatives using simulations.

Low-complexity rapid timing acquisition constitutes a major challenge in realizing the high potential that ultra-wideband (UWB) wireless technology promises for indoor communications. We derive and test two such timing acquisition algorithms which capitalize on the cyclostationarity that is naturally present in UWB transmissions. Our novel schemes are blind, they do not require multiple antennas or oversampling, and rely on frame-rate sampling which reduces complexity and acquisition delay considerably.

Adaptive modulation improves system throughput considerably by matching transmitter parameters to time-varying wireless fading channels. Crucial to adaptive modulation is the quality of channel state information (CSI) at the transmitter. We consider a channel predictor based on pilot symbol assisted modulation (PSAM) for multi-input multi-output (MIMO) Rayleigh fading channels. We analyze the impact of the channel prediction error on the bit error rate (BER) performance of an adaptive system assuming perfect CSI. Our numerical results reveal the critical value of the normalized prediction error, below which the predicted channels can be treated as perfect by the adaptive modulator; otherwise, explicit consideration of the channel imperfection must be accounted for at the transmitter.

We derive a novel block differential codec to bypass estimation of rapidly fading channels. Based on a basis expansion model for time-varying channels, our differential design is easy to implement, and achieves the maximum possible Doppler diversity. Combined with a group partitioning scheme, the differential scheme provides also flexibility to tradeoff decoding complexity with performance. Simulation results corroborate our theoretical analysis.

We design constellations for non-coherent space-time systems. Given in algebraic form, the constructed constellations are easy to design, enjoy full diversity, allow for a simplified maximum likelihood detector, and achieve performance comparable to existing designs that rely on computer search.

Adaptive modulation has the potential to increase the system throughput significantly by matching transmitter parameters to time-varying channel conditions. However, adaptive modulation assuming perfect channel state information (CSI) is sensitive to CSI imperfections induced by estimation errors and feedback delays. In this paper, we design adaptive modulation schemes for multi-antenna transmission based on partial CSI, that models the spatial fading channels as Gaussian random variables with non-zero mean and white covariance, conditioned on feedback information. Based on a two-directional beamformer, our proposed transmitter optimally adapts the beam directions, the power allocation between two beams, and the signal constellation, to maximize the transmission rate while maintaining a target bit error rate (BER). Numerical results demonstrate the rate improvement, and illustrate an interesting tradeoff that emerges between feedback quality and hardware complexity.

Orthogonal frequency division multiple access (OFDMA) gains increasing attention for broadband, high data rate wireless/wireline communications. In this paper, we propose a novel unitary precoded (UP) OFDMA scheme for uplink applications, which increases the system bandwidth efficiency, while preserving constant modulus transmissions. Theoretical analysis for the proposed UP-OFDMA with channel coding quantifies the performance improvement introduced by unitary precoding. It provides guidelines for practical system designs, and reveals performance gap between the proposed system and the single user bound. Simulation results confirm that the proposed system improves performance considerably relative to conventional OFDMA.

While rapid variations of the fading channel cause intercarrier interference (ICI) in orthogonal frequency-division multiplexing (OFDM), thereby degrading its performance considerably, they also introduce temporal diversity, which can be exploited to improve performance. We first derive a matched-filter bound (MFB) for OFDM transmissions over doubly selective Rayleigh fading channels, which benchmarks the best possible performance if ICI is completely canceled without noise enhancement. We then derive universal performance bounds which show that the time-varying channel causes most of the symbol energy to be distributed over a few subcarriers, and that the ICI power on a subcarrier mainly comes from several neighboring subcarriers. Based on this fact, we develop low-complexity minimum mean-square error (MMSE) and decision-feedback equalizer (DFE) receivers for ICI suppression. Simulations show that the DFE receiver can collect significant gains of ICI-impaired OFDM with affordable complexity. In the relatively low Doppler frequency region, the bit-error rate of the DFE receiver is close to the MFB.

Orthogonal frequency-division multiplexing (OFDM) converts a frequency-selective fading channel into parallel flat-fading subchannels, thereby simplifying channel equalization and symbol decoding. However, OFDM's performance suffers from the loss of multipath diversity, and the inability to guarantee symbol detectability when channel nulls occur. We introduce a linear constellation precoded OFDM for wireless transmissions over frequency-selective fading channels. Exploiting the correlation structure of subchannels and choosing system parameters properly, we first perform an optimal subcarrier grouping to divide the set of subchannels into subsets. Within each subset, a linear constellation-specific precoder is then designed to maximize both diversity and coding gains. While greatly reducing the decoding complexity and simplifying the precoder design, subcarrier grouping enables the maximum possible diversity and coding gains. In addition to reduced complexity, the proposed system guarantees symbol detectability regardless of channel nulls, and does not reduce the transmission rate. Analytic evaluation and corroborating simulations reveal its performance merits.

We quantify the performance of wireless transmissions over random fading channels at high signal-to-noise ratio (SNR). The performance criteria we consider are average probability of:error and outage probability. We show that as functions of the average SNR, they can both be characterized by two parameters: the diversity and coding gains. They both exhibit identical diversity orders, but their coding gains in decibels differ by a constant. The diversity and coding gains are found to depend on the behavior of-the random SNR's probability density function only at the origin, or equivalently, on the decaying order of the corresponding moment generating function (i.e., how fast the moment generating function goes to zero as its argument goes to infinity). Diversity and coding gains for diversity combining systems are expressed in terms of the diversity branches' individual diversity and coding gains, where the branches can come from any diversity technique such as space, time, frequency, or, multipath. The proposed analysis offers a simple and unifying approach to evaluating the performance of uncoded and (possibly space-time) coded transmissions over fading channels, and the method applies to almost all digital modulation schemes, including M-ary phaseshift keying, quadrature amplitude modulation, and frequency-shift keying with coherent or noncoherent detection.

Orthogonal frequency-division multiple access (OFDMA) gains increasing attention for broadband, high data rate wireless communications. We develop a novel unitary precoded (UP) OFDMA scheme that is particularly appealing for the uplink, because it offers high bandwidth efficiency, and constant modulus transmissions for each user. Theoretical analysis of UP-OFDMA with channel coding shows the performance improvement introduced by unitary precoding. It provides useful guidelines for practical system designs, and also quantifies the performance of UP-OFDMA relative to the single-user bound. Simulations confirm that UP-OFDMA improves performance considerably relative to conventional OFDMA.

Suppression of multiuser interference (MUI) and mitigation of time- and frequency-selective (doubly selective) channel effects constitute major challenges in the design of third-generation wireless mobile systems. Relying on a basis expansion model (BEM) for doubly selective channels, we develop a channel-independent block spreading scheme that preserves mutual orthogonality among single-cell users at the receiver. This alleviates the need for complex multiuser detection, and enables separation of the desired user by a simple code-matched channel-independent block despreading scheme that is maximum-likelihood (ML) optimal under the BEM plus white Gaussian noise assumption on the channel. In addition, each user achieves the maximum delay-Doppler diversity for Gaussian distributed BEM coefficients. Issues like links with existing multiuser transceivers, existence, user efficiency, special cases, backward compatibility with direct-sequence code-division multiple access (DS-CDMA), and error control coding, are briefly discussed.

High data rates and multipath propagation give rise to frequency-selectivity of wireless channels, while carrier frequency offsets and mobility-induced Doppler shifts introduce time-selectivity in wireless links. The resulting time- and frequency-selective (or doubly selective) channels offer joint multipath-Doppler diversity gains. Relying on a basis expansion model of the doubly selective channel, we prove that the maximum achievable multipath-Doppler diversity order is determined by the rank of the correlation matrix of the channel's expansion coefficients, and is multiplicative in the effective degrees of freedom that the channel exhibits in the time and frequency dimensions. Interestingly, it turns out that time-frequency reception alone does not guarantee maximum diversity, unless the transmission is also designed judiciously. We design such block precoded transmissions. The corresponding designs for frequency-selective or time-selective channels follow as special cases, and thorough simulations are provided to corroborate our theoretical findings.

Orthogonal frequency-division multiplexing (OFDM) converts a time-dispersive channel into parallel subchannels, and thus facilitates equalization and (de)coding. But when the channel has nulls close to or on the fast Fourier transform (FFT) grid, uncoded OFDM faces serious symbol recovery problems. As an alternative to various error-control coding techniques that have been proposed to ameliorate the problem, we perform complex-field coding (CFC) before the symbols are multiplexed. We quantify the maximum achievable diversity order for independent and identically distributed (i.i.d.) or correlated Rayleigh-fading channels, and also provide design rules for achieving the maximum diversity order. The maximum coding gain is given, and the encoder enabling the maximum coding gain is also found. Simulated performance comparisons of CFC-OFDM with existing block and convolutionally coded OFDM alternatives favor CFC-OFDM for the code rates used in a HiperLAN2 experiment.

We study space-time block coding for single-carrier block transmissions over frequency-selective multipath fading channels. We propose novel transmission schemes that achieve a maximum diversity of order N/sub t/N/sub r/(L+1) in rich scattering environments, where N/sub t/ (N/sub r/) is the number of transmit (receive) antennas, and L is the order of the finite impulse response (FIR) channels. We show that linear receiver processing collects full antenna diversity, while the overall complexity remains comparable to that of single-antenna transmissions over frequency-selective channels. We develop transmissions enabling maximum-likelihood optimal decoding based on Viterbi's ( 1998) algorithm, as well as turbo decoding. With single receive and two transmit antennas, the proposed transmission format is capacity achieving. Simulation results demonstrate that joint exploitation of space-multipath diversity leads to significantly improved performance in the presence of frequency-selective fading channels.

Optimal transmitter designs obeying the water-filling principle are well-documented, and widely applied, when the propagation channel is deterministically known and regularly updated at the transmitter. Because channel state information (CSI) may be costly or impossible to acquire in rapidly varying wireless environments, we develop in this paper statistical water-filling approaches for stationary random fading channels. These approaches require only knowledge of the channel correlations that do not necessitate frequent updates, and can be easily acquired. Applied to a multiple transmit-antenna paradigm, our optimal transmitter design turns out to be an eigen-beamformer with multiple beams pointing to orthogonal directions along the eigenvectors of the channel's correlation matrix, and with proper power loading across the beams. The optimality pertains to minimizing a tight bound on the symbol error rate. The resulting loaded eigen-beamforming outperforms not only the equal-power allocation across all antennas, but also the conventional beamformer that transmits the available power along the strongest direction. Coupled with orthogonal space-time block codes, two-dimensional (2-D) eigen-beamforming emerges as a more attractive choice than conventional one-dimensional (1-D) beamforming with uniformly better performance, without rate reduction, and without complexity increase.

In wireless cellular communications, accurate local mean (shadow) power estimation performed at a mobile station is important for use in power control, handoff, and adaptive transmission. Window-based weighted sample average shadow power estimators are commonly used due to their simplicity. In practice, the performance of these estimators degrades severely when the window size deviates beyond a certain range. The optimal window size for window-based estimators is hard to determine and track in practice due to the continuously changing fading environment. Based on a first-order autoregressive model of the shadow process, we propose a scalar Kalman-filter-based approach for improved local mean power estimation, with only slightly increased computational complexity. Our analysis and experiments show promising results.

This paper proposes a novel block differentially encoded orthogonal frequency-division multiplexing for multicarrier transmissions over frequency-selective fading channels. Choosing appropriate system parameters, we divide the set of correlated subchannels into subsets of independent subchannels. Within each subset, differential unitary space-time modulation is performed by treating each subchannel as a transmit antenna. In addition to low complexity, the proposed system enjoys maximum multipath diversity and high coding advantages. Analytic evaluation and corroborating simulations reveal its performance merits.

In wireless communications, the relative strength of the direct and scattered components of the received signal, as expressed by the Ricean K factor, provides an indication of link quality. Accordingly, efficient and accurate methods for estimating K are of considerable interest. In this paper, we propose a general class of moment-based estimators which use the signal envelope. This class of estimators unifies many of the previous estimators, and introduces new ones. We derive, for the first time, the asymptotic variance (AsV) of these estimators and compare them with the Cramer-Rao bound (CRB). We then tackle the problem of estimating K from the in-phase and quadrature-phase (I/Q) components of the received signal and illustrate the improvement in performance as compared with the envelope-based estimators. We derive the CRBs for the I/Q data model, which, unlike the envelope CRB, is tractable for correlated samples. Furthermore, we introduce a novel estimator that relies on the I/Q components, and derive its AsV even when the channel samples are correlated. We corroborate our analytical findings by simulations.

We present a unified approach to designing space-time (ST) block codes using linear constellation precoding (LCP). Our designs are based either on parameterizations of unitary matrices, or on algebraic number-theoretic constructions. With an arbitrary number of N/sub t/ transmit- and N/sub r/ receive-antennas, ST-LCP achieves rate 1 symbol/s/Hz and enjoys diversity gain as high as N/sub t/N/sub r/ over (possibly correlated) quasi-static and fast fading channels. As figures of merit, we use diversity and coding gains, as well as mutual information of the underlying multiple-input-multiple-output system. We show that over quadrature-amplitude modulation and pulse-amplitude modulation, our LCP achieves the upper bound on the coding gain of all linear precoders for certain values of N/sub t/ and comes close to this upper bound for other values of N/sub t/, in both correlated and independent fading channels. Compared with existing ST block codes adhering to an orthogonal design (ST-OD), ST-LCP offers not only better performance, but also higher mutual information for N/sub t/>2. For decoding ST-LCP, we adopt the near-optimum sphere-decoding algorithm, as well as reduced-complexity suboptimum alternatives. Although ST-OD codes afford simpler decoding, the tradeoff between performance and rate versus complexity favors the ST-LCP codes when N/sub t/, N/sub r/, or the spectral efficiency of the system increase. Simulations corroborate our theoretical findings.

We propose novel space-time multipath (STM) coded multi-antenna transmissions over frequency-selective Rayleigh fading channels. We develop STM coded systems that guarantee the maximum possible space-multipath diversity without rate loss for any number of transmit-antennae, and with large coding gains within the class of linearly coded systems. By incorporating subchannel grouping, we also enable desirable tradeoffs between performance and complexity. The merits of our design are confirmed by corroborating simulations, and comparisons with existing approaches.

We quantify the average performance of digital transmissions over fading channels at high signal-to-noise ratio (SNR). The performance criteria considered here are probability of error and outage probability. We show that as functions of the average SNR, they can both be characterized by two parameters: the diversity and coding gains. They have the same diversity order, but their coding gains in dB differ by a constant. The diversity and coding gains are found to be related to the behavior of the probability density function (PDF) only at the origin, or equivalently, to the decaying order of the characteristic function. Diversity and coding gains for diversity combining systems are found in terms of branch average SNR's for arbitrarily distributed independent (in some cases, correlated) branches, which can allow one to analyze, e.g., coded transmissions through independent or correlated fading channels.

We rely on a Basis Expansion Model (BEM) for the channel, to design three Space-Time-Doppler (SID) codecs that enable maximum diversity gains, when block transmissions undergo time-selective fading effects. Within the constraints of each maximum-diversity design, it is also possible to achieve maximum coding gain, at least when the BEM parameters are i.i.d. The theoretical results are corroborated by simulation results and the BEM is validated.

Recently, a so-termed Chip-Interleaved Block-Spread (CIBS) CDMA system has been introduced, which enables Multi-User Interference (MUI) free reception. This transceiver can be used in the uplink as well as in the downlink. In this paper, we focus on the downlink and compare the downlink CIBS-CDMA system employing an MUI-free receiver with the conventional downlink Direct-Sequence (DS) CDMA system employing a chip equalizer receiver. The analysis, which is validated by simulation results, reveals that CIBS-CDMA with an MUI-free receiver has a number of advantages over DS-CDMA with a chip equalizer receiver.

This paper proposes novel space-time-frequency (STF) block coding for multi-antenna OFDM transmissions over frequency-selective Rayleigh fading channels. Incorporating subcarrier grouping and choosing appropriate system parameters, we first convert our system into a set of group STF (GSTF) systems. This enables simplification of STF block coding within each GSTF system. We derive design criteria for STF block coding, and exploit existing ST coding techniques to construct STF block codes. The resulting codes are shown capable of achieving both maximum diversity and coding gains, while affording low-complexity decoding. The performance merits of our design is confirmed by corroborating simulations, and compared with existing alternatives.

High data rates give rise to frequency-selective propagation, while carrier frequency-offsets and mobility-induced Doppler shifts introduce time-selectivity in wireless links. To mitigate the resulting time- and frequency-selective (or doubly-selective) channels, an optimal training strategy is designed in this paper for block transmissions over doubly-selective channels, relying on a basis expansion channel model. The optimality in designing our PSAM parameters consists of maximizing a tight lower bound on the average channel capacity, that is also shown to be equivalent to the minimization of the minimum mean-square channel estimation error. Numerical results corroborate our theoretical designs.

Optimal transmitter designs obeying the water-filling principle are well-documented, and widely applied when the propagation channel is deterministically known, and regularly updated at the transmitter. Because channel state information is impossible to be known perfectly at the transmitter in practical wireless systems, we develop in this paper optimal transmitter design based on the knowledge of mean values of the underlying channels. Applied to a multiple transmit-antenna paradigm, our optimal transmitter design turns out to be an eigen-beamformer with multiple beams pointing to orthogonal directions along the eigenvectors of the channel correlation matrix conditioned on channel mean, and with proper power loading across beams. The optimality pertains to minimizing a tight bound on the symbol error rate. Coupled with orthogonal space time block codes, two-directional eigen-beamforming emerges as a more attractive choice than conventional one-directional beamforming with uniformly improved performance, without rate reduction.

We establish that practical multiple access based on finite size information blocks transmitted with prescribed power and with loaded multicarrier modulation, is optimal with respect to maximizing the sum-rate of circulant intersymbol interference (ISI) channels, that are assumed available at the transmitter. Circulant ISI channels are ensured either with cyclic prefixed block transmissions and an overlap-save reception, or, with zero-padded block transmissions and an overlap-add reception. Analysis asserts that sum-rate optimal multicarrier users could share one or more subcarriers depending on the underlying channels. Optimal loading is performed by specializing an existing iterative low-complexity algorithm to circulant ISI channels.

Transmitting digital information using ultra-short pulses, impulse radio (IR) has received increasing interest for multiple access (MA). Analog IRMA utilizes pulse-position modulation (PPM) and random time-hopping codes to mitigate inter-symbol interference (ISI) and suppress multiuser interference (MUI) statistically. We develop an all-digital IRMA scheme that relies on block-spreading and judiciously designed transceiver pairs to eliminate MUI deterministically, and regardless of ISI multipath effects.

Optimal transmitter designs obeying the water-filling principle are well-documented, and widely applied when the propagation channel is deterministically known and regularly updated at the transmitter. Because channel state information may be costly or impossible to acquire in rapidly varying wireless environments, we develop in this paper statistical water-filling approaches for stationary random fading channels. The resulting optimal designs require only knowledge of the channel's second order statistics that do not require frequent updates, and can be easily acquired. Optimality refers to minimizing a tight bound on the symbol error rate. Applied to a multiple transmit-antenna paradigm, the optimal precoder turns out to be a generalized eigen-beamformer with multiple beams pointing to orthogonal directions along the eigenvectors of the channel's covariance matrix, and with proper power loading across the beams. Coupled with orthogonal space time block codes, two-directional eigen-beamforming emerges as a more attractive choice than conventional one-directional beamforming, with uniformly better performance, and without rate reduction or complexity increase.

A novel space-time-frequency (STF) trellis coding scheme is developed for multi-antenna OFDM transmissions over frequency-selective Rayleigh fading channels. Incorporating subcarrier grouping and choosing appropriate system parameters, we first convert our system into a set of group STF (GSTF) systems. This enables simplification of STF block coding within each GSTF system. We derive design criteria for STF trellis coding, and exploit existing ST trellis coding techniques to construct STF trellis codes. The resulting codes are shown capable of achieving maximum diversity gains, while affording low-complexity decoding. The performance merits of our design is confirmed by corroborating simulations, and compared with existing alternatives.

This paper addresses the design of a novel scheme that combines error control coding (EC) and unitary precoding (UP) in order to obtain high diversity gains in OFDM systems with low complexity. The overall diversity of the proposed system is shown to be the product of the individual diversities achievable by the error control coding and by the unitary precoding, while the complexity is just a linear multiple of the sum of their individual complexities. In a practical HiperLan/2 setup, the proposed system achieves a gain of 4 dB, (3.3 dB), at a bit error rate (BER) of 10/sup -3/, relative to conventional OFDM systems that only deploy convolutional (turbo) coding.

Recent theoretical and experimental studies have shown that with affordable complexity, layered space-time (LST) transmissions can attain very high spectral efficiency in a rich-scattering environment. In this paper, we propose a novel high rate linearly precoded LST system, which allows for any number of transmit and receive antennas, and offers flexibility in trading performance with bandwidth efficiency and decoding complexity. Even with sub-optimum decoding, the system enjoys considerable transmit diversity gains. Its superior performance over existing uncoded V-BLAST and linear dispersion (LD) codes is confirmed by simulations.

Carrier frequency-offsets and mobility-induced Doppler shifts introduce time-selectivity in wireless links. Doppler-RAKE receivers have been developed for collecting the resulting diversity gains only for spread-spectrum systems. Relying on a basis expansion model of time-selective channels, we find that the maximum achievable Doppler diversity is determined by the rank of the correlation matrix of the channel's expansion coefficients. We also prove that RAKE reception can not collect maximum diversity gains, unless the transmission is appropriately designed. Finally, we design such block precoded transmissions to ensure maximum diversity gains, and provide thorough simulations to corroborate our theoretical findings.

Enabling linear minimum-mean square error (LMMSE) based estimation of random time-selective channels, pilot symbol assisted modulation (PSAM) has well documented merits as a fading countermeasure capable of improving bit error rate performance. In this paper, we establish average-rate optimality of PSAM by showing that the insertion of equi-powered and equi-spaced pilot symbols in PSAM transmissions maximizes a tight lower bound of the average channel capacity. Relying on a simple closed form expression of this bound in terms of the LMMSE channel estimator variance, we further design PSAM transmissions with optimal spacing of pilot symbols, and optimal allocation of the transmit-power budget between pilot and information symbols.

We consider the class of linear precoded (LP) orthogonal frequency division multiplexing (OFDM) systems. We first show that single-carrier zero-padded transmissions, termed ZP-only, can be viewed as a special case of LP-OFDM. By resorting to the pair-wise error probability analysis, we establish the optimality of ZP-only among the LP-OFDM class in terms of its performance in random frequency-selective channels. It is shown that ZP-only enjoys maximum diversity and coding gains. We also consider various decoding options for ZP-only, and compare them in terms of performance and complexity.

We develop synchronization algorithms for both the downlink and the uplink of quasi-synchronous and asynchronous orthogonal frequency division multiple access systems. Unlike existing alternatives, the proposed time- and carrier-offset estimators do not require the transmission of known sequences and exhibit performance independent of the underlying channel zero locations. The only necessary assumption is that there are virtual subcarriers which are not occupied by any user. We derive a closed-form variance expression for the carrier-offset estimator at high signal-to-noise ratio (SNR), as a function of the number of active users and the SNR. We compare our method with alternative ones and validate our theoretical derivations with simulation results.

Transmitting digital information using ultra-short pulses, impulse radio (IR) has received increasing interest for multiple access (MA). When IRMA systems have to operate in dense multipath environments, the multiple user interference (MUI) and intersymbol interference (ISI) induced, adversely affect system capacity and performance. Analog IRMA utilizes pulse position modulation (PPM) and random time-hopping codes to mitigate ISI and suppress MUI statistically. We develop an all-digital IRMA scheme that relies on multistage block-spreading (MS-BS), and judiciously designed transceiver pairs to eliminate MUI deterministically, and regardless of ISI multipath effects. Our proposed MS-BS-IRMA system can accommodate a large number of users and is capable of providing different users with variable transmission rates, which is important for multimedia applications. Unlike conventional IRMA systems, MS-BS-IRMA exhibits no degradation in bit-error rate performance, as the number of users increases.

This paper proposes a novel decoding scheme for Alamouti's (see IEEE J. Select. Areas Commun., vol.16, p.1451-1458, 1998) space-time (ST) coded transmissions over time-selective fading channels that arise due to Doppler shifts and carrier frequency offsets. Modeling the time-selective channels as random processes, we employ Kalman filtering for channel tracking in order to enable ST decoding with diversity gains. Computer simulations confirm that the proposed scheme exhibits robustness to time-selectivity with a few training symbols.

Impulse radio is an ultrawideband system with attractive features for baseband asynchronous multiple-access, multimedia services, and tactical wireless communications. Implemented with analog components, the continuous-time impulse radio multiple-access model utilizes pulse-position modulation and random time-hopping codes to alleviate multipath effects and suppress multiuser interference. We introduce a novel continuous-time impulse radio transmitter model and deduce from it an approximate one with lower complexity. We also develop a time-division duplex access protocol along with orthogonal user codes to enable impulse radio as a radio link for wireless cellular systems. Relying on this protocol, we then derive a multiple-input/multiple-output equivalent model for full continuous-time model and a single-input/single-output model, for the approximate one. Based on these models, we finally develop design composite linear/nonlinear receivers for the downlink. The linear step eliminates multiuser interference deterministically and accounts for frequency-selective multipath while a maximum-likelihood receiver performs symbol detection. Simulations are provided to compare performance of the different receivers.

This article extends turbo demodulation to the zero-padded OFDM (ZP-OFDM) system by accounting for the noise color and the symbols estimates correlation introduced by equalization. Resorting to realistic simulations, we show that turbo demodulation used with set partitioning labeling can significantly outperform noniterative decoding with Gray labeling. We also show that it increases the performance gap between ZP-OFDM and OFDM with cyclic prefix (CP-OFDM) relative to noniterative decoding, because it amplifies the performance gain due to the guaranteed symbol recovery of ZP-OFDM.

Zero padding (ZP) of multicarrier transmissions has been proposed as an appealing alternative to the traditional cyclic prefix (CP) orthogonal frequency-division multiplexing (OFDM) to ensure symbol recovery regardless of the channel zero locations. In this paper, both systems are studied to delineate their relative merits in wireless systems where channel knowledge is not available at the transmitter. Two novel equalizers are developed for ZP-OFDM to tradeoff performance with implementation complexity. Both CP-OFDM and ZP-OFDM are then compared in terms of transmitter nonlinearities and required power backoff. Next, both systems are tested in terms of channel estimation and tracking capabilities. Simulations tailored to the realistic context of the standard for wireless local area network HIPERLAN/2 illustrate the pertinent tradeoffs.

The adoption of orthogonal frequency-division multiplexing by wireless local area networks and audio/video broadcasting standards testifies to the importance of recovering block precoded transmissions propagating through frequency-selective finite-impulse response (FIR) channels. Existing block transmission standards invoke bandwidth-consuming error control codes to mitigate channel fades, and training sequences to identify the FIR channels. To enable block-by-block receiver processing, we design redundant precoders with cyclic prefix and superimposed training sequences for optimal channel estimation and guaranteed symbol detectability, regardless of the underlying frequency-selective FIR channels. Numerical results are presented to access the performance of the designed training and precoding schemes.

A novel multiuser-interference (MUI)-free code division multiple access (CDMA) transceiver for frequency-selective multipath channels is developed. Relying on chip-interleaving and zero padded transmissions, orthogonality among different users' spreading codes is maintained at the receiver even after frequency-selective propagation. As a result, deterministic multiuser separation with low-complexity code-matched filtering becomes possible without loss of maximum likelihood optimality. In addition to MUI-free reception, the proposed system guarantees channel-irrespective symbol detection and achieves high bandwidth efficiency by increasing the symbol block size. Filling the zero-gaps with known symbols allows for perfectly constant modulus transmissions. Important variants of the proposed transceivers are derived to include cyclic prefixed transmissions and various redundant or nonredundant precoding alternatives. (Semi-) blind channel estimation algorithms are also discussed. Simulation results demonstrate improved performance of the proposed system relative to competing alternatives.

We compare single user digital multi-carrier spread spectrum (MC-SS) modulation with direct sequence (DS) SS (with a modified implementation) in the presence of narrowband interference (NBI) and multipath fading. We derive closed-form expressions for the symbol error probability for both the linear MMSE receiver as well as the conventional matched-filter receiver under different scenarios: additive white Gaussian noise (AWGN) channel with NBI, multipath channel with or without NBI. We show that DS-SS can achieve the same performance as MC-SS if the spreading code is carefully designed to have perfect periodic autocorrelation function (PACF). On the other hand, MC-SS is more robust to narrowband interference and multipath fading than is DS-SS with the widely used spreading codes that do not possess perfect PACE. Our analysis reveals that the performance improvement of MC-SS is precisely due to the implicit construction of an equivalent spreading code having nonconstant amplitude but possessing perfect periodic autocorrelation.

This paper considers the problem of blind symbol rate estimation of signals linearly modulated by a sequence of unknown symbols. Oversampling the received signal generates cyclostationary statistics that are exploited to devise symbol-rate estimators by maximizing in the cyclic domain a (possibly weighted) sum of modulus squares of cyclic correlation estimates. Although quite natural, the asymptotic (large sample) performance of this estimator has not been studied rigorously. The consistency and asymptotic normality of this symbol-rate estimator is established when the number of samples N converges to infinity. It is shown that this estimator exhibits a fast convergence rate (proportional to N/sup -3/2/), and it admits a simple closed-form expression for its asymptotic variance. This asymptotic expression enables performance analysis of the rate estimator as a function of the number of estimated cyclic correlation coefficients and the weighting matrix. A justification for the high performance of the unweighted estimator in high signal-to-noise scenarios is also provided.

Enabling linear minimum-mean square error (LMMSE)-based estimation of random time-selective channels, pilot-symbol-assisted modulation (PSAM) has well-documented merits as a fading counter-measure boosting bit-error rate performance. We design average-rate optimal PSAM transmissions by maximizing a tight lower bound of the average channel capacity. Relying on a simple closed-form expression of this bound in terms of the LMMSE channel estimator variance, we obtain PSAM transmissions with optimal spacing of pilot symbols and optimal allocation of the transmit-power budget between pilot and information symbols. Equi-powered transmitted symbols, channels with special Doppler spectra, and analytical and simulation based comparisons of possible alternatives shed more light on information-theoretic aspects of PSAM-based transmissions.

Abstract The quest for reliable high‐rate wireless links motivates fading‐resilient and bandwidth‐efficient communication systems capable of capitalizing on available forms of diversity. This tutorial focuses on linear complex field (LCF) coding—a powerful tool that complements the traditional Galois field (GF) coding, in enabling diversity transmissions over single‐ and multi‐antenna fading channels. Performance and capacity analyses are provided, along with systematic guidelines for constructing LCF encoders, and options available to the designer for selecting LCF decoders. Emphasis is placed on high‐performance and high‐rate designs, and the emerging performance‐rate‐complexity trade‐offs. Copyright © 2002 John Wiley & Sons, Ltd.

We apply algebraic number theoretic tools to designing linear space-time constellation-rotating (ST-CR) block codes. With an arbitrary number of M transmit- and N receive-antennas, our ST-CR designs achieve a rate of 1 symbol/second and enjoy maximum diversity gains MN over quasi-static fading channels. When M is an Euler number, /spl phi/(P) for P/spl ne/0 (mod 4), or, when M=2/sup m/ for some positive integer m, the designed ST-CR precoders also maximize coding gains over QAM constellations. When M takes other integer values, we construct a method to design precoders with large coding gains that can be computed explicitly. Simulations corroborate our theoretical findings.

We address the problem of frequency synchronization in OFDM-based communications systems in the context of frequency-selective fading channels. Frequency offsets are estimated by inserting null sub-carriers into a single OFDM block. The paper clarifies issues related to acquisition range and identifiability of carrier frequency offset (CFO), and performance of estimators. A deterministic maximum likelihood estimation approach is adopted. We derive necessary and sufficient conditions on the number of null-subcarriers and their placement in order to ensure identifiability. The Cramer-Rao bound (CRB) for the CFO is derived; for a given number of null sub-carriers, the optimal placement which minimizes the CRB is derived. We show that if the number of null sub-carriers is less than half the total number of sub-carriers, performance is optimal when the null sub-carriers are equispaced.

Suppression of multiuser interference (MUI) and mitigation of time- and frequency-selective effects constitute major challenges in the design of third-generation wireless mobile systems. Relying on block spreading and judiciously chosen time-frequency guard intervals, we propose a multiuser transceiver that eliminates MUI deterministically and guarantees symbol detectability in the presence of unknown time- and frequency-selective fading. Blind channel estimation is also investigated. Simulation results demonstrate the validity of the theoretical results and show improved performance of the proposed transceiver over a multi-user time-frequency RAKE receiver.

We study space-time block coding for single carrier block transmissions through frequency selective multipath channels of order L. We prove that maximum diversity of order 2(L + 1) can be achieved with two transmit and one receive antennas. We show that simple linear receiver processing can achieve full antenna diversity gains, and investigate the performance versus complexity tradeoffs that emerge when the embedded multipath diversity is also exploited. Simulation results demonstrate that joint exploitation of multi-antenna and multipath diversities yields significantly enhanced performance in frequency selective multipath channels.

We present a unified approach to constructing linear space-time (ST) block codes based on unitary constellation-rotating (ST-CR) precoders. We show that with an arbitrary number of M-transmit and N-receive antennas, ST-CR precoders achieve 1 symbol/sec rate and enjoy maximum diversity gain MN over both quasi-static and fast fading channels. We also compare real with complex rotations to delineate the tradeoff between performance and complexity. Based on a simplified decoder, we study diversity and coding gains as well as information-theoretic aspects of the proposed ST-CR scheme. Compared with ST orthogonally designed (ST-OD) codes, ST-CR precoding provides larger coding gain and maximum mutual information. Though ST-OD codes afford simpler decoding, the tradeoff between performance and rate versus complexity favors the ST-CR codes when M, N or the spectral efficiency of the system increase.

The adoption of orthogonal frequency-division multiplexing (OFDM) by wireless local area networks and audio/video broadcasting standards testifies to the importance of recovering block precoded transmissions propagating through frequency-selective FIR channels. Existing block transmission standards invoke bandwidth-consuming error control codes to mitigate channel fades and training sequences to identify the FIR channels. To enable low-complexity block-by-block receiver processing, we design redundant precoders with cyclic prefix (CP) and superimposed training sequences for optimal channel estimation and guaranteed symbol recovery regardless of the underlying FIR frequency-selective channels. Numerical results axe presented to access the performance of the designed training and precoding schemes.

We develop and analyze timing and carrier frequency offset synchronization algorithms for generalized asynchronous and quasi-synchronous orthogonal frequency division multiple access systems using null subcarriers and subcarrier hopping. We derive an approximate analytic expression for the variance of the frequency offset estimators as a function of the number of active users and the SNR and show that the performance of our algorithms is asymptotically independent of the channel zero locations for quasi-synchronous systems. Finally, we validate our theoretical expressions with simulations.

In mobile communications the strength of a line of sight component measured by the K factor of the Ricean received envelope distribution has significant impact on system performance analysis and link budget calculations. In this paper, we study the performance of moment-based estimators for the Ricean K-factor as less complex alternatives to the maximum likelihood estimator. Our asymptotic analysis reveals that the estimators that rely on lower-order moments have a better asymptotic performance for moderate/large values of K. We also illustrate, by Monte Carlo simulations, that the fading correlation among the envelope samples deteriorates the estimator performance. The simplest estimator, which can be expressed in closed form in terms of the second- and fourth-order sample moments offers a good compromise between statistical performance and computational simplicity.

We compare single user digital multi-carrier spread spectrum modulation with direct sequence spread spectrum in the presence of frequency-selective multipath fading. We derive closed-form expressions for the bit error probability and show that MC-SS is more robust to multipath fading than is DS-SS.