Search

This paper considers stochastic convex optimization problems with two sets of constraints: (a) deterministic constraints on the domain of the optimization variable, which are difficult to project onto; and (b) deterministic or stochastic constraints that admit efficient projection. Problems of this form arise frequently in the context of semidefinite programming as well as when various NP-hard problems are solved approximately via semidefinite relaxation. Since projection onto the first set of constraints is difficult, it becomes necessary to explore projection-free algorithms, such as the stochastic Frank-Wolfe (FW) algorithm. On the other hand, the second set of constraints cannot be handled in the same way, and must be incorporated as an indicator function within the objective function, thereby complicating the application of FW methods. Similar problems have been studied before; however, they suffer from slow convergence rates. This work, equipped with momentum based gradient tracking technique, guarantees fast convergence rates on par with the best-known rates for problems without the second set of constraints. Zeroth-order variants of the proposed algorithms are also developed and again improve upon the state-of-the-art rate results. We further propose the novel trimmed FW variants that enjoy the same convergence rates as their classical counterparts, but are empirically shown to require significantly fewer calls to the linear minimization oracle speeding up the overall algorithm. The efficacy of the proposed algorithms is tested on relevant applications of sparse matrix estimation, clustering via semidefinite relaxation, and uniform sparsest cut problem. [ABSTRACT FROM AUTHOR]

With the increased proliferation of smart devices, the transit passengers of today expect a higher quality of service in the form of real-time traffic updates, accurate expected time-of-arrival (ETA) predictions. Providing these services requires public transit agencies and private transportation players to maintain full situational awareness of the city-wide traffic. However, most such agencies and companies are resource-constrained and do not have access to city-wide traffic data. The availability of sparsely sampled and outlier-corrupted traffic data renders the resulting traffic maps patchy and unreliable and necessitates the use of sophisticated real-time traffic interpolation and prediction algorithms. Moreover, since the traffic data is measured and collected in a sequential manner, the estimations must also be generated online. Thankfully, the traffic matrices are spatially and temporally structured, allowing the use of time-series and matrix/tensor completion algorithms. This work puts forth a generative model for the traffic density and subsequently uses a variational Bayesian formalism to learn the parameters of the model. Specifically, we consider low-rank traffic matrices whose subspace evolves according to a state-space model with possible sparse outliers. Unlike most matrix/tensor completion algorithms, the proposed model is equipped with automatic relevance determination priors that allow it to learn the parameters in an entirely data-driven manner. A forward-backward algorithm is proposed that enables the updates to be carried out at low-complexity. Simulations carried out on real traffic speed data demonstrate that the proposed algorithm better predicts the future traffic densities as compared to the state-of-the-art matrix/tensor completion algorithms. [ABSTRACT FROM AUTHOR]

Optimizing non-convex functions is of primary importance in modern pattern recognition because it underlies the training of deep networks and nonlinear dimensionality reduction. First-order algorithms under suitable randomized perturbations or step-size rules have been shown to be effective for such settings as their limit points can be guaranteed to be local extrema rather than saddle points. However, it is well-known that the practical convergence of first-order methods is slower than those which exploit additional structure. In particular, empirically, successive convex approximation (SCA) converges faster than first-order methods. However, to date, SCA in general non-convex settings converges to first-order stationary points, which could either be local extrema or saddle points whose performance is typically inferior. To mitigate this issue, we propose calibrated randomized perturbations of SCA, which exhibit the improved convergence rate as compared to the gradient descent counter part. In particular, our main technical contributions are to establish the non-asymptotic performance of SCA algorithm and its perturbed variant converges to an approximate second-order stationary point. Experiments on multi-dimensional scaling, a machine learning problem whose training objective is non-convex, substantiate the performance gains associated with employing random perturbations. [ABSTRACT FROM AUTHOR]

