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

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

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.