Search

This paper considers an Internet-of-Things (IoT) scenario in which devices sporadically transmit short packets with few pilot symbols over a fading channel. Devices are characterized by unique transmission non-idealities, such as I/Q imbalance. The number of pilots is generally insufficient to obtain an accurate estimate of the end-to-end channel, which includes the effects of fading and of the transmission-side distortion. This paper proposes to tackle this problem by using meta-learning. Accordingly, pilots from previous IoT transmissions are used as meta-training data in order to train a demodulator that is able to quickly adapt to new end-to-end channel conditions from few pilots. Various state-of-the-art meta-learning schemes are adapted to the problem at hand and evaluated, including Model-Agnostic Meta-Learning (MAML), First-Order MAML (FOMAML), REPTILE, and fast Context Adaptation VIA meta-learning (CAVIA). Both offline and online solutions are developed. In the latter case, an integrated online meta-learning and adaptive pilot number selection scheme is proposed. Numerical results validate the advantages of meta-learning as compared to training schemes that either do not leverage prior transmissions or apply a standard joint learning algorithms on previously received data. [ABSTRACT FROM AUTHOR]

In this paper, we propose to extend the standard Convolutional Dictionary Learning problem to a tensor representation where the activations are constrained to be “low-rank” through a Canonical Polyadic decomposition. We show that this additional constraint increases the robustness of the CDL with respect to noise and improve the interpretability of the final results. In addition, we discuss in detail the advantages of this representation and introduce two algorithms, based on ADMM or FISTA, that efficiently solve this problem. We show that by exploiting the low rank property of activations, they achieve lower complexity than the main CDL algorithms. Finally, we evaluate our approach on a wide range of experiments, highlighting the modularity and the advantages of this tensorial low-rank formulation. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the $\ell _1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well explored. In this paper, we show how the manifold structure of the sphere can be exploited to design fast algorithms with provable guarantees for tackling this problem. Specifically, our contribution is fourfold. First, we present a manifold proximal point algorithm (ManPPA) for the problem and show that it converges at a global sublinear rate. Furthermore, we show that ManPPA can achieve a local quadratic convergence rate when applied to sharp instances of the problem. Second, we develop a semismooth Newton-based inexact augmented Lagrangian method for computing the search direction in each iteration of ManPPA and show that it has an asymptotic superlinear convergence rate. Third, we propose a stochastic variant of ManPPA called StManPPA, which is well suited for large-scale computation, and establish its sublinear convergence rate. Both ManPPA and StManPPA have provably faster convergence rates than existing subgradient-type methods. Fourth, using ManPPA as a building block, we propose a new heuristic method for solving a matrix analog of the problem, in which the sphere is replaced by the Stiefel manifold. The results from our extensive numerical experiments on the ODL and RSR problems demonstrate the efficiency and efficacy of our proposed methods. [ABSTRACT FROM AUTHOR]

We consider a distributed resource allocation problem in networks where each transmitter–receiver pair aims at maximizing its local utility function by adjusting its action matrix, which belongs to a given feasible set. This problem has been addressed recently by applying a matrix exponential learning (MXL) algorithm, which has a very appealing convergence rate. In this learning algorithm, however, each transmitter must know an estimate of the gradient matrix of the local utility. The knowledge of the gradient matrix at the transmitters incurs a high signaling overhead, especially that the matrix size increases with the dimension of the action matrix. In this paper, we therefore, investigate two strategies in order to decrease the informational exchange per iteration of the algorithm. In the first strategy, each receiver sends at each iteration part of the elements of the gradient matrix with respect to a certain probability. In the second strategy, each receiver feeds back “sporadically” the whole gradient matrix. We focus on the analysis of the convergence of the MXL algorithm to optimum under these two strategies. We prove that the algorithm can still converge to optimum almost surely. Upper bounds of the average convergence rate are also derived in both situations with general step-size setting, from which we can clearly see the impact of the incompleteness of the feedback information. The proposed algorithms are applied to solve the energy efficiency maximization problem in a multicarrier multiuser multiple-input and multiple-output (MIMO) network. Simulation results further corroborate our claim. [ABSTRACT FROM AUTHOR]

In the practical radar with multiple antennas, the antenna imperfections degrade the system performance. In this paper, the problem of estimating the direction of arrival (DOA) in a multiple-input and multiple-output (MIMO) radar system with unknown mutual coupling effect between antennas is investigated. To exploit the target sparsity in the spatial domain, the compressed sensing based methods have been proposed by discretizing the detection area and formulating the dictionary matrix, so an off-grid gap is caused by the discretization processes. In this paper, different from the present DOA estimation methods, both the off-grid gap due to the sparse sampling and the unknown mutual coupling effect between antennas are considered at the same time, and a novel sparse system model for DOA estimation is formulated. Then, a novel sparse Bayesian learning (SBL)-based method named sparse Bayesian learning with the mutual coupling (SBLMC) is proposed, where an expectation-maximum-based method is established to estimate all the unknown parameters including the noise variance, the mutual coupling vectors, the off-grid vector, and the variance vector of scattering coefficients. Additionally, the prior distributions for all the unknown parameters are theoretically derived. With regard to the DOA estimation performance, the proposed SBLMC method can outperform state-of-the-art methods in the MIMO radar with unknown mutual coupling effect, while keeping the acceptable computational complexity. [ABSTRACT FROM AUTHOR]

Numerical optimization has played a central role in addressing key signal processing (SP) problems. Highly effective methods have been developed for a large variety of SP applications such as communications, radar, filter design, and speech and image analytics, just to name a few. However, optimization algorithms often entail considerable complexity, which creates a serious gap between theoretical design/analysis and real-time processing. In this paper, we aim at providing a new learning-based perspective to address this challenging issue. The key idea is to treat the input and output of an SP algorithm as an unknown nonlinear mapping and use a deep neural network (DNN) to approximate it. If the nonlinear mapping can be learned accurately by a DNN of moderate size, then SP tasks can be performed effectively—since passing the input through a DNN only requires a small number of simple operations. In our paper, we first identify a class of optimization algorithms that can be accurately approximated by a fully connected DNN. Second, to demonstrate the effectiveness of the proposed approach, we apply it to approximate a popular interference management algorithm, namely, the WMMSE algorithm. Extensive experiments using both synthetically generated wireless channel data and real DSL channel data have been conducted. It is shown that, in practice, only a small network is sufficient to obtain high approximation accuracy, and DNNs can achieve orders of magnitude speedup in computational time compared to the state-of-the-art interference management algorithm. [ABSTRACT FROM AUTHOR]

This paper provides new probabilistic guarantees for recovering the common support of jointly sparse vectors in multiple measurement vector (MMV) models. In recent times, Bayesian approaches for sparse signal recovery (such as sparse Bayesian learning and correlation-aware LASSO) have shown preliminary evidence that under appropriate conditions (such as access to ideal covariance matrix of the measurements or certain restrictive orthogonality condition on the signals), it is possible to recover supports of size ($K$) larger than the dimension ($M$) of each measurement vector. However, no results exist that characterize the probability with which this can be achieved for a finite number of measurement vectors ($L$). This paper bridges this gap by formulating the support recovery problem in terms of a multiple hypothesis testing framework. Chernoff-type upper bounds on the probability of error are established, and new sufficient conditions are derived that guarantee its exponential decay with respect to $L$ even when $K=O(M^2)$. Our sufficient conditions are based on the properties of the so-called Khatri–Rao product of the measurement matrix and reveal the importance of a sampler design. Negative results are also established indicating that when $K$ exceeds a certain threshold (in terms of $M$), there will exist a class of measurement matrices for which any support recovery algorithm will fail. Using results from the geometric probability, we characterize the probability with which a randomly generated measurement matrix will belong to this class and show that this probability tends to 1 asymptotically in the size ($N$) of the sparse vectors. [ABSTRACT FROM AUTHOR]

Even though sparse recovery (SR) has been successfully applied in a wide range of research communities, there still exists a barrier to real applications because of the inefficiency of the state-of-the-art algorithms. In this paper, we propose a dynamical approach to SR, which is highly efficient and with finite-time convergence property. First, instead of solving the $\ell _1$ regularized optimization programs that requires exhausting iterations, which is computer-oriented, the solution to SR problem in this paper is resolved through the evolution of a continuous dynamical system which can be realized by analog circuits. Moreover, the proposed dynamical system is proved to have the finite-time convergence property, and thus more efficient than locally competitive algorithm (LCA) (the recently developed dynamical system to solve SR) with exponential convergence property. Consequently, our proposed dynamical system is more appropriate than LCA to deal with the time-varying situations. Simulations are carried out to demonstrate the superior properties of our proposed system. [ABSTRACT FROM PUBLISHER]

Bounded Component Analysis (BCA) is a recent framework which enables development of methods for the separation of dependent as well as independent sources from their mixtures. This paper extends a recent geometric BCA approach introduced for the instantaneous mixing problem to the convolutive mixing problem. The paper proposes novel deterministic convolutive BCA frameworks for the blind source extraction and blind source separation of convolutive mixtures of sources which allows the sources to be potentially nonstationary. The global maximizers of the proposed deterministic BCA optimization settings are proved to be perfect separators. The paper also illustrates that the iterative algorithms corresponding to these frameworks are capable of extracting/separating convolutive mixtures of not only independent sources but also dependent (even correlated) sources in both component (space) and sample (time) dimensions through simulations based on a Copula distributed source system. In addition, even when the sources are independent, it is shown that the proposed BCA approach have the potential to provide improvement in separation performance especially for short data records based on the setups involving convolutive mixtures of digital communication sources. [ABSTRACT FROM PUBLISHER]

Graphical models are powerful tools to describe high-dimensional data; they provide a compact graphical representation of the interactions between different variables and such representation enables efficient inference. In particular for Gaussian graphical models, such representation is encoded by the zero pattern of the precision matrix (i.e., inverse covariance). Existing approaches to learning Gaussian graphical models often leverage the framework of penalized likelihood, and therefore suffer from the issue of regularization selection. In this paper, we address the structure learning problem of Gaussian graphical models from a variational Bayesian perspective. Specifically, sparse promoting priors are imposed on the off-diagonal elements of the precision matrix. We then approximate the posterior distribution of the precision matrix by a Wishart distribution using the framework of variational Bayes, and derive efficient natural gradient based algorithms to learn the model. We consider both monoscale and multiscale graphical models. Numerical results show that the proposed method can learn sparse graphs that can reliably describe the data in an automated fashion. [ABSTRACT FROM AUTHOR]

Despite the tremendous success of deep neural networks in various learning problems, it has been observed that adding intentionally designed adversarial perturbations to inputs of these architectures leads to erroneous classification with high confidence in the prediction. In this work, we show that adversarial examples can be generated using a generic approach that relies on the perturbation analysis of learning algorithms. Formulated as a convex program, the proposed approach retrieves many current adversarial attacks as special cases. It is used to propose novel attacks against learning algorithms for classification and regression tasks under various new constraints with closed-form solutions in many instances. In particular, we derive new attacks against classification algorithms which are shown to be top-performing on various architectures. Although classification tasks have been the main focus of adversarial attacks, we use the proposed approach to generate adversarial perturbations for various regression tasks. Designed for single pixel and single subset attacks, these attacks are applied to autoencoding, image colorization and real-time object detection tasks, showing that adversarial perturbations can degrade equally gravely the output of regression tasks. 1 In the spirit of encouraging reproducible research, the implementations used in this paper have been made available at: github.com/ebalda/adversarialconvex. [ABSTRACT FROM AUTHOR]

Due to the growth of modern dataset size and the desire to harness computing power of multiple machines, there is a recent surge of interest in the design of distributed machine learning algorithms. However, distributed algorithms are sensitive to Byzantine attackers who can send falsified data to prevent the convergence of algorithms or lead the algorithms to converge to value of the attackers’ choice. Some recent work proposed interesting algorithms that can deal with the scenario when up to half of the workers are compromised. In this paper, we propose a novel algorithm that can deal with an arbitrary number of Byzantine attackers. The main idea is to ask the parameter server to randomly select a small clean dataset and compute noisy gradient using this small dataset. This noisy gradient will then be used as a ground truth to filter out information sent by compromised workers. We show that the proposed algorithm converges to the neighborhood of the population minimizer regardless the number of Byzantine attackers. We further provide numerical examples to show that the proposed algorithm can benefit from the presence of good workers and achieve better performance than existing algorithms. [ABSTRACT FROM AUTHOR]

