Recovery of low-rank plus compressed sparse matrices with application to unveiling traffic anomalies

Morteza Mardani, Gonzalo Mateos, Georgios B Giannakis

Research output: Contribution to journalArticlepeer-review

69 Scopus citations

Abstract

Given the noiseless 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 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.

Original languageEnglish (US)
Article number6497613
Pages (from-to)5186-5205
Number of pages20
JournalIEEE Transactions on Information Theory
Volume59
Issue number8
DOIs
StatePublished - Jul 29 2013

Keywords

  • Convex optimization
  • identifiability
  • low rank
  • sparsity
  • traffic volume anomalies

Fingerprint Dive into the research topics of 'Recovery of low-rank plus compressed sparse matrices with application to unveiling traffic anomalies'. Together they form a unique fingerprint.

Cite this