PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Chong You, Daniel P. Robinson, René Vidal

arXiv:1704.03925v1cs.CVstat.ML

TL;DR

Outlier detection is important when data lie near a union of low-dimensional subspaces, but contain points outside those subspaces. This paper combines sparse self-representation with random walks on a directed graph to identify outliers. It reports state-of-the-art performance on image databases and theoretical correctness under stated assumptions.

  • Problem

    The paper addresses detecting points outside unknown low-dimensional subspaces in datasets where outliers must be rejected before subsequent analysis.

    Source: §1 · p. 1

  • Method

    It builds a directed graph from sparse data self-representations and uses random-walk probabilities to identify outliers.

    Source: §1 · p. 2, §3.2 · p. 4

  • Results

    The method achieves state-of-the-art performance on face and object image databases and is guaranteed correct under stated assumptions.

    Source: §4.3 · p. 6, §6 · p. 8

  • Takeaways & Limitations

    The method can handle multiple inlier subspaces without requiring their number or dimensions to be known.

    Source: §6 · p. 8

    Correct identification depends on subspace-preserving representations and connectivity conditions; poor connectivity can lead to inliers or outliers being misclassified.

    Source: §4.1 · p. 5, §4 · p. 5

Abstract

from arXiv · show

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.

1. Introduction

The paper addresses outlier detection when inliers lie near a union of low-dimensional subspaces. It uses sparse self-representation and random walks on a directed graph to detect outliers, with theoretical guarantees and image-database experiments.

1. Introduction

  • Outliers complicate subspace learning, while RANSAC scales exponentially with subspace dimension and many robust-PCA methods model only one inlier subspace.Robust subspace fitting can also require good initialization because its optimization is usually nonconvex.Source: §1 · p. 1
  • The method uses sparse self-representation to build a directed graph and identifies outliers from random-walk probabilities that tend to zero.Inliers represent themselves using other inliers, whereas outliers may use both inliers and outliers.Source: §1 · p. 2
  • It handles multiple inlier subspaces without requiring their number or dimensions, and allows subspaces to intersect.The method also uses neighborhood context when assessing a point’s outlierness.Source: §1 · p. 2
  • The analysis establishes correct detection under suitable assumptions, and experiments on real image databases illustrate the method’s effectiveness.The assumptions concern the data distribution and representation-graph connectivity.Source: §1 · p. 2

2. Related work

Prior outlier-detection approaches use representation norms, low-rank representations, hyperplane fitting, or graph centrality, but each has limitations in the settings described.

2. Related work

  • Thresholding self-representation ℓ1 norms can miss nearby outliers, while LRR requires independent subspaces whose union is low-dimensional.LRR uses a low-rank self-representation and unsquared representation-error penalties.Source: §2 · pp. 2–3
  • OutRank treats low-centrality points as outliers, but its similarity graph can fail when points within a subspace are not densely sampled.Its edge weights use cosine or RBF similarity.Source: §2 · p. 3
  • Recursive hyperplane fitting can detect outliers in a general subspace, but the described approach assumes one inlier subspace of known dimension.The underlying hyperplane formulation can learn a linear hyperplane from outlier-corrupted data.Source: §2 · p. 3

3. Outlier detection by self-representation

R-graph constructs self-representations, turns them into a directed Markov chain, and uses averaged random-walk probabilities to identify outliers.

3.1. Data self-representation

  • The method first constructs a data self-representation matrix, then uses differences in how inliers and outliers represent themselves.Inliers typically use only other inliers; outliers generally use both inliers and outliers.Source: §3 · p. 3, §3.1 · p. 3
  • Elastic-net regularization balances sparse representations against graph connectivity, helping address cases where points are poorly connected.Its ℓ1 term promotes sparsity, while its ℓ2 term promotes more nonzero entries and connections.Source: §3.1 · p. 3

3.2. Representation graph and random walk

  • The representation matrix defines a weighted directed graph whose Markov-chain transitions make inliers absorbing with respect to outlier states.Walks starting at outliers can enter inlier states and then cannot return to outliers.Source: §3.2 · pp. 3–4

3.3. Main algorithm: Outlier detection by R-graph

  • The algorithm initializes walks across all data points and averages their state distributions, since individual t-step distributions need not converge.The Cesàro mean converges, and its limit matches the ordinary limit when that limit exists.Source: §3.3 · p. 4

4. Theoretical guarantees for correctness

