PaperlayerView exact revision on arXiv

Source-linked AI summary

Extension of PCA to Higher Order Data Structures: An Introduction to Tensors, Tensor Decompositions, and Tensor PCA

Ali Zare, Alp Ozdemir, Mark A. Iwen, Selin Aviyente

arXiv:1803.00704v2eess.SP

TL;DR

Higher-order datasets are common, but conventional PCA on vectorized or matricized data does not capture their hidden components and cross-mode structure. This survey reviews tensor decompositions and PCA extensions for dimensionality reduction, supervised learning, and robust recovery, and concludes that decomposition performance depends on data characteristics.

  • Problem

    Standard PCA is limited to vector and matrix data, while higher-order datasets require methods that respect multimodal structure and cross-mode couplings.

    Source: §1 · p. 2

  • Method

    The survey reviews tensor decomposition and PCA extensions for low-rank approximation, subspace learning, and robust tensor recovery, with experimental comparisons for dimensionality reduction and supervised learning.

    Source: §1 · pp. 2–3

  • Results

    Tensor decomposition methods’ performance depends heavily on data characteristics, including variation across slices, number of modes, and data size.

    Source: §6 · p. 21

  • Takeaways & Limitations

    The comparisons point to a need for improved decomposition algorithms and methods combining advantages of existing methods for larger datasets.

    Source: §6 · p. 21

    Tucker factor-matrix subspaces are unique, but their bases may vary and the decomposition is not unique without additional constraints.

    Source: §3.2 · p. 8

Abstract

from arXiv · show

The widespread use of multisensor technology and the emergence of big data sets have brought the necessity to develop more versatile tools to represent higher-order data with multiple aspects and high dimensionality. Data in the form of multidimensional arrays, also referred to as tensors, arises in a variety of applications including chemometrics, hyperspectral imaging, high resolution videos, neuroimaging, biometrics, and social network analysis. Early multiway data analysis approaches reformatted such tensor data as large vectors or matrices and then resorted to dimensionality reduction methods developed for classical two-way analysis such as PCA. However, one cannot discover hidden components within multiway data using conventional PCA. To this end, tensor decomposition methods which are flexible in the choice of the constraints and that extract more general latent components have been proposed. In this paper, we review the major tensor decomposition methods with a focus on problems targeted by classical PCA. In particular, we present tensor methods that aim to solve three important challenges typically addressed by PCA: dimensionality reduction, i.e. low-rank tensor approximation, supervised learning, i.e. learning linear subspaces for feature extraction, and robust low-rank tensor recovery. We also provide experimental results to compare different tensor models for both dimensionality reduction and supervised learning applications.

1. Introduction

Classical PCA addresses dimensionality reduction, subspace learning, and robust low-rank recovery, but vector and matrix models are inadequate for higher-order data. This survey reviews tensor methods for these challenges and compares tensor models experimentally for dimensionality reduction and supervised learning.

  • PCA commonly targets dimensionality reduction, linear subspace learning, and robust low-rank recovery, motivating tensor extensions of these tasks.Source: §1 · p. 1
  • Higher-order data expose limits of standard vector and matrix models: they miss cross-mode couplings and incur increasing storage and computational costs.Source: §1 · p. 2
  • The review focuses on PCA-targeted tensor extensions and pairs theoretical coverage of tensor structures with experiments comparing dimensionality-reduction and supervised-learning models.Source: §1 · p. 2
  • The survey reviews low-rank tensor approximation methods, including CPD, Tucker, and tensor networks, with attention to dimensionality reduction, uniqueness, storage, and compression comparisons.Source: §1 · p. 2
  • It surveys tensor subspace-learning methods that project test tensors into lower-dimensional spaces for classification, including applications to face and object recognition across modalities and angles.Source: §1 · p. 2
  • The survey also covers robust low-rank tensor recovery for grossly corrupted and noisy data, and ongoing work on large-scale factorization and efficient implementation.Source: §1 · p. 3

2. Notation, Tensor Basics, and Preludes to Tensor PCA

The section establishes tensor notation and basic operations, then explains how tensors can be viewed as vectors or matrices and manipulated through mode-wise products. These conventions support later tensor decompositions and PCA methods.

2. Notation, Tensor Basics, and Preludes to Tensor PCA

  • A d-mode tensor is a multidimensional array whose entries are indexed by one coordinate per mode.Source: §2 · p. 3

2.1. Fibers, Slices, and Other Sub-tensors.

  • Fibers are one-mode subtensors, while slices are (d −1)-mode subtensors; a mode-j fiber varies along mode j, and a mode-j slice fixes its index.Source: §2.1 · p. 3

2.2. Tensor Vectorization, Flattening, and Reshaping.

  • Vectorization reshapes a tensor into a vector, while mode-j unfolding forms a matrix whose columns are the tensor’s mode-j fibers.Source: §2.2 · p. 4

2.3. The Standard Inner Product Space of d-mode Tensors.

  • The standard tensor inner product induces a Euclidean norm, and reshaping preserves the inner-product space structure while acting linearly.Source: §2.3 · pp. 5–6

