Conjectured asymptotic formula for the coherence of random sparse vectors
Fix and . Let be a random -sparse vector whose nonzero entries, on an arbitrary support , are independent and identically distributed Gaussian random variables with distribution . Let denote the coherence quantity defined in the paper. Asymptotic coherence conjecture.
where for some constant , and . The conjecture proposes a sparsity-dependent behavior that is not captured by the preceding logarithmic upper bound; it is motivated by simulations showing approximately linear growth of . The authors state that they are unable to prove it, while reporting close agreement between the proposed formula and empirical data.
References
- Borhan M. Sanandaji, Tyrone L. Vincent and Michael B. Wakin, “Concentration of Measure Inequalities for Toeplitz Matrices with Applications”, arXiv:1112.1968 (2012).
Progress summary
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.