Greedy Approximations with Expansions

摘要函数的稀疏表示不仅是一种强大的分析工具，而且在图像/信号处理和数值计算等许多应用领域都得到了应用。寻找稀疏表示的核心是通过给定函数系统（字典）的元素对目标函数进行m项逼近的概念。由于在m项近似中使用的字典元素被允许依赖于被近似的函数，这种类型的近似，称为非线性近似，当可以找到近似时是非常有效的。非线性逼近寻求用简单函数逼近复杂函数的方法，这种方法非线性地依赖于被逼近的函数。近年来，一类特殊的非线性逼近，即贪心逼近，在理论和应用上都引起了广泛的关注。贪婪型算法在图像压缩、信号处理、神经网络设计和非线性偏微分方程的数值解等各种应用中被证明是非常有用的。贪婪逼近理论正在兴起：一些收敛结果已经得到了证明；许多问题仍未解决。基本问题是如何构造好的近似方法（算法）。本研究的目的是设计和研究可实际实现的一般非线性逼近方法。提出的研究将开发算法，证明是有效的收敛和收敛速度。提出的研究目标是开展基础数学和算法研究，以显着提高我们处理（压缩，去噪等）大型数据集的能力。实现这一目标的主要技术是基于非线性稀疏表示。了解如何处理大型数据集是这十年来最大的科学挑战之一。有效地分析数据和提取重要信息是设计系统的关键。研究用更小更简单的数据代替大数据的过程的科学学科是近似理论。它在国防和民用领域有无数现有的和潜在的应用。例如，管理大型数据库，如通过监控获得的安全数据库，需要对数据集进行处理，以便加速提取重要特征或特定信息。

AbstractSparse representations of a function are not only a powerful analytictool but they are utilized in many application areas such as image/signal processing and numerical computation. The backbone of finding sparse representations is the concept of m-term approximation of the target function by the elements of a given system of functions (dictionary). Since the elements of the dictionary used in the m-term approximation are allowed to depend on the function being approximated, this type of approximation, known as nonlinear approximation, is very efficient when the approximants can be found. 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 convergence results have already been established; many problems remain unsolved. The fundamental question is how to construct good methods (algorithms) of approximation. The purpose of the proposed research is to design and study general nonlinear methods of approximation that are practically realizable. The proposed research will develop algorithms that are provably efficient with respect to convergence and rate of convergence.The goal of the proposed research is to carry out fundamental mathematical and algorithmic study to significantly increase our ability to process (compress, de-noise, etc.) large data sets. The main technique that will be used in achieving this goal is based on nonlinear sparse representations. Understanding how to process large data sets is one of the great scientific challenges of this decade. It is key to designing systems to efficiently analyze data and extract essential information. The scientific discipline, which studies the process of replacing large data by smaller and simpler data, is the approximation theory. It has a myriad of existing and potential applications in both the defense and civilian sectors. For instance, managing large data bases such as security data bases obtained through surveillance requires processing of the data sets in order to speed up extraction of significant features or specific information.