Optimization Online


Finding the largest low-rank clusters with Ky Fan 2-k-norm and l1-norm

Xuan Vinh Doan(Xuan.Doan***at***wbs.ac.uk)
Stephen Vavasis(vavasis***at***math.uwaterloo.ca)

Abstract: We propose a convex optimization formulation with the Ky Fan 2-k-norm and l1-norm to fi nd 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.

Keywords: low-rank clustering, Ky Fan 2-k-norm, nonnegative matrix factorization

Category 1: Applications -- Science and Engineering (Data-Mining )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 03/24/2014
Entry Accepted: 03/24/2014
Entry Last Modified: 03/24/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society