function [f,d] = dualkmeans(K,N)

%function [f,d] = dualkmeans(K,N)
%
% Performs dual K-means for ell samples specified by the kernel K
%
%INPUTS
% K = the kernel matrix
% N = the number of clusters desired
%
%OUTPUTS
% f = the cluster allocation vector
% d = the distances of the samples to their respective cluster centroids
%
%
%For more info, see www.kernel-methods.net


% original kernel matrix stored in variable K
% clustering given by a ell x N binary matrix A
% and cluster allocation function f
% d gives the distances to cluster centroids
ell=size(K,1);
A = zeros(ell,N);
f = ceil(rand(ell,1)* N);
for i=1:ell
  A(i,f(i)) = 1;
end
change = 1;
while change == 1
  change = 0;
  E = A * diag(1./sum(A));
  Z = ones(ell,1)* diag(E'*K*E)'- 2*K*E;
  [d, ff] = min(Z, [], 2);
  for i=1:ell
   if f(i) ~= ff(i)
    A(i,ff(i)) = 1;
    A(i, f(i)) = 0;
    change = 1;
   end
  end
  f = ff;
end