Recently, it was discovered that for a given function class $\mathbf{F}$ the error of best linear recovery in the square norm can be bounded above by the Kolmogorov width of $\mathbf{F}$ in the uniform norm. That analysis is based on deep results in discretization of the square norm of functions from finite dimensional subspaces. In this paper we show how very recent results on universal discretization of the square norm of functions from a collection of finite dimensional subspaces lead to an inequality between optimal sparse recovery in the square norm and best sparse approximations in the uniform norm with respect to appropriate dictionaries.
翻译:最近,人们发现,对于某一函数类 $\ mathbf{F} 美元, 平方规范中最佳线性恢复的错误可以被统一规范中的Kolmogorov宽度($\mathbf{F}$) 所约束。 该分析基于从有限维次空间分离函数的正方规范的深刻结果。 本文显示了从有限维次空间集合中普遍分解函数正方规范的近期结果如何导致平方规范中最佳零散恢复与在适当字典中统一规范中最稀少近似之间的不平等。