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

Morteza Mardani, Gonzalo Mateos, Georgios B. Giannakis

Introduction

In the era of massive data, monitoring large-scale systems like backbone communication networks presents a significant challenge. Network operators must distinguish between "normal" traffic patterns and "anomalous" events such as congestion, hardware failures, or cyber-attacks. Traditionally, this has been difficult because anomalies are often buried within high-volume background traffic, and direct measurement of every individual flow is often computationally or logistically impossible.

This paper addresses the problem of decomposing aggregated measurements into a low-rank component (representing stable, common traffic patterns) and a sparse component (representing localized anomalies). By extending the framework of Robust Principal Component Analysis (RPCA) to include a compression matrix, the authors provide a robust method for anomaly detection even when data is highly compressed.

Problem Formulation

The core of the research is the "low-rank plus compressed sparse" model. We observe a matrix $Y$ defined as:

$$Y = X_0 + RA_0$$

Where:

  • $X_0$ is a low-rank matrix representing the nominal traffic.
  • $A_0$ is a sparse matrix representing anomalies.
  • $R$ is a known "fat" compression or routing matrix.

In the context of network monitoring, $Y$ represents link loads, and $R$ is the routing matrix that maps individual flows to specific links. Because there are typically many more flows than links, $R$ is a wide matrix, making the recovery of $A_0$ an underdetermined problem. This framework subsumes both Compressed Sensing (where $X_0 = 0$) and standard Matrix Decomposition (where $R = I$).

Methodology

To recover $X_0$ and $A_0$, the authors formulate a convex optimization problem. Since minimizing the rank of a matrix and the number of non-zero entries in a vector are NP-hard problems, they utilize convex surrogates:

  1. Nuclear Norm (||X||_*): The sum of the singular values of $X$, which promotes low-rank structures.
  2. $ℓ_1$-norm (||A||_1): The sum of the absolute values of the entries in $A$, which promotes sparsity.

The resulting optimization problem seeks to minimize a weighted combination of these two norms subject to the constraint $Y = X + RA$.

Algorithms

The paper introduces two first-order algorithms to solve this non-smooth problem:

  • Accelerated Proximal Gradient (APG): This method is designed for speed, offering a convergence rate of $O(1/k^2)$. It is particularly effective for large-scale datasets where computational efficiency is paramount.
  • Alternating Direction Method of Multipliers (AD-MoM): This approach is more stable and handles the equality constraints of the noiseless formulation more naturally, making it better suited for exact recovery tasks.

Theoretical Guarantees

A significant portion of the work is dedicated to establishing the conditions under which $X_0$ and $A_0$ can be uniquely recovered. The authors identify two critical factors:

  • Incoherence: The low-rank component $X_0$ must not be "too sparse" (looking like an anomaly), and the compressed sparse component $RA_0$ must not be "too low-rank" (looking like background traffic).
  • Isometry Property: The compression matrix $R$ must behave like an isometry when restricted to sparse vectors. This ensures that the compression process does not "smear" the sparse anomalies in a way that makes them indistinguishable from the low-rank background.

Using a "dual certificate" construction, the authors prove that if these conditions are met, the convex program will recover the ground truth with high probability for certain random ensembles.

Experimental Results

The proposed framework was validated using both synthetic simulations and real-world data from the Internet2 backbone.

Synthetic Data

In controlled tests, the algorithms demonstrated remarkable precision, achieving relative errors in the range of $10^{-5}$ to $10^{-6}$. Crucially, the method proved resilient to high compression ratios. It was able to accurately identify anomalies even when the number of measurements was significantly lower than the number of flows (e.g., a compression ratio of 0.2), effectively detecting anomalies with 80% fewer sensors.

Internet2 Network Data

The method was applied to Origin-to-Destination (OD) flow data from the Internet2 network (11 nodes, 41 links, 121 flows). Compared to traditional PCA-based anomaly detection, the proposed approach showed superior performance. While PCA often fails when multiple anomalies occur simultaneously or when the "noise" is structured, this method explicitly models the anomalies as a sparse component, leading to higher detection rates and lower false-alarm probabilities.

Conclusion

This research provides a rigorous foundation for decomposing data into low-rank and compressed sparse components. By bridging the gap between Robust PCA and Compressed Sensing, the authors offer a powerful tool for network monitoring and anomaly detection. Future work remains in extending these proofs to more general classes of compression matrices and developing fully decentralized versions of the algorithms for deployment in distributed network environments.

Summary updated

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.
BibTeX
@article{mardani2012recovery,
  author = {Morteza Mardani and Gonzalo Mateos and Georgios B. Giannakis},
  title = {{Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  doi = {10.1109/tit.2013.2257913},
}
Figure