Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling

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.

16 pages, 7 figures, 2 tables, IEEE Transactions on Signal Processing (submitted)

References in corpus (11)

• User-friendly tail bounds for sums of random matrices
• Rank-Sparsity Incoherence for Matrix Decomposition
• Two Proposals for Robust PCA using Semidefinite Programming
• Statistical Compressed Sensing of Gaussian Mixture Models
• Robust computation of linear models by convex relaxation
• Sketched SVD: Recovering Spectral Features from Compressive Measurements
• Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
• Algorithms and Hardness for Robust Subspace Recovery
• Multistage Adaptive Estimation of Sparse Signals
• On the Power of Adaptivity in Matrix Completion and Approximation
• Adaptive sensing performance lower bounds for sparse signal detection and support estimation

Cited by in corpus (15)

• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• An Overview of Robust Subspace Recovery
• High Dimensional Low Rank plus Sparse Matrix Decomposition
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Fast, Robust and Non-convex Subspace Recovery
• Robust PCA by Manifold Optimization
• Scalable and Robust Community Detection with Randomized Sketching
• A Dictionary-Based Generalization of Robust PCA Part II: Applications to Hyperspectral Demixing
• A Dictionary-Based Generalization of Robust PCA with Applications to Target Localization in Hyperspectral Imaging
• Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
• A Dictionary Based Generalization of Robust PCA
• Target-based Hyperspectral Demixing via Generalized Robust PCA
• Outlier Detection and Data Clustering via Innovation Search
• Compressive PCA for Low-Rank Matrices on Graphs
• Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices