2017/04/12 by Chong You, You, Chong, Daniel P. Robinson +3 · 11 citations
Computer Science · Engineering · Mathematics · #Advanced Statistical Methods and Models #Algorithm #Anomaly Detection Techniques and Applications #Anomaly detection #Artificial intelligence #Computer Vision and Pattern Recognition (cs.CV) #Computer science #Correctness #Data mining #FOS: Computer and information sciences #Graph #Linear subspace #Machine Learning (stat.ML) #Machine learning #Markov chain #Mathematics #Outlier #Pattern recognition (psychology) #Rank (graph theory) #Representation (politics) #Sparse and Compressive Sensing Techniques #Sparse approximation #Sparse matrix #Theoretical computer science #cs.CV #stat.ML
paper · pdf · doi:10.48550/arxiv.1704.03925
published in arXiv (Cornell University) (Cornell University) · 16 pages. CVPR 2017 spotlight oral presentation
arxiv created 2017/04/12 · openalex publication_date 2017/04/12 · arxiv updated 2017/04/14 · openalex created_date 2019/06/27 · openalex updated_date 2026/08/05
Many computer vision tasks involve processing large amounts of data contaminated by outliers, which need to be detected and rejected. While outlier detection methods based on robust statistics have existed for decades, only recently have methods based on sparse and low-rank representation been developed along with guarantees of correct outlier detection when the inliers lie in one or more low-dimensional subspaces. This paper proposes a new outlier detection method that combines tools from sparse representation with random walks on a graph. By exploiting the property that data points can be expressed as sparse linear combinations of each other, we obtain an asymmetric affinity matrix among data points, which we use to construct a weighted directed graph. By defining a suitable Markov Chain from this graph, we establish a connection between inliers/outliers and essential/inessential states of the Markov chain, which allows us to detect outliers by using random walks. We provide a theoretical analysis that justifies the correctness of our method under geometric and connectivity assumptions. Experimental results on image databases demonstrate its superiority with respect to state-of-the-art sparse and low-rank outlier detection methods.