CAREER: Efficient Atomic Decompositions of Massive Data Sets

职业：海量数据集的高效原子分解

• 批准号: 1148243
• 负责人: Benjamin Recht
• 金额: $ 45万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-06-01 至 2013-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1148243&HistoricalAwards=false
• 关键词: CAREER; Efficient; Atomic; Decompositions; Massive

Scientists and Engineers often struggle to deduce the state or structure of a system from partial, noisy measurements. The corresponding problems are ill-posed because there are fewer measurements available than the number of parameters they would like to estimate. In practice, however, many interesting signals or models contain considerably fewer degrees than the apparent number of parameters: a small number of genes may constitute the signature of a disease, very few parameters may specify the correlation structure of a time series, or a sparse collection of geometric constraints may determine a molecular configuration. Discovering, leveraging, or recognizing such low-dimensional structure plays an important role in posing inverse problems well. This project pursues a unified approach to transform notions of simplicity and latent low-dimensionality into convex penalty functions. The investigators focus on a theoretically sound suite of data analysis algorithms designed to decompose complex signals into sums of a small number of simple atoms. The work first catalogs the objects and structures that can be recovered from a small number of measurements using atomic decomposition algorithms, in order to show that many structures of significant scientific and technological interest need only be probed a few times to extract complete and accurate knowledge. Second, the project explores a range of practically useful implementations of atomic decomposition algorithms for data recovery, enabling efficient solutions of large-scale problems with guaranteed success. Finally, practical implementation in a diverse set of applications, including web-scale data analysis, high-throughput biology, and experimental physics, continually motivate and refine this mathematical research program.

科学家和工程师经常努力从部分的、嘈杂的测量中推断出系统的状态或结构。 相应的问题是不适定的，因为可用的测量值比他们想要估计的参数数量少。然而，在实践中，许多有趣的信号或模型包含的度比参数的表观数量少得多：少量的基因可能构成疾病的特征，非常少的参数可能指定时间序列的相关结构，或者稀疏的几何约束集合可能决定分子构型。发现、利用或识别这种低维结构在很好地提出反问题中起着重要作用。该项目追求一种统一的方法，将简单性和潜在低维的概念转化为凸罚函数。研究人员专注于一套理论上合理的数据分析算法，旨在将复杂信号分解为少量简单原子的总和。 这项工作首先使用原子分解算法对可以从少量测量中恢复的对象和结构进行编目，以表明许多具有重大科学和技术意义的结构只需要探测几次就可以提取完整和准确的知识。其次，该项目探索了一系列实用的原子分解算法实现，用于数据恢复，从而确保成功地有效解决大规模问题。最后，在各种应用程序中的实际实施，包括网络规模的数据分析，高通量生物学和实验物理学，不断激励和完善这个数学研究计划。