Numerical Linear Algebra and Approximation Theory Methods for Efficient Data Exploration

点击翻译按钮获取中文摘要

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.