Robust nullspace property conjecture for sparse Bernoulli matrices

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

mmax{C1slogens,C2lognp},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.

Sources & referencesView supporting material

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.