Robust nullspace property conjecture for sparse Bernoulli matrices

About 5 years old · traced to

Let A∈{0,1}m×nA\in\{0,1\}^{m\times n} be a matrix whose entries are independent and identically distributed Bernoulli pp random variables. The robust nullspace property conjecture. There exist constants C1,C2>0C_1,C_2>0 such that, if

m≥max⁡{C1slog⁡ens,C2log⁡np},m\geq\max\left\{C_1s\log\frac{en}{s},C_2\frac{\log n}{p}\right\},

then AA satisfies the ℓ1\ell_1 robust nullspace property of order ss for some ρ<1\rho<1 and τ>0\tau>0. Moreover, any constant C2>1C_2>1 can be taken. This conjecture predicts the sharp measurement threshold and a phase transition for robust sparse recovery with sparse Bernoulli matrices; the supplied text does not give a resolution.

References

Primary source

Pedro Abdalla, “Robust Sparse Recovery with Sparse Bernoulli matrices via Expanders”, arXiv:2112.14148 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.