Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies

Abstract

Given the superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, the goal of this paper is to establish deterministic conditions under which exact recovery of the low-rank and sparse components becomes possible. This fundamental identifiability issue arises with traffic anomaly detection in backbone networks, and subsumes compressed sensing as well as the timely low-rank plus sparse matrix recovery tasks encountered in matrix decomposition problems. Leveraging the ability of ${\ell }_1$- and nuclear norms to recover sparse and low-rank matrices, a convex program is formulated to estimate the unknowns. Analysis and simulations confirm that the said convex program can recover the unknowns for sufficiently low-rank and sparse enough components, along with a compression matrix possessing an isometry property when restricted to operate on sparse vectors. When the low-rank, sparse, and compression matrices are drawn from certain random ensembles, it is established that exact recovery is possible with high probability. First-order algorithms are developed to solve the nonsmooth convex optimization problem with provable iteration complexity guarantees. Insightful tests with synthetic and real network data corroborate the effectiveness of the novel approach in unveiling traffic anomalies across flows and time, and its ability to outperform existing alternatives.

38 pages, submitted to the IEEE Transactions on Information Theory

References in corpus (2)

• Robust PCA via Outlier Pursuit
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank

Cited by in corpus (19)

• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Robust Subspace Clustering with Compressed Data
• Identification of Successive "Unobservable" Cyber Data Attacks in Power Systems Through Matrix Decomposition
• Dynamic Network Cartography
• Anomaly Detection in Partially Observed Traffic Networks
• A Proximal Approach for a Class of Matrix Optimization Problems
• A Dictionary-Based Generalization of Robust PCA with Applications to Target Localization in Hyperspectral Imaging
• A Dictionary-Based Generalization of Robust PCA Part II: Applications to Hyperspectral Demixing
• Semi-blind Source Separation via Sparse Representations and Online Dictionary Learning
• A Dictionary Based Generalization of Robust PCA
• Target-based Hyperspectral Demixing via Generalized Robust PCA
• Collaborative Multi-sensor Classification via Sparsity-based Representation
• Low-Rank Methods in Event Detection and Subsampled Point-to-Subspace Proximity Tests
• Recursive Sparse Recovery in Large but Structured Noise - Part 2
• A Parallel Best-Response Algorithm with Exact Line Search for Nonconvex Sparsity-Regularized Rank Minimization
• Estimating Traffic and Anomaly Maps via Network Tomography