This paper treats a blind detection problem to identify the central nodes in a graph from filtered graph signals. Unlike prior works which impose strong restrictions on the data model, we only require the underlying graph filter to satisfy a low pass property with a generic low-rank excitation model. We treat two cases depending on the low pass graph filter’s strength. When the graph filter is strong low pass, i.e., it has a frequency response that drops sharply at the high frequencies, we show that the principal component analysis (PCA) method detects central nodes with high accuracy. For general low pass graph filter, we show that the graph signals can be described by a structured factor model featuring the product between a low-rank plus sparse factor and an unstructured factor. We propose a two-stage decomposition algorithm to learn the structured factor model via a judicious combination of the non-negative matrix factorization and robust PCA algorithms. We analyze the identifiability conditions for the model which lead to accurate central nodes detection. Numerical experiments on synthetic and real data are provided to support our findings. We demonstrate significant performance gains over prior works. [ABSTRACT FROM AUTHOR]

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]

This paper considers the problem of adaptive classification for performing pattern discrimination in varying conditions when new data arrives. A new efficient method is presented to incrementally update features in a Nyström-approximated linearized kernel embedding (LKE). Our method leverages a fast eigendecomposition algorithm for symmetric Arrowhead matrices. The proposed method can also be applied to kernel principal component analysis (KPCA) or similar problems. A mechanism is proposed which allows the incremental linearized kernel embedding to be used for updating of dictionaries in a sparse representation-based classification algorithm. The method is based on transporting the dictionaries into the embedding expanded with new data points and avoids the need to learn new dictionary matrices every time new data becomes available. The effectiveness of the developed methods is illustrated on two handwritten digit image data sets namely MNIST and USPS. Classification performance before and after sequential embedding updates is evaluated and compared. Comparisons are also made between our incremental LKE algorithm and the conventional approach to updating the empirical kernel map in terms of their computational requirements and numerical stability. [ABSTRACT FROM AUTHOR]

Many signal processing and machine learning problems can be formulated as consensus optimization problems which can be solved efficiently via a cooperative multi-agent system. However, the agents in the system can be unreliable due to a variety of reasons: noise, faults and attacks. Providing erroneous updates leads the optimization process in a wrong direction, and degrades the performance of distributed machine learning algorithms. This paper considers the problem of decentralized learning using ADMM in the presence of unreliable agents. First, we rigorously analyze the effect of erroneous updates (in ADMM learning iterations) on the convergence behavior of the multi-agent system. We show that the algorithm linearly converges to a neighborhood of the optimal solution under certain conditions and characterize the neighborhood size analytically. Next, we provide guidelines for network design to achieve a faster convergence to the neighborhood. We also provide conditions on the erroneous updates for exact convergence to the optimal solution. Finally, to mitigate the influence of unreliable agents, we propose ROAD, a robust variant of ADMM, and show its resilience to unreliable agents with an exact convergence to the optimum. [ABSTRACT FROM AUTHOR]

With the help of auxiliary data, tensor completion may better recover a low rank multidimensional array from limited observation entries. Most existing methods, including coupled matrix-tensor factorization and coupled tensor rank minimization, mainly focus on how to extract and incorporate subspace or directly use auxiliary data for tensor completion. They are either sensitive to a given rank or lack of physical interpretations of subspace information. In addition, the shared subspace information receives little attention in current tensor completion methods, especially there is no analysis of its impact on sample complexity. In this paper, we propose to separately explore and exploit shared subspaces for tensor completion. Specifically, dictionary learning takes the subspace from auxiliary data in the first step. Then a low rank optimization model for tensor completion is provided to incorporate the trained subspace by assuming that the recovered tensor is composed of two low rank components where one shares the subspace information with auxiliary data and the other is outside the shared space. Based on this optimization model, we make a quantitative analysis to illustrate the effect of subspace information on sample complexity, and provide theoretical insights into the usefulness of subspace information. Finally, experiments on simulated data are conducted to validate the theoretical analysis on the impact of subspace information. Experiments in two real-world applications including color image and multispectral image recovery show that the proposed method outperforms state-of-the-art ones in terms of prediction accuracy and CPU time. [ABSTRACT FROM AUTHOR]

Data representation techniques have made a substantial contribution to advancing data processing and machine learning (ML). Improving predictive power was the focus of previous representation techniques, which unfortunately perform rather poorly on the interpretability in terms of extracting underlying insights of the data. Recently, the Kolmogorov model (KM) was studied, which is an interpretable and predictable representation approach to learning the underlying probabilistic structure of a set of random variables. The existing KM learning algorithms using semi-definite relaxation with randomization (SDRwR) or discrete monotonic optimization (DMO) have, however, limited utility to big data applications because they do not scale well computationally.In this paper, we propose a computationally scalable KM learning algorithm, based on the regularized dual optimization combined with enhanced gradient descent (GD) method. To make our method more scalable to large-dimensional problems, we propose two acceleration schemes, namely, the eigenvalue decomposition (EVD) elimination strategy and an approximate EVD algorithm. Furthermore, a thresholding technique by exploiting the error bound analysis and leveraging the normalized Minkowski $\ell _1$ -norm, is provided for the selection of the number of iterations of the approximate EVD algorithm. When applied to big data applications, it is demonstrated that the proposed method can achieve compatible training/prediction performance with significantly reduced computational complexity; roughly two orders of magnitude improvement in terms of the time overhead, compared to the existing KM learning algorithms. Furthermore, it is shown that the accuracy of logical relation mining for interpretability by using the proposed KM learning algorithm exceeds 80%. [ABSTRACT FROM AUTHOR]

Motivated by the recent success of reinforcement learning algorithms, this paper studies a class of biased stochastic approximation (SA) procedures under a mild “ergodicity-like” assumption on the random noise sequence. Building on a multistep Lyapunov function that looks ahead to several future updates to accommodate the stochastic perturbations (thus gaining control over the bias), we prove a general result on the convergence of the SA iterates, and use it to derive non-asymptotic bounds on the mean-square error in the case of constant stepsizes. This novel viewpoint renders finite-time analysis of biased SA algorithms under a family of stochastic perturbations possible. For direct comparison with prior work, we demonstrate these bounds by applying them to TD-learning with linear function approximation, under the Markov chain observation model. The resultant finite-time error bound for TD-learning is the first of its kind, in the sense that it holds i) for the unmodified versions (i.e., without any modification to the updates) using even nonlinear approximators; as well as for Markov chains ii) under sublinear mixing conditions and iii) starting from any initial distribution, at least one of which has to be violated for existing results to be applicable. [ABSTRACT FROM AUTHOR]

