Collaborative Research: Sparse Optimization in Large Scale Data Processing: A Multiscale Proximity Approach

在信息技术、纳米技术、生物技术、民用基础设施和环境等国家战略利益领域，迫切需要从传感器和互联网等各种手段获得的大规模数据中提取有用的知识，用于决策或揭示真相。这些领域的核心问题是建立精确的数学模型，控制抽象过程，并设计有效的算法来解决模型的潜在优化问题。任务的一个挑战来自于给定数据的大规模性质。这种性质需要确定大量的模型参数，并且计算成本很高。为了应对这一挑战，本项目将在建模中利用给定数据的某些固有多尺度结构，以便最终模型需要确定的参数显着减少。引入有效的算法来解决模型的优化问题也是至关重要的，因为模型具有固有的多尺度结构。这项研究的第二个目标是为年轻数学家和计算科学家提供严格的培训，使他们能够通过这项研究及其相关的教育组成部分，拥有面对大数据时代挑战所需的技能。拟议研究的结果及其教育部分肯定会对联邦战略利益领域作出贡献。本研究项目通过适当选择结构化稀疏性来促进建模中的非凸函数，并通过综合数据的多尺度表示以及使用涉及邻近算子的不动点方程/包含来解决由此产生的优化问题，解决了处理大规模数据（如高维和高噪声）的几个关键问题。为了克服现有大规模数据建模方法的不足，提出了结构化非凸稀疏度提升函数，从而设计了高效的单尺度接近算法。为了有效地表示数据，已经发展了多尺度分析，但如何使用数据的多尺度表示来提高定点接近算法的收敛性仍然是一个未解决的问题。提出的多尺度接近方法避免了对不动点方程/包含的全尺度迭代。相反，当数据在多尺度分析中表示时，多尺度接近算法只对方程/包含的（小规模）低频分量（基于单尺度算法）进行迭代，并且只需要对（大规模）高频分量进行一次功能评估。多尺度算法在保持单尺度算法精度的同时，显著加快了单尺度算法的收敛速度。这就产生了一种求解涉及接近算子的不动点方程/包含的快速算法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

There is an emergent demand in areas of national strategic interest such as information technology, nanotechnology, biotechnology, civil infrastructure and environment for abstracting useful knowledge for decision making or uncovering truth from large-scale data acquired via various means such as sensors and internet. A core issue of these areas is to develop accurate mathematical models, which govern the abstraction process, and to design efficient algorithms that solve the underlying optimization problems for the models. A challenge of the tasks comes from the large-scale nature of given data. This nature requires determining a large number of model parameters and it is computationally expensive. To address this challenge, this project will take advantage of certain intrinsic multiscale structure of given data in modeling so that the resulting models have significantly fewer parameters to be determined. It is also crucial to introduce efficient algorithms for solving the resulting optimization problems for the models, which have intrinsic multiscale structures. The second goal of this proposed research is to provide rigorous training of young mathematicians and computational scientists so that they have the skill sets needed to face the challenges of the big data era through this proposed research and its associated educational components. Outcomes of the proposed research and its educational component will certainly contribute to the Federal strategic interest areas.This research project addresses several critical issues of processing large-scale data, such as high dimensionality and high noise, through properly choosing structured sparsity promoting non-convex functions in modeling and through synthesizing the multiscale representation of data and using fixed-point equations/inclusions involved the proximity operator in solving the resulting optimization problem. Structured non-convex sparsity promoting functions are proposed to overcome drawbacks of the existing modeling of large-scale data, leading to the design of efficient single-scale proximity algorithms. Multiscale analysis has been developed to efficiently represent data, while how multiscale representation of data is used to improve convergence of the fixed-point proximity algorithm remains unsolved. The proposed multiscale proximity method avoids iterations on the full large-scale of the fixed-point equation/inclusion. Instead, when data are represented in a multiscale analysis, iterations of the multiscale proximity algorithm are conducted only on a (small-scale) lower frequency component of the equation/inclusion (based on a single-scale algorithm), and only one functional evaluation on a (large-scale) high frequency component is required. The multiscale algorithm will preserve accuracy of the single-scale algorithm while accelerating its convergence significantly. This leads to a fast algorithm for solving the fixed-point equation/inclusion involved the proximity operator.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.