  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.
