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

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

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.