Low-Rank Matrix Sensing (compressive matrix recovery) L1-028
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
Recover a low-rank matrix X in R^{n1 x n2} of rank r from m linear measurements y_k = <A_k, X> + n_k; measurement operators A_k are typically drawn from i.i.d. Gaussian/Bernoulli ensembles or structured (partial Fourier, matrix completion patterns). Specializes to matrix completion when A_k are canonical basis matrices e_{i_k} e_{j_k}^T (single-entry observation).
L-DAG
Well-posedness W
- Existence:
- true
- Uniqueness:
- true
- Stability:
- conditional
- κ:
- 6000
Recovery guaranteed w.h.p. when m >= C * r * (n1 + n2) and A satisfies matrix-RIP; nuclear-norm minimization is exact for noiseless case; stability bound ||X_hat - X||_F <= C * sigma * sqrt(m) / smallest_singular_value.
Solvability C
- Solver class:
- nuclear-norm minimization (SVT, FPC), Burer-Monteiro factorization (alternating GD, ProcGenRAM), Riemannian optimization on fixed-rank manifolds
- Convergence rate q:
- 2
- Complexity:
- O(m * n1 * n2) per iteration for dense; O(r * (n1+n2)) per iteration for factorized Burer-Monteiro