2020/10/28 by Malykhin, Yuri
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA)
paper · doi:10.48550/arxiv.2010.14801
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 ℓ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 n1-δ: dn1-δ(\w1,…,wn\, Lp[0,1]) ≤ n-δ, p∈[1,2), δ=δ(p)gt;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 ℓ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 u1(x1)⋯ ud(xd). In particular, for the set of trigonometric polynomials with spectrum in ∏j=1d[-nj,nj] and of norm ‖t‖_∞≤ 1 we have Θm(\mathcal T(n1,…,nd)_∞,L1[-π,π]d) ≥ c1(d)gt;0, m≤ c2(d)\frac∏ njmax\nj\. Sharp bounds follow for classes of dominated mixed smoothness: Θm(W(r,r,…,r)p,Lq[0,1]d)\asymp m-(rd)/(d-1), \mbox 2≤ p≤∞, 1≤ q≤ 2.