Low-dimensional approximation of uniformly bounded orthonormal systems

We prove that if $f_1,\dots ,f_N$ is an uniformly bounded orthonormal system, then for all $p\in [1,2)$ there is an estimate for its Kolmogorov widths: $d_n(\{f_1,\dots ,f_N\},L_p)\gtrsim \min \{1,n^{-1\mathrm{/}p}{N}^{1\mathrm{/}2}\}$, $n\le N\mathrm{/}2$. In the regime $n\asymp N$ this provides the lower bound $N^{-{\alpha }_p}$ with a sharp exponent ${\alpha }_p:=1\mathrm{/}p-1\mathrm{/}2$. Besides that, it follows that a good approximation of such ONS requires the dimension $n\gtrsim N^{p\mathrm{/}2}$. Our second result is an approximation theorem for Fourier matrices of finite abelian groups (this includes the usual DFT matrices). For every $\eta >0$ there is $a=a(\eta )>0$ such that any Fourier matrix $F$ of sufficiently large order has an approximation of rank $N^{1-a}$ with the row-wise ${\mathrm{\ell }}_1$-error at most $N^{1\mathrm{/}2+\eta }$; the exponent $1\mathrm{/}2$ is sharp. Consequences include the approximation of the same kind for circulant matrices; the approximation of the trigonometric functions $\exp (2\pi i⟨\lambda ,x⟩)$, $\lambda \in \mathrm{\Lambda }=K\cap {\mathbb{Z}}^d$, $K$ is symmetric convex, with dimension $\mathrm{\mid }\mathrm{\Lambda }{\mathrm{\mid }}^{1-a}$ and an optimal error $\mathrm{\mid }\mathrm{\Lambda }{\mathrm{\mid }}^{-{\alpha }_p+\eta }$; bounds for widths of weighted Wiener classes.