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.