compute_non_linear_dim_reduction.m
174be80e92admaster

compute_non_linear_dim_reduction.m
View Options


			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			% Author:
			% Xavier Bresson, xavier.bresson@epfl.ch
			%
			% Course:
			% A Network Tour of Data Science
			% a.k.a. Graph Algorithms in Data Science
			% EPFL, Fall 2015
			%
			% Version:
			% September 23, 2015
			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			% Non-linear dimensionality reduction technique:
			% Belkin-Niyogi, Laplacian eigenmaps for dimensionality reduction and
			% data representation, 2003
			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			% Usages:
			% [X,Y,Z] = compute_non_linear_dim_reduction(W)
			%
			% Notations:
			% n = nb_data
			%
			% Input variables:
			% W = Adjacency matrix. Size = n x n.
			%
			% Output variables:
			% X = 1st data coordinates in low-dim manifold. Size n x 1.
			% Y = 2nd data coordinates in low-dim manifold. Size n x 1.
			% Z = 3rd data coordinates in low-dim manifold. Size n x 1.
			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

			function [X,Y,Z] = compute_non_linear_dim_reduction(W)

			tstart = tic;

			% Compute normalized graph Laplacian
			L = compute_graph_laplacian(W);

			% Regularization for ill-posed graphs
			L = L + 1e-6* speye(size(L));

			% Compute the first three Laplacian Eigenmaps
			opts.disp = 0;
			[V,E] = eigs(L,4,'SM',opts);

			% Sort eigenvalue from smallest to largest values
			E = diag(E);
			[~,idx] = sort(E,'ascend');
			E = E(idx);

			% Coordinates of graph vertices in the low-dim embedding manifold
			V = V(:,idx);
			X = V(:,2);
			Y = V(:,3);
			Z = V(:,4);

			fprintf('\nComputational time for non-linear dim reduction (sec) = %.3f\n\n',toc(tstart));

			end