Numerical Linear Algebra and Approximation Theory Methods for Efficient Data Exploration

本提案旨在发展新的和有效的算法，以执行降维任务的方法，从数值线性代数和近似理论的技术混合。当前大规模集成电路的实现和其他降维方法依赖于矩阵分解，如奇异值分解（SVD）。基于奇异值分解的方法明确地计算优势奇异向量的基，并在此基础上对数据进行投影。这具有滤除噪声和数据固有冗余的理想效果，同时保留其主要结构特征（例如，LSI中的“语义内容”）。然而，基于svd的方法在计算成本和存储方面往往是昂贵的，并且对于非常大的数据集变得不切实际。该建议的前提是不需要计算（部分）SVD来进行降维。一个给定向量的投影到与最大奇异值相关的空间上，可以通过多项式滤波技术精确地再现。这种技术需要将一个向量与原始数据矩阵及其置阵重复相乘，它有几个优点，包括低计算和存储需求。此外，“相关反馈”显著提高了LSI结果的质量，可以很容易地适用于多项式滤波。也许更重要的是多项式滤波在实现各种期望的约简特征方面的出色灵活性。例如，滤波器的适当选择将产生从不需要的分量（小奇异值）到想要的分量（大奇异值）的任意平滑过渡，而不是截断SVD （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.