Random square DFT submatrix norm conjecture

From papers

Let nn be a positive integer, let F\mathbf{F} be the normalized n×nn\times n DFT matrix, and let \mathsfslPδ\mathsfsl{P}_\delta and \mathsfslPδ\mathsfsl{P}_\delta' denote the coordinate projections selecting random subsets of rows and columns of equal density δ\delta. Quartercircle Law. A random square submatrix of the n×nn\times n DFT satisfies

E\mathsfslPδF\mathsfslPδ2δ(1δ).\operatorname{\mathbb{E}}\left\Vert\mathsfsl{P}_\delta\mathbf{F}\mathsfsl{P}_\delta'\right\Vert\leq 2\sqrt{\delta(1-\delta)}.

The inequality becomes an equality as nn\to\infty. This conjecture concerns the limiting behavior of the expected norm when the dimension grows while the proportion of selected rows and columns remains fixed; the source presents it as a direction for further research, and no resolution is given.

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

Joel A. Tropp, “On the linear independence of spikes and sines”, arXiv:0709.0517 (2008).

Solutions 0

No solutions have been posted yet.