Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling

DOI10.1109/TSP.2015.2401536MaRDI QIDQ4580487zbMATH OpenOpenAlexFDO

Authors Xing Guo Li, Jarvis D. Haupt

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0312

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20) Special matrices (15B99)

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.

Recommendations

• Randomized Robust Subspace Recovery and Outlier Detection for High Dimensional Data Matrices
• Efficient Algorithms on Robust Low-Rank Matrix Completion Against Outliers
• Low-Rank Matrix Recovery Via Robust Outlier Estimation
• Low rank approximation in the presence of outliers
• Sampling-based dimension reduction for subspace approximation with outliers
• scientific article; zbMATH DE number 1934540
• High-dimensional outlier detection using random projections
• Low-rank outlier detection
• scientific article; zbMATH DE number 2050873
• Computationally easy outlier detection via projection pursuit with finitely many directions

Cited in

(3)

• scientific article; zbMATH DE number 6846423 (Why is no real title available?)
• Robust PCA by manifold optimization
• Detection of long edges on a computational budget: A sublinear approach

This page was built for publication: Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580487)