Compressed Sensing (random-projection linear inverse) L1-386
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 sparse (or compressible in some basis Psi) signal x is measured via a sub-sampling sensing matrix A in R^{M x N} with M << N; the RIP condition on A allows exact recovery of k-sparse x with overwhelming probability when M = O(k log(N/k)).
L-DAG
Well-posedness W
- Existence:
- true
- Uniqueness:
- with RIP(2k, delta < sqrt(2) - 1)
- Stability:
- conditional
- κ:
- 2000
Well-posed under RIP (Candes-Tao 2006); kappa = (1+delta_2k)/(1-delta_2k). Failure when measurement_ratio < 2*k/N * log(N/k). Mismatch parameters: sparsity_overestimation, non-exact-sparsity (compressible).
Solvability C
- Solver class:
- L1-min (LASSO, BP, ISTA/FISTA), greedy (OMP, CoSaMP, SP), AMP, learned (LDAMP, LISTA, ISTA-Net+)
- Convergence rate q:
- 2
- Complexity:
- OMP: O(M*N*k); LASSO/FISTA: O(M*N*iter); AMP: O(M*N*iter) with fastest convergence