2.4. Tensor Products and j-Mode Products.

  • Tensor products combine tensors into higher-order arrays, while mode-j products apply a matrix along one mode and correspond to left multiplication of the mode-j unfolding.Source: §2.4 · p. 6
  • Mode-j products are bilinear, commute across different modes, and combine in reverse order when applied along the same mode.Source: §2.4 · p. 6

3. Tensor Factorization and Compression Methods

This section reviews tensor decompositions for low-rank approximation and compression, extending PCA/SVD-style analysis to multilinear data. It compares several models’ compression-versus-error performance across three datasets.

3.1. CANDECOMP/PARAFAC Decomposition (CPD).

  • CPD represents a tensor as a sum of weighted rank-one tensors, using O(Rdn) parameters for rank-R approximation when all dimensions equal n.Its factors interact only factorwise across modes; ALS estimates one mode’s factors at a time and may fail to reach a global minimum or require thousands of iterations under substantial noise or high model order.Source: §3.1 · pp. 7–8

3.2. Tucker Decomposition and HoSVD.

  • Tucker decomposes a tensor into a core and mode-specific factor matrices, allowing cross-mode factor interactions; HoSVD adds orthogonality constraints to the component matrices.Tucker subspaces are unique but their bases may vary, so the model is not unique without additional constraints. Truncated HoSVD is not generally the best approximation at a specified multilinear rank; ALS optimization of the best approximation is known as HOOI.Source: §3.2 · pp. 8–9

3.3. Tensor Networks.

  • Tensor networks represent higher-order tensors through contracted lower-order tensors, and their contraction cost depends on the order of index contractions.Different network representations can describe the same tensor, and uniqueness under different constraints remains an active research area.Source: §3.3 · p. 9

3.3.1. Hierarchical Tensor Decomposition.

  • Hierarchical Tucker recursively partitions modes in a binary tree and, at equal mode size n and rank R, stores O(dnR + dR^3) parameters.Its transfer matrices link the factor matrices of child nodes to those of their parent.Source: §3.3.1 · p. 9

3.3.2. Tensor Train Decomposition.

  • Tensor Train is a cascade special case of Hierarchical Tucker that compresses data into core tensors, avoids Tucker’s exponential storage growth, and uses O(dnR^2) parameters at equal mode size n and rank R.Its computation uses sequential SVDs and is linear in tensor order; unlike Tensor Ring, TT requires rank-1 boundary factors and depends on core ordering.Source: §3.3.2 · p. 10

3.4. Tensor Singular Value Decomposition (t-SVD).

  • For third-order tensors, t-SVD uses the t-product, computed through matrix SVDs in the Fourier domain, and defines rank by the number of nonzero singular tubes.Unlike CPD and Tucker, truncated t-SVD at a given rank is an optimal Frobenius-norm approximation; its rank-R representation uses O(Rn3(n1 + n2 + 1)) entries.Source: §3.4 · p. 10

3.5. An Empirical Comparison of Different Tensor Decomposition Methods.

  • The comparison evaluates compression versus normalized reconstruction error for PIE, hyperspectral imagery, and COIL-100; COIL-100 images were reshaped into a four-mode tensor.Compression is output size divided by input size. Methods used different input parameters selected to yield comparable reconstruction errors and compression rates.Source: §3.4 · p. 11, §3.5 · p. 12
  • HoSVD and HOOI give similar results, with HOOI slightly better; they generally perform best where CPD does not work well, except HT and TT outperform them on COIL-100 at higher compression.CPD offers the best compression when it converges, but has difficulty converging at large rank parameters, especially on larger datasets. PIE favors HT for approximation error below 10^-2, while TT and HT perform poorly on HSI around 10^-2; tensor networks may perform better on tensors with more than the four modes tested.Source: §3.5 · p. 12

4. Tensor PCA Approaches

This section reviews tensor PCA methods for learning low-dimensional features and subspaces, including embedding methods for machine learning applications. It covers vectorized PCA and tensor-structured approaches, then compares MPCA and TT-PCA for classification.

4. Tensor PCA Approaches

  • The section surveys tensor decomposition methods for supervised feature extraction, including Tucker-, CPD-, TT-, and HT-based approaches, alongside tensor embedding methods.It begins with PCA based on tensor vectorization.Source: §4 · pp. 13–14

4.1. Trivial PCA for Tensors Based on Implicit Vectorization.

  • Vectorized PCA treats each person’s image tensor as a data point and obtains reshaped eigenface bases via SVD, but very large tensor dimensions make the SVD costly and basis storage inefficient.The section describes early applications to facial recognition, computer vision, and image processing.Source: §4.1 · p. 14

4.2. Multilinear Principal Component Analysis (MPCA).

  • MPCA finds mode-wise orthogonal projections that capture total variation, optimizing one mode at a time with alternating partial projections and partial SVDs.It has no theoretical convergence guarantee, but the authors report fast empirical convergence; it reduces to PCA for d = 1 and 2DPCA for d = 2.Source: §4.2 · p. 15

