We study online robust matrix completion on graphs. At each iteration a vector with some entries missing is revealed and our goal is to reconstruct it by identifying the underlying low-dimensional subspace from which the vectors are drawn. We assume there is an underlying graph structure to the data, that is, the components of each vector correspond to nodes of a certain known and fixed graph, and their values are related accordingly. We propose an algorithm that exploits the graph to reconstruct the incomplete data, in the scenario where there is outlier noise. The theoretical properties of the algorithms are studied and numerical experiments using both synthetic and real world datasets verify the improved performance of the proposed technique compared to other state of the art algorithms.

Matrix Completion (MC) i.e., estimating the missing values of an unknown matrix based on limited information, has been a prominent topic of study in the last decades. In this paper, we focus more precisely on a little-known aspect of MC, namely how the recommendation of new entries can help improve the accuracy of the reconstruction. We present an efficient online algorithm to solve the MC task, and propose an Adaptive Sampling under Smoothness Assumption (AdSSA) strategy, which is suitable for operation on smooth low-rank matrices. This technique is able to predict iteratively which entries are the most informative. Our numerical examples illustrate that AdSSA performs significantly better than the Uniform Random Sampling (URS) and the Query by Committee (QbC). In addition, AdSSA algorithm can be straightforwardly implemented in an online and efficient manner, which constitutes another advantage.

This work presents a distributed algorithm for nonlinear adaptive learning. In particular, a set of nodes obtain measurements, sequentially one per time step, which are related via a nonlinear function; their goal is to collectively minimize a cost function by employing a diffusion based Kernel Least Mean Squares (KLMS). The algorithm follows the Adapt Then Combine mode of cooperation. Moreover, the theoretical properties of the algorithm are studied and it is proved that under certain assumptions the algorithm suffers a no regret bound. Finally, comparative experiments verify that the proposed scheme outperforms other variants of the LMS.

Accurate coverage maps are an important tool for network planning and operation but it is often impossible to obtain these maps completely from measurements. In this paper we describe two new methods that enable operators to minimize the cost for obtaining a complete coverage map at high accuracy. Our first method applies the Singular Value Thresholding (SVT) algorithm to reconstruct a complete map from a sparse matrix of coverage data. We then use the Query by Committee (QbC) rationale to identify the areas where further measurements would maximize accuracy of the completed map. This second method allows operators to plan their drive tests such that a given budget is spent at highest efficiency. Our numerical examples illustrate that our proposed completion technique outperforms relevant state of the art and that QbC further enhances reconstruction accuracy.

Software Defined Networking enables centralized network control and hence paves the way for new services that use network resources more efficiently. Bandwidth Calendaring (BWC) is a typical such example that exploits the knowledge of future to optimally pack the arising demands over the network. In this paper, we consider a generic BWC instance, where a carrier network operator has to accommodate at minimum cost demands of predetermined, but time-varying, bandwidth requirements. Some of the demands may be flexible, i.e., can be scheduled within a specific time window. We demonstrate that the resulting problem is NP-hard and we propose a scalable problem decomposition based on column generation. Our numerical results reveal that the proposed solution approach is near-optimal and outperforms state-of-the art methods based on relaxation and randomized rounding by more than 20% in terms of network cost.

This paper addresses a fundamental limitation for the adoption of caching for wireless access networks due to small population sizes. This shortcoming is due to two main challenges: making timely estimates of varying content popularity and inferring popular content from small samples. We propose a framework which alleviates such limitations. To timely estimate varying popularity in a context of a single cache we propose an Age-Based Threshold (ABT) policy which caches all contents requested more times than a threshold N (τ), where τ is the content age. We show that ABT is asymptotically hit rate optimal in the many contents regime, which allows us to obtain the first characterization of the optimal performance of a caching system in a dynamic context. We then address small sample sizes focusing on L local caches and one global cache. On the one hand we show that the global cache learns L times faster by aggregating all requests from local caches, which improves hit rates. On the other hand, aggregation washes out local characteristics of correlated traffic which penalizes hit rate. This motivates coordination mechanisms which combine global learning of popularity scores in clusters and Least-Recently-Used (LRU) policy with prefetching.

By offloading the control plane to powerful computing platforms running on commodity hardware, Software Defined Networking (SDN) unleashes the potential to operate computation intensive machine learning tools and solve complex optimization problems in a centralized fashion. This paper studies such an opportunity under the framework of the centralized SDN Admission Control (AC) problem. We first review and adapt some of the key AC algorithms from the literature, and evaluate their performance under realistic settings. We then propose to take a step further and build an AC meta-algorithm that is able to track the best AC algorithm under unknown traffic conditions. To this aim, we exploit a machine learning technique called Strategic Expert meta-Algorithm (SEA).

