  Mining and exploring databases should provide users with knowledge and new
insights. Tiles of data strive to unveil true underlying structure and
distinguish valuable information from various kinds of noise. We propose a
novel Boolean matrix factorization algorithm to solve the tiling problem, based
on recent results from optimization theory. In contrast to existing work, the
new algorithm minimizes the description length of the resulting factorization.
This approach is well known for model selection and data compression, but not
for finding suitable factorizations via numerical optimization. We demonstrate
the superior robustness of the new approach in the presence of several kinds of
noise and types of underlying structure. Moreover, our general framework can
work with any cost measure having a suitable real-valued relaxation. Thereby,
no convexity assumptions have to be met. The experimental results on synthetic
data and image data show that the new method identifies interpretable patterns
which explain the data almost always better than the competing algorithms.
