Sparse Signal Recovery (analysis / synthesis sparsity) L1-391
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 signal x admits sparse representation alpha in some dictionary D such that x = D*alpha (synthesis model) or Omega*x is sparse (analysis model). Observations y = A*x + n are measured with a linear operator A. The task is to recover x via sparsity-constrained optimization.
L-DAG
Well-posedness W
- Existence:
- true
- Uniqueness:
- when ||alpha||_0 < 1/2 * (1 + 1/mu(AD))
- Stability:
- conditional
- κ:
- 2000
Unique sparsity under mutual-coherence or RIP bounds; relaxed L0->L1 equivalence under Donoho-Elad theorem. Mismatch: dictionary drift, non-exact sparsity, off-grid sparsity (basis mismatch).
Solvability C
- Solver class:
- OMP, MP, CoSaMP, BPDN/LASSO, FISTA, ISTA, HTP, IRLS, learned (LISTA, ALISTA)
- Convergence rate q:
- 2
- Complexity:
- OMP: O(k*M*N); FISTA: O(N*M) per iter with O(1/k^2) convergence