Robust Principal Component Analysis on Graphs

I. INTRODUCTION

• Classical PCA supports low-rank recovery and clustering, but its quadratic error term makes principal components vulnerable to outliers, harming both applications.Source: §I · p. 1
• Graph-based PCA assumes data embeddings lie on a smooth manifold and uses a graph Laplacian to encode sample similarities for improved clustering.Source: §I · p. 1
• The proposed convex model incorporates spectral graph regularization into Robust PCA to improve clustering and low-rank recovery, with experiments reporting robustness to occlusions and missing values versus 10 models.Source: §I · p. 1

II. MAIN IDEA & PROPOSED MODEL

• The model directly recovers L rather than explicitly learning U and Q, assuming L lies on a smooth manifold and penalizing sparse errors S and graph roughness.Parameters λ and γ control sparsity and graph smoothness, respectively; setting γ = 0 recovers Robust PCA.Source: §II · p. 2

III. RELATED WORKS: FACTORIZED PCA MODELS

• Earlier factorized PCA methods learn U and Q; GLPCA regularizes Q for clustering and also has a robust version addressing occlusions.Source: §III · p. 2
• MMF uses orthonormal U so graph regularization of Q is equivalent to regularizing L, while later ensemble graph and hypergraph extensions, also regularize L.Source: §III · p. 2
• Prior graph-regularized methods are often non-robust, while robust ones can be non-convex; graph and hypergraph ensembles can introduce local-minimum risks.The paper states that only standard Robust PCA and its proposed model are convex and have a unique global optimum with guaranteed convergence.Source: §III · pp. 2–3

IV. COMPARISON WITH RELATED WORKS

• The model is non-factorized: it learns the low-rank matrix L directly rather than separately learning principal directions U and components Q.Its objective targets exact low-rank recovery by representing the data matrix as the sum of low-rank L and sparse S.Source: §IV · p. 3
• The model regularizes L, not only Q, on the graph, allowing graph smoothness to affect the principal directions through L = UQ.The graph terms tr(QΦQ⊤) and tr(LΦL⊤) are equivalent only when U is assumed orthogonal, as in,,,, but not.Source: §IV · p. 3

A. Advantages over Factorized PCA Models

• Low-rank graph regularization is presented as improving low-rank recovery and class separation even with grossly corrupted data.The stated mechanism is that regularizing L also lets the principal directions U benefit from graph regularization.Source: A. Advantages over Factorized PCA Models · p. 3
• The optimization problem is strictly convex and has a unique global optimum obtainable with standard methods such as ADMM.Source: A. Advantages over Factorized PCA Models · p. 3
• Only γ must be selected: nuclear-norm relaxation automatically selects the rank based on λ and γ, and λ = 1/max(n, p) proposed in gives very good results.The paper suggests cross-validation for selecting γ.Source: A. Advantages over Factorized PCA Models · p. 3

V. OPTIMIZATION SOLUTION

• The paper uses ADMM to rewrite Problem (1) and derive iterative updates for L, S, and W.The updates use Lagrange multipliers; further solution, algorithm, convergence, and computational-complexity details are given in supplementary Sections A, B, and C.Source: §V · p. 3

VI. EXPERIMENTAL SETUP

• Experiments assess clustering and low-rank recovery on 8 benchmark, 3 video, and 2 artificial datasets, using 10 corruption types and comparisons with 10 state-of-the-art dimensionality-reduction models.The setup is designed to test the model’s robustness and generalization across corrupted and uncorrupted data.Source: §VI · p. 4

1) Datasets:

• The experiments use six image databases—CMU PIE, ORL, YALE, COIL20, MNIST, and USPS—plus the MFeat and BCI databases.The database selection spans varied properties, including pose changes, digit rotations, data type, and non-negativity.Source: 1) Datasets · p. 4

2) Comparison with 10 models:

• The comparisons include k-means on original data X and dimensionality-reduction models with and without graph regularization.The listed non-graph models are PCA, NMF, and RPCA; graph models include NCuts, LE, GLPCA, RGLPCA, MMF, GNMF, and the proposed low-rank graph model.Source: 2) Comparison with 10 models · p. 4

3) Corruptions in datasets:

• Image databases are tested without corruption, with all images corrupted, and with corruptions limited to 25% of images.Corruptions are block occlusions or missing pixels, ranging from 10% to 40%; missing pixels are simulated by uniformly randomly placing zeros.Source: 3) Corruptions in datasets · p. 4
• Non-image databases are tested with full and sample-specific missing values, but not block occlusions because those would be unrealistic for such data.The sample-specific setting applies missing values to 25% of images in the image-database experiments.Source: 3) Corruptions in datasets · p. 4
• Preprocessing follows corruption introduction, with most listed models standardized to zero mean and unit standard deviation along features.MMF additionally normalizes samples to unit norm; NMF and GNMF instead normalize samples to unit norm on non-negative datasets.Source: 3) Corruptions in datasets · p. 4

4) Clustering Metric:

• Clustering error is the minimum across 10 k-means runs with k equal to the number of classes, applied to principal components.For RPCA and the proposed model, principal components Q are obtained during the nuclear proximal update in each iteration.Source: 4) Clustering Metric · p. 4

B. Setup for Low-Rank Recovery

• Because clustering benchmarks lack low-rank ground truth, recovery is evaluated quantitatively on corrupted artificial data and visually on occluded CMU PIE images and static backgrounds from three videos.The visualizations cover recovered low-rank representations.Source: B. Setup for Low-Rank Recovery · p. 5

C. Normalized Graph Laplacian

• The graph uses pairwise Euclidean distances between vectorized samples, with the intersection mask identifying features uncorrupted in both samples.For block occlusions, only observed pixels are considered.Source: C. Normalized Graph Laplacian · p. 5
• For random missing values, the images are cleaned with Total Variation denoising before pairwise distances are calculated.Source: C. Normalized Graph Laplacian · p. 5
• The normalized graph Laplacian is computed as Φ = I − D^-1/2 A D^-1/2, where D is the degree matrix.Source: C. Normalized Graph Laplacian · p. 5
• Across the experiments and datasets, the authors use Euclidean distance and σ2 = 0.05, while noting that other data may require different metrics or σ2 values.Source: C. Normalized Graph Laplacian · p. 5
• The paper provides a detailed graph-construction example using corrupted and uncorrupted images in supplementary Fig. 12.Source: C. Normalized Graph Laplacian · p. 5

VII. CLUSTERING IN LOW DIMENSIONAL SPACE

• Across CMU PIE, ORL, YALE, and COIL20 clustering experiments with block occlusions and random missing values, Robust PCA on Graphs outperforms ten compared models in most cases.The comparisons include full and partial corruptions.Source: §VII · p. 5, Figure 2 · p. 6

A. Is the Graph Useful?

• On CMU PIE without pose variation, the model reaches 0% clustering error without corruption and lowest error as occlusions and missing pixels increase, outperforming non-graph k-means, PCA, NMF, and RPCA.Its principal components are also described as better separated than those of the other models.Source: A. Is the Graph Useful? · p. 5
• On pose-varying COIL20, the model outperforms RPCA and other non-graph models, showing that even a simple graph enhances robustness to gross corruptions and pose changes.Source: A. Is the Graph Useful? · p. 5

B. Low-Rank or Principal Components Graph?

• Compared with models using a principal-components graph, the low-rank graph performs better even on pose-changing datasets; graph regularization also makes principal directions robust to corruptions, improving low-dimensional clustering.This benefit holds even when the graph is constructed from corrupted data.Source: B. Low-Rank or Principal Components… · p. 7

C. Robustness to Graph Quality

• On YALE with 35% random missing pixels, the model outperforms others as corruption-mask information decreases; with no mask information, it matches RPCA and beats principal-components-graph models.Source: C. Robustness to Graph Quality · p. 7, Figure 4 · p. 7

VIII. LOW-RANK RECOVERY — A. Low-Rank Recovery from Artificial Datasets

• Across every rank-error pair in two artificial datasets, the low-rank graph gives lower reconstruction error than RPCA.The experiments use matrices with rank d = 0.02n to 0.3n and 6% to 30% corrupted entries, under random-sign and coherent-sign schemes.Source: A. Low-Rank Recovery from Artificial… · p. 7

B. Low-Rank Recovery from Corrupted Faces

• On CMU PIE faces with block occlusions, the model separates occlusion better than the other models and its low-rank graph enhances recovery beyond inherited RPCA robustness.The images are corrupted by 10% block occlusions; the figure compares recovered images with whitened occluded and un-occluded images.Source: B. Low-Rank Recovery from Corrupted… · p. 7, Figure 6 · p. 8