Recent demands on data privacy have called for federated learning (FL) as a new distributed learning paradigm in massive and heterogeneous networks. Although many FL algorithms have been proposed, few of them have considered the matrix factorization (MF) model, which is known to have a vast number of signal processing and machine learning applications. Since the MF problem involves two blocks of variables and the variables are usually subject to constraints related to specific solution structure, it requires new FL algorithm designs to achieve communication-efficient MF in heterogeneous data networks. In this paper, we address the challenge by proposing two new federated MF (FedMF) algorithms, namely, FedMAvg and FedMGS, based on the model averaging and gradient sharing principles, respectively. Both FedMAvg and FedMGS adopt multiple steps of local updates per communication round to speed up convergence, and allow only a randomly sampled subset of clients to communicate with the server for reducing the communication cost. Convergence properties for the two algorithms are thoroughly analyzed, which delineate the impacts of heterogeneous data distribution, local update number, and partial client communication on the algorithm performance, and guide the design of proposed algorithms. By focusing on a data clustering task, extensive experiment results are presented to examine the practical performance of proposed algorithms, as well as demonstrating their efficacy over the existing distributed clustering algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes a constrained stochastic successive convex approximation (CSSCA) algorithm to find a stationary point for a general non-convex stochastic optimization problem, whose objective and constraint functions are non-convex and involve expectations over random states. Most existing methods for non-convex stochastic optimization, such as the stochastic (average) gradient and stochastic majorization-minimization, only consider minimizing a stochastic non-convex objective over a deterministic convex set. The proposed CSSCA algorithm can also handle stochastic non-convex constraints in optimization problems, and it opens the way to solving more challenging optimization problems that occur in many applications. The algorithm is based on solving a sequence of convex objective/feasibility optimization problems obtained by replacing the objective/constraint functions in the original problems with some convex surrogate functions. The CSSCA algorithm allows a wide class of surrogate functions and thus provides many freedoms to design good surrogate functions for specific applications. Moreover, it also facilitates parallel implementation for solving large-scale stochastic optimization problems, which arise naturally in today's signal processing such as machine learning and big data analysis. We establish the convergence of the CSSCA algorithm with a feasible initial point, and customize the algorithmic framework to solve several important application problems. Simulations show that the CSSCA algorithm can achieve superior performance over existing solutions. [ABSTRACT FROM AUTHOR]

Spectrum cartography constructs maps of metrics such as channel gain or received signal power across a geographic area of interest using spatially distributed sensor measurements. Applications of these maps include network planning, interference coordination, power control, localization, and cognitive radios to name a few. Since existing spectrum cartography techniques require accurate estimates of the sensor locations, their performance is drastically impaired by multipath affecting the positioning pilot signals. This phenomenon occurs especially in indoor or dense urban scenarios. To overcome such a limitation, this paper introduces a novel paradigm for spectrum cartography, where estimation of spectral maps relies on features of these positioning signals rather than on location estimates. Specific learning algorithms are built on this approach and offer a markedly improved estimation performance than those of the existing approaches relying on localization, as demonstrated by simulation studies in indoor scenarios. [ABSTRACT FROM AUTHOR]

Intelligent mobile platforms such as smart vehicles and drones have recently become the focus of attention for onboard deployment of machine learning mechanisms to enable low latency decisions with low risk of privacy breach. However, most such machine learning algorithms are both computation-and-memory intensive, which makes it highly difficult to implement the requisite computations on a single device of limited computation, memory, and energy resources. Wireless distributed computing presents new opportunities by pooling the computation and storage resources among devices. For low-latency applications, the key bottleneck lies in the exchange of intermediate results among mobile devices for data shuffling. To improve communication efficiency, we propose a co-channel communication model and design transceivers by exploiting the locally computed intermediate values as side information. A low-rank optimization model is proposed to maximize the achieved degrees-of-freedom (DoF) by establishing the interference alignment condition for data shuffling. Unfortunately, existing approaches to approximate the rank function fail to yield satisfactory performance due to the poor structure in the formulated low-rank optimization problem. In this paper, we develop an efficient difference-of-convex-functions (DC) algorithm to solve the presented low-rank optimization problem by proposing a novel DC representation for the rank function. Numerical experiments demonstrate that the proposed DC approach can significantly improve the communication efficiency whereas the achievable DoF almost remains unchanged when the number of mobile devices grows. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of selecting an optimal sampling set for signals on graphs. The proposed sampling set selection (SSS) is based on a localization operator that can consider both vertex domain and spectral domain localizations. We clarify the relationships among the proposed method, sensor position selection methods in machine learning, and existing SSS methods based on graph frequency. In contrast to the alternative graph signal processing-based approaches, the proposed method does not need to compute the eigendecomposition of a variation operator, while still considering (graph) frequency information. We evaluate the performance of our approach through comparisons of prediction errors and execution time. [ABSTRACT FROM AUTHOR]

This paper considers a set of multiple independent control systems that are each connected over a nonstationary wireless channel. The goal is to maximize control performance over all the systems through the allocation of transmitting power within a fixed budget. This can be formulated as a constrained optimization problem examined using Lagrangian duality. By taking samples of the unknown wireless channel at every time instance, the resulting problem takes on the form of empirical risk minimization, a well-studied problem in machine learning. Due to the nonstationarity of wireless channels, optimal allocations must be continuously learned and updated as the channel evolves. The quadratic convergence property of Newton's method motivates its use in learning approximately optimal power allocation policies over the sampled dual function as the channel evolves over time. Conditions are established under which Newton's method learns approximate solutions with a single update, and the subsequent suboptimality of the control problem is further characterized. Numerical simulations illustrate the near-optimal performance of the method and resulting stability on a wireless control problem. [ABSTRACT FROM AUTHOR]

In this paper, learning of tree-structured Gaussian graphical models from distributed data is addressed. In our model, samples are stored in a set of distributed machines where each machine has access to only a subset of features. A central machine is then responsible for learning the structure based on received messages from the other nodes. We present a set of communication-efficient strategies, which are theoretically proved to convey sufficient information for reliable learning of the structure. In particular, our analyses show that even if each machine sends only the signs of its local data samples to the central node, the tree structure can still be recovered with high accuracy. Our simulation results on both synthetic and real-world datasets show that our strategies achieve a desired accuracy in inferring the underlying structure while spending a small budget on communication. [ABSTRACT FROM AUTHOR]

We study convex optimization problems that feature low-rank matrix solutions. In such scenarios, non-convex methods offer significant advantages over convex methods due to their lower space complexity, as well as practical faster convergence. Under mild assumptions, these methods feature global convergence guarantees. In this paper, we extend the results on this matter by following a different path. We derive a non-Euclidean optimization framework in the non-convex setting that takes nonlinear gradient steps on the factors. Our framework enables the possibility to further exploit the underlying problem structures, such as sparsity or low-rankness on the factorized domain, or better dimensional dependence of the smoothness parameters of the objectives. We prove that the non-Euclidean methods enjoy the same rigorous guarantees as their Euclidean counterparts under appropriate assumptions. Numerical evidence with Fourier ptychography and FastText applications, using real data, shows that our approach can enhance solution quality, as well as convergence speed over the standard non-convex approaches. [ABSTRACT FROM AUTHOR]

Filtering and smoothing algorithms for linear discrete-time state-space models with skew- $t$ -distributed measurement noise are proposed. The algorithms use a variational Bayes based posterior approximation with coupled location and skewness variables to reduce the error caused by the variational approximation. Although the variational update is done suboptimally using an expectation propagation algorithm, our simulations show that the proposed method gives a more accurate approximation of the posterior covariance matrix than an earlier proposed variational algorithm. Consequently, the novel filter and smoother outperform the earlier proposed robust filter and smoother and other existing low-complexity alternatives in accuracy and speed. We present both simulations and tests based on real-world navigation data, in particular the global positioning system data in an urban area, to demonstrate the performance of the novel methods. Moreover, the extension of the proposed algorithms to cover the case where the distribution of the measurement noise is multivariate skew- $t$ is outlined. Finally, this paper presents a study of theoretical performance bounds for the proposed algorithms. [ABSTRACT FROM AUTHOR]

As a new member of convex universal learning machines (CULMs), an augmented space linear model (ASLM) demonstrates strong learning and tracking capabilities in the fields of signal process and machine learning. Unfortunately, the ASLM is only suitable for offline learning, and its estimated accuracy and noise immunity highly depend on the estimated error learned from a generated error table. To address these two issues and apply ASLM into adaptive filtering, online ASLM algorithms with a weighted $k$ nearest neighbor ($k$ -NN) method, based on an updated orthogonal error table, are therefore proposed in this paper. To further improve the robustness of ASLM to heavy-tail noises, a robust ASLM (RASLM) algorithm is proposed with the help of kernel function, and thus a novel robust adaptive filtering algorithm named maximum correntropy criterion RASLM (MCC-RASLM) is developed based the maximum correntropy criterion. However, the linear growth error table existing in MCC-RASLM incurs an ever-growing computational burden. Therefore, to reduce the computational complexity of MCC-RASLM, another novel online variable-centroid clustering is proposed to generate a maximum correntropy criterion cluster RASLM (MCC-C-RASLM) algorithm. Finally, the theoretical analyses regarding robustness and the error bound of RASLM with weighted $k$ -NN regression are performed to verify the effectiveness of MCC-RASLM. Simulation results based on synthetic and real-world data validate the superiorities of the proposed algorithms from aspects of filtering accuracy and robustness. [ABSTRACT FROM AUTHOR]

Recent advances in objective-based uncertaintyquantification (objective-UQ) have shown that such a goal-driven approach for quantifying model uncertainty is extremely usefulin real-world problems that aim at achieving specific objectives based on complex uncertain systems. Central to this objective-UQ is the concept of mean objective cost of uncertainty (MOCU), which provides effective means of quantifying the impact of uncertainty on the operational goals at hand. MOCU is especially useful for optimal experimental design (OED) as the potential efficacy of an experimental (or data acquisition) campaign can be quantified by estimating the MOCU that is expected to remain after the campaign. However, MOCU-based OED tends to be computationally expensive, which limits its practical applicability. In this paper, we propose a novel machine learning (ML) scheme that can significantly accelerate MOCU computation and expedite MOCU-based experimental design. The main idea is to use an ML model to efficiently search for the optimal robust operator under model uncertainty, a necessary step for computing MOCU. We apply the proposed ML-based OED acceleration scheme to design experiments aimed at optimally enhancing the control performance of uncertain Kuramoto oscillator models. Our results show that the proposed scheme results in up to ${154}$ -fold speed improvement without any degradation of the OED performance. [ABSTRACT FROM AUTHOR]

Deep multi-view clustering utilizes neural networks to extract the potential peculiarities of complementarity and consistency information among multi-view features. This can obtain a consistent representation that improves clustering performance. Although a multitude of deep multi-view clustering approaches have been proposed, most lack theoretic interpretability while maintaining the advantages of good performance. In this paper, we propose an effective differentiable network with alternating iterative optimization for multi-view co-clustering termed differentiable bi-sparse multi-view co-clustering (DBMC) and an extension named elevated DBMC (EDBMC). The proposed methods are transformed into equivalent deep networks based on the constructed objective loss functions. They have the advantages of strong interpretability of the classical machine learning methods and the superior performance of deep networks. Moreover, DBMC and EDBMC can learn a joint and consistent collaborative representation from multi-source features and guarantee sparsity between multi-view feature space and single-view sample space. Meanwhile, they can be converted into deep differentiable network frameworks with block-wise iterative training. Correspondingly, we design two three-step iterative differentiable networks to resolve resultant optimization problems with theoretically guaranteed convergence. Extensive experiments on six multi-view benchmark datasets demonstrate that the proposed frameworks outperform other state-of-the-art multi-view clustering methods. [ABSTRACT FROM AUTHOR]