We consider stochastic optimization of a smooth non-convex loss function with a convex non-smooth regularizer. In the online setting, where a single sample of the stochastic gradient of the loss is available at every iteration, the problem can be solved using the proximal stochastic gradient descent (SGD) algorithm and its variants. However in many problems, especially those arising in communications and signal processing, information beyond the stochastic gradient may be available thanks to the structure of the loss function. By constructing a strongly convex surrogate of the loss function at every iteration, the stochastic SCA algorithms can exploit the structural properties of the loss function. In this work, we take a closer look at the stochastic SCA algorithm and develop its asynchronous variant which can be used for resource allocation in wireless networks. While the stochastic SCA algorithm is known to converge asymptotically, its iteration complexity has not been well-studied, and is the focus of the current work. The insights obtained from the non-asymptotic analysis allow us to develop a more practical asynchronous variant of the stochastic SCA algorithm which allows the use of surrogate calculated in earlier iterations. We characterize precise bound on the maximum delay the algorithm can tolerate, while still achieving the same convergence rate. We apply the algorithm to the problem of linear precoding in wireless sensor networks, where it can be implemented at low complexity but is shown to perform well in practice. [ABSTRACT FROM AUTHOR]

This article considers a downlink transmission in a multiuser massive multi-input–multi-output (massive-MIMO) system in both the large-scale and small-scale fading environments. While the base station has many antennas, the associated circuit costs require some antennas to be turned off, thus necessitating antenna/RF-chain selection. Furthermore, the users have quality-of-service (QoS) constraints and cannot be served within the specified power budget and also with arbitrarily low signal-to-interference-plus-noise ratios. Instead, the base stations seek to schedule only a subset of users for which the QoS-constraints can be met, while the remaining users must be scheduled in other time-frequency slots. The problem is considered under both long and short time-scales. The longer time-scale problem entails solving for the power, user allocation, and number of active antennas to be used over multiple coherence intervals. While the need to select the optimum set of users makes the problem combinatorial, a low-complexity algorithm is proposed that allows us to solve it in polynomial time. For the more computationally intensive per-coherence interval problem, we employ a convex relaxation-based approach in order to obtain an approximate solution. Detailed simulations are carried out to establish that the proposed algorithms outperform standard greedy approaches and are close to optimal for several settings. [ABSTRACT FROM AUTHOR]

Recent decades have observed an exponential growth in network traffic, thanks to the increased popularity of real-time applications, such as live video chat and gaming. The resulting growth in the network infrastructure has made it difficult for the service providers to abide by the service level agreements, especially with regards to the quality-of-service guarantees. Predicting network latencies from noisy and missing measurements has therefore emerged as an important problem, and a plethora of solutions have been proposed for the same. Existing network latency predictions rely either on Euclidean embedding or matrix completion methods. This work considers the estimation and prediction of network latencies from a sequence of noisy and incomplete latency matrices collected over time. An adaptive matrix completion algorithm is proposed that can handle streaming data at low computational complexity. The performance of the proposed algorithm is characterized both in theory and using a real dataset, demonstrating its viability as a network monitoring tool. [ABSTRACT FROM AUTHOR]

Online convex optimization (OCO) encapsulates supervised learning when training sets are large-scale or dynamic, and has grown essential as data has proliferated. OCO decomposes learning into a sequence of sub-problems, each of which must be solved with limited information. To ensure safe model adaption or to avoid overfitting, constraints are often imposed, which are often addressed with projections or Lagrangian relaxation. To avoid this complexity incursion, we propose to study Frank-Wolfe (FW), which operates by updating in collinear directions with the gradient but guaranteed to be feasible. We specifically focus on its use in non-stationary settings, motivated by the fact that its iterates have structured sparsity that may be employed as a distribution-free change-point detector. We establish performance in terms of dynamic regret, which quantifies cost accumulation as compared with the optimal at each individual time slot. Specifically, for convex losses, we establish O(T1/2) dynamic regret up to metrics of non-stationarity. We relax the algorithm's required information to only noisy gradient estimates, i.e., partial feedback. We also consider a mini-batching ‘Meta-Frank Wolfe’, and characterize its dynamic regret. Experiments on matrix completion problem and background separation in video demonstrate favorable performance of the proposed scheme. Moreover, the structured sparsity of FW is experimentally observed to yield the sharpest tracker of change points among alternative approaches to non-stationary online convex optimization. [ABSTRACT FROM AUTHOR]

