Many signal processing and machine learning applications are framed as constrained optimization problems with positive definite constraints. Important examples include kernel matrix learning, covariance estimation of Gaussian distributions, maximum likelihood parameter estimation of elliptically contoured distributions, parameter estimation in Gaussian mixture models and matrix square root. In this work, utilizing Riemannian geometric principles, we propose coordinate-descent algorithms on the Riemannian manifold of symmetric positive definite (SPD) matrices. We further identify a broad class of functions encompassing all the aforementioned applications. Finally, we demonstrate that for this class of functions, the proposed algorithm achieves per-iteration complexities of O(n)—an order of magnitude lower than the O(n3) or higher complexities of full update algorithms like Riemannian gradient-descent and interior-point methods. Interestingly, the proposed algorithm is significantly faster than the Burer-Monteiro factorization based coordinate descent algorithm, which has a per-iteration complexity of O(n2), as confirmed through simulations on the log-det minimization problem.

This paper explores consensus-based decentralized stochastic optimization for minimizing stochastic non-convex objectives, potentially accompanied by non-smooth convex regularizers and subject to non-linear functional constraints. The original problem is reformulated using the exact penalty method. Our proposed approach relies on successive convex approximation (SCA), specifically the Decentralized Momentum-based Linear Stochastic SCA (D-MLSSCA), to solve this equivalent problem. The algorithm iteratively solves a strongly convex subproblem at each node with linearized constraints. Recursive momentum-based local gradient updates are leveraged to accelerate the convergence. Despite solving a simpler subproblem, we achieve a stochastic first-order (SFO) complexity of ${\mathcal{O}}\left({{ \in ^{ - 3/2}}}\right)$ to reach an ϵ-stationary point. Notably, this SFO complexity matches the lower bound for unconstrained stochastic non-convex optimization in the centralized setting.

This work considers a high-dimensional decentralized optimization problem where computing the full gradient is prohibitively expensive. This is a common issue in Partial Difference Equation (PDE)-constrained optimization and some machine learning applications. Stochastic subspace descent (SSD) solves this problem in a single-agent setting by computing the projection of gradients on random low-dimensional subspaces. We study this problem in a more challenging decentralized setting, where individual agents can only access their local objective losses. We propose VR-DSSD-GT, a novel variance reductionbased extension of SSD, to overcome this issue. Variance reduction (VR) helps achieve accelerated convergence, while gradient tracking (GT) facilitates exact convergence to the global solution, regardless of the heterogeneity across local objectives. With smooth and strongly convex loss functions, our algorithm achieves linear convergence to the solution. Our results generalize the existing results for gradient-based methods to the broader class of subspace-based methods. Experimental results corroborate and complement our theoretical findings.

The problem of minimizing the sum of $n$ functions in $d$ dimensions is ubiquitous in machine learning and statistics. In many applications where the number of observations $n$ is large, it is necessary to use incremental or stochastic methods, as their per-iteration cost is independent of $n$. Of these, Quasi-Newton (QN) methods strike a balance between the per-iteration cost and the convergence rate. Specifically, they exhibit a superlinear rate with $O(d^2)$ cost in contrast to the linear rate of first-order methods with $O(d)$ cost and the quadratic rate of second-order methods with $O(d^3)$ cost. However, existing incremental methods have notable shortcomings: Incremental Quasi-Newton (IQN) only exhibits asymptotic superlinear convergence. In contrast, Incremental Greedy BFGS (IGS) offers explicit superlinear convergence but suffers from poor empirical performance and has a per-iteration cost of $O(d^3)$. To address these issues, we introduce the Sharpened Lazy Incremental Quasi-Newton Method (SLIQN) that achieves the best of both worlds: an explicit superlinear convergence rate, and superior empirical performance at a per-iteration $O(d^2)$ cost. SLIQN features two key changes: first, it incorporates a hybrid strategy of using both classic and greedy BFGS updates, allowing it to empirically outperform both IQN and IGS. Second, it employs a clever constant multiplicative factor along with a lazy propagation strategy, which enables it to have a cost of $O(d^2)$. Additionally, our experiments demonstrate the superiority of SLIQN over other incremental and stochastic Quasi-Newton variants and establish its competitiveness with second-order incremental methods.

