Reduction of sampling and data complexity by modern sparsification techniques

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

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.