Download All

Code covered by the BSD License  

Highlights from
Statistical Learning Toolbox

from Statistical Learning Toolbox by Dahua Lin
Functions for statistical learning, pattern recognition and computer vision, covering many topics.

Description of sllemap
Home > sltoolbox > manifold > sllemap.m

sllemap

PURPOSE ^

SLLEMAP Solves Laplacian Eigenmap Embedding

SYNOPSIS ^

function [Y, spectrum] = sllemap(G, d, sch)

DESCRIPTION ^

SLLEMAP Solves Laplacian Eigenmap Embedding

 $ Syntax $
   - Y = sllemap(G, d)
   - Y = sllemap(G, d, sch)
   - [Y, spectrum] = sllemap(...)

 $ Arguments $
   - G:        The affinity graph (in any acceptable form): n x n
   - d:        The embedding dimension
   - sch:      The scheme to use
   - Y:        The solved embedded coordinates (d x n)

 $ Description $
   - Y = sllemap(G, d) uses the default scheme to solve the Laplacian
     Eigenmap embedding in a d-dimensional space.

   - Y = sllemap(G, d, sch) uses the specified scheme to solve the 
     Laplacian Eigenmap embedding in a d-dimensional space.

     Three schemes are implemented to resolve the problem, they are
     under three different formulations:
       (1) 'minLI':
           objective: minimize sum_ij w_ij ||y_i - y_j||^2
                      s.t. forall i, ||y_i||^2 = 1
           in matrix form, it is expressed as:
               minimize y^T * L * y,  s.t. y^T * y = 1
       (2) 'minLD': 
           objective: minimize sum_ij w_ij ||y_i - y_j||^2
                      s.t. forall i, d_ii ||y_i||^2 = 1
           in matrix form, it is expressed as:
               minimize y^T * L * y, s.t. y^T * D * y = 1
           This is the original formulation in many papers in the fields
           of spectral learning, clustering and manifold learning.
       (3) 'maxWD': (default)
           objective: maximize sum_ij w_ij <y_i, y_j>
                      s.t. forall i, d_ii ||y_i||^2 = 1
           in matrix form, it is expressed as:
               maximize y^T * W * y, s.t. y^T * D * y = 1
           In theory, this objective is equivalent to 'minLD'. However,
           due to that its implementation is based on finding the 
           eigenvectors corresponding to the largest eigenvalues instead
           of the smallest ones, thus it is much more efficient and
           numerically stable. Hence, it is selected as the default
           scheme.

   - [Y, spectrum] = sllemap(...) additionally outputs the spectrum 
     of the embedding. The definition of the spectrum varies for different
     schemes:
     'minLI': the spectrum is the eigenvalues of L, in ascending order
     'minLD': the spectrum is the eigenvalues of D^(-1/2) * L * D^(-1/2),
              in ascending order
     'maxWD': the spectrum is the eigenvalues of D^(-1/2) * W * D^(-1/2),
              in descending order.

 $ Remarks $
   - If the input graph does not have edge values or it is logical, 
     it just assume 1 between neighboring samples and 0 for other pairs.

   - The embedding dimension d should be strictly less than the number
     of samples n.

 $ History $
   - Created by Dahua Lin, on Sep 12nd, 2006

CROSS-REFERENCE INFORMATION ^

This function calls:
  • slmulrowcols SLMULROWCOLS Multiplies the vectors to all rows and all columns
  • slmulvec SLMULVEC multiplies a vector to columns or rows of a matrix
  • slsymeig SLSYMEIG Compute the eigenvalues and eigenvectors for symmetric matrix
  • sladjmat SLADJMAT Constructs the adjacency matrix representation of a graph
  • slgraphinfo SLGRAPHINFO Extracts basic information of a given graph representation
  • raise_lackinput RAISE_LACKINPUT Raises an error indicating lack of input argument
