Matrix Completion (low-rank recovery from partial entries) L1-392
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
A low-rank matrix M* in R^{m x n} of rank r << min(m,n) has only a subset P_Omega(M*) of entries observed. Recover M* from observed entries under low-rank assumption.
L-DAG
Well-posedness W
- Existence:
- true
- Uniqueness:
- when p >= C * mu_0^2 * r * (m+n) * log^2(m+n) / (m*n) (Candes-Tao 2010)
- Stability:
- conditional
- κ:
- 500
Unique recovery via nuclear-norm minimization under incoherence assumption. Fails when coherence is high (spiky matrices) or observation ratio is below sample-complexity threshold.
Solvability C
- Solver class:
- SVT (singular value thresholding), nuclear-norm SDP, alt-min (PowerFactorization), OptSpace, learned (Neural CF, Matrix-Factorization NN)
- Convergence rate q:
- 1.5
- Complexity:
- SVT: O(m*n*r) per iteration; alt-min: O(|Omega| * r) per iteration; SDP: O(m^6) (not scalable)