Is k-means clustering guaranteed to converge if using Manhattan distance?

Question

The k-means algorithm is an iterative clustering algorithm that partitions the data points into K clusters (with centroids {$\mu_1, ... , \mu_k$}, minimizing the Sum-of-Squared-Error:

$$ SSE = \sum_{i=1}^K \sum_{x \in S_i} ||x -\mu_i ||^2 $$

K-means uses Euclidean distance (L2 norm) as the distance function , that is $D_{euclidean}= \|(X-Y)\|^2=\sqrt{(x_1-y_1)^2 + ... + (x_n-y_n)^2}$.

My question: If I use Manhattan distance (L1 norm) is used instead of euclidean, is there any guarantee that the algorithm still minimizes SSE? If not, which function is minimized if L1 norm is used?

EDIT: Below is a picture that demonstrates how a 2-D space is partitioned using L1 and L2 norms:

Thanks

Answer 1

The $L_1$ norm has a big flaw:

try to apply $K$-clustering in a 2d space, with 2 centroids. When you have to say which points are near to which centroid there's a high grade of uncertainty, since the surface wiht the same distance from both centroids has infinite (lebesgue) measure. (on the contrary, euclidean distance has only a line, so a 0-measure set).

So the algorithm isn't really well-defined, and it could not finish with any function