Constructive subsampling of finite frames with applications in optimal function recovery (Q6038824)

The authors deal with the question of how to choose a well-conditioned subframe out of a given frame. Namely, they present new constructive methods, random and deterministic, for the efficient subsampling of finite frames in \(\mathbb{C}^m\), i.e., extracting a similarly conditioned reweighted subframe consisting of merely \(O(m \log m)\) elements. Further, utilizing a deterministic subsampling method based on principles developed by Batson, Spielman, and Srivastava to control the spectrum of sums of Hermitian rank-1 matrices, they reduce the number of elements to \(O(m)\) (with a constant close to one). By controlling the weights via a preconditioning step, they, in addition, preserve the lower frame bound in the unweighted case. This permits the derivation of new quasi-optimal unweighted (left) Marcinkiewicz-Zygmund inequalities for \(L_2 (D, ν)\) with constructible node sets of size \(O(m)\) for \(m\)-dimensional subspaces of bounded functions. Those are applied for (plain) least-squares sampling reconstruction of functions, where the authors obtain new quasi-optimal results avoiding the Kadison-Singer theorem. Several numerical experiments indicate the applicability of the results.