The section establishes that the method identifies outliers when the representation is subspace-preserving and the graph satisfies stated connectivity conditions. Under these assumptions, inliers and outliers correspond to essential and inessential Markov-chain states, respectively.

4.1. Subspace-preserving representation

  • Condition (7) gives a sufficient geometric condition for the optimization solution to be subspace-preserving: in-subspace points must cover the normalized oracle point more strongly than competing points do.The condition requires nearby points from the same subspace and separation from outliers and points in other subspaces.Source: §4.1 · p. 5

4.2. Connectivity considerations

  • Connectivity assumptions require each inlier subspace to form a strongly connected graph and every outlier subset to have an edge leading outside itself.Without adequate connectivity, an inlier can be mistaken for an outlier, or an outlier subset can behave like inliers.Source: §4.2 · p. 5

4.3. Main theorem: guaranteed outlier detection

  • Under a subspace-preserving representation and Assumptions 4.1–4.2, Algorithm 1 correctly identifies outliers for T = ∞ and ϵ = 0.The result follows because inliers correspond to essential states, outliers to inessential states, and the Cesàro-averaged distribution has zero limiting probability exactly at inessential states.Source: §4.3 · p. 6
  • The Cesàro mean of the random-walk distributions converges to a distribution whose zero-probability states are exactly the inessential states.The theorem therefore establishes correctness under the stated geometric and connectivity conditions.Source: §4 · p. 5, §4.3 · p. 6

5. Experiments

Across face and object image tasks, R-graph achieves the best reported performance, including when inliers span multiple groups. The experiments evaluate one- and multiple-group settings against sparse, low-rank, and graph-based baselines.

5.1. Experimental setup

  • The experiments use Yale B faces, Caltech-256 categories, and Coil-100 objects, with outliers drawn from other subjects, clutter, or other categories, respectively.The evaluation reports AUC and the largest F1-score across thresholds; reported experiment averages are over 50 trials.Source: §5.1 · pp. 6–7, §5.2 · p. 7, §5.3 · p. 8

5.2. Outliers in face images

  • On Yale B with one inlier subject, R-graph outperforms the other methods; REAPER, Outlier Pursuit, and DPCP also perform well on this single-subspace setting.The authors attribute the latter methods’ performance to their fitting a single subspace, suitable for images of one individual.Source: §5.2 · p. 7, Table 1 · p. 7
  • For Yale B, LRR and ℓ1-thresholding perform poorly, while R-graph’s connection patterns yield significantly better results than using representation-vector magnitude alone.The authors suggest LRR’s results may reflect that its solver is not guaranteed to converge to a global optimum.Source: §5.2 · p. 7, Table 1 · p. 7
  • On Yale B with three inlier subjects, Outlier Pursuit and R-graph are the two best methods, while REAPER and DPCP are less competitive.The authors postulate that Outlier Pursuit may eventually fail as the number of inlier groups increases because their union may no longer be low rank; they state that R-graph does not have this limitation.Source: §5.2 · pp. 7–8, Table 1 · p. 7

5.3. Outliers in images of objects

  • R-graph achieves the best performance on Caltech-256 and Coil-100; geometric methods do well with one inlier category but deteriorate as categories increase.The authors suggest that linear-subspace methods may fare worse because these datasets may be better modeled by a nonlinear manifold; self-expression methods seem more powerful for this data.Source: §5.3 · p. 8, Table 2 · p. 8, Table 3 · p. 8

6. Conclusion

The paper presents a self-representation and random-walk method for outlier detection in multiple subspaces. It reports theoretical guarantees under stated conditions and state-of-the-art performance on face and object image databases.

6. Conclusion

  • The method combines data self-representation with random walks on a representation graph and does not require knowing the number or dimensions of subspaces.The analysis guarantees outlier identification when certain geometric conditions and two connectivity assumptions hold; experiments report state-of-the-art performance on face and object image databases.Source: §6 · p. 8

Appendices

The appendices provide proof-related material, Markov-chain background, and additional experimental results.

Appendices

  • Section A discusses subspace-preserving representations and outlines the proof of Theorem 4.1.Section A also contains an overview of that theorem’s proof.Source: Appendices · p. 9
  • Section B gives Markov-chain background used in Section C to prove Lemmas 4.1 and 4.2 and discuss the Cesàro mean used for outlier detection.Source: Appendices · p. 9
  • Section D provides additional Extended Yale B experimental results intended to give further insight into method behavior.Source: Appendices · p. 9

