Unveiling Anomalies in Large-Scale Networks via Sparsity and Low Rank

Friday, March 2, 2012 - 9:00am - 9:45am
Keller 3-180
Georgios Giannakis (University of Minnesota, Twin Cities)
In the backbone of large-scale networks, traffic flows experience abrupt
unusual changes which can result in congestion, and limit the extent
to which end-user quality of service requirements are met. Diagnosing
such traffic volume anomalies is a crucial task towards engineering
the network traffic. This is challenging however, since the available
data are the superposition of unobservable origin-to-destination (OD)
flows per link. Leveraging the low intrinsic-dimensionality of OD flows
and the sparse nature of anomalies, a convex program is formulated to
unveil anomalies across flows and time. A centralized solver is developed
using the proximal gradient algorithm, which offers provable iteration
complexity guarantees. An equivalent nonconvex but separable criterion
enables in-network processing of link-load measurements, when optimized
via the alternating-direction method of multipliers. The novel distributed
iterations entail reduced-complexity local tasks, and affordable message
passing between neighboring nodes. Interestingly, under mild conditions
the distributed algorithm approaches its centralized counterpart.
Numerical tests with synthetic and real network data corroborate
the effectiveness of the novel scheme.
MSC Code: