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 language | English (US) |
|---|---|
| Title of host publication | 2016 19th IEEE Statistical Signal Processing Workshop, SSP 2016 |
| Publisher | IEEE Computer Society |
| ISBN (Electronic) | 9781467378024 |
| DOIs | |
| State | Published - Aug 24 2016 |
| Event | 19th IEEE Statistical Signal Processing Workshop, SSP 2016 - Palma de Mallorca, Spain Duration: Jun 25 2016 → Jun 29 2016 |
Publication series
| Name | IEEE Workshop on Statistical Signal Processing Proceedings |
|---|---|
| Volume | 2016-August |
Other
| Other | 19th IEEE Statistical Signal Processing Workshop, SSP 2016 |
|---|---|
| Country/Territory | Spain |
| City | Palma de Mallorca |
| Period | 6/25/16 → 6/29/16 |
Bibliographical note
Publisher Copyright:© 2016 IEEE.
Keywords
- adaptive sensing
- compressive sensing
- outlier pursuit
- robust PCA
- stochastic ordering