Robust Principal Component Analysis (low-rank plus sparse) L1-393
Unclaimed Principle — open for contribution
This Principle is declared in the catalog but has no reference solver, no pinned dataset, and is not registered on-chain. There is no reward pool. Submitting a cert against this Principle today will record the cert for reproducibility but pay zero PWM.
To claim it as a Bounty #7 contribution: open a PR adding (1) a reference solver, (2) ≥1 dataset pinned to IPFS, (3) updates to the L3 manifest with dataset CIDs. After verifier-agent triple-review, the founders' 3-of-5 multisig signs PWMRegistry.register() and the Principle becomes mineable.
Forward model E
Observed matrix M is a sum of a low-rank component L* and a sparse outlier component S*; task is to exactly recover L* and S* under mutual-incoherence assumption via principal component pursuit (PCP).
L-DAG
Well-posedness W
- Existence:
- true
- Uniqueness:
- when rank r <= C * min(m,n) / (mu_0 * log^2(max(m,n))) and s < C * m*n (Candes-Li-Ma-Wright 2011)
- Stability:
- conditional
- κ:
- 1000
Identifiable under rank-sparsity incoherence: low-rank component must be incoherent w.r.t. standard basis; sparse component must be spread among entries. PCP (nuclear+L1) solves exactly under mild conditions.
Solvability C
- Solver class:
- Inexact ALM (IALM), ADMM-based PCP, GoDec, accelerated alt-min (AltProj), learned (deep-RPCA, Corenet)
- Convergence rate q:
- 1.5
- Complexity:
- IALM: O(m*n*r*k) with k iterations; AltProj: O(m*n*r) per iteration