Numerical Linear Algebra and Approximation Theory Methods for Efficient Data Exploration

该方案旨在通过融合数值线性代数和逼近理论的方法来开发新的有效的降维算法，目前LSI和其他降维方法的实现依赖于矩阵分解，例如奇异值分解(SVD)。基于奇异值分解的方法显式地计算主导奇异向量的基，并在此基础上进行数据的投影。这具有过滤掉数据固有的噪声和冗余，同时保留其主要结构特征(例如，LSI中的“语义内容”)的理想效果。然而，基于奇异值分解的方法往往在计算代价和存储方面都很昂贵，并且对于非常大的数据集变得不实用，该方案的前提是不需要计算(部分)奇异值分解来执行降维。给定向量在与最大奇异值相关的空间上的投影可以通过多项式滤波技术准确地再现。这种技术需要将一个向量与原始数据矩阵及其序列重复相乘，具有几个优点，包括较低的计算和存储需求。此外，“相关反馈”可以很容易地适用于多项式滤波，它显著提高了LSI结果的质量。也许更重要的是多项式滤波在实现各种所需的约简特征方面的出色灵活性。例如，适当地选择滤波器将产生从不需要的分量(小的奇异值)到想要的分量(大的奇异值)的任意平滑过渡，而不是表征截断奇异值(TSVD)的不连续截止。此外，一些应用程序可能需要精确的投影(高次多项式)，而对另一些应用程序来说，这将是浪费甚至适得其反的。社会目前正面临科学、工程和经济应用程序中可开发信息的爆炸性激增。可用数据集的大小迅速增加，开始使许多用于数据探索的算法变得不足，尽管当计算成本被搁置在一边时，它们的优点仍然存在。本文所研究的方法将通过采取一种新的方法来解决代价问题，完全避免了经典算法的瓶颈。如果完全成功，将要开发的方法可能会极大地增强当前在信息技术关键领域使用的最先进方法的能力。例如，初步研究表明，当处理数据库中的查询时，所提出的方法有时可以提供比标准方法快十倍的速度，而不会损失任何精度。调查小组还将把这种方法推广到人脸识别问题上。该方法在图像处理、医学层析成像等领域也有很好的应用前景。

This proposal aims at developing new and effective algorithms forperforming dimensionality reduction tasks by methods which blendtechniques from numerical linear algebra and approximation theory.Current implementations of LSI, and other dimensionality reductionmethods, rely on matrix decompositions such as the Singular ValueDecomposition (SVD). SVD-based methods compute explicitly the basisof the dominant singular vectors and proceed with a projection of thedata on this basis. This has the desirable effect of filtering outnoise and redundancy inherent to the data, while retaining its mainstructural features (e.g., `semantic contents' in LSI). However,SVD-based methods tend to be expensive, both in terms of computationalcost and storage, and become impractical for very large data sets.The premise of this proposal is that there is no need to compute the(partial) SVD in order to perform dimensionality reduction. Theprojection of a given vector onto the space associated with thelargest singular values can be accurately reproduced by a polynomialfiltering technique. This technique, which entails repeatedmultiplication of a vector by the original data matrix and itstranspose, offers several advantages including low computational andstorage requirements. In addition, ``relevance feedback'', whichenhances significantly the quality of the results of LSI, can beeasily adapted for polynomial filtering. Perhaps more important isthe excellent flexibility of polynomial filtering in enabling variousdesired reduction features. For example, an appropriate choice of thefilter will yield an arbitrarily smooth transition from the unwantedcomponents (small singular values) to the wanted ones (large singularvalues) in contrast with the discontinuous cut-off which characterizesTruncated SVD (TSVD). Also, some applications may require an accurateprojection (high degree polynomial) while for others this would bewasteful or even counter-productive.Society is currently facing an explosive surge of exploitableinformation in scientific, engineering, and economical applications.The rapidly increasing sizes of the data sets becoming available isstarting to render inadequate many of the algorithms used in `dataexploration' in spite of their merits when computational costs are setaside. The methods investigated in this research will address theissue of cost by taking a new approach which completely avoids thebottleneck of the classical algorithms. If fully successful themethods to be developed may significantly enhance the capabilities ofcurrent state-of-the-art methods used in key areas of informationtechnology. For example, preliminary studies have shown that whenprocessing a query in a database, the proposed methods can sometimesoffer a tenfold gain in speed relative to standard methods, withoutany loss of accuracy. The investigating team will also extend thisapproach to the problem of face recognition. The method also hasexcellent prospects in other potential applications including imageprocessing, and medical tomography.