PaperlayerView exact revision on arXiv

Source-linked AI summary

Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis

Mostafa Rahmani, George Atia

arXiv:1609.04789v3cs.LGstat.ML

TL;DR

Robust PCA must recover a low-dimensional subspace despite outlying columns, while many existing approaches have computational or outlier-model limitations. CoP compares each data point’s coherence with the rest of the data to distinguish inliers from outliers. The paper reports exact recovery even when the inlier-to-outlier ratio is 0.01, and gives guarantees for structured and unstructured outliers.

Abstract

from arXiv · show

This paper presents a remarkably simple, yet powerful, algorithm termed Coherence Pursuit (CoP) to robust Principal Component Analysis (PCA). As inliers lie in a low dimensional subspace and are mostly correlated, an inlier is likely to have strong mutual coherence with a large number of data points. By contrast, outliers either do not admit low dimensional structures or form small clusters. In either case, an outlier is unlikely to bear strong resemblance to a large number of data points. Given that, CoP sets an outlier apart from an inlier by comparing their coherence with the rest of the data points. The mutual coherences are computed by forming the Gram matrix of the normalized data points. Subsequently, the sought subspace is recovered from the span of the subset of the data points that exhibit strong coherence with the rest of the data. As CoP only involves one simple matrix multiplication, it is significantly faster than the state-of-the-art robust PCA algorithms. We derive analytical performance guarantees for CoP under different models for the distributions of inliers and outliers in both noise-free and noisy settings. CoP is the first robust PCA algorithm that is simultaneously non-iterative, provably robust to both unstructured and structured outliers, and can tolerate a large number of unstructured outliers.

I. INTRODUCTION

The paper targets column-wise robust PCA, where ordinary PCA can deviate arbitrarily from the true subspace under outliers. It proposes Coherence Pursuit (CoP), which compares each point’s coherence with the rest of the data to identify inliers and recover the subspace.

I. INTRODUCTION

  • Ordinary PCA is sensitive to outliers: even a small number can make its solution deviate arbitrarily from the true subspace.The paper frames its contribution against prior methods’ computational, guarantee, and outlier-model limitations.Source: §I · p. 1, A. Motivation and summary of… · p. 3

A. The inlier-outlier structure

  • The paper focuses on column-wise corruption, where only a fraction of corruption columns are nonzero and some inlier columns remain unaffected.It does not consider the element-wise corruption model; outliers may be unstructured or form small low-dimensional clusters distinct from the inliers.Source: §I · p. 1, A. The inlier-outlier structure · pp. 1–2

B. Notation and definitions

II. RELATED WORK

A. Motivation and summary of contributions

  • CoP uses coherence with the rest of the data to distinguish outliers, and is presented as a non-iterative method with guarantees for structured and unstructured outliers.It roughly involves one matrix multiplication to compute the Gram matrix and can tolerate a large number of unstructured outliers.Source: A. Motivation and summary of… · p. 3

2. Mutual Coherence Measurement

CoP scores columns by their coherence with the rest of the data and uses high-scoring columns to span the target subspace. The supplied examples show separation under heavy unstructured outliers, noise, and clustered outliers, alongside sampling and complexity considerations.

2. Mutual Coherence Measurement

  • CoP measures each column’s coherence by the norm of its off-diagonal Gram-matrix row, then selects columns with the largest scores to span an r-dimensional subspace.The output columns form a basis for col(L).Source: §2 · p. 3

III. PROPOSED METHOD

  • Because inliers are correlated within a low-dimensional subspace, CoP expects their coherence scores to exceed outlier scores when m ≫ r.Under Assumption 1, the expected inlier score is given as (n1−1)r/m + n2/m for p = 2.Source: §III · pp. 3–4

A. Large number of unstructured outliers

C. Structured outlying columns

D. Subspace identification

  • Adaptive sampling projects data to a random kr-dimensional subspace and samples columns that add innovation, avoiding redundant selections.The projection parameter k may be 2; for noisy data, the number of sampling rounds h trades closer alignment to col(A) against possible outlier sampling when chosen unreasonably large.Source: D. Subspace identification · p. 4

B. Robustness to noise

E. Computational complexity

  • CoP’s overall complexity is O(mn2 + r3n); randomized sketching can reduce it to O(r4), and the method roughly uses one matrix multiplication.The authors describe CoP as non-iterative and suitable for simple hardware implementation.Source: §2 · p. 5

IV. THEORETICAL INVESTIGATIONS

