Recovering the Best Polynomial Approximation of High-dimensional Parameterized Equations
Tuesday, February 23, 2016 - 2:50pm - 3:35pm
In this talk, we present a new generalized methodology for constructing and analyzing best s-term polynomial approximations, applicable to a wide class of parameterized PDEs with both deterministic and stochastic inputs. Such methods construct a quasi-optimal multi-index set that corresponds to the best s-terms, based on sharp estimates of the polynomial coefficients. Our approach for analyzing the asymptotic truncation error avoids the use of the standard Stechkin inequality, but is instead based on an extension of the underlying multi-index set into a continuous domain, and then an approximation of the cardinality (number of integer multi-indices) by its Lebesgue measure. We consider several cases of d-dimensional affine and non-affine input data, and our proofs reveal sharp asymptotic error estimates in which we achieve sub-exponential convergence rates with respect to the total number of degrees of freedom. In addition, we are also interested in high-dimensional solutions that are characterized by a rapidly decaying polynomial expansion, whose most important terms are captured by a lower (or downward closed) set. By exploiting this fact, we also developed innovative compressed sensing techniques which impose the lower set structure, leading to a provably reduced sample complexity. Using these approaches, the best s-term recovery is established through an improved bound for restricted isometry property for general bounded orthonormal systems. Computational evidence complements our theory and shows the advantage of our generalized methodologies compared to existing approaches and current published results.