A. Subspace-preserving representation and proof of Theorem 4.1

This section defines subspace-preserving representations and adapts prior analysis to study them when outliers are present.

A. Subspace-preserving representation and proof of Theorem 4.1

A.1. Proof of Theorem 4.1

The proof establishes conditions for self-representations to preserve subspaces, then uses Markov-chain state structure and Cesàro averaging to justify outlier detection. Its correctness guarantee requires both subspace preservation and connectivity assumptions.

A.1. Proof of Theorem 4.1

  • Low correlation between the oracle direction and points outside the subspace is a sufficient condition for the constructed representation to be subspace-preserving.The proof constructs a representation by padding zeros outside the target subspace and tests whether it solves the optimization problem.Source: §A.1 · p. 9

A.2. Discussions

  • The inradius corollary gives a stronger sufficient condition, met more easily when points densely and broadly cover their subspace.The inradius is the radius of the largest Euclidean ball inscribed in the convex body; the corollary’s condition is stronger than Theorem 4.1’s.Source: §A.2 · pp. 9–10

B. Background on Markov chain theory

  • A Markov chain’s state space partitions into inessential states and closed communicating classes, whose states are essential.States in other communicating classes are inessential.Source: §B.1 · p. 10

B.2. Stationary distribution

  • Each closed communicating class has a unique positive stationary distribution, while a chain with multiple such classes need not have a unique stationary distribution.Source: §B.2 · p. 10

B.3. Convergence of the Ces`aro mean 1

  • The Cesàro mean converges even when the sequence of t-step transition probabilities does not; its limit incorporates hitting probabilities from inessential states to closed classes.Source: §B.3 · p. 11

C. Guaranteed outlier detection

  • Under subspace-preserving representations and connectivity assumptions, inliers and outliers correspond to essential and inessential states, which the Cesàro mean identifies.Source: C. Guaranteed outlier detection · p. 11

C.1. Proof of Lemma 4.1

The proof links graph reachability to Markov-chain state type: inliers are essential, while outliers are inessential under the stated assumptions.

C.1. Proof of Lemma 4.1

  • Each Markov-chain state corresponds to one data point.Source: §C.1 · p. 11
  • For an inlier, subspace preservation confines outgoing links to its subspace, and strong connectivity makes reachable states able to return, so the state is essential.Source: §C.1 · p. 11
  • An outlier’s reachable set must include an inlier, but subspace preservation prevents that inlier from linking back, making the outlier state inessential.Source: §C.1 · p. 11

C.2. Proof of Lemma 4.2

The Cesàro limit identifies inessential states, and the discussion and experiments examine its interpretation, runtime, parameter sensitivity, and performance as outlier prevalence changes.

C.2. Proof of Lemma 4.2

  • In the Cesàro limit, a state has zero probability exactly when it is inessential.Source: §C.2 · p. 11

C.3. Discussion

  • The Cesàro mean converges to a stationary distribution that may be any convex combination of class-specific stationary distributions, depending on the initial distribution.Source: §C.3 · p. 11

D.1. Computational time comparison

  • OutRank and CoP run much faster than the other methods in the reported experiment; each sparse R-graph walk step costs O(sN).The experiment uses Extended Yale B with three inlier groups and 15% outliers; s is the average number of nonzero entries per representation vector.Source: §D.1 · p. 12

D.2. Influence of the algorithm parameters

  • R-graph performs well across α values from 1 to 50 on Extended Yale B with three inlier groups and 15% outliers.Source: §D.2 · p. 12

D.3. Influence of the percentage of outliers

  • R-graph remains stable and performs best among the compared methods as outlier prevalence varies from 1% to 15%, with parameters fixed.Source: §D.3 · p. 12

D.4. Visualization of the outliers

In the visualization experiments, R-graph is reported as more robust than ℓ1-thresholding, while extreme-illumination images account for many false positives across methods.

D.4. Visualization of the outliers

  • The visualization ranks the top 10 detected outliers using 64 images of one subject as inliers and 10 randomly selected images from 37 other subjects as outliers.Source: §D.4 · p. 12, Figure D.2 · p. 13
  • False positives across methods are mostly images under extreme illumination, whose shadows can remove them from the subject’s underlying subspace.Source: §D.4 · p. 12
  • R-graph is significantly better than ℓ1-thresholding among the visualized results, and the authors attribute the difference to connectivity being more robust than representation magnitude.Source: §D.4 · pp. 12–13
Loading 1704.03925v1…