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 sllocalcoordalign
Home > sltoolbox > manifold > sllocalcoordalign.m

sllocalcoordalign

PURPOSE ^

SLLOCALCOORDALIGN Performs optimal local coordinate alignment

SYNOPSIS ^

function [GC, spectrum, LT] = sllocalcoordalign(GM, LC, dg)

DESCRIPTION ^

SLLOCALCOORDALIGN Performs optimal local coordinate alignment

 $ Syntax $
   - [GC, spectrum, LT] = sllocalcoordalign(GM, LC)
   - [GC, spectrum, LT] = sllocalcoordalign(GM, LC, dg)
   - [GC, spectrum] = sllocalcoordalign(...)

 $ Arguments $
   - GM:       The index map graph (n x n)
   - LC:       The matrix of all local coordinates (dl x nnz)
   - GC:       The global coordinates in the embedding  (dg x n)
   - spectrum: The eigenvalues of the embedding dimensions
   - LT:       The local transforms of all local models (dl x dg x n)

 $ Description $
   - [GC, spectrum, LT] = sllocalcoordalign(GM, LC) performs optimal 
     coordinate alignment in terms of minimizing L2 reconstruction error. 
     This process will simultaneously resolves the optimal configuration 
     of global coordinates in the embedded space and learns the linear
     transforms for all sets of local coordinates to the global 
     coordinate. By default the dimension of the global embedding will be
     set to the same as the local dimension dl.
     The GM is a neighborhood graph, with the neighborhood of each target
     sample represented by the source nodes of the corresponding target
     node. The value of the edges give the index of columns of the local
     coordinates in LC. That is to say, LC stores all local coordinate
     vectors obtained by applying each target model to its neighboring
     samples and they are sorted according to the order of elements in 
     GM. (GM should be a valued adjacency matrix)

   - [GC, spectrum, LT] = sllocalcoordalign(GM, LC, dg) performs local 
     coordinate alignment to a global embedding of the specified dimension 
     dg.

   - [GC, spectrum] = sllocalcoordalign(...) only pursues the global 
     embedding coordinate without the need of learning local transforms.

 $ History $
   - Created by Dahua Lin, on Sep 14, 2006

CROSS-REFERENCE INFORMATION ^

