Finding the largest low-rank clusters with Ky Fan $2$-$k$-norm and ${\ell }_1$-norm

Abstract

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.

References in corpus (2)

• Clustered Multi-Task Learning: A Convex Formulation
• Sparse Prediction with the $k$-Support Norm

Cited by in corpus (1)

• On Approximating Functions of the Singular Values in a Stream