  We propose a convex optimization formulation with the Ky Fan $2$-$k$-norm and
$\ell_1$-norm to find $k$ largest approximately rank-one submatrix blocks of a
given nonnegative matrix that has low-rank block diagonal structure with noise.
We analyze low-rank and sparsity structures of the optimal solutions using
properties of these two matrix norms. We show that, under certain hypotheses,
with high probability, the approach can recover rank-one submatrix blocks even
when they are corrupted with random noise and inserted into a much larger
matrix with other random noise blocks.
