Abdellah Chkifa

Abdellah Chkifa, Nick Dexter, Hoang Tran et al.

This work proposes and analyzes a compressed sensing approach to polynomial approximation of complex-valued functions in high dimensions. Of particular interest is the setting where the target function is smooth, characterized by a rapidly decaying orthonormal expansion, whose most important terms are captured by a lower (or downward closed) set. By exploiting this fact, we present an innovative weighted $\ell_1$ minimization procedure with a precise choice of weights, and a new iterative hard thresholding method, for imposing the downward closed preference. Theoretical results reveal that our computational approaches possess a provably reduced sample complexity compared to existing compressed sensing techniques presented in the literature. In addition, the recovery of the corresponding best approximation using these methods is established through an improved bound for the restricted isometry property. Our analysis represents an extension of the approach for Hadamard matrices in [5] to the general case of continuous bounded orthonormal systems, quantifies the dependence of sample complexity on the successful recovery probability, and provides an estimate on the number of measurements with explicit constants. Numerical examples are provided to support the theoretical results and demonstrate the computational efficiency of the novel weighted $\ell_1$ minimization strategy.

Abdellah Chkifa

In the papers [6, 7] we have established linear and quadratic bounds, in $k$, on the growth of the Lebesgue constants associated with the $k$-sections of Leja sequences on the unit disc $\mathcal{U}$ and $\Re$-Leja sequences obtained from the latter by projection into $[-1, 1]$. In this paper, we improve these bounds and derive sub-linear and sub-quadratic bounds. The main novelty is the introduction of a "quadratic" Lebesgue function for Leja sequences on $\mathcal{U}$ which exploits perfectly the binary structure of such sequences and can be sharply bounded. This yields new bounds on the Lebesgue constants of such sequences, that are almost of order $\sqrt{k}$ when $k$ has a sparse binary expansion. It also yields an improvement on the Lebesgue constants associated with $\Re$-Leja sequences.