Reduction of sampling and data complexity by modern sparsification techniques

在当前的数字时代，传输、收集和处理的数字数据有了巨大的增长，例如，在基于机器学习（ML）的应用程序中。为了应对这一现象，需要有效的方法来存储、处理和减少产生的大量数据集，并从中提取相关信息。这样的需求给数学、计算机科学和电子工程的前沿领域带来了重大挑战。其中一些需要全新的方法。尽管ML在最近十年取得了巨大的成功，但一个基本问题仍然存在。对于大多数基于机器学习的算法来说，需要大量的训练数据来“保证”它们的成功。然而，通常数据采集是困难和昂贵的，例如，当需要高价传感器时。此外，训练步骤通常伴随着数据量大幅增长的计算工作。因此，在这个项目中，我们的目标是寻找新的方法来减少这些模型中的采样和数据复杂性。因此，我们将重点放在数据约简问题上，而不是开发新的ML方法。事实证明，许多数据集可以在不丢失相关信息的情况下进行显著的“次采样”。为此，可以利用数据固有的稀疏性。相应的“稀疏化”问题出现在不同的场景中。其核心任务主要可以表述为减少庞大数据矩阵中数据向量的数量，同时保持其频谱特性。光谱信息是对相关信息进行编码的地方。与此密切相关的是帧子采样的任务，这是一个基于卡迪逊-辛格问题的解决而取得进展的领域。利用这些最近的结果，我们的计划是开发和分析在数据表示中争取最佳稀疏性的新方法。在一个相关但略有不同的上下文中，我们的目标是减少函数采样离散化中的节点数量。这允许在从部分和不完全信息中恢复函数的异常困难但重要的问题中控制最优最坏情况误差。我们在这里的主要目标之一是克服目前非建设性和建设性方法之间的差距。在这个方向上的进展肯定会有助于构思适合未来实际应用的新方法。

The present digital age has seen an enormous growth of digital data that is transmitted, collected, and processed, for instance, in machine learning (ML) based applications. In order to cope with this phenomenon, efficient methods are needed for storing, handling, and reducing the arising massive data sets as well as to extract relevant information out from them. Such demand sets major challenges at the frontier of mathematics, computer science, and electrical engineering. Some of those require fundamentally new approaches. Despite the great success of ML in the recent decade, a fundamental problem remains. For most ML based algorithms a huge amount of training data is needed to “guarantee” their success. However, often data acquisition is difficult and expensive, for instance, when there is a need for high-priced sensors. In addition, the training step typically comes with a computational effort growing vastly in the amount of data. In this project, we hence aim for new approaches to reduce the sampling and data complexity in such models. Rather than on the development of new ML methods, we thereby focus on the problem of data reduction. It turned out that many data sets can be significantly “sub-sampled” without losing relevant information. For this, one takes advantage of inherent sparsity of the data. The corresponding problem of “sparsification” appears in different scenarios. The core task can mostly be formulated as reducing the number of data vectors in a huge data matrix while preserving its spectral properties. The spectral information is where the relevant information is encoded. Closely connected is the task of frame subsampling, a field which has seen recent progress based on the solution of the Kadison–Singerproblem. Utilizing such recent results, our plan is to develop and analyze new methods striving for optimal sparsity in data representation. In a related but slightly different context, we aim to reduce the number of nodes in the sampling discretization of functions. This allows for controlling the optimal worst-case error in the extraordinarily difficult but important problem of function recovery from partial and incomplete information. One of our main goals here is to overcome the current gap between non-constructive and constructive methods. Progress in this direction will certainly help to conceive new methods suitable for practical applications in the future.