PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Robust PCA on Graphs

Nauman Shahid, Nathanael Perraudin, Vassilis Kalofolias, Gilles Puy, Pierre Vandergheynst

arXiv:1507.08173v2cs.CV

TL;DR

High-dimensional clustering methods can be computationally costly, non-convex, or susceptible to gross corruption. FRPCAG uses sample- and feature-graph smoothness for convex approximate low-rank recovery. The paper reports improved clustering performance and roughly 100-times-faster ordinary clustering than nuclear-norm-based methods, with bounded-error recovery for clusterable data.

  • Problem

    Existing dimensionality-reduction approaches can involve costly nuclear-norm minimization, non-convex matrix factorization, or sensitivity to gross data corruption.

    Source: B. PCA and Related Work · p. 2

  • Method

    FRPCAG performs convex approximate low-rank recovery by enforcing graph smoothness across both data samples and features.

    Source: C. Our Contributions · p. 3, §VIII · p. 15

  • Results

    FRPCAG tends to outperform several state-of-the-art exact low-rank recovery methods in clustering and is approximately 100 times faster than nuclear-norm-based methods in ordinary clustering.

    Source: §VIII · p. 16

  • Takeaways & Limitations

    For clusterable data with rank equal to the number of clusters, the analysis establishes approximate low-rank recovery with bounded error.

    Source: C. Our Contributions · p. 3

Abstract

from arXiv · show

Mining useful clusters from high dimensional data has received significant attention of the computer vision and pattern recognition community in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome the curse of dimensionality. However, often such methods are accompanied with three different problems: high computational complexity (usually associated with the nuclear norm minimization), non-convexity (for matrix factorization methods) and susceptibility to gross corruptions in the data. In this paper we propose a principal component analysis (PCA) based solution that overcomes these three issues and approximates a low-rank recovery method for high dimensional datasets. We target the low-rank recovery by enforcing two types of graph smoothness assumptions, one on the data samples and the other on the features by designing a convex optimization problem. The resulting algorithm is fast, efficient and scalable for huge datasets with O(nlog(n)) computational complexity in the number of data samples. It is also robust to gross corruptions in the dataset as well as to the model parameters. Clustering experiments on 7 benchmark datasets with different types of corruptions and background separation experiments on 3 video datasets show that our proposed model outperforms 10 state-of-the-art dimensionality reduction models. Our theoretical analysis proves that the proposed model is able to recover approximate low-rank representations with a bounded error for clusterable data.

I. INTRODUCTION

This introduction frames matrix factorization as a tool for finding structure in high-dimensional data and motivates graph priors as a way to use local manifold information. It presents FRPCAG as a convex, graph-based approach to approximate low-rank recovery for clustering, with theoretical guarantees under a clusterability condition.

I. INTRODUCTION

  • Graph-regularized PCA incorporates local sample proximity, which can enhance clustering quality in the low-dimensional space.The introduction describes the data manifold through a discrete graph and its normalized Laplacian.Source: §I · p. 2

A. Focus of this work

  • The paper focuses on PCA for clustering in a single linear subspace and calls clusterable data with rank equal to cluster count low-rank matrices on graphs.Its motivation contrasts a single PCA subspace with unions of subspaces and positive low-rank representations.Source: §I · p. 1, A. Focus of this work · p. 2

B. PCA and Related Work

  • GLPCA and MMF are non-convex and corruption-sensitive, while RPCAG uses an expensive nuclear-norm SVD at every iteration.The introduction also notes that GLPCA and MMF require the subspace rank to be specified upfront.Source: B. PCA and Related Work · p. 2

C. Our Contributions

  • FRPCAG uses sample- and feature-graph smoothness to approximate low-rank recovery, with bounded error for clusterable data whose cluster count equals the rank.The method is convex and uses only graph-smoothness assumptions for potentially corrupted data.Source: C. Our Contributions · pp. 2–3
  • The proposed method is convex and efficiently solvable with FISTA; graph construction costs O(n log n), and experiments report close approximation to nuclear-norm recovery even with gross corruption.The method uses sparse-matrix multiplications and elementwise soft-thresholding.Source: C. Our Contributions · p. 3

D. Connections and differences with the state-of-the-art

FRPCAG uses smoothness on sample and feature graphs to recover an approximate low-rank matrix, and replaces RPCAG’s nuclear-norm term with graph regularization. The paper contrasts this direct recovery objective with methods that smooth factors or labels, then describes a FISTA solution.

D. Connections and differences with the state-of-the-art

II. FAST ROBUST PCA ON GRAPHS (FRPCAG)

  • FRPCAG regularizes U using sample- and feature-graph Laplacians and an L1 residual term for sparse outliers, replacing RPCAG’s nuclear norm with a graph Tikhonov term.The two graph terms encode smoothness on U and provide an approximate low-rank representation without the expensive nuclear norm.Source: §II · pp. 3–4

