Conjectured asymptotic formula for the coherence of random sparse vectors

From papers

Fix NN and MM. Let aRN\boldsymbol{a} \in \mathbb{R}^N be a random KK-sparse vector whose KK nonzero entries, on an arbitrary support SS, are independent and identically distributed Gaussian random variables with distribution N(0,1K)\mathcal{N}(0,\frac{1}{K}). Let ρc(a)\rho_c(\boldsymbol{a}) denote the coherence quantity defined in the paper. Asymptotic coherence conjecture.

E[ρc(a)]Kc1K+c2,{\bf E}\left[\rho_c\left(\boldsymbol{a}\right)\right] \sim \frac{K}{c_1K+c_2},

where c1=1clogLc_1=\frac{1}{c\log L} for some constant cc, and c2=1c1c_2=1-c_1. 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 K/ρˉc(a)K/{\bar{\rho}_c(\boldsymbol{a})}. The authors state that they are unable to prove it, while reporting close agreement between the proposed formula and empirical data.

Progress summary

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

Sources & referencesView supporting material

Primary source

Borhan M. Sanandaji, Tyrone L. Vincent and Michael B. Wakin, “Concentration of Measure Inequalities for Toeplitz Matrices with Applications”, arXiv:1112.1968 (2012).

Solutions 0

No solutions have been posted yet.