CoP’s guarantees cover exact subspace recovery with unstructured outliers, including settings where outliers outnumber inliers. Recovery depends on inlier density and coherence relative to the outlier population.

IV. THEORETICAL INVESTIGATIONS

  • For unstructured outliers, CoP has sufficient conditions for an expected inlier-coherence gap and high-probability exact recovery; guarantees cover p = 1 and p = 2.The expected-gap conditions are presented for both p values, while the remaining theoretical studies use p = 1.Source: §IV · p. 5

A. Subspace recovery with dominant unstructured outliers

  • Recovery favors a sufficiently large inlier density n1/r relative to the outlier ratio n2/m, because these ratios affect mutual coherence.The passages connect increasing inlier density with greater inlier coherence and describe outlier coherence as proportional to n2/m.Source: A. Subspace recovery with dominant… · p. 5
  • CoP can recover the exact subspace when the inlier-to-outlier ratio is 0.01 in the illustrated setting.The passage attributes this to a clear gap between inlier and outlier entries of p.Source: A. Subspace recovery with dominant… · p. 6
  • The sufficient conditions indicate that CoP with p = 2 can tolerate more unstructured outliers than with p = 1 in high-dimensional settings.The passage says this is confirmed by the last-row plots in Fig. 1.Source: A. Subspace recovery with dominant… · p. 6

B. Distinguishing structured outliers

CoP’s analysis extends from structured outliers to noisy data. Structured outliers are distinguishable under population and structure conditions, while noise adds terms to sufficient conditions without changing their order.

B. Distinguishing structured outliers

  • For structured outliers, distinguishability improves when their population is smaller or their clustering is weaker, and the inlier population must be sufficiently larger.The conditions concern outliers clustered around a direction, with their similarity increasing as µ decreases.Source: B. Distinguishing structured outliers · pp. 6–7
  • The function f(t) used in the structured-outlier analysis decreases nearly exponentially with t and converges as m grows.The plotted curves for m = 10^10 and m = 10^20 coincide.Source: B. Distinguishing structured outliers · p. 6

C. Performance analysis with noisy data

  • Noise affects subspace identification through recovery from noisy inliers, and increasing noise power increases the distance from the noise-free inlier subspace.The passage describes this recovery error as inevitable for noisy data; the noise-related term in the sufficient condition is linear in 1/√m.Source: C. Performance analysis with noisy data · p. 7
  • With noisy data, the sufficient condition for separating inlier and outlier coherence retains the noise-free condition’s order, with an added term approximately linear in σn.The theorem gives a high-probability separation condition; the added noise term does not change its order relative to the noise-free case.Source: C. Performance analysis with noisy data · p. 7

D. The distribution of inliers

The analysis considers clustered inliers and finds that CoP is more likely to recover the correct subspace when the inliers are less randomly distributed. The parameter ν describes their clustering.

D. The distribution of inliers

  • Assumption 4 models inliers clustered around a direction in U, with larger ν corresponding to less clustering.Fig. 5 shows the inlier distribution for different values of ν.Source: D. The distribution of inliers · pp. 7–8, Figure 5 · p. 8
  • As ν decreases, inliers become less randomly distributed, and CoP is more likely to recover the correct subspace.The paper’s conclusion is that CoP prefers clustered inliers to randomly distributed ones.Source: D. The distribution of inliers · p. 8

Error Correction

The section describes iterative error correction by fitting subspace bases to clusters and updating assignments, then evaluates CoP on synthetic and real data against robust PCA methods. Across the simulations, CoP handles unstructured and structured outliers and runs faster than the compared approaches.

Error Correction

  • The error-correction procedure applies robust PCA to clustered data, obtains subspace bases, then updates point assignments using those bases.The output consists of orthonormal bases for the identified subspaces.Source: Error Correction · p. 8

A. Phase transition

  • When n2/m increases, larger n1/r is needed for exact recovery, but n1/r > 4 can still succeed when n2/m > 30.The phase-transition plot marks correct recovery in white and incorrect recovery in black.Source: A. Phase transition · p. 8, Figure 6 · p. 8

B. Running time

  • CoP is remarkably faster than the compared robust PCA approaches across the tested data sizes.The experiments use n1 = n/5 and n2 = 4n/5; Table I reports runtimes in seconds.Source: B. Running time · p. 8, Table I · p. 9

C. Subspace recovery in presence of unstructured outliers

D. Detection of structured outliers

E. Clustering error correction – Real data

