Consider a finite abelian group $G$ (I'm mostly interested in $\mathbb{Z}_2^n$).
For two subsets $A$ and $B$ of $G$, one can form a submatrix of the Fourier transform matrix on $G$ by keeping only the rows corresponding to $A$ and the columns corresponding to $B$.
Assuming $A$ and $B$ have some fixed cardinality, how small can the operator norm of the submatrix be? Can we find explicit large $A$ and $B$ such that the norm is small?
Any relevant pointer appreciated.
Let's normalise the Fourier matrix ${\mathcal F}$ to have entries of magnitude 1. Then the Fourier submatrix ${\mathcal F}_{A,B}$ corresponding to two subsets $A,B$ has Frobenius norm $(|A| |B|)^{1/2}$ and rank at most $\min(|A|, |B|)$, hence must have operator norm at least $(|A| |B|)^{1/2} / \min(|A|,|B|)^{1/2} = \max(|A|,|B|)^{1/2}$.
This bound is pretty much sharp. For instance, if $A$ is a subgroup of $G$, and $B$ is formed by selecting $k$ elements from each coset of the orthogonal complement $A^\perp$, then $|B| = k |A|$ and a routine application of Plancherel's theorem shows that ${\mathcal F}_{A,B}$ is equal to $|B|^{1/2}$ times an isometry, so the operator norm is exactly $\max(|A|,|B|)^{1/2}$. Even when $G$ has very few subgroups (e.g., $G$ is a cyclic group of prime order), one should be able to concoct similar examples (losing some constants) by using approximate groups in place of groups.