In this work, we address optimization problems where the objective function is a nonlinear function of an expected value, i.e., compositional stochastic programs. We consider the case where the decision variable is not vector-valued but instead belongs to a Reproducing Kernel Hilbert Space (RKHS), motivated by risk-aware formulations of supervised learning. We develop the first memory-efficient stochastic algorithm for this setting, which we call Compositional Online Learning with Kernels (COLK). COLK, at its core a two time-scale stochastic approximation method, addresses the facts that (i) compositions of expected value problems cannot be addressed by stochastic gradient method due to the presence of an inner expectation; and (ii) the RKHS-induced parameterization has complexity which is proportional to the iteration index which is mitigated through greedily constructed subspace projections. We provide, for the first time, a non-asymptotic tradeoff between the complexity of a function parameterization and its required convergence accuracy for both strongly convex and non-convex objectives under constant step-sizes. Experiments with risk-sensitive supervised learning demonstrate that COLK consistently converges and performs reliably even when data is full of outliers, and thus marks a step towards overfitting. Specifically, we observe a favorable tradeoff between model complexity, consistent convergence, and statistical accuracy for data associated with heavy-tailed distributions. [ABSTRACT FROM AUTHOR]

With growing connection of distributed energy resources, availability of demand side response technologies, deployment of smart meters, the distribution system needs advanced network automation for running the system efficiently. State estimation is the core driver of network automation. While the output from SMs will make the state estimation more accurate, advanced metering infrastructures come with several challenges such as noisy, erroneous measurement including lost or missed measurements, exposure to cyber attack and so on. This study proposes a three-phase unbalanced distribution system state estimation which is robust against noisy distribution system measurements, bad data attacks and missing or delayed measurements. This method considers measurement from hybrid sources such as SCADA, micro-phasor measurement units (${\mu}$μ PMUs) and SMs. Kalman smoother is used to fill the missing measurements and expectation-maximisation based forecasting is used to interpolate the hybrid measurements to a common timestamp and compensate for the delay in SM measurements. Extensive numerical comparisons are made on IEEE 13, 37 and 123 bus systems to test the robustness of the proposed DSSE against delayed SM measurements and bad or noisy data. An IEEE 24 bus system is modelled and real-time measurement devices are interfaced to it in Hypersim. The data from the hybrid measurement devices of IIT Kanpur smart grid is also used to test the robustness of the proposed method. [ABSTRACT FROM AUTHOR]

With growing connection of distributed energy resources, availability of demand side response technologies, deployment of smart meters, the distribution system needs advanced network automation for running the system efficiently. State estimation is the core driver of network automation. While the output from SMs will make the state estimation more accurate, advanced metering infrastructures come with several challenges such as noisy, erroneous measurement including lost or missed measurements, exposure to cyber attack and so on. This study proposes a three‐phase unbalanced distribution system state estimation which is robust against noisy distribution system measurements, bad data attacks and missing or delayed measurements. This method considers measurement from hybrid sources such as SCADA, micro‐phasor measurement units (μ PMUs) and SMs. Kalman smoother is used to fill the missing measurements and expectation‐maximisation based forecasting is used to interpolate the hybrid measurements to a common timestamp and compensate for the delay in SM measurements. Extensive numerical comparisons are made on IEEE 13, 37 and 123 bus systems to test the robustness of the proposed DSSE against delayed SM measurements and bad or noisy data. An IEEE 24 bus system is modelled and real‐time measurement devices are interfaced to it in Hypersim. The data from the hybrid measurement devices of IIT Kanpur smart grid is also used to test the robustness of the proposed method. [ABSTRACT FROM AUTHOR]

Batch training of machine learning models based on neural networks is well established, whereas, to date, streaming methods are largely based on linear models. To go beyond linear in the online setting, nonparametric methods are of interest due to their universality and ability to stably incorporate new information via convexity or Bayes's rule. Unfortunately, when applied online, nonparametric methods suffer a "curse of dimensionality," which precludes their use: their complexity scales at least with the time index. We survey online compression tools that bring their memory under control and attain approximate convergence. The asymptotic bias depends on a compression parameter that trades off memory and accuracy. Applications to robotics, communications, economics, and power are discussed as well as extensions to multiagent systems. [ABSTRACT FROM AUTHOR]

