Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling

DOI10.1109/TSP.2015.2401536zbMATH Open1394.94826arXiv1407.0312OpenAlexW2087445541MaRDI QIDQ4580487FDOQ4580487

Authors: Xing Guo Li, Jarvis D. Haupt 

Publication date: 22 August 2018

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

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.

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

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

Mathematics Subject Classification ID

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

Cited In (3)

• Title not available (Why is that?)
• 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)