The monitoring and management of high-volume feature-rich traffic in large networks offers significant challenges in storage, transmission and computational costs. The predominant approach to reducing these costs is based on performing a linear mapping of the data to a low-dimensional subspace such that a certain large percentage of the variance in the data is preserved in the low-dimensional representation. This variance-based subspace approach to dimensionality reduction forces a fixed choice of the number of dimensions, is not responsive to real-time shifts in observed traffic patterns, and is vulnerable to normal traffic spoofing. Based on theoretical insights proved in this paper, we propose a new distance-based approach to dimensionality reduction motivated by the fact that the real-time structural differences between the covariance matrices of the observed and the normal traffic is more relevant to anomaly detection than the structure of the training data alone. Our approach, called the distance-based subspace method, allows a different number of reduced dimensions in different time windows and arrives at only the number of dimensions necessary for effective anomaly detection. We present centralized and distributed versions of our algorithm and, using simulation on real traffic traces, demonstrate the qualitative and quantitative advantages of the distance-based subspace approach.
Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model.  In this paper, we revisit the distributed total least squares (D-TLS) algorithm, which operates in an ad hoc sensor network where each node has access to a subset of the equations of an overdetermined set of linear equations. The D-TLS algorithm computes the total least squares (TLS) solution of the full set of equations in a fully distributed fashion (without fusion center). We modify the D-TLS algorithm to eliminate the large computational complexity due to an eigenvalue decomposition (EVD) at every node and in each iteration. In the modified algorithm, a single power iteration (PI) is performed instead of a full EVD computation, which significantly reduces the computational complexity. Since the nodes then do not exchange their true eigenvectors, the theoretical convergence results of the original D-TLS algorithm do not hold anymore. Nevertheless, we find that this PI-based D-TLS algorithm still converges to the network-wide TLS solution, under certain assumptions, which are often satisfied in practice. We provide simulation results to demonstrate the convergence of the algorithm, even when some of these assumptions are not satisfied.  In this paper, we consider principal component analysis (PCA) in decomposable Gaussian graphical models. We exploit the prior information in these models in order to distribute PCA computation. For this purpose, we reformulate the PCA problem in the sparse inverse covariance (concentration) domain and address the global eigenvalue problem by solving a sequence of local eigenvalue problems in each of the cliques of the decomposable graph. We illustrate our methodology in the context of decentralized anomaly detection in the Abilene backbone network. Based on the topology of the network, we propose an approximate statistical graphical model and distribute the computation of PCA.  Motivated by applications in multi-sensor array detection and estimation, this paper studies the problem of tracking the principal eigenvector and the principal subspace of a signal's covariance matrix adaptively in a fully decentralized wireless sensor network (WSN). Sensor networks are traditionally designed to simply gather raw data at a fusion center, where all the processing occurs. In large deployments, this model entails high networking cost and creates a computational and storage bottleneck for the system. By leveraging both sensors' abilities to communicate and their local computational power, our objective is to propose distributed algorithms for principal eigenvector and principal subspace tracking. We show that it is possible to have each sensor estimate only the corresponding entry of the principal eigenvector or corresponding row of the p-dimensional principal subspace matrix and do so by iterating a simple computation that combines data from its network neighbors only. This paper also examines the convergence properties of the proposed principal eigenvector and principal subspace tracking algorithms analytically and by simulations. Gossip algorithms are attractive for in-network processing in sensor networks because they do not require any specialized routing, there is no bottleneck or single point of failure, and they are robust to unreliable wireless network conditions. Recently, there has been a surge of activity in the computer science, control, signal processing, and information theory communities, developing faster and more robust gossip algorithms and deriving theoretical performance guarantees. This paper presents an overview of recent work in the area. We describe convergence rate results, which are related to the number of transmitted messages and thus the amount of energy consumed in the network for gossiping. We discuss issues related to gossiping over wireless links, including the effects of quantization and noise, and we illustrate the use of gossip algorithms for canonical signal processing tasks including distributed estimation, source localization, and compression.