State estimator (SE) is a critical tool in the power system control center (CC) and is used by the system operators for real-time control and monitoring. Traditional SE techniques (static and dynamic) work under the assumption that there is no delay in communicating the sensor measurements to the CC. But in actual scenario, measurements are often randomly delayed and are not immediately available for processing. When the observations arrive with a delay, the current estimate of the system state may not be evaluated correctly, since the missing measurement may be carrying relevant information for estimating the states. With the increased deployment of phasor measurement units (PMUs) as sensors in the grid, time-stamped synchronized measurements are readily available. Time-stamped measurements enable the delay to be exactly known at the estimator. In this paper, a modified re-iterated Kalman filter that can handle both lost and delayed measurements without having any knowledge of the delay statistics, is proposed. The proposed algorithm is tested and validated in real-time using Real Time Digital Power System Simulator (RTDS). [ABSTRACT FROM AUTHOR]

Well-designed queuing systems form the backbone of modern communications, distributed computing, and content delivery architectures. Designs balancing infrastructure costs and user experience indices require tools from teletraffic theory and operations research. A standard approach to designing such systems involves formulating optimization problems that strive to maximize the pertinent utility functions while adhering to quality-of-service and other physical constraints. In many cases, formulating such problems necessitates making simplistic assumptions on arrival and departure processes to keep the problem simple. This work puts forth a stochastic optimization framework for designing queuing systems where the exogenous processes may have arbitrary and unknown distributions. We show that many such queuing design problems can generally be formulated as stochastic optimization problems where the objective and constraint are non-linear functions of expectations. The compositional structure obviates the use of classical stochastic approximation approaches where the stochastic gradients are often required to be unbiased. To this end, a constrained stochastic compositional gradient descent algorithm is proposed that utilizes a tracking step for the expected value functions. The non-asymptotic performance of the proposed algorithm is characterized via its iteration complexity. Numerical tests allow us to validate the theoretical results and demonstrate the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Indoor localization is a challenging task as the signal propagation in indoor environments does not adhere to the classical path loss or other simple models. Modern high-accuracy indoor localization algorithms rely on fingerprinting methods that entail an offline phase of data collection and mapping phase. This work puts forth a dictionary learning framework for fingerprinting indoor locations using GSM, WiFi, and other sensor measurements. Different from the existing works, the proposed methods are model-free, can handle missing measurements, and fingerprints can be flexibly updated in an online fashion. The dictionary learning algorithm itself is appropriately modified to ensure incoherence between fingerprints of nearby locations and appropriate weighing of the sparse coefficients. A hidden markov model based tracking algorithm is also provided that considers the recent history while estimating the user location. Detailed experiments are carried out over four different maps to demonstrate the efficacy and usefulness of the proposed algorithm, in comparison to the state-of-the-art classification-based and model-based indoor localization algorithms. [ABSTRACT FROM AUTHOR]

Tracking the system states of an extensive power system is an onerous task as it estimates the power system states by processing a large measurement set. This paper proposes a new asynchronous decentralized forecasting-aided state estimator (ADFASE) to track the states of a power system. The networked power system is partitioned into smaller systems, which processes the local measurements in parallel to estimate system states of reduced dimensionality; thereby reducing the computational complexity. The subsystems then communicate the local information to neighboring subsystems, which collate the incoming information to obtain near-optimal estimates. The decentralized topology eliminates the need for any centralized infrastructure. Each processor operates in an asynchronous manner, and the information is communicated to neighboring subsystems as and when the information is processed. The information received by the subsystems are assimilated asynchronously and does not need any prior synchronization between the nodes. The performance of the proposed estimator is evaluated using IEEE 30 and 118-bus systems. [ABSTRACT FROM AUTHOR]

