We propose a novel Boolean matrix factorization algorithm, based on recent results from optimization theory. We demonstrate the superior robustness of the new approach in the presence of several kinds of noise and the interpretability on synthetic and real-world data. Given the task to explore binary data, Boolean Matrix Factorization (BMF) is a method of choice. BMF yields a simultaneous clustering of rows and columns of the data matrix into binary, thus interpretable, cluster representatives. Furthermore, state-of-the art methods automatically estimate the number of prevalent clusters through the application of the minimum description length principle [2]. Unfortunately, existing algorithms are greedy and rely on heuristics to solve the NPhard problem of BMF. We propose with the Picture Factorization 1 procedure Primp to apply the optimization scheme PALM to a real-valued relaxation of the objective. PALM enables the minimization of the generally nonconvex description Factorization 2 Factorization 3 length and the nonsmooth penalization of non-binary values under convergence guarantees. A rounding procedure rounds the result to binary values and decides over the number of returned clusters. For more information, we refer to [1].