Sample and Expand: Discovering Low-rank Submatrices With Quality Guarantees

Martino Ciaperoni, Aristides Gionis, Heikki Mannila

The problem of approximating a matrix by a low-rank one has been extensively studied. This problem assumes, however, that the whole matrix has a low-rank structure. This assumption…