C. Low-Rank Background Extraction from Videos

• For shopping-mall video, graph regularization recovers a cleaner static background than RPCA, which leaves a person and his shadow in the low-rank frame.The comparison is visual because low-rank ground truth is unavailable; the graph Laplacian is constructed between frames without prior information about sparse errors.Source: C. Low-Rank Background Extraction from… · p. 8, Figure 7 · p. 8

IX. PARAMETER SELECTION SCHEME FOR OUR MODEL

• Set λ approximately to 1/max(n, p), following Candes et al.; this rule works reasonably well for the clustering and low-rank recovery experiments.Here n is the number of samples and p is the dimension.Source: §IX · pp. 8–9
• After fixing λ, select graph penalty γ by cross-validation; the minimum clustering error occurs around the recommended λ across dataset sizes, class counts, and corruption levels.Detailed variation over the (λ, γ) grid is reported in supplementary Figs. 16 and 17.Source: §IX · p. 9

X. COMPARISON OF COMPUTATION TIMES

• For CMU PIE with 20% occlusions, RGLPCA has the highest runtime and the proposed model ranks second, with its cost dominated by an SVD at every iteration.The authors describe the clustering-error/runtime trade-off as worth observing and propose randomized SVD and parallel processing as future ways to reduce cost.Source: §X · p. 9, Figure 8 · p. 9

XI. CONCLUSION

• The proposed convex, minimally parameterized Robust PCA on Graphs targets exact low-rank recovery and enhanced clustering, with experiments reporting improvements over factorized PCA models.The conclusion also reports enhanced recovery on artificial data and in video background separation.Source: §XI · p. 9
• The conclusion reports that the method performs well even when its graph is constructed from corrupted data, indicating robustness to graph construction strategy.The conclusion also summarizes its clustering and low-rank recovery results across benchmark, artificial, and video data.Source: §XI · p. 9

A. Details of ADMM Solution

• The method uses ADMM, introducing a problem split, augmented Lagrangian, and iterative scheme with dual variables Z1 and Z2 and iteration index k.The split and scheme are described, but their equations are not included in the supplied passages.Source: A. Details of ADMM Solution · p. 11
• For a lower-semicontinuous convex function with nonempty domain, its proximity operator is the unique solution to the associated minimization problem.The appendix uses this definition to derive primal-variable updates.Source: A. Details of ADMM Solution · p. 11
• At iteration k + 1, L, S, and W are updated using proximity operators and the previous primal and dual iterates.The previous iterates are Lk, Sk, Wk, Z1k, and Z2k.Source: A. Details of ADMM Solution · p. 11
• The L update defines element-wise soft-thresholding and singular-value thresholding, with Dτ(A) obtained by thresholding the singular values in A’s singular value decomposition.The passage also defines the intermediate quantities H1k and H2k.Source: A. Details of ADMM Solution · p. 11
• The S update is derived using a procedure similar to the L update.The supplied passage does not include its update equation.Source: A. Details of ADMM Solution · p. 11
• For W, the appendix describes a smooth objective whose optimality condition yields a closed-form solution, and reports using projected conjugate gradient to update W.Both the closed-form characterization and the projected conjugate-gradient implementation are stated in the supplied passages.Source: A. Details of ADMM Solution · p. 11

B. Algorithm

• The procedure takes X, Φ, λ, and γ as inputs and randomly initializes L, W, and S.The iteration index starts at k = 0.Source: B. Algorithm · p. 12
• Each iteration updates L and S using equations 5 and 6, then W, Z1, Z2, and P using equations 7, 2, and 3.Source: B. Algorithm · p. 12
• The algorithm returns L and S after the while loop ends.Source: B. Algorithm · p. 12

• Algorithm 1 is a special case of alternating-directions methods,, within the augmented Lagrange multiplier family; convergence of these algorithms is well-studied,,.Source: C. Convergence Analysis &… · p. 12
• O(np^2 + p^3) is the nuclear norm proximal cost for n > p, versus O(np) per Conjugate Gradient iteration updating W; the proximal computation dominates each iteration.Source: C. Convergence Analysis &… · p. 12
• A small number of iterations has been reported to achieve good accuracy across a wide range of problems.Source: C. Convergence Analysis &… · p. 12
• Proposed cost reductions include partial or approximate SVD, randomized SVD [16], and exploiting parallel processing.Source: C. Convergence Analysis &… · p. 12

