Hasan ERBAY, Cenker BİÇER, Fahrettin HORASAN, Fatih VARÇIN

Block classical Gram–Schmidt-based block updating in low-rank matrix approximation

Low-rank matrix approximations have recently gained broad popularity in scientific computing areas. Theyare used to extract correlations and remove noise from matrix-structured data with limited loss of information. Truncatedsingular value decomposition (SVD) is the main tool for computing low-rank approximation. However, in applicationssuch as latent semantic indexing where document collections are dynamic over time, i.e. the term document matrixis subject to repeated updates, SVD becomes prohibitive due to the high computational expense. Alternative decompositions have been proposed for these applications such as low-rank ULV/URV decompositions and truncated ULVdecomposition. Herein, we propose a BLAS-3 compatible block updating truncated ULV decomposition algorithm basedon the block classical Gram–Schmidt process. The simulation results presented show that the block update algorithm ispromising

PDF

___

Barlow JL, Aydoğan E, Erbay H. Block updates on truncated ULV decomposition. Advances in Computational Science, Engineering and Information Technology 2013; 225: 73-79.
Barlow JL, Erbay H. Modifible low-rank approximation to a matrix. Numer Linear Algebr 2009; 16: 833-860.
Barlow JL, Smoktunowicz A. Reorthogonalized block classical Gram-Schmidt. Numer Math 2013; 123: 395–423.
Barlow JL, Smoktunowicz A, Erbay H. Improved Gram-Schmidt type downdating methods. BIT 2005; 45: 259-285.
Berry MW, Browne M. Understanding Search Engines: Mathematical Modeling and Text Retrieval. Philadelphia, PA, USA: SIAM, 2005.
Berry MW, Dumais S, O’Brien GW. Using linear algebra for intelligent information retrieval. SIAM Rev 1995; 37: 573-595.
Davis C, Kahan WM. The rotation of eigenvectors by a perturbation III. SIAM J Numer Anal 1970; 7: 1-46.
Deerwester S, Dumais S, Furnas S, Landauer TG, Harshman R. Indexing by latent semantic analysis. J Am Soc Inform Sci 1990; 41: 391-407.
Deprettere F. SVD and Signal Processing: Algorithms, Applications and Architectures. Amsterdam, the Netherlands: North-Holland Publishing Co., 1989.
Dongarra JJ, du Croz J, Hammarling S, Duff I. A set of level 3 basic linear algebra subprograms. ACM T Math Software 1990; 16: 1-17.
Drineas P, Kannan R, Mahoney MW. Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix. SIAM J Comput 2006; 36: 158-183.
Fierro RD, Hansen PC. Low-rank revealing UTV decompositions. Numer Algorithms 1997; 15: 37-55.
Golub GH, Van Loan CF. Matrix Computations. Baltimore, MD, USA: Johns Hopkins Press, 2013.
Halko N, Martinsson P, Tropp J. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev 2011; 53: 217–288.
Higham NJ. Accuracy and Stability of Numerical Analysis. Cambridge, UK: Cambridge University Press, 2002.
Hoemmen M. Communication-avoiding Krylov Subspace Methods. Berkeley, CA, USA: University of California, 2010.
Kleinberg JM. Two algorithms for nearest-neighbor search in high dimensions. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 1997, pp. 599-608.
Kleinberg JM. Authoritative sources in a hyperlinked environment. J ACM 1999; 46: 604-632.
Matthew B. Fast low-rank modifications of the thin singular value decomposition. Linear Algebra Appl 2006; 415: 20-30.
Moonen M, De Moor B. SVD and Signal Processing III: Algorithms, Architectures and Applications. Amsterdam, the Netherlands: Elsevier, 1995.
Papadimitriou CH, Raghavan P, Tamaki H, Vempala S. Latent semantic indexing: a probabilistic analysis. In: Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998, pp. 159-168.
Stewart GW. Block Gram-Schmidt orthogonalization. SIAM J Sci Comput 2008; 31: 761-775.
Vaccaror RJ. SVD and Signal Processing II: Algorithms, Analysis and Applications. Amsterdam, the Netherlands: Elsevier, 1991.
Watkins DS. Fundamentals of Matrix Computations. New York, NY, USA: John Wiley and Sons, 2002.

ISSN: 1300-0098
Yayın Aralığı: Yılda 6 Sayı
Yayıncı: TÜBİTAK

Arşiv