SDN unleashes the potential to perform computational intensive machine learning algorithms to solve complex routing problems. This demo presents an architecture for the SDN controller that integrates several online routing algorithms for the real-time admission control of new connection requests. The demonstrator permits to compare the evolution of the network according to the admission decisions taken by different online algorithms and to simulate future scenarios to support strategic decisions aimed at improving the infrastructure.

This paper proposes a novel algorithm for online distributed dictionary learning, where a set of nodes is requested to collectively estimate a common dictionary via sequentially received data vectors. At each time instance, in which a new datum becomes available, the sparse representation of the data with respect to the estimated dictionary is computed locally at each node by employing a sparsity promoting algorithm. In the sequel, the nodes cooperate in order to collaboratively update the dictionary via the distributed Recursive Least Squares (RLS) algorithm. Numerical examples, both with synthetic and real data, validate that the performance of the proposed algorithm is comparable to that of centralized state of the art algorithms.

A novel algorithm for distributed labeling of speech sources is proposed. We consider a wireless sensor network comprising devices that are equipped with multiple microphones, which can “hear” a number of speech signals. The labeling task is performed in a decentralized fashion with a new two-step approach. The first step corresponds to the distributed extraction of proper source-specific features from the mixed signals. In the second step, these features are exploited via a distributed unsupervised learning technique. We present approaches that can be used in hierarchically organized or in non-hierarchically organized network configurations. Numerical examples using real data display the performance of the proposed technique.

A promising approach when dealing with massive data sets is to apply randomized dimensionality reduction and then operate in lower dimensions. This paper deals with the randomized linear regression task in the case where the available data are sporadically corrupted. Instead of relying to minimization of norms, which are robust to outliers, an alternative route is taken. Building upon the observation that outliers can be detected, while operating in a low dimensional randomized projections produced embedding, a mechanism for iteratively detecting and excluding corrupted data is proposed. As a result, the linear regression is performed using conventional LS approximation, without the need to resort to linear programming-based ℓ1norm minimization tasks.

This paper presents pattern classification to a predefined set of classes as a missing data task. This is achieved by first augmenting the feature vector of each training pattern with the corresponding binary codeword representing its class. A Restricted Boltzmann Machine (RBM) or a Dictionary Learning (DL) algorithm is then trained on the augmented feature space. During the classification stage, the binary codeword of the unknown pattern is treated as missing data. In the case of the RBM, it is filled in by means of an alternating Gibbs sampling procedure. In the case of the DL method, the set of atoms in the dictionary is first learned from the training data, and the label of the unknown pattern is predicted based on those atoms that represent this pattern. Application of the method in an audio genre classification task verifies that the obtained results are highly competitive compared with state-of-the-art methods. Moreover, the DL approach lends itself readily for online implementations, in line with the current trend in big data applications.

In this paper, an Adaptive Projected Subgradient Method (APSM) based algorithm for robust subspace tracking is introduced. A properly chosen cost function is constructed at each time instance and the goal is to seek for points, which belong to the zero level set of this function; i.e., the set of points which score a zero loss. In each iteration, an outlier detection mechanism is employed, in order to conclude whether the current data vector contains outlier noise or not. Furthermore, a sparsity-promoting greedy algorithm is employed for the outlier vector estimation allowing the purification of the corrupted data from the outlier noise prior further processing. A theoretical analysis is carried out and experiments within the context of robust subspace estimation exhibit the enhanced performance of the proposed scheme compared to a recently developed state of the art algorithm.

In this paper, a distributed adaptive algorithm for sparsity-aware learning in diffusion networks is developed. The algorithm follows the greedy roadmap for sparsity along with the adapt-combine co-operation strategy, based on the LMS rationale for adaptivity. A bound on the error norm between the obtained estimates and the target vector is computed, and the algorithm is shown to converge in the mean under some general assumptions. Finally, comparative experiments with a recently developed sparsity-promoting diffusion LMS demonstrate the enhanced performance of the proposed algorithm.

This letter establishes a novel analysis of the Adaptive Projected Subgradient Method (APSM) in the intersection of the stochastic and robust estimation paradigms. Utilizing classical worst-case bounds on the noise process, drawn from the robust estimation methodology, the present study demonstrates that the hyperslab-inspired version of the APSM generates a sequence of estimates which converges to a point located, with probability one, arbitrarily close to the estimand. Numerical tests and comparisons with classical time-adaptive algorithms corroborate the theoretical findings of the study.

In this paper, a novel algorithm for bandwidth reduction in adaptive distributed learning is introduced. We deal with diffusion net works, in which the nodes cooperate with each other, by exchanging information, in order to estimate an unknown parameter vector of interest. We seek for solutions in the framework of set theoretic estimation. Moreover, in order to reduce the required bandwidth by the transmitted information, which is dictated by the dimension of the unknown vector, we choose to project and work in a lower dimension Krylov subspace. This provides the benefit of trading off dimensionality with accuracy. Full convergence properties are presented, and experiments, within the system identification task, demonstrate the robustness of the algorithmic technique.