$k$-POD: A Method for $k$-Means Clustering of Missing Data
  The $k$-means algorithm is often used in clustering applications but its usage requires a complete data matrix. Missing data, however, is common in many applications. Mainstream approaches to clustering missing data reduce the missing data problem to a complete data formulation through either deletion or imputation but these solutions may incur significant costs. Our $k$-POD method presents a simple extension of $k$-means clustering for missing data that works even when the missingness mechanism is unknown, when external information is unavailable, and when there is significant missingness in the data. 
Jocelyn T. Chi, Eric C. Chi, Richard G. Baraniuk
stat.CO stat.ME