We propose two new algorithms to improve greedy sampling of high-dimensional functions. While the techniques have a substantial degree of generality, we frame the discussion in the context of methods for empirical interpolation and the development of reduced basis techniques for high-dimensional parametrized functions. The first algorithm, based on a saturation assumption of the error in the greedy algorithm, is shown to result in a significant reduction of the workload over the standard greedy...

Let id be the natural embedding of the Sobolev space $W_p^l\left(\Omega \right)$ in the Zygmund space $L_q{\left(logL\right)}_a\left(\Omega \right)$, where $\Omega ={(0,1)}^n$, 1 < p < ∞, l ∈ ℕ, 1/p = 1/q + l/n and a < 0, a ≠ -l/n. We consider the entropy numbers $e_k\left(id\right)$ of this embedding and show that $e_k\left(id\right)\asymp k^{-\eta }$, where η = min(-a,l/n). Extensions to more general spaces are given. The results are applied to give information about the behaviour of the eigenvalues of certain operators of elliptic type.