math.FA cs.CC
Matrix and tensor rigidity and L p approximation. 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 delta by a linear space of dimension n 1 delta d n 1 delta ( w 1, ldots,w n , L p 0,1 ) le n delta , quad p in 1,2), delta delta(p) 0. We do not know if this is possible for the trigonometric system. We show that the algebraic method of Alon Frankl R "odl 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 Theta 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 Theta m( mathcal T(n 1, ldots,n d) infty,L 1 pi, pi 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 Theta 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.