Sparse approximation of multivariate functions from small datasets via weighted orthogonal matching pursuit
For researchers in sparse approximation and function recovery, this work offers a computationally efficient alternative to weighted ℓ1 minimization, though the improvement is incremental.
The paper extends orthogonal matching pursuit to weighted sparsity for sparse approximation of multivariate functions from small datasets, achieving accuracy comparable to weighted ℓ1 minimization with improved computational efficiency for small sparsity levels.
We show the potential of greedy recovery strategies for the sparse approximation of multivariate functions from a small dataset of pointwise evaluations by considering an extension of the orthogonal matching pursuit to the setting of weighted sparsity. The proposed recovery strategy is based on a formal derivation of the greedy index selection rule. Numerical experiments show that the proposed weighted orthogonal matching pursuit algorithm is able to reach accuracy levels similar to those of weighted $\ell^1$ minimization programs while considerably improving the computational efficiency for small values of the sparsity level.