We consider expected risk minimization in multi-agent systems comprised of distinct subsets of agents operating without a common time scale. Each individual in the network is charged with minimizing the global objective function, which is an average of sum of the statistical average loss function of each agent in the network. Since agents are not assumed to observe data from identical distributions, the hypothesis that all agents seek a common action is violated, and thus the hypothesis upon that consensus constraints are formulated is violated. Thus, we consider nonlinear network proximity constraints, which incentivize nearby nodes to make decisions that are close to one another but do not necessarily coincide. Moreover, agents are not assumed to receive their sequentially arriving observations on a common time index, and thus seek to learn in an asynchronous manner. An asynchronous stochastic variant of the Arrow–Hurwicz saddle point method is proposed to solve this problem that operates by alternating primal stochastic descent steps and Lagrange multiplier updates that penalize the discrepancies between agents. This tool leads to an implementation that allows for each agent to operate asynchronously with local information only and message passing with neighbors. Our main result establishes that the proposed method yields convergence in expectation both in terms of the primal sub-optimality and constraint violation to radii of sizes ${\mathcal O}(\sqrt{T})$ and ${\mathcal O}(T^{3/4})$ , respectively. Empirical evaluation on an asynchronously operating wireless network that manages user channel interference through an adaptive communications pricing mechanism demonstrates that our theoretical results translates well to practice. [ABSTRACT FROM AUTHOR]

We consider nondifferentiable dynamic optimization problems such as those arising in robotics and subspace tracking. Given the computational constraints and the time-varying nature of the problem, a low-complexity algorithm is desirable, while the accuracy of the solution may only increase slowly over time. We put forth the proximal online gradient descent (OGD) algorithm for tracking the optimum of a composite objective function comprising of a differentiable loss function and a nondifferentiable regularizer. An online learning framework is considered and the gradient of the loss function is allowed to be erroneous. Both, the gradient error as well as the dynamics of the function optimum or target are adversarial and the performance of the inexact proximal OGD is characterized in terms of its dynamic regret, expressed in terms of the cumulative error and path length of the target. The proposed inexact proximal OGD is generalized for application to large-scale problems where the loss function has a finite sum structure. In such cases, evaluation of the full gradient may not be viable and a variance reduced version is proposed that allows the component functions to be subsampled. The efficacy of the proposed algorithms is tested on the problem of formation control in robotics and on the dynamic foreground–background separation problem in video. [ABSTRACT FROM AUTHOR]

Stochastic network optimization problems entail finding resource allocation policies that are optimum on an average but must be designed in an online fashion. Such problems are ubiquitous in communication networks, where resources such as energy and bandwidth are divided among nodes to satisfy certain long-term objectives. This paper proposes an asynchronous incremental dual decent resource allocation algorithm that utilizes delayed stochastic gradients for carrying out its updates. The proposed algorithm is well-suited to heterogeneous networks as it allows the computationally-challenged or energy-starved nodes to, at times, postpone the updates. The asymptotic analysis of the proposed algorithm is carried out, establishing dual convergence under both, constant and diminishing step sizes. It is also shown that with constant step size, the proposed resource allocation policy is asymptotically near-optimal. An application involving multicell coordinated beamforming is detailed, demonstrating the usefulness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper considers a general stochastic resource allocation problem that arises widely in wireless networks, cognitive radio, networks, smart-grid communications, and cross-layer design. The problem formulation involves expectations with respect to a collection of random variables with unknown distributions, representing exogenous quantities such as channel gain, user density, or spectrum occupancy. We consider the constant step-size stochastic dual subgradient descent (SDSD) method that has been widely used for online resource allocation in networks. The problem is solved in dual domain, which results in a primal resource allocation subproblem at each time instant. The goal here is to characterize the non-asymptotic behavior of such stochastic resource allocations in an almost sure sense. It is well known that with a step size of \epsilon , SDSD converges to an \mathcal {O}(\epsilon) -sized neighborhood of the optimum. In practice, however, there exists a trade-off between the rate of convergence and the choice of \epsilon $ . This paper establishes a convergence rate result for the SDSD algorithm that precisely characterizes this trade-off. Toward this end, a novel stochastic bound on the gap between the objective function and the optimum is developed. The asymptotic behavior of the stochastic term is characterized in an almost sure sense, thereby generalizing the existing results for the stochastic subgradient methods. For the stochastic resource allocation problem at hand, the result explicates the rate with which the allocated resources become near-optimal. As an application, the power and user-allocation problem in device-to-device networks is formulated and solved using the SDSD algorithm. Further intuition on the rate results is obtained from the verification of the regularity conditions and accompanying simulation results. [ABSTRACT FROM PUBLISHER]