A. Optimization Solution

  • FISTA solves the convex model by splitting it into a differentiable graph-regularization term and an L1 data-fit term, using elementwise soft-thresholding for the latter.The paper uses a step size based on an upper bound for the gradient’s Lipschitz constant.Source: A. Optimization Solution · p. 4

III. GRAPHS CONSTRUCTION

The method builds one graph over samples and another over features, using nearest-neighbor search and normalized Laplacians. It offers exact neighbor search for smaller datasets and FLANN for larger ones, trading some graph quality for speed.

III. GRAPHS CONSTRUCTION

  • The method constructs G1 between data samples (columns) and G2 between features (rows), using K-nearest neighbors and a normalized graph Laplacian.The graph weights are computed from connected-neighbor distances; the adjacency entries can be computed in parallel.Source: §III · p. 4
  • For small n and p, direct graph construction costs O(n^2) but can still finish in a few seconds on sufficiently small datasets.This strategy can be used even when the data are corrupted.Source: §III · p. 4
  • For large datasets, FLANN approximate nearest-neighbor search reduces graph-construction complexity to O(n log n), with slightly lower graph quality than exact search.The paper notes that FRPCAG still performs better than other state-of-the-art models on MNIST with lower-quality graphs.Source: §III · p. 5
  • The authors distinguish three graph-quality settings: both graphs good, only the feature graph noisy, or both graphs noisy.These settings correspond respectively to small n and p, small n with large p, and large n and p.Source: §III · p. 5

IV. OUR MOTIVATION: LOW-RANK MATRIX ON GRAPHS

The section motivates dual-graph regularization through the alignment between feature-graph Laplacian eigenvectors and covariance eigenvectors. USPS examples show this alignment for one digit and for the full dataset, supporting the use of low-frequency feature eigenvectors as a basis for approximate low-rank data.

IV. OUR MOTIVATION: LOW-RANK MATRIX ON GRAPHS

  • The motivation section presents low-rank matrices on graphs as a model for clusterable data that supports the paper’s theoretical analysis.The discussion introduces this concept after asking why two graphs are needed.Source: §IV · p. 5

A. The graph of features provides a basis for data

  • For USPS digit 3, sr(Γ3) = 0.97, and the diagonal energy is concentrated in the first few entries, indicating alignment between the leading covariance and feature-graph eigenvectors.The figure compares the 16 highest-eigenvalue covariance eigenvectors with the 16 smallest non-zero-eigenvalue Laplacian eigenvectors.Source: Figure 2 · p. 5, A. The graph of features provides a… · p. 5
  • The authors conclude that columns of a low-rank X lie approximately in the span of the feature graph’s lowest-frequency eigenvectors, with higher-frequency components much smaller for a suitable k2.They describe those eigenvectors as meaningful features for USPS and compare their role to principal directions in PCA.Source: A. The graph of features provides a… · pp. 5–6
  • For the full USPS dataset, sr(Γ) = 0.82, indicating alignment between the covariance and feature-graph eigenvectors across all digits.The figure shows the same comparison of covariance and Laplacian eigenvectors as for digit 3.Source: A. The graph of features provides a… · p. 5, Figure 3 · p. 6

B. The graph of samples provides embedding for data

The sample graph’s low-frequency eigenvectors provide an embedding that aligns low-rank representations with cluster structure. A matrix is defined as low-rank on the graphs when its rows and columns lie in the respective graphs’ low-frequency eigenspaces.

B. The graph of samples provides embedding for data

  • The sample-graph Laplacian term aligns the low-rank representation with its smallest-eigenvalue eigenvectors, allowing it to benefit from class structure and enhance clustering.It also represents the data through low-frequency sample-graph eigenvectors.Source: B. The graph of samples provides… · p. 6

C. Low-rank matrix on graphs

  • The proposed representation uses low-frequency eigenvectors from both the feature and sample graphs; higher graph frequencies are treated as noise.The eigenvectors Qk1 and Pk2 provide features for matrices in LR(Qk1, Pk2).Source: C. Low-rank matrix on graphs · p. 6
  • A matrix is (k1, k2)-low-rank on graphs L1 and L2 when each row lies in span(Qk1) and each column lies in span(Pk2).The set of such matrices is denoted LR(Qk1, Pk2).Source: C. Low-rank matrix on graphs · p. 6

D. Theoretical Analysis

The analysis studies the graph-regularized estimate under an assumption that the observed data are a graph-low-rank matrix plus corruption. It establishes approximate low-rank recovery for a broad class of convex losses, with clusterability reflected in graph eigengaps.

