# Provable Self-Representation Based Outlier Detection in a Union of Subspaces

arXiv: https://arxiv.org/abs/1704.03925 · HTML: https://mlsanity.com/paper/1704.03925/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2017.

## Built on by (most cited first, 18 of 18)

- [One-Class Classification: A Survey](https://mlsanity.com/paper/2101.03064/) (2021)
- [A Survey on Open Set Recognition](https://mlsanity.com/paper/2109.00893/) (2021)
- [Learning a Self-Expressive Network for Subspace Clustering](https://mlsanity.com/paper/2110.04318/) (2021)
- [Applications of Generative Adversarial Networks in Anomaly Detection: A Systematic Literature Review](https://mlsanity.com/paper/2110.12076/) (2021)
- [Stabilizing Adversarially Learned One-Class Novelty Detection Using Pseudo Anomalies](https://mlsanity.com/paper/2203.13716/) (2022)
- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Evaluation of (Un-)Supervised Machine Learning Methods for GNSS Interference Classification with Real-World Data Discrepancies](https://mlsanity.com/paper/2503.23775/) (2025)
- [The Vision of Self-Evolving Computing Systems](https://mlsanity.com/paper/2204.06825/) (2022)
- [Unknown Face Presentation Attack Detection via Localised Learning of Multiple Kernels](https://mlsanity.com/paper/2204.10675/) (2022)
- [Coupled-Space Attacks against Random-Walk-based Anomaly Detection](https://mlsanity.com/paper/2307.14387/) (2023)
- [Connective Reconstruction-based Novelty Detection](https://mlsanity.com/paper/2210.13917/) (2022)
- [Beyond the Known: Adversarial Autoencoders in Novelty Detection](https://mlsanity.com/paper/2404.04456/) (2024)
- [Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search](https://mlsanity.com/paper/2106.12190/) (2021)
- [Generalized One-Class Learning Using Pairs of Complementary Classifiers](https://mlsanity.com/paper/2106.13272/) (2021)
- [Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension](https://mlsanity.com/paper/2201.09079/) (2022)
- [Semantic Novelty Detection and Characterization in Factual Text Involving Named Entities](https://mlsanity.com/paper/2210.17440/) (2022)
- [A Robust Likelihood Model for Novelty Detection](https://mlsanity.com/paper/2306.03331/) (2023)
- [Cascade Subspace Clustering for Outlier Detection](https://mlsanity.com/paper/2306.13500/) (2023)

## Abstract (arXiv)

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.