Non-parametric function approximators provide a principled way to fit nonlinear statistical models while affording formal performance guarantees. However, their complexity drawbacks are well-understood: they define a statistical representation whose complexity scales with the sample size through the fact that they retain all past samples. In the case of streaming data, this complexity may grow unbounded. One is faced with the question of how to suitably trade off representational complexity with statistical accuracy, which may be addressed with various approximation methods. In this work, we formalize that greedy-based approximations, under suitably chosen compression statistics, can admit near-optimal representations. The key driver of this result is a novel connection between the reproducing kernel Hilbert Space (RKHS) norm and the log-determinant of the kernel matrix, which has been shown to be a submodular set function of a collection of points. This allows us to design a constructive variant of a greedy subspace projections in [1], [2] according to a submodular set cover (SSC) problem, which provably picks at most logarithmically more elements than the optimal one. We validate our constructive approach by doing simulation on real ocean data from the Gulf of Mexico [3].

Newton-type methods are popular in federated learning due to their fast convergence. Still, they suffer from two main issues, namely: low communication efficiency and low privacy due to the requirement of sending Hessian information from clients to parameter server (PS). In this work, we introduced a novel framework called FedNew in which there is no need to transmit Hessian information from clients to PS, hence resolving the bottleneck to improve communication efficiency. In addition, FedNew hides the gradient information and results in a privacy-preserving approach compared to the existing state-of-the-art. The core novel idea in FedNew is to introduce a two level framework, and alternate between updating the inverse Hessian-gradient product using only one alternating direction method of multipliers (ADMM) step and then performing the global model update using Newton’s method. Though only one ADMM pass is used to approximate the inverse Hessian-gradient product at each iteration, we develop a novel theoretical approach to show the converging behavior of FedNew for convex problems. Additionally, a significant reduction in communication overhead is achieved by utilizing stochastic quantization. Numerical results using real datasets show the superiority of FedNew compared to existing methods in terms of communication costs.

Non-asymptotic analysis of quasi-Newton methods have received a lot of attention recently. In particular, several works have established a non-asymptotic superlinear rate of $$\mathcal{O}((1/\sqrt{t})^t)$$ for the (classic) BFGS method by exploiting the fact that its error of Newton direction approximation approaches zero. Moreover, a greedy variant of the BFGS method was recently proposed which accelerates the convergence of BFGS by directly approximating the Hessian matrix, instead of Newton direction, and achieves a fast local quadratic convergence rate. Alas, the local quadratic convergence of Greedy-BFGS requires way more updates compared to the number of iterations that BFGS requires for a local superlinear rate. This is due to the fact that in Greedy-BFGS the Hessian is directly approximated and the Newton direction approximation may not be as accurate as the one for BFGS. In this paper, we close this gap and present a novel BFGS method that has the best of two worlds. More precisely, it leverages the approximation ideas of both BFGS and Greedy-BFGS to properly approximate both the Newton direction and the Hessian matrix. Our theoretical results show that our method out-performs both BFGS and Greedy-BFGS in terms of convergence rate, while it reaches its quadratic convergence rate with fewer steps compared to Greedy-BFGS. Numerical experiments on various datasets also confirm our theoretical findings.

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.

Cloud computing facilitates the access of applications and data from any location by a distributed storage system. Erasure codes offer better data replication technique with reduced storage costs for more reliability. This paper considers the erasure-coded data center with multiple servers in a wireless network where each is equipped with a base-station. The cause of latency in the file retrieval process is mainly due to queuing delays at each server. This work puts forth a stochastic optimization framework for obtaining the optimal scheduling policy that maximizes users’ quality of service (QoS) while adhering to the latency requirements. We further show that the problem has non-linear functions of expectations in objective and constraints and is impossible to solve with traditional SGD like algorithms. We propose a new algorithm that addresses compositional structure in the problem. Further, we show that the proposed algorithm achieves a faster convergence rate than the best-known results. Finally, we test the efficacy of the proposed method in a simulated environment.

