Numerical Linear Algebra and Approximation Theory Methods for Efficient Data Exploration

用于高效数据探索的数值线性代数和近似理论方法

• 批准号: 0810938
• 负责人: Yousef Saad
• 金额: $ 27.55万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-15 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0810938&HistoricalAwards=false
• 关键词: Numerical; Linear; Algebra; Approximation; Theory

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.

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