Conformalized Robust Principal Component Analysis

1. Problem Statement

Robust Principal Component Analysis (RPCA) aims to decompose an observed data matrix $Y$ into a low-rank component $X^*$ (capturing latent structure) and a sparse component $S^*$ (capturing outliers or gross corruptions), often in the presence of missing entries and random noise.

• The Gap: While numerous algorithms exist for accurate point estimation of $X^*$ and $S^*$, they lack rigorous methods for uncertainty quantification. Existing approaches often rely on strict parametric assumptions (e.g., Gaussian noise, specific incoherence conditions) that are frequently violated in real-world data.
• The Goal: The authors propose a framework to construct entrywise confidence intervals for the recovered low-rank entries that are:
  • Distribution-free: Valid under arbitrary noise distributions and model misspecification.
  • Robust: Effective even with sparse, large-magnitude outliers and heterogeneous missingness.
  • Finite-sample: Providing guaranteed coverage rates without relying on asymptotic approximations.

2. Methodology: CP-RPCA Framework

The proposed Conformalized RPCA (CP-RPCA) integrates Conformal Prediction (CP) with RPCA estimators. It operates under a "low-rank plus sparse" decomposition model where randomness arises from the observation process and the location of corruptions, rather than the noise distribution itself.

Core Components

1. Two-Stage Procedure (Split CP):

   • Stage 1 (Training & Trimming): The observed data is split into a training set and a calibration set. An RPCA algorithm (e.g., Fast-RPCA) estimates the low-rank matrix $\hat{X}$ and identifies a set of potentially corrupted indices $\hat{\Omega}^*_{obs}$. The calibration set is then "trimmed" by removing these suspected outliers to create a clean set $\Omega'_{cal}$.
   • Stage 2 (Calibration): Standardized residual scores are computed on the trimmed calibration set. A data-driven threshold $\hat{q}$ is determined via weighted empirical quantiles to ensure the target coverage level ($1-\alpha$).

2. Handling Heterogeneity (Weighted Conformal Prediction):

   • The method addresses heterogeneous missingness (where observation probabilities $p_{ij}$ vary) and covariate shift.
   • It employs weighted exchangeability. Instead of assuming uniform sampling, it calculates weights based on the odds ratios of observation probabilities ($h_{ij} = (1-p_{ij})/p_{ij}$).
   • A "one-shot" weighting strategy is used to construct a unified upper bound for the threshold, making the method computationally scalable while maintaining theoretical validity.

3. Full Conformal Implementation:

   • An exact (but computationally heavier) version is also proposed (Algorithm 2) which avoids data splitting, offering slightly tighter finite-sample guarantees by re-evaluating the model for every candidate value of a missing entry.

4. Uncertainty Scale:

   • The confidence intervals take the form $\hat{C}_{ij} = \hat{X}_{ij} \pm \hat{q} \cdot \hat{\sigma}_{ij}$.
   • The uncertainty scale $\hat{\sigma}_{ij}$ combines model uncertainty (estimated via Bootstrap) and noise variance estimated from the uncontaminated training data.

3. Key Contributions

• Distribution-Free Inference for RPCA: The first framework to provide finite-sample, distribution-free confidence intervals for robust matrix recovery, independent of the specific underlying RPCA solver used.
• Two-Stage Robustness: Unlike previous conformal matrix completion methods, CP-RPCA explicitly accounts for sparse outliers by trimming the calibration set, preventing outliers from distorting the uncertainty quantification.
• Theoretical Guarantees: The authors establish non-asymptotic lower and upper bounds on the coverage probability. They prove that the average coverage satisfies:
  $$\mathbb{E}[\text{AvgCov}] \geq 1 - \alpha - \mathbb{E}[\Delta] - \mathbb{E}[\xi]$$
  where $\Delta$ represents error from estimating observation probabilities and $\xi$ represents error from imperfect outlier identification.
• Practical Utility: Demonstrated application in identifying high-uncertainty regions in face recognition and video background modeling, offering interpretability beyond simple point estimates.

4. Experimental Results

The paper validates CP-RPCA through extensive simulations and real-world applications:

• Simulation Studies:

  • Robustness: CP-RPCA achieves coverage rates close to the nominal level (e.g., 90%) across various noise distributions (Gaussian, heavy-tailed $t$-distribution), missingness mechanisms (uniform, logistic, rank-1), and rank misspecifications.
  • Comparison: Compared to a Bootstrap-based baseline, CP-RPCA produces significantly shorter (tighter) intervals while maintaining valid coverage. The Bootstrap method suffered from over-coverage due to inflated variance estimates on unobserved entries.
  • Adversarial Noise: The method remains robust even under adversarial heterogeneous noise where high variance is concentrated on rarely observed entries.

• Real-Data Applications:

  • Face Recognition (YaleB Dataset): CP-RPCA successfully separated facial features from illumination artifacts. The confidence intervals were wider in regions with high variability (e.g., eyes, lips), effectively flagging areas where the low-rank model is less reliable.
  • Video Background Modeling (CDnet Dataset): The method separated static backgrounds from moving foreground objects. The constructed intervals provided reliable coverage for the background pixels, even in the presence of structured foreground motion that violates ideal RPCA assumptions.

5. Significance and Impact

• Reliability in High-Stakes Applications: By providing statistical coverage guarantees, CP-RPCA allows practitioners to assess the reliability of recovered data in critical fields like bioinformatics, surveillance, and finance, where point estimates alone are insufficient.
• Model Agnosticism: The framework decouples uncertainty quantification from the specific optimization algorithm used for RPCA, making it compatible with both convex (e.g., ALM) and non-convex (e.g., Fast-RPCA) solvers.
• Future Directions: The paper opens avenues for extending conformal inference to other structured matrix problems (e.g., 1-bit matrix completion, online matrix completion) and exploring conditional coverage guarantees.

In summary, CP-RPCA bridges the gap between robust matrix recovery and statistical inference, offering a scalable, theoretically grounded tool for uncertainty-aware analysis of corrupted and incomplete data.