Algorithms in Nonlinear Approximation

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

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.