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.