Low-dimensional approximation of uniformly bounded orthonormal systems

Abstract

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/p}{N}^{1/2}\}$, $n\le N/2$. In the regime $n\asymp N$ this provides the lower bound $N^{-{\alpha }_p}$ with a sharp exponent ${\alpha }_p:=1/p-1/2$. Besides that, it follows that a good approximation of such ONS requires the dimension $n\gtrsim N^{p/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 ${\ell }_1$-error at most $N^{1/2+\eta }$; the exponent $1/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 \Lambda =K\cap {\mathbb{Z}}^d$, $K$ is symmetric convex, with dimension $|\Lambda {|}^{1-a}$ and an optimal error $|\Lambda {|}^{-{\alpha }_p+\eta }$; bounds for widths of weighted Wiener classes.