This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function [Y, spectrum] = sllemap(G, d, sch)
0002 %SLLEMAP Solves Laplacian Eigenmap Embedding
0003 %
0004 % $ Syntax $
0005 %   - Y = sllemap(G, d)
0006 %   - Y = sllemap(G, d, sch)
0007 %   - [Y, spectrum] = sllemap(...)
0008 %
0009 % $ Arguments $
0010 %   - G:        The affinity graph (in any acceptable form): n x n
0011 %   - d:        The embedding dimension
0012 %   - sch:      The scheme to use
0013 %   - Y:        The solved embedded coordinates (d x n)
0014 %
0015 % $ Description $
0016 %   - Y = sllemap(G, d) uses the default scheme to solve the Laplacian
0017 %     Eigenmap embedding in a d-dimensional space.
0018 %
0019 %   - Y = sllemap(G, d, sch) uses the specified scheme to solve the
0020 %     Laplacian Eigenmap embedding in a d-dimensional space.
0021 %
0022 %     Three schemes are implemented to resolve the problem, they are
0023 %     under three different formulations:
0024 %       (1) 'minLI':
0025 %           objective: minimize sum_ij w_ij ||y_i - y_j||^2
0026 %                      s.t. forall i, ||y_i||^2 = 1
0027 %           in matrix form, it is expressed as:
0028 %               minimize y^T * L * y,  s.t. y^T * y = 1
0029 %       (2) 'minLD':
0030 %           objective: minimize sum_ij w_ij ||y_i - y_j||^2
0031 %                      s.t. forall i, d_ii ||y_i||^2 = 1
0032 %           in matrix form, it is expressed as:
0033 %               minimize y^T * L * y, s.t. y^T * D * y = 1
0034 %           This is the original formulation in many papers in the fields
0035 %           of spectral learning, clustering and manifold learning.
0036 %       (3) 'maxWD': (default)
0037 %           objective: maximize sum_ij w_ij <y_i, y_j>
0038 %                      s.t. forall i, d_ii ||y_i||^2 = 1
0039 %           in matrix form, it is expressed as:
0040 %               maximize y^T * W * y, s.t. y^T * D * y = 1
0041 %           In theory, this objective is equivalent to 'minLD'. However,
0042 %           due to that its implementation is based on finding the
0043 %           eigenvectors corresponding to the largest eigenvalues instead
0044 %           of the smallest ones, thus it is much more efficient and
0045 %           numerically stable. Hence, it is selected as the default
0046 %           scheme.
0047 %
0048 %   - [Y, spectrum] = sllemap(...) additionally outputs the spectrum
0049 %     of the embedding. The definition of the spectrum varies for different
0050 %     schemes:
0051 %     'minLI': the spectrum is the eigenvalues of L, in ascending order
0052 %     'minLD': the spectrum is the eigenvalues of D^(-1/2) * L * D^(-1/2),
0053 %              in ascending order
0054 %     'maxWD': the spectrum is the eigenvalues of D^(-1/2) * W * D^(-1/2),
0055 %              in descending order.
0056 %
0057 % $ Remarks $
0058 %   - If the input graph does not have edge values or it is logical,
0059 %     it just assume 1 between neighboring samples and 0 for other pairs.
0060 %
0061 %   - The embedding dimension d should be strictly less than the number
0062 %     of samples n.
0063 %
0064 % $ History $
0065 %   - Created by Dahua Lin, on Sep 12nd, 2006
0066 %
0067 
0068 %% parse and verify input arguments
0069 
0070 if nargin < 2
0071     raise_lackinput('sllemap', 2);
0072 end
0073 
0074 gi = slgraphinfo(G, {'square'});
0075 n = gi.n;
0076 if strcmp(gi, 'adjmat')
0077     if isnumeric(G)
0078         W = G;
0079     else
0080         W = double(G);
0081     end
0082 else
0083     W = sladjmat(G);
0084 end
0085 
0086 if d >= n
0087     error('sltoolbox:invalidarg', ...
0088         'The embeded dimension d should be strictly less than n');
0089 end
0090 
0091 if nargin < 3 || isempty(sch)
0092     sch = 'maxWD';
0093 end
0094 
0095 %% main delegation
0096 
0097 % L = Di + Dj - Wij - Wji
0098 % we let
0099 %   W = Wij + Wji
0100 %   D = Di + Dj = diag(diag(W))
0101 %   L = D - W
0102 W = W + W';
0103 
0104 switch sch
0105     case 'maxWD'
0106         [Y, spectrum] = solve_maxWD(W, d);
0107     case 'minLD'
0108         [Y, spectrum] = solve_minLD(W, d);
0109     case 'minLI'
0110         [Y, spectrum] = solve_minLI(W, d);
0111     otherwise
0112         error('sltoolbox:invalidarg', ...
0113             'Invalid scheme for solving eigenmap: %s', sch);
0114 end
0115 
0116 %% Core functions
0117 
0118 function [Y, spectrum] = solve_maxWD(W, d)
0119 
0120 vD = calcDv(W);
0121 W = calcNormalizeMat(W, vD);
0122 
0123 [spectrum, Y] = slsymeig(W, d+1, 'descend');
0124 spectrum = spectrum(2:d+1);
0125 Y = Y(:, 2:d+1)';
0126 Y = denormY(Y, vD);
0127 
0128 function [Y, spectrum] = solve_minLD(W, d)
0129 
0130 vD = calcDv(W);
0131 L = calcL(vD, W);
0132 L = calcNormalizeMat(L, vD);
0133 
0134 [spectrum, Y] = slsymeig(L, d+1, 'ascend');
0135 spectrum = spectrum(2:d+1);
0136 Y = Y(:, 2:d+1)';
0137 Y = denormY(Y, vD);
0138 
0139 
0140 function [Y, spectrum] = solve_minLI(W, d)
0141 
0142 vD = calcDv(W);
0143 L = calcL(vD, W);
0144 
0145 [spectrum, Y] = slsymeig(L, d+1, 'ascend');
0146 spectrum = spectrum(2:d+1);
0147 Y = Y(:, 2:d+1)';
0148 
0149 
0150 %% Computation routines
0151 
0152 function vD = calcDv(W)
0153 
0154 vD = sum(W, 1)';
0155 
0156 function L = calcL(vD, W)
0157 
0158 n = length(vD);
0159 if issparse(W)
0160     D = sparse((1:n)', (1:n)', vD, n, n, n);
0161     L = D - W;
0162 else
0163     L = -W;
0164     dinds = (1:n)'*(n+1) - n;
0165     L(dinds) = L(dinds) + vD;
0166 end
0167 
0168 function Mn = calcNormalizeMat(M, vD)
0169 
0170 vD(vD < eps) = eps;
0171 cv = 1 ./ sqrt(vD);
0172 
0173 if issparse(M)
0174     n = size(M,1);
0175     Mn = M;
0176     for i = 1 : n
0177         Mn(:,i) = Mn(:,i) * cv(i);
0178     end
0179     for i = 1 : n
0180         Mn(i,:) = Mn(i,:) * cv(i);
0181     end
0182 else    
0183     rv = cv';
0184     Mn = slmulrowcols(M, rv, cv);
0185 end
0186 
0187 function Y = denormY(Y, vD)
0188 
0189 vD = vD';
0190 vD(vD < eps) = eps;
0191 Y = slmulvec(Y, 1 ./ sqrt(vD), 2);
0192 
0193 
0194 
0195
Generated on Wed 20-Sep-2006 12:43:11 by m2html © 2003

Contact us at files@mathworks.com