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.