Clustered matrix approximations: Test 1

Symmetric matrix A, with dense diagonal block structure

Contents

Load data

clear
% Load partial LiveJournal data
load('lj-partial')

Clustering with GRACLUS

% Number of clusters
noc = 20;
[prt,obj] = graclus(A,noc);

% Reorder vertices
[ind,prtsz,prtc] = reorderVertices(prt);

% Visualize clustering structure of A
spy(A(ind,ind))

----------------------------------------------------------------------
 Graclus 1.2 Copyright 2008, Brian Kulis and Yuqiang Guan 

Graph Information:
  #Vertices: 55692, #Edges: 3262654, #Clusters: 20
#local search steps: 0

Normalized-Cut... 
   Cut value: 0.583963, Balance:  2.44 

Timing Information:
  I/O:          		   0.033
  Clustering:   		   0.957   (Graclus time)
  Total:        		   1.012
----------------------------------------------------------------------

Plot sorted block sizes

% sort and plot block sizes
ssz = sort(prtsz,'descend');
plot(ssz,'r-o')
title('Sorted block sizes')
grid on

Fraction of non-zeros within diagonal blocks

[nnzBlks, nnzBlFr, nnzFrac] = compClustNnz(A,prtc);
bar3custom(nnzBlFr)
title(['Fraction of non-zeros in blocks A_{ij},  ', num2str(nnzFrac), ...
    ' % in all diagonal blocks'])

% Relative error due to clustering: || A - diag(A11,...,Acc) || / || A ||
relerr = compClustRelErr(A,prtc);
fprintf('Fraction of non-zeros in diagonal blocks  : %8.2f %% \n', nnzFrac)
fprintf('Relative error in a block diagonal approx.: %8.2f %% \n', relerr)

Fraction of non-zeros in diagonal blocks  :    97.29 % 
Relative error in a block diagonal approx.:    16.47 % 

Compute clustered matrix approximatons

% Specify rank k for approximations of diagonal blocks
k = 20;

% Or use different ranks for different blocks
%k = [2,3,4,5,6,2,3,4,5,6,2,3,4,5,6,2,3,4,5,6]';

% Compute approximations for diagonal blocks of a symmetric matrix
[V,D] = clustEigs(A,prtc,k,'eigs');

% if laneig is available and prefered
%[V,D] = clustEigs(A,prtc,k,'laneig');

Compute core matrix

% Compute the core matrix to get an approximation of entire A, i.e.
% A \approx V*DD*V'
DD = compCoreSymFull(A,V,D,prtc,'diag');

Compute relative error in % of clustered matrix approximation

nA  = norm(A,'fro');
relerrCmapp = sqrt( nA^2 - norm(DD,'fro')^2 )/nA*100;

% Compute memory consumption
memCmapp = memUsageCmapp(V,DD,[],'sym');

% Get rank k for a regular matrix approximation with = or > memory usage
m = size(A,1);
[memRmapp,kreg] = memUsageRmapp(m,[],memCmapp,'sym');

[Vr,Dr] = eigs(A,kreg);
relerrRmapp = sqrt( nA^2 - norm(Dr,'fro')^2 )/nA*100;

% fpns = floating point numbers
disp('-------------------------------------------------------------------')
fprintf('Clustered matrix approximation: relErr    = %10.2f %% \n', relerrCmapp)
fprintf('Regular   matrix approximation: relErr    = %10.2f %% \n', relerrRmapp)
disp('-------------------------------------------------------------------')
fprintf('Clustered matrix approximation: memUsage  = %10.0f fpns \n', memCmapp)
fprintf('Regular   matrix approximation: memUsage  = %10.0f fpns \n', memRmapp)
disp('-------------------------------------------------------------------')

-------------------------------------------------------------------
Clustered matrix approximation: relErr    =      52.56 % 
Regular   matrix approximation: relErr    =      78.40 % 
-------------------------------------------------------------------
Clustered matrix approximation: memUsage  =    1193640 fpns 
Regular   matrix approximation: memUsage  =    1225246 fpns 
-------------------------------------------------------------------

Compute cosines of principal angles

% Compute angles for column space matrices
angCol = compSubspaceAngles(Vr,V,prtc);

clf
plot(angCol,'b-o')
grid on
title('Cosines of principal angles between clustered and regular approximation subspaces')
legend('Column space matrices','location','SouthWest')
xlim([1,kreg])

Published with MATLAB® R2014b