D. Theoretical Analysis

  • The analysis establishes approximate low-rank recovery for solutions of the graph-regularized objective under proper, positive, convex, lower semi-continuous losses.The objective combines data-fit loss with sample- and feature-graph Laplacian penalties.Source: D. Theoretical Analysis · p. 6
  • The recovery setup assumes X = X* + E, with X* low-rank on both graphs and E representing noise or corruptions.Source: D. Theoretical Analysis · p. 6
  • For K-nearest-neighbor graphs of clusterable data, the analysis expects a small eigengap ratio λk1/λk1+1, with the analogous condition for the feature graph.The theorem’s regularization choices depend on the eigenvalues immediately above the retained graph eigenspaces.Source: D. Theoretical Analysis · p. 7

E. Remarks on the theoretical analysis

The theoretical remarks link recovery quality to graph eigengaps and corruption fit, while the model’s described operations are singular-value penalization and estimation of clean singular vectors.

E. Remarks on the theoretical analysis

  • The recovery error bound improves with larger graph eigengaps, expected when rows and columns cluster, and with a loss metric that minimizes φ(E).The resulting estimate has rank approximately min{k1, k2}.Source: E. Remarks on the theoretical analysis · p. 7

V. WORKING OF FRPCAG

  • For clusterable data, FRPCAG penalizes higher singular values to clean data and determines clean left and right singular vectors.Source: §V · p. 7

A. FRPCAG is a singular value penalization method

FRPCAG’s graph regularization attenuates singular values according to the corresponding graph eigenvalues, while its singular vectors are encouraged to align with low-frequency graph eigenvectors.

A. FRPCAG is a singular value penalization method

  • The paper presents proximal operators for the two graph-regularization terms as an alternative computation, noting that this route is more computationally expensive than the gradient-based treatment.Source: A. FRPCAG is a singular value… · p. 7
  • Each singular value σxi of X is penalized by 1/(1 + γ1λi)(1 + γ2ωi); the solution also requires computing two inverses, which can be computationally intractable for big datasets.Source: A. FRPCAG is a singular value… · p. 8

B. Estimation of clean singular vectors

  • The graph regularization minimizes singular values and aligns large-component principal components and directions with low-frequency eigenvectors of the sample and feature graphs.The account identifies wi and vi as the principal components and principal directions of U, respectively.Source: B. Estimation of clean singular vectors · p. 8

C. Experimental Justification of working of FRPCAG

On 1,000 MNIST samples from digits 0 and 1, increasing both graph weights strengthens the low-rank and subspace structure while lowering clustering error. The model’s singular values closely approximate those of nuclear-norm methods across corruption levels.

C. Experimental Justification of working of FRPCAG

  • The MNIST experiment uses k-means on the recovered low-rank matrix and examines WWᵀ and singular-value-scaled alignment with both graph eigenvector sets.The sample comprises 1,000 examples from two digit classes.Source: C. Experimental Justification of… · p. 8
  • Increasing γ1 and γ2 from 1 to 30 penalizes singular values, aligns leading singular vectors with their graph eigenvectors, strengthens subspace structure, and lowers clustering error.The corresponding WWᵀ structure becomes more block diagonal.Source: C. Experimental Justification of… · p. 8, Figure 4 · p. 9
  • Across ORL experiments with no, 15%, and 25% block occlusions, FRPCAG’s low-rank singular values closely approximate those of RPCA and RPCAG.Model parameters were selected for minimum clustering error.Source: C. Experimental Justification of… · pp. 8, 10, Figure 5 · p. 10

VI. COMPUTATIONAL COMPLEXITY

The method constructs sample and feature graphs, applies FISTA, and optionally computes an economic SVD to obtain explicit projections. Its stated overall complexity combines graph construction, iterations, and final SVD, with scalability supported by approximate-neighbor construction and parallel computations.

A. Complexity of Graph Construction

  • For fixed K, FLANN graph construction costs O(pn log(n)) for sample graph G1 and O(np log(p)) for feature graph G2; experiments use K = 10.The broader expressions depend on K and the number of neighbors.Source: A. Complexity of Graph Construction · p. 10

1) FISTA:

  • FISTA costs O(Ipn) per convergence run, where I is the iteration count, p the data dimension, and n the number of samples.The per-iteration cost is linear in n.Source: 1) FISTA · p. 10

2) Final SVD:

  • Because FRPCAG preserves convexity by finding U without factorizing it, an economic SVD can afterward provide an explicit low-dimensional representation.For p ≪ n, it computes V from the p × p matrix UUᵀ, retains the c largest singular values, and obtains W from V, Σ, and U; its O(np²) cost does not change the algorithm’s asymptotic complexity.Source: 2) Final SVD · p. 10

