In the traditional Canonical Correlation Analysis (CCA) based face recognition methods, the size of sample is always smaller than the dimension of sample. This problem is so called the Small Sample Size (SSS) problem. In order to solve this problem, a new supervised learning method called Two-dimensional CCA (2DCCA) is developed in this paper. Different from traditional CCA method, 2DCCA directly extracts the features from image matrix rather than matrix-tovector transformation. In practice, the covariance matrix extracted by 2DCCA is always full rank. Hence the Small Sample Size (SSS) problem can be effectively dealt with by this new developed method. The theory foundation of 2DCCA method is firstly developed, and the construction method for the class-membership matrix Y which is used to precisely represent the relationship between samples and classes in the 2DCCA framework is then clarified. Simultaneously, the analytic form of the generalized inverse of such class-membership matrix is derived. From our experiment results on face recognition, we clearly find that not only the SSS problem can be effectively solved, but also better recognition performance than several other CCA based methods has been achieved.