Top

Published in:

2013 | OriginalPaper | Chapter

8. Decomposition in Transition: Adaptive Matrix Factorization

Authors : Alexander Paprotny, Michael Thess

Published in: Realtime Data Mining

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We introduce SVD/PCA-based matrix factorization frameworks and present applications to prediction-based recommendation. Furthermore, we devise incremental algorithms that enable to compute the considered factorizations adaptively in a realtime setting. Besides SVD and PCA-based frameworks, we discuss more sophisticated approaches like non-negative matrix factorization and Lanczos-based methods and assess their effectiveness by means of experiments on real-world data. Moreover, we address a compressive sensing-based approach to Netflix-like matrix completion problems and conclude the chapter by proposing a remedy to complexity issues in computing large elements of the low-rank matrices, which, as we shall see, is a recurring problem related to factorization-based prediction methods.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Breaking Dimensions: Adaptive Scoring with Sparse Grids

next chapter Decomposition in Transition II: Adaptive Tensor Factorization

[Beb08]

Bebendorf, M.: Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems. Lecture Notes in Computational Science and Engineering (LNCSE), vol. 63. Springer-Verlag, Berlin (2008)

[BNS78]

Bunch, J.R., Nielsen, C.P., Sorensen, D.C.: Rank-one modification of the symmetric eigenproblem. Numer. Math. 31, 31–48 (1978)CrossRefMATHMathSciNet

[Bra02]

Brand, M.E.: Incremental singular value decomposition of uncertain data with missing values. In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds.) Computer Vision ECCV. Lecture Notes in Computer Science, vol. 2350, pp. 707–720. Springer, Berlin/Heidelberg (2002)

[Bra03]

Brand, M.E.: Fast online svd revisions for lightweight recommender systems. In: SIAM International Conference on Data Mining (SDM) (2003)

[Bra06]

Brand, M.E.: Fast low-rank modifications of the thin singular value decomposition. Linear Algebra Appl. 415, 20–30 (2006)CrossRefMATHMathSciNet

[CR08]

Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2008)CrossRef

[CRT06]

Candès, E.J., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math. 59, 1207–1223 (2006)CrossRefMATHMathSciNet

[CS09]

Chen, J., Saad, Y.: Lanczos vectors versus singular vectors for effective dimension reduction. IEEE Trans. Knowl. Data Eng. 21, 1091–1103 (2009)CrossRef

[CT10]

Candès, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Info. Theor. 56(5), 2053–2080 (2010)CrossRef

[DHS05]

Ding, C., He, X., Simon, H.D.: On the equivalence of nonnegative matrix factorization and spectral clustering. Proc. SIAM Data Mining Conf. 4, 606–610 (2005)

[DLJ10]

Ding, C., Li, T., Jordan, M.I.: Convex and semi-nonnegative matrix factorizations. IEEE Trans. Pattern Anal. Mach. Intell. 32(1), 45–55 (2010)CrossRef

[Don06]

Donoho, D.L.: Compressed sensing. IEEE Trans. Info.Theor. 52(4), 1289–1306 (2006)CrossRefMathSciNet

[Fun06]

Funk, S.: Netflix update: try this at home. http://sifter.org/~simon/journal/20061211.html

[GNBT92]

Goldberg, D., Nichols, D., Oki, B.M., Terry, D.: Using collaborative filtering to weave an information tapestry. Commun. ACM 35(12), 61–70 (1992). Special issue on information filteringCrossRef

[GH03]

Grasedyck, L., Hackbusch, W.: Construction and arithmetics of H-matrices. Computing 70, 295–334 (2003)CrossRefMATHMathSciNet

[GE94]

Gu, M., Eisenstat, S.C.: A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem. SIAM J. Matrix Anal. Appl. 15, 1266–1276 (1994)CrossRefMATHMathSciNet

[Ha99]

Hackbusch, W.: A sparse matrix arithmetic based on H-matrices. Part I: introduction to H-matrices. Computing 62, 89–108 (1999)CrossRefMATHMathSciNet

[HK00]

Hackbusch, W., Khoromskij, B.N.: A sparse H-matrix arithmetic. Part II: application to multi-dimensional problems. Computing 64, 21–47 (2000)MATHMathSciNet

[HJ85]

Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, New York (1985)CrossRefMATH

[LSY03]

Linden, G., Smith, B., York, J.: Amazon.com recommendations: item-to-item collaborative filtering. IEEE Internet Comput. (2003)

[MHT10]

Mazumder, R., Hastie, T., Tibshirani, R.: Spectral regularization algorithms for learning large incomplete matrices. J. Mach. Learn. Res. 11, 2287–2322 (2010)MATHMathSciNet

[Pap09]

Paprotny A.: Praktikumsbericht zum Fachpraktikum bei der Firma prudsys AG. (in German) Report. TU Hamburg-Harburg (2009)

[RFP10]

Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum rank solutions of matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471–501 (2010)CrossRefMATHMathSciNet

[RS05]

Rennie J.D.M., Srebro N.: Fast maximum margin matrix factorization for collaborative prediction. In: Proceedings of the 22nd International Conference on Machine Learning, pp. 713–719. ACM (2005)

[SHB05]

Shani, G., Heckerman, D., Brafman, R.I.: An MDP-based recommender system. J. Mach. Learn. Res. 6, 1265–1295 (2005)MATHMathSciNet

[VB96]

Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996)CrossRefMATHMathSciNet

[ZWSP08]

Zhou, Y., Wilkinson, D., Schreiber, R., Pan, R.: Large-scale parallel collaborative filtering for the netflix prize. In: Proceedings of 4th International Conference Algorithmic Aspects in Information and Management, LNCS 5034 (2008)

Title: Decomposition in Transition: Adaptive Matrix Factorization
Authors: Alexander Paprotny
Michael Thess
Publisher: Springer International Publishing
Book: Realtime Data Mining
Print ISBN: 978-3-319-01320-6

Electronic ISBN: 978-3-319-01321-3

Copyright Year: 2013
DOI: https://doi.org/10.1007/978-3-319-01321-3_8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner