High-dimensional sparse recovery from function samples – Decoders, guarantees and instance optimality

Moritz Moeller

doi:10.1016/j.acha.2026.101941

High-dimensional sparse recovery from function samples – Decoders, guarantees and instance optimality

2026-10-01

0

PRE

AI

DOI：10.1016/j.acha.2026.101941

Original

Original request for help

Save

Abstract

En 中文

We combine known sparse recovery techniques from compressed sensing with error bounds for the well-investigated decoders Square Root Lasso, Orthogonal Matching Pursuit, and Compressive Sampling Matching Pursuit. This enables us to show that, given only a search space V_J and a sparsity parameter n, the L₂-approximation error for function recovery decays no worse than a best n-term error plus the truncation error with respect to the search space. The number of samples required by these decoders is O ( n log2 n log dim ( V J ) ) in our setting, and we again use compressed sensing techniques to establish lower bounds on the sample complexity of instance-optimal error guarantees which substantiate that the log dim ( V J ) factor is indeed necessary. Finally, we conduct several large-scale numerical experiments which support our theoretical observations on the error bounds and their proximity to optimality, and which give a comparison of practical abilities and limitations of the decoders.

Keywords:

multivariate approximation

best n-term approximation

uniform norm

rate of convergence

sampling recovery

41A46

42A10

42B35

41A25

41A63

94A12

68Q25

High-dimensional sparse recovery from function samples – Decoders, guarantees and instance optimality

Abstract

Journal

Organization

Cited Papers