Numerical Linear Algebra and Approximation Theory Methods for Efficient Data Exploration

在各种应用程序中处理的数据集的规模迅速增加，这开始使许多用于数据探索的传统方法变得不足。这些方法的失败不仅是因为观测数量的增加（数据集本身的大小），还因为观测到的潜在现象本质上是高维的，即它们涉及大量变量或参数。高维数据集提出了巨大的数学挑战，但在实践中，在大多数情况下，并非所有测量的变量对理解潜在现象都很重要，这一事实减轻了相关的困难。当前降维技术面临的困难之一是，当处理非常大的数据集时，现有的算法往往过于昂贵。为了解决其中的一些挑战，该项目的研究团队将专注于开发计算效率高的方法，这些方法将经典技术（如PCA或LLE）与数值线性代数和近似理论的其他策略相结合，以减少问题的规模。因此，多层或分而治之技术在科学计算的其他领域非常常见，但在数据挖掘中受到的关注相对较少。拟议的工作将把这类方法放在首位。研究小组还将考虑借用图论的工具，特别是基于超图、图划分和kNN图构造的技术，以帮助降维。最后，本计画将处理复杂的降维问题，使用张量和多元线性代数。当前，社会正面临着科学、工程和经济应用领域可利用信息的空前激增。这类应用的典型例子包括用于安全和商业的面部识别，以及处理全球网络上的查询。在这些应用程序中生成的数据集不仅在大小上（更多的数据样本），而且在维度上（表示每个数据样本的参数或变量的数量）也在增加。例如，在人脸识别中，当处理一组图片时，大小就是图片的数量，维度就是用来表示每张图片的像素的数量。在处理大型数据集的应用程序中，降低数据的维度是一个重要的工具。因此，这方面的研究在过去几年中获得了巨大的重要性也就不足为奇了。本项目的研究人员将探索解决这一问题的方法，重点是那些计算成本低的方法。在这些方法中有一类分而治之的技术，它将集合划分为较小的集合，而经典方法则独立应用于较小的集合。

The rapidly increasing sizes of the data sets being treated in various applications is starting to render inadequate many of the traditional methods used in data exploration. These methods break down not only because of the increase in the number of observations (size of datasets themselves) but also because the underlying phenomena observed are intrinsically of high dimension, i.e., they involve a large number of variables or parameters. High-dimensional datasets present great mathematical challenges but in practice, the related difficulties are mitigated by the fact that in most cases, not all the measured variables are important for an understanding of the underlying phenomenon. One of the difficulties faced by current dimension reduction techniques is that existing algorithms are often too costly when dealing with very large data sets. To tackle a few of these challenges the research team of this project will focus on the development of computationally efficient methods which blend classical techniques such as PCA or LLE, with other strategies from numerical linear algebra and approximation theory, to reduce problem sizes. Thus, multilevel or divide and conquer techniques are quite common in other areas of scientific computing but received relatively little attention in data mining. The proposed work will put methods of this type at the forefront. The research team will also consider tools borrowed from graph theory, specifically techniques based on hypergraphs, graph partitioning, and kNN graph construction, to help with dimension reduction. Finally, this project will address the complex issue of dimension reduction by means of tensors and the use of multilinear algebra.Society is currently facing an unparalleled surge of exploitable information in scientific, engineering, and economical applications. Typical examples of such applications include face-recognition which has uses in security and commerce for example, and the processing of queries on the world-wide web. The data sets generated in these applications are not only gaining in size (more data samples) but also in their dimension (number of parameters or variables to represent each data sample). For example, in face recognition, where one deals with sets of pictures the size would be the number of pictures and the dimension would be the number of pixels used to represent each picture. Reducing the dimension of data is a vital tool used in applications dealing with large data sets. It is therefore not too surprising that this line of research has gained enormous importance in the last few years. The investigators of this project will explore methods to solve this problem, putting an emphasis on those methods characterized by low computational cost. Among these methods are a class of divide and conquer techniques which divide the sets in smaller ones on which the classical methods are applied independently.