Multiagent systems are being increasingly deployed in challenging environments for performing complex tasks such as multitarget tracking, search-and-rescue, and intrusion detection. Not with standing the computational limitations of individual robots, such systems rely on collaboration to sense and react to the environment. This paper formulates the generic target tracking problem as a time-varying optimization problem and puts forth an inexact online gradient descent method for solving it sequentially. The performance of the proposed algorithm is studied by characterizing its dynamic regret, a notion common to the online learning literature. Building upon the existing results, we provide improved regret rates that not only allow nonstrongly convex costs but also explain the role of the cumulative gradient error. Two distinct classes of problems are considered: one in which the objective function adheres to a quadratic growth condition, and another where the objective function is convex but the variable belongs to a compact domain. For both cases, results are developed while allowing the error to be either adversarial or arising from a white noise process. Further, the generality of the proposed framework is demonstrated by developing online variants of existing stochastic gradient algorithms and interpreting them as special cases of the proposed inexact gradient method. The efficacy of the proposed inexact gradient framework is established on a multiagent multitarget tracking problem, while its flexibility is exemplified by generating online movie recommendations for Movielens 10M dataset. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of decentralized sequential estimation in dynamic wireless sensor networks. A coherent medium access control layer is considered, and optimal linear precoder and decoder matrices are designed to minimize the mean square error (MSE) in an online setting. Different from the state-of-the-art decentralized estimators, the proposed framework is flexible enough to handle time-varying parameters, channel gains, and power constraints. Although the general transceiver design problem is nonconvex, a fast block coordinate descent-based method is proposed that incurs very low complexity and yields near-optimal solutions. Motivated by the need to reduce the communication overhead incurred by the centralized schemes, two fully distributed transceiver design algorithms that make use of the constrained linear minimum MSE machinery are also advocated. The resulting approximate precoders are not only near optimal but can also be calculated locally at each sensor. Finally, the entire framework is generalized so as to allow tracking of parameters that follow a known state-space model. Extensive simulations are provided to demonstrate the efficacy of the proposed class of algorithms. [ABSTRACT FROM PUBLISHER]

The low-rank matrix completion problem is fundamental to a number of tasks in data mining, machine learning, and signal processing. This paper considers the problem of adaptive matrix completion in time-varying scenarios. Given a sequence of incomplete and noise-corrupted matrices, the goal is to recover and track the underlying low rank matrices. Motivated from the classical least-mean square (LMS) algorithms for adaptive filtering, three LMS-like algorithms are proposed for estimating and tracking low-rank matrices. Performance of the proposed algorithms is provided in form of nonasymptotic bounds on the tracking mean-square error. Tracking performance of the algorithms is also studied via detailed simulations over real-world datasets. [ABSTRACT FROM PUBLISHER]

We integrate a wireless powered communication network with a cooperative cognitive radio network, where multiple secondary users (SUs) powered wirelessly by a hybrid access point (HAP) help a primary user relay the data. As a reward for the cooperation, the secondary network gains the spectrum access where SUs transmit to HAP using time division multiple access. To maximize the sum throughput of SUs, we present a secondary sum-throughput optimal resource allocation (STORA) scheme. Under the constraint of meeting target primary rate, the STORA scheme chooses the optimal set of relaying SUs and jointly performs the time and energy allocation for SUs. In particular, by exploiting the structure of the optimal solution, we find the order in which SUs are prioritized to relay primary data. Since the STORA scheme focuses on the sum throughput, it becomes inconsiderate toward individual SU throughput, resulting in low fairness. To enhance fairness, we investigate three resource allocation schemes, which are: 1) equal time allocation; 2) minimum throughput maximization; and 3) proportional time allocation. Simulation results reveal the tradeoff between sum throughput and fairness. The minimum throughput maximization scheme is the fairest one as each SU gets the same throughput, but yields the least SU sum throughput. [ABSTRACT FROM AUTHOR]