The paper applies robust PCA to clustered data to correct misclassifications, then updates assignments using the estimated subspace bases. On Hopkins155 traffic sequences, CoP outperforms the compared approaches; the proof material also states a random-subspace and random-direction condition.

E. Clustering error correction – Real data

  • Algorithm 3 treats misclassified points in each cluster as outliers, estimates subspace bases with robust PCA, and updates the clustering from those bases.The procedure can be applied to the output of any subspace-clustering algorithm.Source: E. Clustering error correction – Real… · p. 11
  • With an initial 20% clustering error on Hopkins155 traffic data, CoP clearly outperforms the other approaches, while most robust PCA methods increase clustering error.The data include eight two-motion and eight three-motion scenarios; Fig. 11 plots average clustering error after each iteration.Source: E. Clustering error correction – Real… · p. 11, Figure 11 · p. 11

VI. PROOFS OF THE MAIN RESULTS

  • The proof material states that U is a random subspace and each a_i is a random direction within U.Source: §VI · p. 11

Proof of Theorem 3

The proof compares lower bounds on coherence-column norms for inliers with upper bounds for outliers. Under condition (9), the inlier bound exceeds the outlier bound with high probability.

  • If condition (9) holds, the proof establishes with high probability that every inlier column's ℓ1 norm in G exceeds the maximum outlier-column ℓ1 norm.The argument obtains lower bounds for inlier columns and upper bounds for outlier columns.Source: Proof of Theorem 3 · p. 12
  • Corollary 13 supplies a lower bound on the ℓ1 norm of each inlier column under Assumption 1.The proof invokes a result for independent random vectors uniformly distributed on a unit sphere.Source: Proof of Theorem 3 · p. 12
  • Corollaries 14 and 15 provide upper bounds on the ℓ1 norms of outlier columns under Assumption 1.Source: Proof of Theorem 3 · p. 12

Proof of Lemma 15

The proof of Lemma 15 invokes a random-subspace result and concludes exact recovery with high probability when condition (9) holds. Theorem 4 is established through additional lemmas and corollaries.

Proof of Lemma 15

  • A random-subspace lemma is used to establish an intermediate probability bound in the proof of Lemma 15.The passage states the bound holds with probability at least 1 − δ.Source: Proof of Lemma 15 · p. 12
  • When condition (9) is satisfied, the proposed algorithm recovers the exact subspace with probability at least 1 − 3δ.Source: Proof of Lemma 15 · p. 12

Proof of Theorem 4

  • The proof states that its argument for Theorem 4 follows from lemmas and resulting corollaries.The excerpted corollaries assume Assumption 1.Source: Proof of Theorem 4 · pp. 12–13

Proof of Lemma 5

The Proof of Lemma 5 uses a Beta-distributed squared projection and probability bounds. The accompanying Proof of Lemma 7 bounds a component and an expected value.

Proof of Lemma 5

  • The proof gives a Beta distribution for the squared projection, with parameters α = 1/2 and β = m/2 − 1/2, and expectation 1/m.It then uses the definition of f(t) for a probability bound and Corollaries 14 and 15 to upper-bound remaining right-hand-side terms.Source: Proof of Lemma 5 · p. 13

Proof of Lemma 7

  • The cited passages state that the first component of (51) can be lower-bounded and that the expected value of (55) can be upper-bounded.Source: Proof of Lemma 7 · p. 13
  • The cited passage says its statement is according to (52) and similar to (21) and (26).Source: Proof of Lemma 7 · p. 13

Proof of Theorem 8

The Proof of Theorem 8 derives sufficient conditions using several corollaries, including Corollary 22. The Proof of Lemma 9 invokes Assumption 4.

Proof of Theorem 8

  • The proof obtains sufficient conditions using Corollaries 13, 14, 15, and 22, with Corollary 22 derived from Lemmas 11 and 12.Source: Proof of Theorem 8 · p. 13
  • Corollary 22 is stated under Assumption 3 for indices j and i in the specified ranges.Source: Proof of Theorem 8 · p. 14

Proof of Lemma 9

  • The Proof of Lemma 9 proceeds under Assumption 4 and refers to a bound involving t and vectors a.Source: Proof of Lemma 9 · p. 14

VII. PROOFS OF INTERMEDIATE RESULTS

The intermediate-results proofs use mean-centering and concentration bounds. The proofs of Lemmas 16 and 17 state probability bounds involving η defined in (73).

Proof of Lemma 16

Loading 1609.04789v3…