Tensor Embedding Methods

Guang Dai, Dit-Yan Yeung

Abstract

Traditional manifold learning algorithms often require data to be flattened into vectors, a process that destroys intrinsic spatial structures and exacerbates the curse of dimensionality. This paper introduces a framework for tensor-based manifold learning, specifically extending Neighborhood Preserving Embedding (NPE), Locality Preserving Projection (LPP), and Local Discriminant Embedding (LDE) into the tensor domain. By treating data as multi-dimensional arrays, these methods—TNPE, TLPP, and TLDE—achieve higher accuracy and greater computational efficiency, particularly in small-sample scenarios like face recognition.

Introduction

In machine learning, data such as images and videos are naturally structured as multi-dimensional arrays, or tensors. Conventional dimensionality reduction techniques typically "vectorize" this data, converting a 2D image into a 1D list of pixels. This transformation results in several critical drawbacks: the loss of local spatial relationships, high computational costs due to massive covariance matrices, and the "curse of dimensionality" where the number of parameters far exceeds the available training samples.

To address these issues, Dai and Yeung (2006) proposed tensor embedding methods that perform manifold learning directly on tensors. By preserving the original data structure, these methods extract more meaningful features while significantly reducing the parameter space.

Methodology

The core innovation lies in extending three popular manifold learning algorithms to the tensor domain:

  1. Tensor Neighborhood Preserving Embedding (TNPE): Approximates the local neighborhood structure of the manifold in tensor space.
  2. Tensor Locality Preserving Projection (TLPP): Preserves the geometric and topological properties of the data manifold.
  3. Tensor Local Discriminant Embedding (TLDE): A supervised approach that utilizes class labels to maximize inter-class separation and intra-class cohesion.

Unlike vector-based methods that solve for a single large transformation matrix, tensor methods solve for a set of smaller matrices—one for each dimension (mode) of the tensor. For example, a $56 \times 46$ image is processed using two matrices of sizes $56 \times 56$ and $46 \times 46$, rather than one $2576 \times 2576$ matrix. Because the simultaneous optimization of these matrices is non-linear, the authors employ an iterative scheme that converges to a solution by optimizing one mode at a time while holding others constant.

Experimental Results

The proposed methods were evaluated using the FERET face database. The study compared standard vector-based methods (NPE, LPP, LDE) against their tensor counterparts (2nd-order raw images and 3rd-order Gabor-filtered images).

Performance Across Dimensions

A key advantage of tensor embedding is its ability to reach high classification accuracy at much lower dimensions compared to vector methods.

Classification accuracy of TNPE variants versus reduced dimension d on the FERET database.

As shown in Figure 6, TNPE (especially the 3rd-order variant) significantly outperforms the standard NPE and its Gabor-vectorized version across nearly all dimensions. The tensor approach achieves peak performance much more rapidly, demonstrating its efficiency in feature extraction.

Robustness to Small Training Sets

Tensor methods are particularly effective when training data is scarce. By reducing the number of parameters to be estimated, they avoid the overfitting common in high-dimensional vector spaces.

Top classification accuracy of TLDE variants versus training set size r.

Figure 1 illustrates the performance of TLDE as the number of training images per subject ($r$) increases. Even with very few training samples (e.g., $r=2$ or $3$), the tensor-based TLDE maintains a substantial lead over the vectorized LDE, highlighting its robustness in data-constrained environments.

Conclusion

Tensor embedding methods represent a significant step forward in manifold learning. By respecting the natural structure of data, TNPE, TLPP, and TLDE offer superior accuracy, reduced computational overhead, and improved robustness to small sample sizes. These techniques are especially valuable for high-dimensional, multi-modal data where traditional vectorization is either computationally prohibitive or structurally damaging.

Summary updated

Abstract

Over the past few years, some embedding methods have been proposed for feature extraction and dimensionality reduction in various machine learning and pattern classification tasks. Among the methods proposed are Neighborhood Preserving Embedding (NPE), Locality Preserving Projection (LPP) and Local Discriminant Embedding (LDE) which have been used in such applications as face recognition and image/video retrieval. However, although the data in these applications are more naturally represented as higher-order tensors, the embedding methods can only work with vectorized data representations which may not capture well some useful information in the original data. Moreover, high-dimensional vectorized representations also suffer from the curse of dimensionality and the high computational demand. In this paper, we propose some novel tensor embedding methods which, unlike previous methods, take data directly in the form of tensors of arbitrary order as input. These methods allow the relationships between dimensions of a tensor representation to be efficiently characterized. Moreover, they also allow the intrinsic local geometric and topological properties of the manifold embedded in a tensor space to be naturally estimated. Furthermore, they do not suffer from the curse of dimensionality and the high computational demand. We demonstrate the effectiveness of the proposed tensor embedding methods on a face recognition application and compare them with some previous methods. Extensive experiments show that our methods are not only more effective but also more efficient.
BibTeX
@inproceedings{dai2006tensor,
  author = {Guang Dai and Dit-Yan Yeung},
  title = {{Tensor Embedding Methods}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure