Low-dimensional approximation of uniformly bounded orthonormal systems

Abstract

We prove that if $f_1,\ldots,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\langle \lambda,x\rangle)$, $\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.