CAREER: Efficient Atomic Decompositions of Massive Data Sets

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

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.