Prof. Dr. Tobias Friedrich

Binary Matrix Factorization

MSc Seminar - Winter 2020/21

This lecture will be held virtually via Zoom. For this, it is important that all participants subscribe until 02 November 2020 to our course moodle. There we will announce all organizational details as well as the Zoom link. In case of problems with subscribing to our moodle, please get back to the lecture team via e-mail. Note that the moodle subscription is additionally required to the official course subscription via the Studienreferat and that the moodle subscription must be done before the first lecture on 03 November 2020 at 11:00.


The seminar will consist of students giving presentations about some recent results on the topic of binary matrix factorization (BMF). We will meet once a week (virtually). In the initial couple of lectures, we will give an overview of the topic and review some basics required for reading the papers. Each student presentation will be about 75 minutes on a topic from one of the papers below, followed by a 15 minutes discussion. The number of presentations per student will be determined on basis of the number of participants (maximum 3 per student). The presenting student is also required to prepare a 1-2 page handout for the audience and a 2-6 page summary of the presentation afterwards. The student should prepare the first draft of the presentation at least a couple of days before the date of presentation and discuss the presentation with us in a personal meeting.The grading will be 75% based on the presentation and the other 25% will be based on the handouts and the summary. The course will be conducted completely online.


Binary matrix factorization (BMF) is a topic having applications in the areas of data mining, machine learning, and bioinformatics and has been recently gathering attraction in the theoretical computer science community. In BMF, we are given a matrix \(A\in \{0,1\}^{m\times n}\) and a positive integer k, and we want to find matrices \(U\in \{0,1\} ^{m\times k}\) and \(V\in \{0,1\}^{k\times n}\) such that \(||A-U\boldsymbol\cdot V||_p\) is minimized for some \(p\ge 0\). Depending on the choice of the arithmetic for the multiplication \(U\boldsymbol\cdot V\) and the choice of the norm \(||\dots ||_p\), we obtain different problems. The most commonly used arithmetics are boolean arithmetic, standard integer arithmetic and GF(2) arithmetic, and the most commonly used norms are \(\ell_0,\ell_1\) and \(\ell_2\). 


There are no formal requirements, but we expect the students to have the ability to read and understand mathematically involved proofs.

List of papers

Here is a prelliminary list of papers from which the results to be presented will be selected:

  1. Approximation Schemes for Low-Rank Binary Matrix Approximation Problems. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov,  Fahad Panolan and Saket Saurabh. TALG 2019.
  2. A PTAS for ℓp-Low Rank Approximation. Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee and David P. Woodruff. SODA 2019.

  3. Faster Algorithms for Binary Matrix Factorization. Ravi Kumar, Rina Panigrahy, Ali Rahimi, David Woodruff . ICML 2019.

  4. Parameterized Low-Rank Binary Matrix Approximation. Fedor V. Fomin, Petr A. Golovach, Fahad Panolan. ICALP 2018.

  5. Streaming PTAS for Binary 0-Low Rank Approximation. Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. 2019.


We meet weekly tuesdays, 11:00-12:30.