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)';