Matrix and tensor rigidity and L_p-approximation
share
In this note we make two observations. First: the low-rank approximation of Walsh-Hadamard matrices (that disproves ridigity) via Alman and Williams provides good ℓ_p-approximation for p<2. It follows that the first N functions of Walsh-Paley system can be approximated with an error N^-δ by a linear space of dimension N^1-δ: d_N^1-δ({w_1,…,w_N}, L_p[0,1]) ≤ N^-δ, p∈[1,2), δ=δ(p)>0. We do not know if this is possible for the trigonometric system. Second, we notice 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. That implies lower bounds for Θ_m – the error of m-term approximation of multivariate functions by sums of tensor products u^1(x_1)⋯ u^d(x_d). In particular, for the set of trigonometric polynomials with spectrum in ∏_j=1^d[-n_j,n_j] and of norm t_∞≤ 1 we have Θ_m(𝒯(n_1,…,n_d)_∞,L_1[-π,π]^d) ≥ c_1(d)>0, m≤ c_2(d)∏ n_j/max{n_j}.
READ FULL TEXT