-
Notifications
You must be signed in to change notification settings - Fork 7
/
ncut.m
97 lines (84 loc) · 2.87 KB
/
ncut.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
function [Eigenvectors,Eigenvalues] = ncut(W,nbEigenValues,dataNcut);
% function [Eigenvectors,Eigenvalues] = ncut(W,nbEigenValues,dataNcut);
%
% Input:
% W= symmetric similarity matrix
% nbEigenValues= number of Ncut eigenvectors computed
% dataNcut= optional parameters
%
% default parameters for dataNcut:
% dataNcut.offset = 5e-1; offset in the diagonal of W
% dataNcut.verbose = 0; 0 for verbose off mode, 1,2,3 for verbose on modes
% dataNcut.maxiterations = 100; max number of iterations in eigensolver
% dataNcut.eigsErrorTolerance = 1e-6; error tolerance in eigensolver
% dataNcut.valeurMin=1e-6; % truncates any values in W less than valeurMin
%
% Output:
% Eigenvectors= continuouse Ncut eigenvectos, size = length(W) x nbEigenValues
% Eigenvalues= Ncut eigenvalues, size = 1x nbEigenValues
%
% Timothee Cour, Stella Yu, Jianbo Shi, 2004.
if nargin < 2
nbEigenValues = 8;
end
if nargin < 3
dataNcut.offset = 5e-1;
dataNcut.verbose = 0;
dataNcut.maxiterations = 300;
dataNcut.eigsErrorTolerance = 1e-8;
dataNcut.valeurMin=1e-6;
end
% if nargin < 3
% dataNcut.offset = 5e-1;
% dataNcut.verbose = 0;
% dataNcut.maxiterations = 100;
% dataNcut.eigsErrorTolerance = 1e-6;
% dataNcut.valeurMin=1e-6;
% end
% make W matrix sparse
W = sparsifyc(W,dataNcut.valeurMin);
% check for matrix symmetry
if max(max(abs(W-W'))) > 1e-10 %voir (-12)
%disp(max(max(abs(W-W'))));
error('W not symmetric');
end
n = size(W,1);
nbEigenValues = min(nbEigenValues,n);
offset = dataNcut.offset;
% degrees and regularization
d = sum(abs(W),2);
dr = 0.5 * (d - sum(W,2));
d = d + offset * 2;
dr = dr + offset;
W = W + spdiags(dr,0,n,n);
Dinvsqrt = 1./sqrt(d+eps);
P = spmtimesd(W,Dinvsqrt,Dinvsqrt);
clear W;
options.issym = 1;
if dataNcut.verbose
options.disp = 3;
else
options.disp = 0;
end
options.maxit = dataNcut.maxiterations;
options.tol = dataNcut.eigsErrorTolerance;
options.v0 = ones(size(P,1),1);
options.p = max(35,2*nbEigenValues); %voir
options.p = min(options.p,n);
%warning off
%[vbar,s,convergence] = eigs2(@mex_w_times_x_symmetric,size(P,1),nbEigenValues,'LA',options,tril(P));
[vbar,s,convergence] = eigs(@mex_w_times_x_symmetric,size(P,1),nbEigenValues,'LA',options,tril(P));
%[vbar,s,convergence] = eigs_new(@mex_w_times_x_symmetric,size(P,1),nbEigenValues+1,'LA',options,tril(P)); % used by defaut
%warning on
s = real(diag(s));
[x,y] = sort(-s);
Eigenvalues = -x;
vbar = vbar(:,y);
vbar = vbar(:,1:nbEigenValues); %by Pan
Eigenvectors = spdiags(Dinvsqrt,0,n,n) * vbar;
for i=1:size(Eigenvectors,2)
Eigenvectors(:,i) = (Eigenvectors(:,i) / norm(Eigenvectors(:,i)) )*norm(ones(n,1));
if Eigenvectors(1,i)~=0
Eigenvectors(:,i) = - Eigenvectors(:,i) * sign(Eigenvectors(1,i));
end
end