This paper targets developing algorithms for solving distributed learning problems in a communication-efficient fashion, by generalizing the recent method of lazily aggregated gradient (LAG) to deal with stochastic gradient — justifying the name of the new method LASG. While LAG is effective at reducing communication without sacrificing the rate of convergence, we show it only works with deterministic gradients. We introduce new rules and analysis for LASG that are tailored for stochastic gradients, so it effectively saves downloads, uploads, or both for distributed stochastic gradient descent. LASG achieves impressive empirical performance — it typically saves total communication by an order of magnitude. LASG can be used together with gradient quantization to bring more savings. [ABSTRACT FROM AUTHOR]

Low overhead error-resiliency techniques such as algorithmic noise-tolerance (ANT) have been shown to be particularly effective for signal processing and machine learning kernels. However, the overhead of conventional ANT can be as large as 30% due to the use of explicit estimator block. To overcome this overhead, embedded ANT (E-ANT) is proposed [S. Zhang and N. Shanbhag, “Embedded error compensation for energy efficient DSP systems,” in Proc. GlobalSIP, Dec. 2014, pp. 30–34], where the estimator is embedded in the main computation block via data path decomposition (DPD). E-ANT reduces the logic overhead to be below 8% as compared with the 20%–30% associated with conventional reduced precision replica (RPR) ANT system while maintaining the same error compensation functionality. DPD was first proposed in our original paper [Zhang and Shanbhag, 2014] where its benefits were studied in the case of a simple multiply-accumulator (MAC) kernel. This paper builds upon [Zhang and Shanbhag, 2014] by 1) providing conditions for the existence of DPD, 2) demonstrating DPD for a variety of commonly employed kernels in signal processing and machine learning applications, and 3) evaluating the robustness improvement and energy savings of DPD at the system level for an SVM-based EEG seizure classification application. Simulation results in a commercial 45 nm CMOS process show that E-ANT can compensate for error rates up to 0.38 for errors in FE only, and 0.17 for errors in FE and CE, while maintain a true positive rate ptp > 0.9 and a false positive rate pfp\leq 0.01. This represents a greater than 3-orders-of-magnitude improvement in error tolerance over the conventional system. This error tolerance is employed to reduce energy via the use of voltage overscaling (VOS). E-ANT is able to achieve 51% energy savings when errors are in FE only, and up to 43% savings when errors are in both FE and CE. [ABSTRACT FROM AUTHOR]

In this paper, we develop online learning algorithms that enable the agents to cooperatively learn how to maximize the overall reward in scenarios where only noisy global feedback is available without exchanging any information among themselves. We prove that our algorithms' learning regrets—the losses incurred by the algorithms due to uncertainty—are logarithmically increasing in time and thus the time average reward converges to the optimal average reward. Moreover, we also illustrate how the regret depends on the size of the action space, and we show that this relationship is influenced by the informativeness of the reward structure with regard to each agent's individual action. When the overall reward is fully informative, regret is shown to be linear in the total number of actions of all the agents. When the reward function is not informative, regret is linear in the number of joint actions. Our analytic and numerical results show that the proposed learning algorithms significantly outperform existing online learning solutions in terms of regret and learning speed. We illustrate how our theoretical framework can be used in practice by applying it to online Big Data mining using distributed classifiers. [ABSTRACT FROM PUBLISHER]

In this paper, we consider solving a class of nonconvex and nonsmooth problems frequently appearing in signal processing and machine learning research. The traditional alternating direction method of multipliers encounters troubles in both mathematics and computations in solving the nonconvex and nonsmooth subproblem. In view of this, we propose a reweighted alternating direction method of multipliers. In this algorithm, all subproblems are convex and easy to solve. We also provide several guarantees for the convergence and prove that the algorithm globally converges to a critical point of an auxiliary function with the help of the Kurdyka–Łojasiewicz property. Several numerical results are presented to demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Bounded component analysis (BCA) is a recent approach that enables the separation of both dependent and independent signals from their mixtures. This paper introduces a novel deterministic instantaneous BCA framework for the separation of sparse bounded sources. The framework is based on a geometric maximization setting, where the objective function is defined as the volume ratio of two objects, namely, the principal hyperellipsoid and the bounding $\ell _1$ -norm ball, defined over the separator output samples. It is shown that all global maxima of this objective are perfect separators. This paper also provides the corresponding iterative algorithms for both real and complex sparse sources. The numerical experiments illustrate the potential benefits of the proposed approach, with applications on image separation and neuron identification. [ABSTRACT FROM AUTHOR]

Estimating the joint probability mass function (PMF) of a set of random variables lies at the heart of statistical learning and signal processing. Without structural assumptions, such as modeling the variables as a Markov chain, tree, or other graphical model, joint PMF estimation is often considered mission impossible—the number of unknowns grows exponentially with the number of variables. But who gives us the structural model? What if we only observe random subsets of the variables, can we still reliably estimate the joint PMF of all? This paper shows, perhaps surprisingly, that if the joint PMF of any three variables can be estimated, then the joint PMF of all the variables can be provably recovered under relatively mild conditions. The result is reminiscent of Kolmogorov's extension theorem – consistent specification of lower-dimensional distributions induces a unique probability measure for the entire process. The difference is that for processes of limited complexity (rank of the high-dimensional PMF) it is possible to obtain complete characterization from only three-dimensional distributions. In fact not all three-dimensional PMFs are needed; and under more stringent conditions even two-dimensional will do. Exploiting multilinear (tensor) algebra, this paper proves that such higher-dimensional PMF completion can be guaranteed—several pertinent identifiability results are derived. It also provides a practical and efficient algorithm to carry out the recovery task. Judiciously designed simulations and real-data experiments on movie recommendation and data classification are presented to showcase the effectiveness of the approach. [ABSTRACT FROM AUTHOR]

