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.