Algorithms in Nonlinear Approximation

非线性近似算法

• 批准号: 9970326
• 负责人: Vladimir Temlyakov
• 金额: $ 8.23万
• 依托单位: University of South Carolina at Columbia
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-06-01 至 2002-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9970326&HistoricalAwards=false
• 关键词: Algorithms; Nonlinear; Approximation

Our main interest in this proposal is nonlinear approximation. The basic idea behind nonlinear approximation is that the elements used in the approximation do not come from a fixed linear space but are allowed to depend on the function being approximated. While the scope of our proposal is mostly theoretical, we should note that this form of approximation appears in many numerical applications such as adaptive PDE solvers, compression of images and signals, statistical classification, and so on. The standard problem in this regard is the problem of m-term approximation where one fixes a basis and looks to approximate a target function by a linear combination of m terms of the basis. When the basis is a wavelet basis or a basis of other waveforms, then this type of approximation is the starting point for compression algorithms. We are interested in the quantitative aspects of this type of approximation. Namely, we want to understand the properties (usually smoothness) of the function which govern its rate of approximation in some given norm (or metric). We are also interested in stable algorithms for finding good or near best approximations using m terms. Some of our earlier work has introduced and analyzed such algorithms. More recently, there has emerged another more complicated form of nonlinear approximation which we call highly nonlinear approximation. It takes many forms but has the basic ingredient that a basis is replaced by a larger system of functions that is usually redundant. Some types of approximation that fall into this general category are mathematical frames, adaptive pursuit (or greedy algorithms) and adaptive basis selection. 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 practical problems. With this motivation, our recent work and the current proposal focuses on nonlinear approximation both in the classical form of m-term approximation (where several important problems remain unsolved) and in the form of highly nonlinear approximation where a theory is only now emerging.Nonlinear approximation seeks ways to approximate complicated functions by simple functions using methods that depend nonlinearly on the function being approximated. Such methods of approximation are more flexible than traditional linear approximation methods and 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 purpose of the proposed research is to continue investigations of nonlinear approximation. Emphasis will be placed on studying the efficiency of algorithms which are important in practical applications. Implementation of these algorithms may substantially reduce time for signal and image prosessing. This is important for automated target recognition and related applications including autonomous landing of aircraft and registration of images from a database.

我们对这一建议的主要兴趣是非线性逼近。非线性逼近背后的基本思想是，逼近中使用的元素不是来自固定的线性空间，而是允许依赖于被逼近的函数。虽然我们的建议的范围主要是理论上的，但我们应该注意到，这种形式的近似出现在许多数值应用中，例如自适应PDE求解器、图像和信号的压缩、统计分类等。在这方面的标准问题是m项近似问题，其中一个人固定一个基并寻求通过该基的m个项的线性组合来近似目标函数。当基数是小波基或其他波形的基数时，这种类型的近似是压缩算法的起点。我们对这种近似的量化方面很感兴趣。也就是说，我们想要了解函数的性质(通常是光滑性)，这些性质控制着函数在某种给定范数(或度量)下的逼近速度。我们还对使用m项找到良好或接近最佳近似的稳定算法感兴趣。我们早期的一些工作已经介绍和分析了这样的算法。最近，出现了另一种更复杂的非线性逼近形式，我们称之为高度非线性逼近。它有多种形式，但有一个基本要素，即一个基础被一个通常是多余的更大的功能系统所取代。属于这一一般类别的一些类型的近似是数学框架、自适应追逐(或贪婪算法)和自适应基选择。冗余一方面在逼近速度方面为更高的效率提供了很大的希望，但另一方面也带来了非常重要的理论和实践问题。在这个动机下，我们最近的工作和当前的建议都集中在m项逼近的经典形式(其中几个重要问题仍未解决)和高度非线性逼近的形式上，其中一个理论才刚刚出现。非线性逼近寻求通过使用非线性依赖于被逼近函数的方法来用简单函数逼近复杂函数的方法。这种逼近方法比传统的线性逼近方法更灵活，在图像压缩、信号处理、神经网络设计和非线性偏微分方程组的数值求解等方面都被证明是非常有用的。本研究的目的是继续研究非线性逼近问题。重点研究在实际应用中很重要的算法的效率。这些算法的实现可以大大减少信号和图像处理的时间。这对于自动目标识别和相关应用，包括飞机的自动着陆和数据库中的图像配准非常重要。