Linear dimensionality reduction: survey, insights, and generalizations

John P. Cunningham, Zoubin GhahramaniJMLR 2015

TL;DR

This paper reframes linear dimensionality reduction (LDR) as a unified optimization problem over matrix manifolds. By doing so, it reveals shortcomings of traditional eigenvector-based methods and proposes a generic, objective-agnostic solver that can outperform heuristic approaches, paving the way for LDR to become a more standardized numerical technology.

What Problem Does This Paper Address?

Analyzing high-dimensional data is a central challenge in many scientific fields. Linear dimensionality reduction (LDR) techniques are widely used to simplify this data by projecting it into a lower-dimensional space while preserving important features. However, the field is characterized by a plethora of methods with diverse names and motivations, making it difficult to see the connections between them. Many practitioners rely on eigenvector or generalized eigenvalue problems to solve these LDR tasks, which the authors argue can lead to suboptimal solutions and limit the generality of the methods. This paper aims to consolidate the understanding of LDR, highlight the limitations of traditional approaches, and propose a more unified and principled framework.

Methods

The core contribution of this paper is the formulation of LDR as an optimization problem over matrix manifolds. Specifically, for a given objective function $f_X(M)$ and a matrix manifold $\mathcal{M}$, the goal is to find a matrix $M \in \mathcal{M}$ that optimizes $f_X(M)$. The authors show that many LDR methods can be cast in this form, with $\mathcal{M}$ typically being either the space of unconstrained matrices ($\mathbb{R}^{d \times r}$) or the manifold of orthonormal matrices ($O^{d \times r}$, the Stiefel manifold).

They then propose a generic solver for LDR problems that optimizes over the Stiefel manifold using projected gradient methods. This solver takes the data $X$ and a differentiable objective function $f_X(M)$ as input and returns an optimal low-dimensional projection. This framework allows for direct optimization of the intended objective, rather than relying on potentially suboptimal eigenvector heuristics. The paper also discusses the mathematical underpinnings of optimization on the Stiefel manifold, including tangent spaces, projections, and retractions.

Datasets

Not discussed in the paper. The paper focuses on theoretical framework and experimental validation using simulated data.

Key Insights and Ideas

  • Unified Framework: LDR methods can be elegantly unified as optimization problems over matrix manifolds, revealing deep connections between seemingly disparate techniques.
  • Eigenvector Heuristics are Suboptimal: Traditional reliance on eigenvector or generalized eigenvalue problems for LDR is often suboptimal, especially for higher-dimensional projections ($r > 1$). Direct optimization over the manifold is crucial for achieving the intended objective.
  • Generic Solver Potential: The matrix manifold framework enables the development of an objective-agnostic solver for LDR, similar to how numerical optimization has become a general technology.
  • Orthogonal Projections are Key: Many LDR applications, particularly for visualization, require orthogonal projections. The framework naturally accommodates this constraint.
  • Identifiability vs. Optimization: The choice between the Stiefel (ordered orthonormal bases) and Grassmann (unordered orthonormal bases) manifolds is primarily an issue of identifiability, with empirical results showing little impact on algorithmic performance.

Key Results

  • Performance Improvements: Experiments demonstrate that directly optimizing LDR objectives using manifold methods yields significant performance improvements over heuristic eigenvector approaches for methods like LDA, CCA, and MAF. For example, in one case, Orthogonal CCA showed a performance difference of 0.39 compared to heuristic LDA.
  • PCA Equivalence: For PCA, where the eigenvector solution is provably optimal, the manifold optimization method shows no improvement, confirming its correctness and lack of empirical downside.
  • Computational Feasibility: The proposed manifold optimization approach does not incur prohibitively high computational costs, with runtime increasing approximately linearly with data dimensionality ($d$) and projected dimensionality ($r$).
  • Robustness of Solvers: Both first-order (steepest descent) and second-order (trust region) optimization methods on the Stiefel and Grassmann manifolds are shown to be effective, with second-order methods generally converging faster.

Limitations and Future Work

  • Non-differentiable Objectives: The current generic solver relies on differentiable objective functions. Future work could explore methods for optimizing non-differentiable objectives over nonconvex sets.
  • Local Optima: While empirical results suggest that the optimization often finds global optima, a deeper characterization of local optima for various objectives is needed.
  • Scope Limitations: The paper explicitly excludes nonlinear manifold methods and nonparametric methods, which are important areas of dimensionality reduction.
  • Future Directions: The authors suggest that future LDR algorithms can be derived in a simpler and more principled fashion using this framework. The potential for LDR to become a "blackbox" numerical technology is highlighted.

Summary updated

BibTeX
@article{cunningham2015linear,
  author = {John P. Cunningham and Zoubin Ghahramani},
  title = {{Linear dimensionality reduction: survey, insights, and generalizations}},
  journal = {J. Mach. Learn. Res.},
  year = {2015},
}
Figure