Kernel methods have been successfully applied to nonlinear problems in machine learning and signal processing. Various kernel-based algorithms have been proposed over the last two decades. In this paper, we investigate the kernel conjugate gradient (KCG) algorithms in both batch and online modes. By expressing the solution vector of CG algorithm as a linear combination of the input vectors and using the kernel trick, we developed the KCG algorithm for batch mode. Because the CG algorithm is iterative in nature, it can greatly reduce the computations by the technique of reduced-rank processing. Moreover, the reduced-rank processing can provide the robustness against the problem of overlearning. The online KCG algorithm is also derived, which converges as fast as the kernel recursive least squares (KRLS) algorithm, but the computational cost is only a quarter of that of the KRLS algorithm. Another attractive feature of the online KCG algorithm compared with other kernel adaptive algorithms is that it does not require the user-defined parameters. To control the growth of data size in online applications, a simple sparsification criterion based on the angles among elements in reproducing kernel Hilbert space is proposed. The angle criterion is equivalent to the coherence criterion but does not require the kernel to be unit norm. Finally, numerical experiments are provided to illustrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The demand for accurate localization in complex environments continues to increase despite the difficulty in extracting positional information from measurements. Conventional range-based localization approaches rely on distance estimates obtained from measurements (e.g., delay or strength of received waveforms). This paper goes one step further and develops localization techniques that rely on all probable range values rather than on a single estimate of each distance. In particular, the concept of soft range information (SRI) is introduced, showing its essential role for network localization. We then establish a general framework for SRI-based localization and develop algorithms for obtaining the SRI using machine learning techniques. The performance of the proposed approach is quantified via network experimentation in indoor environments. The results show that SRI-based localization techniques can achieve performance approaching the Cramér–Rao lower bound and significantly outperform the conventional techniques especially in harsh wireless environments. [ABSTRACT FROM AUTHOR]

This paper studies resilient multiagent distributed estimation of an unknown vector parameter when a subset of the agents is adversarial. We present and analyze a flag raising distributed estimator ( $\mathcal {FRDE}$ ) that allows the agents under attack to perform accurate parameter estimation and detect the adversarial agents. The $\mathcal {FRDE}$ algorithm is a consensus+innovations estimator in which agents combine estimates of neighboring agents (consensus) with local sensing information (innovations). We establish that, under $\mathcal {FRDE}$ , either the uncompromised agents' estimates are almost surely consistent, or the uncompromised agents detect compromised agents (with arbitrarily small false alarm probability) if and only if the network of uncompromised agents is connected and globally observable. Numerical examples illustrate the performance of $\mathcal {FRDE}$. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm for the sparse signal recovery problem that incorporates damped Gaussian generalized approximate message passing (GGAMP) into expectation-maximization-based sparse Bayesian learning (SBL). In particular, GGAMP is used to implement the E-step in SBL in place of matrix inversion, leveraging the fact that GGAMP is guaranteed to converge with appropriate damping. The resulting GGAMP-SBL algorithm is much more robust to arbitrary measurement matrix A than the standard damped GAMP algorithm while being much lower complexity than the standard SBL algorithm. We then extend the approach from the single measurement vector case to the temporally correlated multiple measurement vector case, leading to the GGAMP-TSBL algorithm. We verify the robustness and computational advantages of the proposed algorithms through numerical experiments. [ABSTRACT FROM AUTHOR]

The emergence of big data has caused a dramatic shift in the operating regime for optimization algorithms. The performance bottleneck, which used to be computations, is now often communications. Several gradient compression techniques have been proposed to reduce the communication load at the price of a loss in solution accuracy. Recently, it has been shown how compression errors can be compensated for in the optimization algorithm to improve the solution accuracy. Even though convergence guarantees for error-compensated algorithms have been established, there is very limited theoretical support for quantifying the observed improvements in solution accuracy. In this paper, we show that Hessian-aided error compensation, unlike other existing schemes, avoids accumulation of compression errors on quadratic problems. We also present strong convergence guarantees of Hessian-based error compensation for stochastic gradient descent. Our numerical experiments highlight the benefits of Hessian-based error compensation, and demonstrate that similar convergence improvements are attained when only a diagonal Hessian approximation is used. [ABSTRACT FROM AUTHOR]

Given a dataset, the task of learning a transform that allows sparse representations of the data bears the name of dictionary learning. In many applications, these learned dictionaries represent the data much better than the static well-known transforms (Fourier, Hadamard etc.). The main downside of learned transforms is that they lack structure and, therefore, they are not computationally efficient, unlike their classical counterparts. These posse several difficulties especially when using power limited hardware such as mobile devices, therefore, discouraging the application of sparsity techniques in such scenarios. In this paper, we construct orthogonal and nonorthogonal dictionaries that are factorized as a product of a few basic transformations. In the orthogonal case, we solve exactly the dictionary update problem for one basic transformation, which can be viewed as a generalized Givens rotation, and then propose to construct orthogonal dictionaries that are a product of these transformations, guaranteeing their fast manipulation. We also propose a method to construct fast square but nonorthogonal dictionaries that are factorized as a product of few transforms that can be viewed as a further generalization of Givens rotations to the nonorthogonal setting. We show how the proposed transforms can balance very well data representation performance and computational complexity. We also compare with classical fast and learned general and orthogonal transforms. [ABSTRACT FROM PUBLISHER]

Sparse modeling has been widely and successfully used in many applications, such as computer vision, machine learning, and pattern recognition. Accompanied with those applications, significant research has studied the theoretical limits and algorithm design for convex relaxations in sparse modeling. However, theoretical analyses on non-negative versions of sparse modeling are limited in the literature either to a noiseless setting or a scenario with a specific statistical noise model, such as Gaussian noise. This paper studies the performance of non-negative sparse modeling in a more general scenario where the observed signals have an unknown arbitrary distortion, especially focusing on non-negativity constrained and L1-penalized least squares, and gives an exact bound for which this problem can recover the correct signal elements. We pose two conditions to guarantee the correct signal recovery: minimum coefficient condition and nonlinearity versus subset coherence condition. The former defines the minimum weight for each of the correct atoms present in the signal and the latter defines the tolerable deviation from the linear model relative to the positive subset coherence, a novel type of “coherence” metric. We provide rigorous performance guarantees based on these conditions and experimentally verify their precise predictive power in a hyperspectral data unmixing application. [ABSTRACT FROM AUTHOR]

In this paper, the problem of adaptive distributed learning in diffusion networks is considered. The algorithms are developed within the convex set theoretic framework. More specifically, they are based on computationally simple geometric projections onto closed convex sets. The paper suggests a novel combine-project-adapt protocol for cooperation among the nodes of the network; such a protocol fits naturally with the philosophy that underlies the projection-based rationale. Moreover, the possibility that some of the nodes may fail is also considered and it is addressed by employing robust statistics loss functions. Such loss functions can easily be accommodated in the adopted algorithmic framework; all that is required from a loss function is convexity. Under some mild assumptions, the proposed algorithms enjoy monotonicity, asymptotic optimality, asymptotic consensus, strong convergence and linear complexity with respect to the number of unknown parameters. Finally, experiments in the context of the system-identification task verify the validity of the proposed algorithmic schemes, which are compared to other recent algorithms that have been developed for adaptive distributed learning. [ABSTRACT FROM PUBLISHER]