This function calls:
  • sladdrowcols SLADDROWCOLS Adds the vectors to all rows and all columns
  • sladdvec SLADDVEC adds a vector to columns or rows of a matrix
  • slsymeig SLSYMEIG Compute the eigenvalues and eigenvectors for symmetric matrix
  • 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:
  • slltsa SLLTSA Performs Local Tangent Space Alignment Learning

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function [GC, spectrum, LT] = sllocalcoordalign(GM, LC, dg)
0002 %SLLOCALCOORDALIGN Performs optimal local coordinate alignment
0003 %
0004 % $ Syntax $
0005 %   - [GC, spectrum, LT] = sllocalcoordalign(GM, LC)
0006 %   - [GC, spectrum, LT] = sllocalcoordalign(GM, LC, dg)
0007 %   - [GC, spectrum] = sllocalcoordalign(...)
0008 %
0009 % $ Arguments $
0010 %   - GM:       The index map graph (n x n)
0011 %   - LC:       The matrix of all local coordinates (dl x nnz)
0012 %   - GC:       The global coordinates in the embedding  (dg x n)
0013 %   - spectrum: The eigenvalues of the embedding dimensions
0014 %   - LT:       The local transforms of all local models (dl x dg x n)
0015 %
0016 % $ Description $
0017 %   - [GC, spectrum, LT] = sllocalcoordalign(GM, LC) performs optimal
0018 %     coordinate alignment in terms of minimizing L2 reconstruction error.
0019 %     This process will simultaneously resolves the optimal configuration
0020 %     of global coordinates in the embedded space and learns the linear
0021 %     transforms for all sets of local coordinates to the global
0022 %     coordinate. By default the dimension of the global embedding will be
0023 %     set to the same as the local dimension dl.
0024 %     The GM is a neighborhood graph, with the neighborhood of each target
0025 %     sample represented by the source nodes of the corresponding target
0026 %     node. The value of the edges give the index of columns of the local
0027 %     coordinates in LC. That is to say, LC stores all local coordinate
0028 %     vectors obtained by applying each target model to its neighboring
0029 %     samples and they are sorted according to the order of elements in
0030 %     GM. (GM should be a valued adjacency matrix)
0031 %
0032 %   - [GC, spectrum, LT] = sllocalcoordalign(GM, LC, dg) performs local
0033 %     coordinate alignment to a global embedding of the specified dimension
0034 %     dg.
0035 %
0036 %   - [GC, spectrum] = sllocalcoordalign(...) only pursues the global
0037 %     embedding coordinate without the need of learning local transforms.
0038 %
0039 % $ History $
0040 %   - Created by Dahua Lin, on Sep 14, 2006
0041 %
0042 
0043 %% parse and verify input arguments
0044 
0045 if nargin < 2
0046     raise_lackinput('sllocalcoordalign', 2);
0047 end
0048 
0049 gi = slgraphinfo(GM, {'adjmat', 'square', 'numeric'});
0050 n = gi.n;
0051 
0052 if ~isnumeric(LC) || ndims(LC) ~= 2
0053     error('sltoolbox:invalidarg', ...
0054         'LC should be a 2D numeric matrix');
0055 end
0056 [dl, ny] = size(LC);
0057 if ny ~= nnz(GM)
0058     error('sltoolbox:invalidarg', ...
0059         'The number of samples in LC does not match the non-zero entries in GM');
0060 end
0061 
0062 if nargin < 3
0063     dg = dl;
0064 end
0065 
0066 if nargout >= 3
0067     learnLT = true;
0068 else
0069     learnLT = false;
0070 end
0071 
0072 
0073 %% Pursue optimal embedding (global coordinates)
0074 
0075 % prepare data structure
0076 B = prepareBmat(GM, n);
0077 if learnLT
0078     LRs = cell(n, 1);
0079 end
0080 
0081 % construct W matrices
0082 
0083 for i = 1 : n
0084     
0085     % get local coords
0086     cinds = find(GM(:,i));
0087     curlc = LC(:, GM(cinds, i));
0088     
0089     % decompose
0090     cn = size(curlc, 2);
0091     [cu, cs, cv] = svd(curlc, 0);
0092     
0093     %decide rank
0094     cs = diag(cs);
0095     rk = max(sum(cs > eps(cs(1)) * cn), 1);
0096     
0097     % compute W, M and add it to B
0098     if rk < cn              % note that when rk == cn, the contribution of current model is zero
0099         cv = cv(:, 1:rk);
0100         W = eye(cn) - cv * cv';     % note that for W = I - VV^T, it always has that W = W * W
0101         vm = sum(W, 1) / cn;
0102         M = sladdrowcols(W, -vm, -vm') + sum(vm) / cn; 
0103         B(cinds, cinds) = B(cinds, cinds) + M;                
0104     end
0105     
0106     % prepare for learning local transforms (make use of u, s, v, so that
0107     % we need not to do svd again
0108     if learnLT
0109         cLTR = compute_pinv(cu(:, 1:rk), cs(1:rk), cv);
0110         LRs{i} = sladdvec(cLTR, -sum(cLTR, 1)/cn);
0111     end
0112     
0113 end
0114 
0115 % post process B
0116 B = postprocessBmat(B);
0117 
0118 % solve eigen-problem of B
0119 [spectrum, GC] = slsymeig(B, dg+1, 'ascend');
0120 spectrum = spectrum(2:dg+1);
0121 GC = GC(:, 2:dg+1)';
0122 
0123 
0124 %% Learn the local transforms
0125 LT = zeros(dl, dg, n);
0126 
0127 if learnLT
0128     for i = 1 : n
0129         cLR = LRs{i};            
0130         cGC = GC(:, GM(:,i) ~= 0);
0131         cLT = cGC * cLR;
0132         LT(:,:,i) = cLT;
0133     end    
0134 end
0135 
0136 
0137 
0138 
0139 %% Auxiliary functions
0140 
0141 function B = prepareBmat(GM, n)
0142 % estimate the number of non-zeros in B and prepare the most efficient
0143 % storage.
0144 % The strategy is
0145 %   first allocate a logical array to record which elements may possibly
0146 %   be set to zeros
0147 % Then according to nnz,
0148 %   if nnz > n * n / 4, use full matrix, make an n x n zeros
0149 %   otherwise use sparse matrix, make with all elements that would be used
0150 %   set to 1 first. After all computation, these ones should be reduced
0151 %   using postprocessBmat
0152 %
0153 
0154 % estimate the maximum number of non-zeros
0155 nnzb = 0;
0156 for i = 1 : n
0157     cnnb = nnz(GM(:,i));
0158     nnzb = nnzb + cnnb * cnnb;
0159 end
0160 nnzb = min(nnzb, n * n);
0161 
0162 % prepare the indicator matrix
0163 if n * n > nnzb * 20
0164     Z = sparse(1, 1, false, n, n, nnzb);
0165 else
0166     Z = false(n, n);
0167 end
0168 
0169 % set the indicators
0170 for i = 1 : n
0171     cinds = find(GM(:,i));
0172     Z(cinds, cinds) = 1;
0173 end
0174 
0175 % re-estimate the nnz accurately
0176 nnzb = nnz(Z);
0177 
0178 % make B
0179 if n * n > nnzb * 4
0180     B = zeros(n, n);
0181 else
0182     [I, J] = find(Z);    
0183     B = sparse(I, J, 1, n, n);
0184 end
0185 
0186 
0187 function B = postprocessBmat(B)
0188 
0189 if issparse(B)
0190     B = spfun(@(x) x - 1, B);
0191 end
0192 
0193 
0194 function R = compute_pinv(u, s, v)
0195 
0196 R = v * diag(1 ./ s) * u';
0197 
0198     
0199 
0200 
0201 
0202 
0203 
0204     
0205     
0206 
0207 
0208 
0209     
0210     
0211 
0212 
0213 
0214 
0215 
0216 
0217
Generated on Wed 20-Sep-2006 12:43:11 by m2html © 2003

Contact us at files@mathworks.com