# Finding the largest low-rank clusters with Ky Fan 2-k-norm and ℓ1-norm

arXiv: https://arxiv.org/abs/1403.5901 · HTML: https://mlsanity.com/paper/1403.5901/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2014.

## Built on by (most cited first, 2 of 2)

- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Low-Rank Tensor Completion Based on Fractional Regularization with Ky Fan p-k Norm](https://mlsanity.com/paper/2606.19046/) (2026)

## Abstract (arXiv)

We propose a convex optimization formulation with the Ky Fan 2-k-norm and ℓ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.