4.3. Tensor Rank-One Decomposition (TROD).

  • TROD represents tensor subspaces with rank-one tensor bases and greedily updates their factor vectors, but can be computationally costly and slow to converge when data do not fit a low-CPD-rank model..Source: §4.2 · p. 16, §4.3 · p. 16

4.4. Tensor Train PCA (TT-PCA).

  • TT-PCA learns subspaces by minimizing the distance of data points from a tensor-train subspace; one approach uses successive SVDs and thresholding to derive left-orthogonal subspaces and project data points.A related approach changes sample and mode ordering, then uses successive SVDs and thresholding to extract subspaces.Source: §4.4 · pp. 16–17

4.5. Hierarchical tensor PCA (HT-PCA).

  • HT-PCA builds a hierarchical subspace using a dimension tree and truncated SVDs of node unfoldings; reported results show lower classification error than TT-PCA for a given number of training samples.Estimating both the tree and subspaces is NP-hard, so current applications use balanced or TT trees with a suboptimal algorithm.Source: §4.5 · p. 17

4.6. Tensor Embedding Methods.

  • Tensor embedding methods estimate local geometric and topological structure in tensor spaces and determine projections that preserve the manifold’s local structure through iterative algorithms.Examples include TNPE, TLPP, and TLDE; TNPE has also been extended to the TT model as TTNPE.Source: §4.6 · p. 17

4.7. An Empirical Comparison of Two Tensor PCA Approaches.

  • For COIL-100 and EYFDB, MPS outperforms MPCA across training-set sizes and compression ratios, especially at smaller training ratios; on MNIST, the methods are nearly tied, with MPCA slightly better.The authors suggest MNIST may fit the Tucker model better because within-class variation can be approximated by a few factor matrices across modes.Source: Table 2 · p. 18, Table 3 · p. 18, §4.7 · p. 18

5. Robust Tensor PCA

Robust tensor recovery addresses the sensitivity of low-rank decompositions to outliers by separating low-rank structure from corruption and noise. CPD, HoSVD, and t-SVD approaches differ in their rank formulations, algorithms, and recovery conditions.

5. Robust Tensor PCA

  • Robust tensor recovery targets outlier-sensitive decompositions by reconstructing low-rank structure from corrupted data, including sparse corruption and, in some models, dense noise.Conventional decompositions minimize Frobenius error, which can be sensitive to outliers; early matrix-based robust methods ignore tensor rank constraints.Source: §5 · pp. 18–19, §5.2 · p. 20

5.1. Robust CPD.

  • For orthogonal low-rank CP tensors with block-sparse corruption, RTD alternates low-rank projection and residual thresholding, with convergence proven under those conditions.Its alternating updates estimate the low-rank component through eigenvector computation and the sparse component through residual thresholding.Source: §5.1 · p. 19

5.2. Robust HoSVD.

  • HoSVD-based tensor PCP uses Tucker-rank formulations: Singleton penalizes all mode unfoldings, while the relaxed Mixture model sums tensors low-rank in their corresponding modes.The Tucker-rank problem is NP-hard and can be convexified; the Singleton formulation can be solved with ADAL, while the cited alternative is harder but solvable with inexact ADAL.Source: §5.2 · p. 20

5.3. Robust t-SVD.

  • Robust t-SVD methods minimize tubal rank or its tensor nuclear-norm surrogate, which preserves mode relationships and corresponds to low-rank recovery of frontal slices in the Fourier domain.Exact recovery is established under stated incoherence and sparsity conditions; OR-TPCA also provides subspace-recovery guarantees under tensor column-incoherence conditions.Source: §5.3 · pp. 20–21

6. Conclusion

The paper surveys tensor decompositions for data reduction and compares their performance across tensor sizes, while also reviewing tensor PCA for learning and robust recovery. Its conclusion emphasizes that decomposition performance depends on data characteristics and identifies more general and scalable methods as ongoing needs.

6. Conclusion

  • The survey reviews tensor decomposition methods for data reduction, compares performance across tensor sizes, and introduces tensor PCA extensions for learning and robust low-rank recovery.The paper notes that its focus is mostly tensor data reduction rather than learning approaches.Source: §6 · p. 21
  • Empirical results show that commonly used decompositions depend on data characteristics, motivating improved methods for larger datasets that combine strengths of existing approaches.Block term decompositions model more complex structures using low-rank factors that need not be rank one, combining aspects of Tucker and CP decompositions.Source: §6 · p. 21
  • Tensor subspace learning is an expanding area that includes extensions of LDA and manifold learning to tensor data.The paper notes that its focus is mostly on tensor data reduction rather than learning approaches.Source: §6 · p. 21
  • Higher-dimensional tensor data motivates hierarchical methods for visualization and representation, alongside parallel and distributed implementations of decomposition methods.The conclusion also points to multiscale HoSVD for data reduction and denoising and to existing strategies for efficient large-scale matrix SVD.Source: §6 · p. 21
Loading 1803.00704v2…