On the approximation of vector-valued functions by volume sampling

Abstract

Given a Hilbert space $\mathcal{H}$ and a finite measure space $\hat{I}\text{c◯}$, the approximation of a vector-valued function $f:\hat{I}\text{c◯}\to \mathcal{H}$ by a $k$-dimensional subspace $\mathcal{U}\subset \mathcal{H}$ plays an important role in dimension reduction techniques, such as reduced basis methods for solving parameter-dependent partial differential equations. For functions in the Lebesgue-Bochner space $L^2(\hat{I}\text{c◯};\mathcal{H})$, the best possible subspace approximation error $d_k^{(2)}$ is characterized by the singular values of $f$. However, for practical reasons, $\mathcal{U}$ is often restricted to be spanned by point samples of $f$. We show that this restriction only has a mild impact on the attainable error; there always exist $k$ samples such that the resulting error is not larger than $\sqrt{k+1}\cdot d_k^{(2)}$. Our work extends existing results by Binev at al. (SIAM J. Math. Anal., 43(3):1457-1472, 2011) on approximation in supremum norm and by Deshpande et al. (Theory Comput., 2:225-247, 2006) on column subset selection for matrices.