A refined analysis for the sample complexity of adaptive compressive outlier sensing

Xingguo Li, Jarvis Haupt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

The Adaptive Compressive Outlier Sensing (ACOS) method, proposed recently in (Li & Haupt, 2015), is a randomized sequential sampling and inference method designed to locate column outliers in large, otherwise low rank, matrices. While the original ACOS established conditions on the sample complexity (i.e., the number of scalar linear measurements) sufficient to enable accurate outlier localization (with high probability), the guarantees required a minimum sample complexity that grew linearly (albeit slowly) in the number of matrix columns. This work presents a refined analysis of the sampling complexity of ACOS that overcomes this limitation; we show that the sample complexity of ACOS is sublinear in both of the matrix dimensions-on the order of the squared rank of the low-rank component plus the number of outliers, times constant and logarithmic factors.

Original languageEnglish (US)
Title of host publication2016 19th IEEE Statistical Signal Processing Workshop, SSP 2016
PublisherIEEE Computer Society
ISBN (Electronic)9781467378024
DOIs
StatePublished - Aug 24 2016
Event19th IEEE Statistical Signal Processing Workshop, SSP 2016 - Palma de Mallorca, Spain
Duration: Jun 25 2016Jun 29 2016

Publication series

NameIEEE Workshop on Statistical Signal Processing Proceedings
Volume2016-August

Other

Other19th IEEE Statistical Signal Processing Workshop, SSP 2016
CountrySpain
CityPalma de Mallorca
Period6/25/166/29/16

Bibliographical note

Funding Information:
The authors acknowledge support from NSF Award No. CCF-1217751.

Publisher Copyright:
© 2016 IEEE.

Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

Keywords

  • adaptive sensing
  • compressive sensing
  • outlier pursuit
  • robust PCA
  • stochastic ordering

Fingerprint Dive into the research topics of 'A refined analysis for the sample complexity of adaptive compressive outlier sensing'. Together they form a unique fingerprint.

Cite this