Generalized low rank approximations of matrices

ABSTRACT

We consider the problem of computing low rank approximations of matrices. The novelty of our approach is that the low rank approximations are on a sequence of matrices. Unlike the problem of low rank approximations of a single matrix, which was well studied in the past, the proposed algorithm in this paper does not admit a closed form solution in general. We did extensive experiments on face image data to evaluate the effectiveness of the proposed algorithm and compare the computed low rank approximations with those obtained from traditional Singular Value Decomposition based method.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: Charu C. Aggarwal, On the effects of dimensionality reduction on high dimensional similarity search, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.256-266, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.383213]
• 3: Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
• 4: Vittorio Castelli , Alexander Thomasian , Chung-Sheng Li, CSVD: Clustering and Singular Value Decomposition for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.671-685, March 2003 [doi>10.1109/TKDE.2003.1198398]
• 5: Deerwester, S., Dumais, S., Furnas, G., Landauer, T., & Harshman, R. (1990). Indexing by latent semantic analysis. Journal of the Society for Information Scienc, 41, 391--407.
• 6: Inderjit S. Dhillon , Dharmendra S. Modha, Concept Decompositions for Large Sparse Text Data Using Clustering, Machine Learning, v.42 n.1-2, p.143-175, January-February 2001 [doi>10.1023/A:1007612920971]
• 7: P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
• 8: Alan Edelman , Tomás A. Arias , Steven T. Smith, The Geometry of Algorithms with Orthogonality Constraints, SIAM Journal on Matrix Analysis and Applications, v.20 n.2, p.303-353, April 1999 [doi>10.1137/S0895479895290954]
• 9: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 10: Golub, G. H., & Van Loan, C. F. (1996). Matrix computations. Baltimore, MD, USA: The Johns Hopkins University Press. Third edition.
• 11: Gu, M., & Eisenstat, S. C. (1993). A fast and stable algorithm for undating the singular value decomposition (Technical Report Technical Report YALEU/DCS/RR-966, Department of Computer Science, Yale University).
• 12: K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States
• 13: Jon Kleinberg , Andrew Tomkins, Applications of linear algebra in information retrieval and hypertext analysis, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.185-193, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303995]
• 14: Martinez, A., & Benavente, R. (1998). The ar face database (Technical Report CVC Tech. Report No. 24).
• 15: Terence Sim , Simon Baker , Maan Bsat, The CMU Pose, Illumination, and Expression (PIE) Database, Proceedings of the Fifth IEEE International Conference on Automatic Face and Gesture Recognition, p.53, May 20-21, 2002
• 16: Srebro, N., & Jaakkola, T. (2003). Weighted low-rank approximations. ICML Conference Proceedings (pp. 720--727).
• 17: Jieping Ye , Ravi Janardan , Qi Li, GPCA: an efficient dimension reduction scheme for image compression and retrieval, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014092]

INDEX TERMS

Keywords:
Singular Value Decomposition (SVD), classification, low rank approximation