I have encountered a need for fast computation of a transformation $Ax$ where $A\in \mathbb{C}^{K\times N},\ K\sim 10^7,\ N\sim 10^3$ is designed, and $x\in \mathbb{C}^N$ has iid $\mathcal{CN}(0,1)$ components.

$A$'s design, in current strict analyses, demands $A$'s rows to be independent and identically distributed as $\mathcal{CN}(0,I_{N\times N})$. This demand can be relaxed considerably and I suspect the real requirement is weak closeness of the empirical distribution of $A$'s rows to the proper distribution.

What sorts of structures can be imposed on $A$ such that its rows are quantitatively empirically similar to Gaussian for large $K,N,$ while admitting fast multiplication structure?