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

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

原文链接

原文求助

摘要

En 中文

我们将已知稀疏恢复技术与Square Root Lasso、正交匹配追踪和压缩采样匹配追踪等研究充分的解码器的误差界相结合。这使得我们能够证明，仅给定一个搜索空间V_J和稀疏度参数n，函数恢复的L₂-近似误差的衰减不劣于最佳n项误差加上相对于搜索空间的截断误差。这些解码器所需的样本数量在我们的设置中为O(n log² n log dim(V_J))，并且我们再次使用压缩感知技术来建立关于实例最优误差保证的样本复杂度下界，以证实log dim(V_J)因子确实是必要的。最后，我们进行了多项大规模数值实验，这些实验支持了我们关于误差界及其接近最优性的理论观察，并比较了解码器的实际能力和局限性。

Keyword:

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

摘要

期刊

机构

引用论文