Multiclass Total Variation Clustering

Many clustering models rely on the minimization of an energy over possible partitions of the data set. These discrete optimizations usually pose NPhard problems, however. A natural resolution of this issue involves relaxing the discrete minimization space into a continuous one to obtain an easier minimization procedure. Many current algorithms, such as spectral clustering methods or nonnegative matrix factorization (NMF) methods, follow this relaxation approach. A fundamental problem arises when using this approach, however; in general the solution of the relaxed continuous problem and that of the discrete NPhard problem can differ substantially.