Identifying outliers in large matrices via randomized adaptive compressive sampling

Xingguo Li, Jarvis D Haupt

Research output: Contribution to journalArticlepeer-review

41 Scopus citations

Abstract

This paper examines the problem of locating outlier columns in a large, otherwise low-rank, matrix. We propose a simple two-step adaptive sensing and inference approach and establish theoretical guarantees for its performance; our results show that accurate outlier identification is achievable using very few linear summaries of the original data matrix-as few as the squared rank of the low-rank component plus the number of outliers, times constant and logarithmic factors. We demonstrate the performance of our approach experimentally in two stylized applications, one motivated by robust collaborative filtering tasks, and the other by saliency map estimation tasks arising in computer vision and automated surveillance, and also investigate extensions to settings where the data are noisy, or possibly incomplete.

Original languageEnglish (US)
Article number7035075
Pages (from-to)1792-1807
Number of pages16
JournalIEEE Transactions on Signal Processing
Volume63
Issue number7
DOIs
StatePublished - Apr 1 2015

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

Keywords

  • Adaptive sensing
  • compressed sensing
  • robust PCA
  • sparse inference

Fingerprint

Dive into the research topics of 'Identifying outliers in large matrices via randomized adaptive compressive sampling'. Together they form a unique fingerprint.

Cite this