Federated Learning (FL) refers to the paradigm where multiple worker nodes (WNs) build a joint model by using local data. Despite extensive research, for a generic non-convex FL problem, it is not clear, how to choose the WNs' and the server's update directions, the minibatch sizes, and the local update frequency, so that the WNs use the minimum number of samples and communication rounds to achieve the desired solution. This work addresses the above question and considers a class of stochastic algorithms where the WNs perform a few local updates before communication. We show that when both the WN's and the server's directions are chosen based on certain stochastic momentum estimator, the algorithm requires $\tilde{\mathcal{O}}(\epsilon^{-3/2})$ samples and $\tilde{\mathcal{O}}(\epsilon^{-1})$ communication rounds to compute an $\epsilon$-stationary solution. To the best of our knowledge, this is the first FL algorithm that achieves such {\it near-optimal} sample and communication complexities simultaneously. Further, we show that there is a trade-off curve between local update frequencies and local minibatch sizes, on which the above sample and communication complexities can be maintained. {Finally, we show that for the classical FedAvg (a.k.a. Local SGD, which is a momentum-less special case of the STEM), a similar trade-off curve exists, albeit with worse sample and communication complexities. Our insights on this trade-off provides guidelines for choosing the four important design elements for FL algorithms, the update frequency, directions, and minibatch sizes to achieve the best performance.}

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.

Projection based algorithms are popular in the literature for online convex optimization with convex constraints and the projection step results in a bottleneck for the practical implementation of the algorithms. To avoid this bottleneck, we propose a projection-free scheme based on Frank-Wolfe: where instead of online gradient steps, we use steps that are collinear with the gradient but guaranteed to be feasible. 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 $\mathcal{O}\left( {{T^{1/2}}} \right)$ dynamic regret up to metrics of non-stationarity. We relax the algorithm’s required information to only noisy gradient estimates, i.e., partial feedback and derived the dynamic regret bounds. Experiments on matrix completion problem and background separation in video demonstrate favorable performance of the proposed scheme.

Many real world applications that suffer from missing data and outliers can be modeled in a matrix completion framework. In this paper, we consider low-rank matrices whose subspace evolves according to a state-space model and propose an online variational Bayesian formulation to learn the low rank components as well as the state-space model. Unlike the other matrix/tensor completion techniques, in our framework, the key algorithm parameters like rank and various noise power need not be fine-tuned and are learned automatically. We also propose a forward-backward algorithm that allows update to be carried out at low complexity manner. Simulations performed on the real world traffic data illustrates promising imputation as well as temporal prediction performance even in an online setup.

This paper considers a single cell multi-antenna base station delivering content to multiple cache enabled single-antenna users. Coding strategies are developed that allow for decentralized placement in the wireless setting. Three different cases namely, max-min multicasting, linear combinations in the complex field, and linear combinations in the finite field, are considered and closed-form rate expressions are provided that hold with high probability. For the case of max-min fair multicasting delivery, we propose a new coding scheme that is capable of working with only two-user broadcasts. A cyclic-exchange protocol for efficient content delivery is proposed and shown to perform almost as well as the original multi-user broadcast scheme.

This paper considers the problem of online optimal trajectory design under time-varying environments. Of particular interest is the design of energy-efficient trajectories under strong and uncertain disturbances in ocean environments and time-varying goal location. We formulate the problem within the constrained online convex optimization formalism, and a modified online gradient descent algorithm is motivated. The mobility constraints are met using a carefully chosen stepsize, and the proposed algorithm is shown to incur sublinear regret. Different from the state-of-the-art algorithms that entail planning and re-planning the full trajectory using forecast data at each time instant, the proposed algorithm is entirely online and relies mostly on the current ocean velocity measurements at the vehicle locations. The trade-off between excess delay incurred in reaching the goal and the overall energy consumption is examined via numerical tests carried out on real data obtained from the regional ocean modelling system. As compared to the state-of-the-art algorithms, the proposed algorithm is not only energy-efficient but also several orders of magnitude computationally efficient.

