Clustering of Data with Missing Entries using Non-convex Fusion
  Penalties
  The presence of missing entries in data often creates challenges for pattern
recognition algorithms. Traditional algorithms for clustering data assume that
all the feature values are known for every data point. We propose a method to
cluster data in the presence of missing information. Unlike conventional
clustering techniques where every feature is known for each point, our
algorithm can handle cases where a few feature values are unknown for every
point. For this more challenging problem, we provide theoretical guarantees for
clustering using a $\ell_0$ fusion penalty based optimization problem.
Furthermore, we propose an algorithm to solve a relaxation of this problem
using saturating non-convex fusion penalties. It is observed that this
algorithm produces solutions that degrade gradually with an increase in the
fraction of missing feature values. We demonstrate the utility of the proposed
method using a simulated dataset, the Wine dataset and also an under-sampled
cardiac MRI dataset. It is shown that the proposed method is a promising
clustering technique for datasets with large fractions of missing entries.