C. Overall Complexity

  • Combining FISTA, both graph constructions, and final SVD gives overall complexity O(pn(log(n)+I+p+log(p))) when p ≪ n.The component costs are O(Ipn), O(pn log(n)), O(pn log(p)), and O(np²), respectively.Source: C. Overall Complexity · p. 10

D. Scalability

  • For large datasets, FLANN constructs approximate-neighbor graphs, while sparse-matrix gradient calculations and element-wise soft-thresholding can be parallelized.The graph construction also supports parallel computation of adjacency entries once nearest neighbors are found.Source: D. Scalability · p. 10

VII. RESULTS

  • Clustering is tested on seven datasets, with block occlusions and random missing pixels; video background separation is reported only qualitatively as proof of concept.The datasets include face, object, handwritten-digit image, and numeral-feature data; block occlusions are not used for the non-image MFeat dataset.Source: §VII · p. 11
  • Clustering error is evaluated using k-means, with minimum error over ten runs reported; the low-rank methods may cluster U directly or use its SVD-derived W.Parameters are selected on validation data; non-convex models are run ten times per parameter tuple, while convex models are run once.Source: §VII · p. 12

A. Clustering

FRPCAG(A), using good sample and feature graphs, performs better than competing matrix-factorization models in most tested cases, including corrupted data. On ORL, it also outperforms nuclear-norm models; video experiments show comparable background separation to RPCAG with substantially shorter convergence time.

1) Comparison with Matrix Factorization Models:

  • FRPCAG(A) performs better than the other matrix-factorization models in most cases, with and without corruption, and outperforms them in most MNIST cases despite noisy graphs.FRPCAG(B), with a noisy feature graph, performs reasonably well; FRPCAG(C), with two noisy graphs, performs worse than models using a good sample graph on five datasets.Source: 1) Comparison with Matrix… · p. 12, Figure 6 · p. 13

2) Comparison with Nuclear Norm based Models:

  • With 15% randomly missing MNIST pixels, FRPCAG’s principal components show digit separation comparable to or better than other state-of-the-art dimensionality-reduction models.The figure shows 1,000 samples of digits 0 and 1.Source: Figure 7 · p. 14
  • Across three videos, FRPCAG separates static backgrounds as well as RPCAG and converges in under 2 minutes, versus more than 45 minutes for RPCA and RPCAG.The videos show a restaurant counter, shopping-mall lobby, and airport lobby; moving people belong to the sparse component.Source: Figure 8 · p. 14
  • On the small ORL dataset, FRPCAG(A) outperforms RPCA and RPCAG even with large gross errors; FRPCAG(B) also beats RPCAG with a good graph.FRPCAG(C) with two noisy graphs is comparable to RPCAG with a noisy graph but remains better than RPCA.Source: 2) Comparison with Nuclear Norm based… · pp. 12, 15

B. Principal Components

The experiments examine cluster separation, graph-neighbor choice, video background recovery, and computational performance. The authors conclude that FRPCAG combines faster clustering with approximate low-rank recovery and robustness to gross corruptions.

B. Principal Components

  • On MNIST with 15% missing pixels, FRPCAG’s two-dimensional components separated digits 0 and 1 comparably to other state-of-the-art dimensionality reduction models.The experiment used 1,000 samples, with 500 examples of each digit.Source: B. Principal Components · p. 15

C. Effect of the number of nearest neighbors for graphs

  • On ORL, clustering errors were 17.5% at K = 5, 17% at K = 10, 23% at K = 25, and 31% at K = 40.The authors report lower error when K is approximately equal to or below the number of images per class, and use K = 10 across datasets.Source: C. Effect of the number of nearest… · p. 15

D. Static background separation from videos

  • On three videos, FRPCAG separated static backgrounds from moving people accurately and converged in under 2 minutes, versus over 45 minutes for RPCA and RPCAG.The examples used restaurant, shopping mall, and airport lobby footage.Source: D. Static background separation from… · p. 15

E. Computational Time

  • On the 1990 US census dataset with approximately 2.5 million samples and 68 features, FRPCAG converged in 65 minutes and 200 iterations on a single-core machine.The study did not compare its performance with other methods because ground truth was unavailable.Source: E. Computational Time · p. 15
  • For 25,000 MNIST samples, FRPCAG converged in under a minute, while RPCAG and RPCA did not converge within 4 hours.On MNIST, FRPCAG was 100 times faster than RPCAG; the timing experiments used a single-core 3.3 GHz machine.Source: E. Computational Time · p. 15, Table V · p. 16

VIII. CONCLUSION

  • In ordinary clustering, FRPCAG is approximately 100 times faster than nuclear norm-based methods, while its double-graph structure contributes to robustness against gross corruptions.Its recovered low-rank matrix also has singular values that closely approximate those from nuclear norm-based methods.Source: §VIII · p. 16

Related papers

Loading 1507.08173v2…