Legendre-symbol construction conjecture for optimal restricted isometry matrices
Statement
Fix . Let , , and be positive parameters, and let be the matrix defined entrywise using the Legendre symbol modulo a prime by
Legendre-symbol RIP conjecture. There exists a universal constant such that for every , there exist and such that, whenever
and is prime, the matrix satisfies the -restricted isometry property.
This conjecture would give the optimal measurement scaling , improving the paper's bound, which scales like . It is presented as a possible strengthening of the Legendre-symbol construction and remains open in the supplied text.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.