Greedy Approximation

PI：Vladimir Temlyakov，南卡罗来纳大学DMS-0200187摘要：非线性逼近寻求用简单函数逼近复杂函数的方法，这些方法依赖于被逼近的函数。近年来，一种特殊的非线性逼近，即贪婪逼近，引起了理论界和实用界的广泛关注。贪婪算法在图像压缩、信号处理、神经网络设计、非线性偏微分方程组的数值求解等领域有着广泛的应用。贪婪逼近理论现在正在兴起：一些基本的收敛结果已经建立，许多基本的问题仍然没有解决。本研究的目的是继续对贪婪逼近的研究。我们建议继续研究关于基的贪婪逼近，最近在这方面已经取得了实质性进展。我们建议重点研究贪婪算法在冗余系统(词典)方面的效率。冗余一方面在逼近速度方面为更高的效率提供了很大的希望，但另一方面也带来了非常重要的理论和实践问题。我们注意到，在理论问题和实际应用中都有充分的理由证明冗余系统的重要性。接近理论是数学的一个分支，研究用更简单的对象代替复杂对象的方法。这一想法在许多现实世界问题的应用中被证明是卓有成效的。这些应用包括信号处理、图像压缩、金融问题和许多其他应用。作为模型问题之一，考虑图像压缩。以电视屏幕上的图像(图片)为例。为什么我们要近似它呢？在许多情况下，我们无法传输(或存储在计算机内存中)一幅图像的全部信息，这可能是因为传输少量信息的成本很高，或者是因为通道容量有限。这正是应用近似理论可以取得丰硕成果的地方。显然，当我们用图像的近似值替换图像时，我们就会失去图像的质量：我们保留的信息越多，就越能更好地逼近原始图像。结果，我们在信息的减少和近似的质量之间产生了相互作用。在逼近理论中，我们试图找到这个问题的最佳(最优)解。这项研究的目的是继续研究这些类型的应用所激发的近似方法。我们注意到，非线性逼近处于当前逼近理论的前沿。非线性逼近是目前唯一的希望，因为处理真正有实际意义的问题仍然需要增加可用的逼近能力。

PI: Vladimir Temlyakov, University of South CarolinaDMS-0200187 Abstract:Nonlinear approximation seeks ways to approximate complicated functions by simple functions using methods that depend nonlinearly on the function being approximated. Recently, a particular kind of nonlinear approximation, namely, greedy approximation attracted a lot of attention in both theoretical and applied settings. Greedy type algorithms proved to be very useful in various applications such as image compression, signal processing, design of neural networks, and the numerical solution of nonlinear partial differential equations. The theory of greedy approximation is emerging now: some fundamental convergence results have already been established; many fundamental problems remain unsolved. The purpose of the proposed research is to continue investigations of greedy approximation. We propose to continue to study greedy approximation with regard to bases, where substantial progress has been achieved recently. We propose to place emphasis on studying the efficiency of greedy algorithms with regard to redundant systems (dictionaries). Redundancy on the one hand offers much promise for greater efficiency in terms of approximation rate, but on the other hand gives rise to highly nontrivial theoretical and practicalproblems. We note that there is a solid justification of importance of redundant systems in both theoretical questions and practical applications.Approximation theory is a branch of Mathematics that studies methods of replacing complicated objects by simpler objects. This idea has proved to be fruitful in many applications to the real world problems. Among these applications are signal processing, image compression, financeproblems, and many others. As one of the model problems consider image compression.Take for example an image (picture) on a TV screen. Why should we approximate it? In many cases we cannot afford to transmit (or store in a computer memory) the whole information of an image, perhaps because of a high cost for transmission of a bit of information orlimited channel capacity. This is exactly the point where an application of approximation theory can be fruitful. Clearly, when we replace an image by its approximant we lose the quality of picture: the more information we keep the better approximation to the original image we have. As a result we have an interplay between the reduction of information and the quality of approximation. In approximation theory we try to find the best (optimal) solution to this problem. The purpose of the proposed research is to continue the investigations of methods of approximation which are motivated by these types of applications. We note that nonlinear approximation is at the current frontiers of approximation theory. Nonlinear approximation is the only hope at present for the increase in available approximation power still needed to handle problems of real practical interest.