Robotic calibration allows for the fusion of data from multiple sensors such as odometers, cameras, etc., by providing appropriate relationships between the corresponding reference frames. For wheeled robots equipped with camera/lidar along with wheel encoders, calibration entails learning the motion model of the sensor or the robot in terms of the data from the encoders and generally carried out before performing tasks such as simultaneous localization and mapping (SLAM). This work puts forward a novel Gaussian Process-based non-parametric approach for calibrating wheeled robots with arbitrary or unknown drive configurations. The procedure is more general as it learns the entire sensor/robot motion model in terms of odometry measurements. Different from existing non-parametric approaches, our method relies on measurements from the onboard sensors and hence does not require the ground truth information from external motion capture systems. Alternatively, we propose a computationally efficient approach that relies on the linear approximation of the sensor motion model. Finally, we perform experiments to calibrate robots with un-modelled effects to demonstrate the accuracy, usefulness, and flexibility of the proposed approach.

Multi-agent systems are being increasingly deployed in challenging environments for performing complex tasks such as multi-target tracking, search-and-rescue, and intrusion detection. 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 non-strongly convex costs but also explicating the role of the cumulative gradient error. The objective function is convex but the variable belongs to a compact domain. The efficacy of the proposed inexact gradient framework is established on a multi-agent multi-target tracking problem.

This paper considers the problem of designing the user trajectory in a device-to-device communications setting. We consider a pair of pedestrians connected through a D2D link. The pedestrians seek to reach their respective destinations, while using the D2D link for data exchange applications such as file transfer, video calling, and online gaming. In order to enable better D2D connectivity, the pedestrians are willing to deviate from their respective shortest paths, at the cost of reaching their destinations slightly late. A generic trajectory optimization problem is formulated and solved for the case when full information about the problem in known in advance. Motivated by the D2D user's need to keep their destinations private, we also formulate a regularized variant of the problem that can be used to develop a fully online algorithm. The proposed online algorithm is quite efficient, and is shown to achieve a sublinear offline regret while satisfying the required mobility constraints exactly. The theoretical results are backed by detailed numerical tests that establish the efficacy of the proposed algorithms under various settings.

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. The problem is solved in dual domain using a constant step-size stochastic dual subgradient descent (SDSD) method. This 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. This paper establishes a convergence rate result for the SDSD algorithm that precisely characterizes the trade-off between the rate of convergence and the choice of constant step size e. Towards 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. 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.

This paper considers a general stochastic resource allocation problem that arises widely in wireless networks, cognitive radio, networks, smart-grid communications, and crosslayer 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 E, SDSD converges to an O(E)-sized neighborhood of the optimum. In practice, however, there exists a trade-off between the rate of convergence and the choice of E. 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.

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.

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. It is shown that with constant step size, the proposed resource allocation policy is asymptotically near-optimal. An application involving multi-cell coordinated beamforming is detailed, demonstrating the usefulness of the proposed algorithm.

This paper considers a robust precoder design for MIMO-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. To this end, the precoder is designed to be robust to the errors in the available channel estimates, by considering the worst-case BER for optimization. Interestingly, channel estimates at both transmitter and receiver are allowed to be in error. Extensive simulations are carried out to compare the performance of various MIMO-OFDM systems with and without robust precoders.

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.

This paper considers the problem of parameter tracking in wireless sensor networks. The sensor nodes observe a random vector source that varies according to a state-space model, and perform linear precoding on the observations, before coherently transmitting them to the fusion center. The fusion center then linearly decodes the received vector in order to recover the source vector. Compared to the state-of-the-art linear estimation approaches, the tracking requirement complicates the optimal precoder and decoder design, which must themselves be time-varying. Towards this end, the paper proposes an online, block-coordinate descent (BCD)-based algorithm that minimizes the mean-square error at every time slot. The proposed designs are not only near-optimal, but also provably convergent for some cases. Simulation results corroborate the performance enhancements provided by the proposed approach.

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.

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.

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.

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.

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.

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.

We present two maximum likelihood (ML) based estimators for non-data-aided (NDA) symbol timing recovery in MIMO systems. These estimators are based on the classical unconditional ML and the stochastic ML (SML) methods. The proposed estimators utilize information about the particular space-time code used and give performance comparable to data aided estimators, though for a relatively higher complexity. An approximate version of the SML estimator which requires lower implementation complexity is also presented. The loss in SNR due to timing estimation error is also analyzed.