Factorizing Gigantic Matrices: Tutorial at ECML-PKDD 2011

Christian Bauckhage (Fraunhofer IAIS), Kristian Kersting (Fraunhofer IAIS), Christian Thurau (Fraunhofer IAIS)

Tutorial description

Low-rank approximations of data matrices have become an important tool in machine learning and data mining. They allow for embedding high dimensional data in lower dimensional spaces and can therefore mitigate effects due to noise, uncover latent relations, or facilitate further processing. These properties have been proven successful in many applications areas such as bio-informatics, computer vision, text process ing, recommender systems, social network analysis, among others. Present day technologies are characterized by exponentially growing amounts of data. Recent advances in sensor technology, Internet applications, and communication networks call for methods that scale to very large and/or growing data matrices. In this tutorial, we discuss basic characteristics of matrix factorization and introduce several recent approaches that scale to modern massive data analysis problems.

Intended audience
The tutorial aims at a wide audience as it reviews both machine learning and data mining techniques. It is intended for PhD students, practitioners, and researchers who are interested in large scale machine learning and data analysis.


The tutorial is divided into three parts:
  • Part I: Matrix Factorization — Traditional Optimization Approaches and Statistical Foundations: In this block, we will discuss foundations and multi-linear extensions of traditional methods such as SVD, PCA, K-Means, and Vector Quantization.
  • Part II: Constraint Matrix Factorization Many real-world applications of matrix factorization impose constraints on the factorization problem. For instance, matrix factors need to be non-negative, convex combinations of existing data, or compact binary codes. Among others, we discuss techniques such as Spectral Hashing, NMF, Archetypal Analysis, CNMF, and CH-NMF.
  • Part III: Data-driven Matrix Factorization Techniques: The first and second part of the tutorial consider norm minimization problems to obtain suitable matrix factors. Recent approaches that extend matrix factorization towards massive data assume a different point of view: they attempt to maximize the volume of a selection of rows and columns of a given data matrix. In this final part of the tutorial, we present and review approaches such as FastMap, CUR, CMD, and SiVM.
    In each of the parts, we present practical applications from fields such as image processing, computer vision, robotics, web mining, and social media analysis.

CVs of the presenters:
  • Christian Bauckhage is professor of media informatics at the University of Bonn and heads the Visual and Social Media Group at the Fraunhofer Institute for Intelligent Analysis and Information Systems (IAIS). He obtained a Ph.D. in computer Science from Bielefeld University, Germany, and was a postdoctoral researcher at the Centre for Vision Research in Toronto, Canada. Later, he worked as a senior research scientist at Deutsche Telekom Laboratories in Berlin, where he conducted and coordinated industrial ICT research. He is a regular reviewer for leading journals and conferences and has (co)authored more than 100 technical papers on pattern recognition, web data mining, social media, and future Internet related topics.
  • Kristian Kersting is the head of the STREAM group at Fraunhofer IAIS, Bonn, Germany, and a research fellow of the University of Bonn. He received his Ph.D. from the University of Freiburg, Germany, in 2006. After a PostDoc at the MIT, USA, he joined Fraunhofer IAIS in 2008 to build up the STREAM research group. His main research interests are statistical relational AI, machine learning, data mining, and robotics. He has published more than 70 papers, has received the ECML Best Student Paper Award in 2006 and the ECCAI Dissertation Award 2006 for the best European dissertation in the field of AI, and is an ERCIM Cor Baayen Award 2009 finalist. He served as area chair and PC member for numerous conferences in the area of machine learning and artificial intelligence. He is on the editorial board of the Machine Learning Journal, the Journal of Artificial Intelligence Research, and is an action editor for Knowledge Discovery and Data Mining Journal.
  • Christian Thurau is a PostDoc at the Visual and Social Media Group at Fraunhofer IAIS and at the Bonn-Aachen International Center for Information Technology (B-IT). In 2006 he received a Ph.D. in computer science from Bielefeld University, Germany. From 2007 till 2008 he was a Marie Curie post-doctoral researcher at he Center for Machine Perception Prague, Czech Republic. In 2008 he stayed at the Technical University Dortmund, before joining Fraunhofer IAIS the same year. His main research interests are pattern recognition and data mining, and their application to new media data. He reviews for leading journals and conferences, and has organized several workshops and sessions in this area.

  • L. M. Blumenthal. Theory and Applications of Distance Geometry. Oxford University Press, 1953.
  • A. Cutler and L. Breiman. Archetypal Analysis, Technometrics 36(4), 338–347, 1994.
  • D. D. Lee and H. S. Seung. Learning the Parts of Objects by Non-negative Matrix Factorization. Nature 401(6755), 788–799, 1999.
  • S. A. Goreinov and E. E. Tyrtyshnikov. The maximum-volume concept in approximation by low-rank matrices. Contemporary Mathematics, volume 280, pages 47–51. AMS, 2001.
  • J. Sun, Y. Xie, H. Zhang, and C. Faloutsos. Less is More: Compact Matrix Decomposition for Large Sparse Graphs. In SDM, 2007.
  • B. Klingenberg, J. Curry, and A. Dougherty. Non-negative Matrix Factorization: Illposedness and a Geometric Algorithm. Pattern Recognition 42(5), 918-928, 2008.
  • A. Civril and M. Magdon-Ismail. On Selecting A Maximum Volume Sub-matrix of a Matrix and Related Problems. Theoretical Computer Science, 410(47-49):4801-4811, 2009.
  • C. Ding, T. Li. and M. Jordan. Convex and Semi-Nonnegative Matrix Factorizations. IEEE Trans. on Pattern Analysis and Machine Intelligence 32(1), 45–55, 2009.
  • M. W. Mahoney and P. Drineas. CUR matrix decompositions for improved data analysis. PNAS, 106(3):697–702, 2009.
  • C. Thurau, K. Kersting, and C. Bauckhage. Yes We Can - Simplex Volume Maximization for Descriptive Web Scale Matrix Factorization. In CIKM, 2010.
  • C. Thurau, K. Kersting, M. Wahabzada, and C. Bauckhage. Convex non negative matrix factorization for massive datasets. Knowledge and Information Systems (KAIS), 2011.
  • C. Thurau, K. Kersting, M. Wahabzada, and C. Bauckhage. Descriptive matrix factorization for sustainability: Adopting the principle of opposites. Journal of Data Mining and Knowledge Discovery, 2011.