Random square DFT submatrix norm conjecture

About 19 years old · traced to

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 n→∞n\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.

References

Primary source

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

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.