Generalized low rank approximations of matrices. (English) Zbl 1087.65043

The author describes a novel approach to evaluate the expensive computation of the singular value decompositions for the low rank approximations of matrices. The problem is formulated as an optimization one, which approximates a collection of matrices with matrices of lower rank. An iterative algorithm is derived in this sense and a performance study presented.


65F30 Other matrix algorithms (MSC2010)
65F20 Numerical solutions to overdetermined systems, pseudoinverses


CMU PIE; AR face
Full Text: DOI


[1] Achlioptas, D., & McSherry, F. (2001). Fast computation of low rank matrix approximations. In ACM STOC Conference Proceedings (pp. 611–618). · Zbl 1311.94032
[2] Aggarwal, C. C. (2001). On the effects of dimensionality reduction on high dimensional similarity search. In ACM PODS Conference Proceedings (pp. 256–266).
[3] Averbuch, A., Lazar, D., & Israeli, M. (1996). Image compression using wavelet transform and multiresolution decomposition. IEEE Transactions on Image Processing, 5:1, 4–15.
[4] Berry, M., Dumais, S., & O’Brie, G. (1995). Using linear algebra for intelligent information retrieval. SIAM Review, 37, 573–595. · Zbl 0842.68026
[5] Bjork, A., & Golub, G. (1973). Numerical methods for computing angles between linear subspaces. Mathematics of Computation, 27:123, 579–594. · Zbl 0282.65031
[6] Brand, M. (2002). Incremental singular value decomposition of uncertain data with missing values. In ECCV Conference Proceedings (pp. 707–720). · Zbl 1034.68580
[7] Castelli, V., Thomasian, A., & Li, C.-S. (2003). CSVD: Clustering and singular value decomposition for approximate similarity searches in high dimensional space. IEEE Transactions on Knowledge and Data Engineering, 15:3, 671–685. · Zbl 05109112
[8] Deerwester, S., Dumais, S., Furnas, G., Landauer, T., & Harshman, R. (1990). Indexing by latent semantic analysis. Journal of the Society for Information Science, 41, 391–407.
[9] Dhillon, I., & Modha, D. (2001). Concept decompositions for large sparse text data using clustering. Machine Learning, 42, 143–175. · Zbl 0970.68167
[10] Drineas, P., Frieze, A., Kannan, R., Vempala, S., & Vinay, V. (1999). Clustering in large graphs and matrices. In ACM SODA Conference Proceedings (pp. 291–299). · Zbl 0938.68068
[11] Duda, R., Hart, P., & Stork, D. (2000). Pattern classification. Wiley. · Zbl 0968.68140
[12] Edelman, A., Arias, T. A., & Smith, S. T. (1998). The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications, 20:2, 303–353. · Zbl 0928.65050
[13] Frieze, A., Kannan, R., & Vempala, S. (1998). Fast monte-carlo algorithms for finding low-rank approximations. In ACM FOCS Conference Proceedings (pp. 370–378). · Zbl 1125.65005
[14] Fukunaga, K. (1990). Introduction to statistical pattern classification. San Diego, California, USA: Academic Press. · Zbl 0711.62052
[15] Golub, G. H., & Van Loan, C. F. (1996). Matrix computations, 3rd edition. Baltimore, MD, USA: The Johns Hopkins University Press. · Zbl 0865.65009
[16] Gu, M., & Eisenstat, S. C. (1993). A fast and stable algorithm for updating the singular value decomposition. Technical Report YALEU/DCS/RR-966, Department of Computer Science, Yale University.
[17] Kanth, K. V. R., Agrawal, D., Abbadi, A. E., & Singh, A. (1998). Dimensionality reduction for similarity searching in dynamic databases. In ACM SIGMOD Conference Proceedings (pp. 166–176).
[18] Kleinberg, J., & Tomkins, A. (1999). Applications of linear algebra in information retrieval and hypertext analysis. In ACM PODS Conference Proceedings (pp. 185–193).
[19] Kolda, T. G. (2001). Orthogonal tensor decompositions. SIAM Journal on Matrix Analysis and Applications, 23:1, 243–255. · Zbl 1005.15020
[20] Martinez, A., & Benavente, R. (1998). The AR face database. Technical Report CVC Tech. Report No. 24.
[21] Papadimitriou, C. H., Tamaki, H., Raghavan, P., & Vempala, S. (1998). Latent semantic indexing: A probabilistic analysis. In PODS Conference Proceedings (pp. 159–168). · Zbl 0963.68063
[22] Samaria, F., & Harter, A. (1994). Parameterisation of a stochastic model for human face identification. In Proceedings of 2nd IEEE Workshop on Applications of Computer Vision, Sarasota FL (pp. 138–142).
[23] Shashua, A., & Levin, A. (2001). Linear image coding for regression and classification using the tensor-rank principle. In CVPR Conference Proceedings (pp. 42–49).
[24] Sim, T., Baker, S., & Bsat, M. (2004). The CMU pose, illumination, and expression (PIE) database. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25:12, 1615–1618.
[25] Srebro, N., & Jaakkola, T. (2003). Weighted low-rank approximations. In ICML Conference Proceedings (pp. 720–727).
[26] Vasilescu, M. A. O., & Terzopoulos, D. (2002). Multilinear analysis of image ensembles: Tensorfaces. In ECCV Conference Proceedings (pp. 447–460). · Zbl 1034.68693
[27] Yang, J., Zhang, D., Frangi, A., & Yang, J. (2004). Two-dimensional PCA: A new approach to appearance-based face representation and recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 5:1, 131–137. · Zbl 05110393
[28] Zhang, T., & Golub, G. H. (2001). Rank-one approximation to high order tensors. SIAM Journal on Matrix Analysis and Applications, 5:2, 534–550. · Zbl 1001.65036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.