This paper considers the problem of cooperative localization in mobile networks. In static networks, node locations can be obtained from pairwise distance measurements using the classical multidimensional scaling (MDS) approach. This paper introduces a modified MDS framework that also incorporates relative velocity measurements if available in mobile networks. The proposed cost function is minimized via a low complexity majorization algorithm. A distributed variant of the proposed algorithm is also outlined for use in large resource-constrained multi-hop networks. The proposed algorithm incurs low computational and communication cost, and handles practical constraints such as missing measurements and variable node velocities. Simulation results corroborate the performance gains obtained by the proposed algorithm over state-of-the-art localization algorithms. [ABSTRACT FROM AUTHOR]

This letter considers precoder design for orthogonal frequency division multiplexing (OFDM) systems with insufficient cyclic prefix (CP). Interference alignment is utilized to formulate the precoder design problem as a bit error rate (BER) minimization problem subject to a total power constraint. Subsequently, a novel closed-form solution is derived for the optimal precoder by exploiting Schur convexity and interference alignment-based interblock interference (IBI) suppression. The resulting precoder is also shown to be mean-square-error (MSE) optimal, and generalizes the existing designs. Closed-form expressions are also developed for quantifying the signal-to-noise ratio (SNR) gain of the proposed design over existing designs for practical channels with a decaying power-delay profile. Simulation results corroborate the performance improvements over existing MSE optimal designs considering the availability of both full and partial channel state information at the transmitter (CSIT) for various power delay profiles. [ABSTRACT FROM PUBLISHER]

Distributed medium access control (MAC) is important for efficient exploitation of spectrum opportunities in cognitive radio networks. This letter proposes a channel-aware distributed MAC protocol for multichannel cognitive radio networks. The transmitting nodes use channel state information to exploit the available multiuser and multichannel diversity, by contending only under relatively favorable channel conditions. Towards this end, each node utilizes a threshold that is dynamically updated according to certain rules. Simulation results corroborate the throughput gains achieved by the proposed protocol. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

Communication networks have evolved from specialized research and tactical transmission systems to large-scale and highly complex interconnections of intelligent devices, increasingly becoming more commercial, consumer oriented, and heterogeneous. Propelled by emergent social networking services and high-definition streaming platforms, network traffic has grown explosively thanks to the advances in processing speed and storage capacity of state-of-the-art communication technologies. As ?netizens? demand a seamless networking experience that entails not only higher speeds but also resilience and robustness to failures and malicious cyberattacks, ample opportunities for signal processing (SP) research arise. The vision is for ubiquitous smart network devices to enable data-driven statistical learning algorithms for distributed, robust, and online network operation and management, adaptable to the dynamically evolving network landscape with minimal need for human intervention. This article aims to delineate the analytical background and the relevance of SP tools to dynamic network monitoring, introducing the SP readership to the concept of dynamic network cartography?a framework to construct maps of the dynamic network state in an efficient and scalable manner tailored to large-scale heterogeneous networks. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM PUBLISHER]

This paper deals with network-coded multicast for real-time and streaming-media applications where packets have explicit expiration deadlines. Most of the popular network coding approaches require asymptotically large block-lengths, thereby incurring long decoding delays. The present paper introduces a joint scheduling and network coding design that aims to maximize the average throughput while respecting the packet deadlines. The novel approach relies on a time-unwrapped graph expansion in order to construct the network codes. The resultant algorithm draws from the well-known augmenting-path algorithm, and is both distributed as well as scalable. For networks with primary interference, a lower-bound on the worst-case performance of the algorithm is provided. The associated optimization problem is also analyzed from an integer programming perspective, and a set of valid inequalities is derived to obtain an upper bound. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

Training sequences for data-aided timing estimation in multi-input multi-output systems are designed. It is observed that for low complexity implementation, the sequences must necessarily satisfy the zero cross-correlation zone property. By restricting our search to a more tractable subset of this class of sequences, we are able to minimize the modified Cramer-Rao bound in closed form and obtain sequences whose mean square error performance is close to that of the optimal orthogonal sequences. Two constant modulus sequences with even lower implementation complexity are also proposed. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]