Over the last decade, kernel methods for nonlinear processing have successfully been used in the machine learning community. The primary mathematical tool employed in these methods is the notion of the reproducing kernel Hilbert space (RKHS). However, so far, the emphasis has been on batch techniques. It is only recently, that online techniques have been considered in the context of adaptive signal processing tasks. Moreover, these efforts have only been focussed on real valued data sequences. To the best of our knowledge, no adaptive kernel-based strategy has been developed, so far, for complex valued signals. Furthermore, although the real reproducing kernels are used in an increasing number of machine learning problems, complex kernels have not, yet, been used, in spite of their potential interest in applications that deal with complex signals, with Communications being a typical example. In this paper, we present a general framework to attack the problem of adaptive filtering of complex signals, using either real reproducing kernels, taking advantage of a technique called complexification of real RKHSs, or complex reproducing kernels, highlighting the use of the complex Gaussian kernel. In order to derive gradients of operators that need to be defined on the associated complex RKHSs, we employ the powerful tool of Wirtinger's Calculus, which has recently attracted attention in the signal processing community. Wirtinger's calculus simplifies computations and offers an elegant tool for treating complex signals. To this end, in this paper, the notion of Wirtinger's calculus is extended, for the first time, to include complex RKHSs and use it to derive several realizations of the complex kernel least-mean-square (CKLMS) algorithm. Experiments verify that the CKLMS offers significant performance improvements over several linear and nonlinear algorithms, when dealing with nonlinearities. [ABSTRACT FROM AUTHOR]

Learning of the cell-load in radio access networks (RANs) has to be performed within a short time period. Therefore, we propose a learning framework that is robust against uncertainties resulting from the need for learning based on a relatively small training set. To this end, we incorporate prior knowledge about the cell-load in the learning framework. For example, an inherent property of the cell-load is that it is monotonic in downlink (data) rates. To obtain additional prior knowledge we first study the feasible rate region, i.e., the set of all vectors of user rates that can be supported by the network. We prove that the feasible rate region is compact. Moreover, we show the existence of a Lipschitz function that maps feasible rate vectors to cell-load vectors. With these results in hand, we present a learning technique that guarantees a minimum approximation error in the worst-case scenario by using prior knowledge and a small training sample set. Simulations in the network simulator NS3 demonstrate that the proposed method exhibits better robustness and accuracy than standard learning techniques, especially for small training sample sets. [ABSTRACT FROM AUTHOR]

The goal of this paper is to derive a novel online algorithm for classification in reproducing kernel hilbert spaces (RKHS) by exploiting projection-based adaptive filtering tools. The paper brings powerful convex analytic and set theoretic estimation arguments in machine learning by revisiting the standard kernel-based classification as the problem of finding a point which belongs to a closed halfspace (a special closed convex set) in an RKHS. In this way, classification in an online setting, where data arrive sequentially, is viewed as the problem of finding a point (classifier) in the nonempty intersection of an infinite sequence of closed halfspaces in the RKHS. Convex analysis is also used to introduce sparsification arguments in the design by imposing an additional simple convex constraint on the norm of the classifier. An algorithmic solution to the resulting optimization problem, where new convex constraints are added every time instant, is given by the recently introduced adaptive projected subgradient method (APSM), which generalizes a number of well-known projection-based adaptive filtering algorithms such as the classical normalized least mean squares (NLMS) and the affine projection algorithm (APA). Under mild conditions, the generated sequence of estimates enjoys monotone approximation, strong convergence, asymptotic optimality, and a characterization of the limit point. Further, we show that the additional convex constraint on the norm of the classifier naturally leads to an online sparsification of the resulting kernel series expansion. We validate the proposed design by considering the adaptive equalization problem of a nonlinear channel, and by comparing it with classical as well as with recently developed stochastic gradient descent techniques. [ABSTRACT FROM PUBLISHER]

The combination of the famed kernel trick and the least-mean-square (LMS) algorithm provides an interesting sample-by-sample update for an adaptive filter in reproducing kernel Hubert spaces (RKHS), which is named in this paper the KLMS. Unlike the accepted view in kernel methods, this paper shows that in the finite training data case, the KLMS algorithm is well posed in RKHS without the addition of an extra regularization term to penalize solution norms as was suggested by Kivinen [Kivinen, Smola and Williamson, "Online Learning With Kernels," IEEE Transactions on Signal Processing, vol. 52, no. 8, pp. 2165-2176, Aug. 2004] and Smale [Smale and Yao, "Online Learning Algorithms," Foundations in computational Mathematics, vol. 6, no. 2, pp. 145-176, 20061. This result is the main contribution of the paper and enhances the present understanding of the LMS algorithm with a machine learning perspective. The effect of the KLMS step size is also studied from the viewpoint of regularization. Two experiments are presented to support our conclusion that with finite data the KLMS algorithm can be readily used in high dimensional spaces and particularly in RKHS to derive nonlinear, stable algorithms with comparable performance to batch, regularized solutions. [ABSTRACT FROM AUTHOR]

This paper addresses the optimal power and rate allocation control in multiple-input multiple-output (MIMO) wireless systems over Markovian fading channels. The problem is posed as an infinite horizon average-cost constrained Markov decision process (CMDP) with the goal of minimizing the average transmission power subject to delay constraints. By using a Lagrangian formulation of the CMDP, we use the concepts of stochastic dominance, submodularity, and multimodularity to prove that the optimal randomized policies are monotone. Three important structural results on the nature of the optimal randomized policies are derived. First, we show that the action space can be exponentially reduced by decomposing the rate allocation problem into bit-loading problem across individual antennas and the total rate allocation based on the current buffer occupancy and channel state. Second, we show that the optimal rate allocation policy is a randomized mixture of two pure policies that are monotonically increasing in the buffer occupancy. Finally, we show that the optimal power allocation is piecewise linear in the delay constraint. These three structural results can be exploited to devise efficient online reinforcement learning algorithms for optimal rate allocation. [ABSTRACT FROM AUTHOR]