readme

Fei Sha 等人编写的流形学习算法CCA的matlab代码

README

( Aug 18, 2006)

--------------------------------------------------------------------
I.   Introduction
II.  Installation
III. Usage & Examples
IV.  Contacts & Copyrights
V.   References


--------------------------------------------------------------------
I. Introduction

Function [Z, CCAEIGEN, CCADETAILS] = CCA(X, Y, EDGES, OPTS) computes a low
dimensional embedding Z in R^d that maximally preserves angles among  input 
data X that lives in R^D, with the algorithm Conformal Component Analysis (CCA).

The key idea is to constrain Z = L*Y where Y is a partial basis that 
spans the space of R^d. Such Y can be computed from graph Laplacian (such as 
the outputs of Laplacian eigenmap [3] and Locally Linear Embedding, ie, LLE [4]). 
The parameterization matrix L is optimized to maximally
preserve angles between edges coded in the sparse matrix EDGES.


Ref.[1-2] shows that the optimization problem can be formulated as a semidefinite 
programming problem (SDP) in P = L'*L.  SDPs are convex optimization problems; 
they can be solved efficiently.

Recently, the linear parameterization idea (Z=L*Y) has also been used in finding
maximum variance unfolding (MVU, a.k.a, Semidefinite Embedding) [5] and has
been applied to sensor localization problems [6]. MVU aims to compute (local) 
distance mapping between high dimensional data points and low dimensional 
representation, while CCA computes angle preserving mappings. 
    
This distribution also implements a variant of MVU, which is described in [6].

--------------------------------------------------------------------
II. Installation

The distribution of this package includes following files

1. README: this file
2. cca.m:  main Matlab function
3. mexCCACollectData.c:  a C source file 
4. demoCCA.m:  demo function
    
To install, make sure cca.m (optionally, demoCCA.m) is in your Matlab path.
Also, in Matlab's command window, issue command "mex mexCCACollectData.c" to 
the C source file compile and make sure the compiled object is in your Matlab
path.

A SDP solver is needed. This implementation uses CSDP solver [7]. Make sure the
main Matlab function csdp.m is in your Matlab path.

This distribution has been tested on MAC OS X 10.3.x or above, with Matlab 7.0 
or above, as well as Intel-based Linux (kernel 2.4 or above) with Matlab 7.0 or
above. The CSDP solver that has been tested is version 4.9 and 5.0.

--------------------------------------------------------------------
III. Usage & Examples.

1. To run examples, type demoCCA

Note: You need an implementaiton of LLE to run demoCCA().
This distribution provides one based on Sam Roweis's implementation at 
http://www.cs.toronto.edu/~roweis/lle/ .

2. To call the function cca(), use following syntax:

<=== Inputs:

X: input data stored in matrix  (D x N) where D is the dimensionality

Y: partial basis stored in matrix (d x N)
   Note that if graph Laplacians/LLE are used to compute Y, then make sure Y(1,:)
   is not a constant vector.

EDGES: a sparse matrix of (N x N). In each column i, the row indices j to
  nonzero entrices define data points that are in the nearest neighbors of
  data point i.

OPTS:
   OPTS.method
        == 'CCA':   implements CCA algorithm [1,2]  
        == 'MVU':   implements MVU [6]
        
        default is 'CCA'

   OPTS.regularizer: the tradeoff factor when maximizing trace (as in MVU [5])
    while preserving distances (it is okay to use a nonzero regularizer in CCA
    algorithm, where we will get an "unfolded" CCA to enforce low rank in
    solutions)
        default is 0.
        
   OPTS.relative: In MVU, either absolute distance can be preserved 
    (OPTS.relative ==0) or relative distance can be preserved (OPTS.relative == 1)

        default is 0
        
====> Outputs:

Z: low dimensional embedding (d X N)

CCAEIGN: eigenspectra of the matrix P = L'*L. If P is low-rank (say d' < d),
  then Z can be cutoff at d' dimension as dimensionality reduced further.

CCADetails:
   CCADetails.cost: final objective function value
   CCADetails.c: if OPTS.method == 'CCA', this is the local scaling
    coefficient for each data point
   CCADetails.P: matrix P = L'*L 
   CCADetails.opts: options used to run the algorithm, same as OPTS with
    checked parameters
   CCADetails.sdpflag: SDP solver exit flag. (check CSDP solver manual. In
   general, an exit flag of 0 means normal exit.)

--------------------------------------------------------------------
IV. Misc.

1. Please send bug report to [e-mail]

2. Feel free to use it for educational and research purpose.

--------------------------------------------------------------------

V. References
   
[1]   
 Fei Sha and Lawrence K. Saul (2005).   Analysis and Extension of Spectral
 Methods for Nonlinear Dimensionality Reduction.  Proceedings of 22nd 
 International Conference on Machine Learning (ICML 2005), Bonn, Germany

[2]
 Fei Sha, Kilian Weinberge and Lawrence K. Saul (200x). Manifold learning by 
 semidefinite programming. Manuscript in preparation.

[3]. 
 M. Belkin and P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and 
 Data Representation, Neural Comp., 15(6):1373-1396, 2003.
    
[4].
 L. K. Saul and S. T. Roweis (2003). Think globally, fit locally: unsupervised 
 learning of low dimensional manifolds. Journal of Machine Learning Research 4:119-155

[5]. 
 K. Q. Weinberger and L. K. Saul (2006). Unsupervised learning of image 
 manifolds by semidefinite programming. International Journal of Computer 
 Vision 70(1): 77-90
 
[6].
 K. Q. Weinberger, Fei Sha, Qihui Zhu and L. K. Saul (2006). Localization in 
 Large Scale Sensor Networks via Semidefinite Programming and Graph 
 Regularization. Submitted manuscript.
 
[7].
 Borchers, B., CSDP, A C Library for Semidefinite Programming. Optimization 
 Methods and Software 11(1):613-623, 1999. 
 http://infohost.nmt.edu/~borchers/csdp.html
 --------------------------------------------------------------------