Interpolation via weighted \(\ell_{1}\) minimization (Q905907)

In practice, one has often to interpolate functions which are smooth as well as sparse in some sense. In this excellent paper, the authors merge classical smoothness-based interpolation methods with modern sparsity constraints and nonlinear reconstruction methods. For a bounded domain \(D\), let \(\psi_j:\, D \to {\mathbb C}\) \((j \in \Lambda)\) be orthonormal functions with finite index set \(\Lambda\), \(|\Lambda| = N\). For given sampling points \(t_{\ell}\in D\) \((\ell = 1,\ldots,m)\) and \(f=\sum_{j\in \Lambda} x_j\,\psi_j\), let \(y = (f(t_{\ell}))_{\ell =1}^m\) and let \(A\) be the sampling matrix with the entries \(A_{\ell,j} = \psi_j(t_{\ell})\) \((\ell =1,\ldots,m;\,j\in \Lambda)\). For interpolation, the authors consider the function \(f^{\sharp} = \sum_{j\in \Lambda} x_j^{\sharp}\,\psi_j\), whose coefficient vector \(x^{\sharp}\) is the solution of the \textit{weighted} \(\ell_1\) \textit{minimization problem} \[ \min \|z\|_{\omega,1}\quad {\mathrm{subject to}}\quad \|Az - y\|_2 \leq \eta \] with the weighted \(\ell_1\) norm \(\|z\|_{\omega,1} = \sum_{j\in \Lambda} \omega_j\,|z_j|\) and convenient weights \(\omega_j \geq 1\). Using the new concepts of weighted null space property and weighted restricted isometry property of the sampling matrix \(A\), the authors prove general interpolation theorems. Corresponding error estimates of \(f -f^{\sharp}\) in \(L_{\infty}\) resp. \(L_2\) norm are given. In several examples and numerical tests, this theory is applied to spherical harmonic interpolation and tensorized polynomial interpolation (with Chebyshev resp. Legendre polynomials).