论文标题
矩阵和张量刚度以及$ L_P $ - APPROXIMATION
Matrix and tensor rigidity and $L_p$-approximation
论文作者
论文摘要
在本文中，我们将起源于复杂性理论的方法应用于一些近似问题。 我们注意到，Alman和Williams的构建反驳了Walsh-Hadamard矩阵的刚性，提供了$ P <2 $的良好$ \ ell_p $ -Approximation。因此，可以通过尺寸的线性空间$ n^{1-Δ} $：$ n^{1-Δ} $：$ n^{1- {1- a^{1-Δ}}}（\ n^{1-Δ}}（\ n^{1-Δ}}）（\ n^{w_1，w_1，w_1，w_1，w_n \ w_n \}，l_p [0，11） n^{ - δ}，\ quad p \ in [1,2），\;δ=δ（p）> 0。 $$我们不知道三角系统是否可以。 我们表明，alon-frankl-rödl的代数方法用于界定低静态矩阵的数量，用于张紧器的作品：几乎所有的信号张者都具有较大的信号量，并且不能$ \ ell_1 $ - appprox-appRox-approx-apptro-apptro-apptro-approximim-appto tensors均由低率量量。这意味着$θ_m$〜的下限 - $ m $ term term近似多变量函数的误差通过张量产品的总和$ u^1（x_1）\ cdots u^d（x_d）$。特别是，对于$ \ prod_ {j = 1}^d [-n_j，n_j] $和norm $ \ \ | t \ | _ \ | _ \ infty \ le 1 $，我们有$θ_m（\ nathcalcal） t（n_1，\ ldots，n_d）_ \ infty，l_1 [-π，π]^d）\ ge c_1（d）> 0，\ quad m \ le c_2（d）\ frac {\ frac {\ prod n_j} $$尖锐的界限是统治混合平滑度的类别：$$ θ_m（w^{（r，r，\ \ ldots，r）} _ p，l_q [0,1]^d）\ asymp m^{ - \ frac {rd} {d-1}}} {d-1}}，\ quad \ quad \ quad \ mbox 2 \ le p \ le p \ le p \ le p \ le \ le \ iffty，\; 1 \ le q \ le 2。$$
In this paper we apply methods originated in Complexity theory to some problems of Approximation. We notice that the construction of Alman and Williams that disproves the rigidity of Walsh-Hadamard matrices, provides good $\ell_p$-approximation for $p<2$. It follows that the first $n$ functions of Walsh system can be approximated with an error $n^{-δ}$ by a linear space of dimension $n^{1-δ}$: $$ d_{n^{1-δ}}(\{w_1,\ldots,w_n\}, L_p[0,1]) \le n^{-δ},\quad p\in[1,2),\;δ=δ(p)>0. $$ We do not know if this is possible for the trigonometric system. We show that the algebraic method of Alon--Frankl--Rödl for bounding the number of low-signum-rank matrices, works for tensors: almost all signum-tensors have large signum-rank and can't be $\ell_1$-approximated by low-rank tensors. This implies lower bounds for $Θ_m$~ -- the error of $m$-term approximation of multivariate functions by sums of tensor products $u^1(x_1)\cdots u^d(x_d)$. In particular, for the set of trigonometric polynomials with spectrum in $\prod_{j=1}^d[-n_j,n_j]$ and of norm $\|t\|_\infty\le 1$ we have $$ Θ_m(\mathcal T(n_1,\ldots,n_d)_\infty,L_1[-π,π]^d) \ge c_1(d)>0,\quad m\le c_2(d)\frac{\prod n_j}{\max\{n_j\}}. $$ Sharp bounds follow for classes of dominated mixed smoothness: $$ Θ_m(W^{(r,r,\ldots,r)}_p,L_q[0,1]^d)\asymp m^{-\frac{rd}{d-1}},\quad\mbox 2\le p\le\infty,\; 1\le q\le 2. $$
