AF: small: Numerical Linear Algebra Methods for Efficient Data Exploration

AF：小：高效数据探索的数值线性代数方法

• 批准号: 1318597
• 负责人: Yousef Saad
• 金额: $ 34.04万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1318597&HistoricalAwards=false
• 关键词: AF; small; Numerical; Linear; Algebra

The amount of information that is becoming available every day is expanding at an exponential rate and this is starting to render ineffective standard techniques for data exploration. Though high-dimensional datasets present great mathematical challenges, in practice the related difficulties are mitigated by the fact that not all the measured variables are important for an understanding of the underlying phenomenon. The "dimensionality reduction techniques" considered in this project address this issue. Their principle is to combine the variables into a smaller set onto which the data is projected before attempting a solution of the original problem. The problem of dimension reduction gives rise to many interesting mathematical and algorithmic challenges to linear algebra specialists. In particular, one of the difficulties faced by current techniques is that existing algorithms are often too costly when dealing with very large data sets. For example, a number of methods are based on a form of Principal Component Analysis (PCA) which becomes exceedingly expensive as the number of variables (features) and the number of samples increase. A similar calculation is also required for graph-based approaches such as the Locally Linear Embedding (LLE), or Laplacean eigenmaps. In addition, in many applications data sets are frequently updated, e.g., by adding or deleting data items, a situation for which standard matrix algorithms are not adapted. The proposed work will tackle a few of these challenges. It will focus on the development of computationally efficient dimension reduction methods and related techniques, by exploiting ideas from computational linear algebra. Multilevel or divide and conquer techniques are quite common in other areas of scientific computing but have received relatively little attention in data mining. The proposed work puts methods of this type at the forefront. One of the broader impacts of the proposed work is that it will help promote interest in problems related to the current information revolution because its research theme blends mathematical methods, good algorithmic practices, and applications requiring effective numerical methods. The applications under consideration in this work are all of great relevance to many of the new challenges of society (social networks, commerce, and security). Finally, the software resulting from this research will be broadly disseminated to join an excellent pool of existing web sites that provide tools and repositories related to data exploration.

每天可用的信息量正在以指数级的速度扩展，这开始使数据探索的标准技术无效。 尽管高维数据集出现了巨大的数学挑战，但实际上，与并非所有测得的变量对于理解基本现象都很重要的事实可以减轻相关的困难。 该项目中考虑的“降低降低技术”解决了此问题。他们的原理是将变量组合到较小的集合中，然后在尝试解决原始问题的解决方案之前投射到数据。降低尺寸的问题引起了许多有趣的数学和算法挑战，对线性代数专家产生了挑战。特别是，当前技术所面临的困难之一是，在处理非常大的数据集时，现有算法通常太昂贵了。 例如，许多方法基于主组件分析（PCA）的形式，该形式随着变量数量（特征）的数量和样品数量的增加而变得非常昂贵。 对于基于图的方法，例如局部线性嵌入（LLE）或拉乳镜本征图也需要类似的计算。 此外，在许多应用程序中，经常会更新数据集，例如，通过添加或删除数据项，不适合标准矩阵算法的情况。拟议的工作将应对其中一些挑战。 它将通过利用计算线性代数的思想来开发计算有效的降低方法和相关技术的开发。在科学计算的其他领域，多级或鸿沟和征服技术非常普遍，但在数据挖掘中的关注较少。拟议的工作将这种类型的方法放在了最前沿。 拟议工作的更广泛的影响之一是，它将有助于促进对与当前信息革命有关的问题的兴趣，因为其研究主题融合了数学方法，良好的算法实践以及需要有效数值方法的应用。这项工作中所考虑的申请与社会（社交网络，商业和安全）的许多新挑战非常相关。 最后，这项研究产生的软件将被广泛传播，以加入一个现有网站的出色库，这些网站提供与数据探索有关的工具和存储库。