function novelindices = simplenovelty(K,Ktest,varargin)

%function novelindices = simplenovelty(K,Ktest,varargin)
%
% Performs novelty detection based on a sample stored in K,
% for test samples specified in Ktest
%
%INPUTS
% K = the training kernel matrix (ell x ell)
% Ktest = the test kernel matrix ((ell+1) x t), containing
%         the kernel evaluations between test sample j and
%         training sample i at position (i,j), and where the
%         last row contains the kernel evaluations of the
%         samples with themselves
% varargin = optional argument specifying the conficence;
%            if not specified, the default value of 0.01 is
%            used.
%
%OUTPUTS
% novelindices = a vector of size t indicating which test
%                samples are assumed to be novelties
%
%
%For more info, see www.kernel-methods.net


% K kernel matrix of training points
% inner products between ell training and t test points
%   stored in matrix Ktest of dimension (ell + 1) x t
%   last entry in each column is inner product with itself 
% confidence parameter
if ~isempty(varargin)
    delta = varargin{1};
else
    delta=0.01;
end

% first compute distances of data to centre of mass
% D is a row vector storing the column averages of K
% E is the average of all the entries of K
ell = size(K,1);
D = sum(K) / ell;
E = sum(D) / ell;
traindist2 = diag(K) - 2 * D' + E * ones(ell, 1);
maxdist = sqrt(max(traindist2));

% compute the estimation error of empirical centre of mass
esterr = sqrt(2*max(diag(K))/ell)*(sqrt(2) + sqrt(log(1/delta)));

% compute resulting threshold
threshold = maxdist + 2 * esterr;
threshold = threshold * threshold;

% now compute distances of test data
t = size(Ktest,2);
Dtest = sum(Ktest(1:ell,:)) / ell;
testdist2 = Ktest(ell+1,:) - 2 * Dtest + E * ones(1, t);

% indices of novel test points are now
novelindices = (testdist2 > threshold)';