D. Properties of Various Models & Datasets

• Table II summarizes evaluation datasets and notes that NMF and GNMF are not evaluated on USPS, MFeat, or BCI because they require non-negative data.Source: Table II · p. 13
• Fig. 9 summarizes the properties of all models evaluated in the work.The supplied caption does not specify the individual properties shown in the Venn diagram.Source: Figure 9 · p. 13

E. Evaluation Scheme and Parameter Selection for all Models

• Models are evaluated across their parameter ranges, reporting minimum error; non-convex models and k-means are each run 10 times per relevant setting.Fig. 11 describes the evaluation and parameter-selection procedure, while Table III gives the parameter ranges used for the reported clustering results.Source: Figure 11 · p. 14, Table III · p. 15

F. Adjacency Matrix Construction from Corrupted & Uncorrupted Data

• Adjacency construction accounts for corruption by extending detected block-occlusion masks across paired images or using inpainting for missing pixels.The caption gives Total Variation denoising as an example inpainting technique.Source: Figure 12 · p. 16

G. Clustering Results on all Databases

• Tables IV–VI compare clustering errors across image and non-image datasets under block occlusions or missing values, with dataset-specific exclusions.The captions identify the comparison scope and note that the best results are highlighted, but do not provide error values or identify a winning model.Source: Table IV · p. 17, Table V · p. 18, Table VI · p. 18
• Table IV compares clustering errors on ORL, CMU PIE, YALE, and COIL20 under block occlusions and random missing values.It compares our model with dimensionality-reduction baselines and reports numerical errors corresponding to Fig. 2 bar plots.Source: Table IV · p. 17
• Table V compares clustering errors on MNIST and USPS under block occlusions and random missing values.The caption states that the best results are highlighted but supplies no values in this passage.Source: Table V · p. 18
• Table VI compares PCA models and k-means on MFeat and BCI; it omits block-occlusion trials and excludes NMF and GNMF.The caption treats block occlusions in these non-image datasets as unrealistic and notes that the data include negative values, incompatible with NMF and GNMF.Source: Table VI · p. 18

H. A Comparison of the Principal Directions U Learned with Low-Rank and Principal Components Graph

• The low-rank graph produces a corruption-free first principal direction, while its occlusion-affected second direction has a much smaller singular value than the first; other models’ two directions are affected.The passage links this result to enhanced low-rank recovery and lower clustering error in low-dimensional space than principal-components graph regularization.Source: Figure 13 · p. 19

I. Additional Low-Rank Recovery Results on CMU PIE Dataset

• With 10% block occlusions, recovered low-rank images from GLPCA, RGLPCA, MMF, RPCA, and the proposed model resemble the unoccluded whitened images.The visual inspection highlights the best recovered representations with red boxes but does not identify them by model in the supplied caption.Source: Figure 14 · p. 20

J. Additional Results for Background Separation from Videos

• For video background separation, the proposed model shows less illumination change in the restaurant scene and a less visible moving person in the airport scene than Robust PCA; both perform equally in the mall scene.The comparison uses the specified Robust PCA and proposed-model settings, with γ = 10 for the proposed model.Source: Figure 15 · p. 21

2) Parameter Selection for Low-Rank Recovery:

• For CMU PIE clustering, choose λ in [1, 2]/√(n·p) and cross-validate over a coarse γ range; the minimum error occurs within that λ range across matrix sizes, occlusions, and class counts.A wide range of γ values also attains minimum clustering error there, and graph regularization broadens the range of λ values attaining minimum error compared with Robust PCA.Source: Figure 16 · p. 22, 2) Parameter Selection for Low-Rank… · p. 22
• For low-rank recovery, choose λ in [1, 2]/max(n,p) and cross-validate over a coarse range of γ; λ = 1/max(n,p) is always a good choice for datasets with a low fraction of errors.Source: Figure 17 · p. 23, 2) Parameter Selection for Low-Rank… · p. 23

L. Comparison of Computation Times

• RGLPCA takes the most computation time, followed by the proposed model, which takes longer to converge but attains the minimum clustering error; its time is dominated by per-iteration SVD.The comparison uses one run for convex models and the minimum-clustering-error run among 10 runs for non-convex models.Source: Table VII · p. 24