Trace Quotient with Sparsity Priors for Learning Low Dimensional Image Representations

Xian Wei, Hao Shen, Martin Kleinsteuber

TL;DR

This paper introduces SparLow, a unified machine learning framework that jointly learns a sparse dictionary and a dimensionality reduction projection to extract highly discriminative, low-dimensional image features. By combining sparse coding with the Trace Quotient (TQ) criterion and optimizing it over a Riemannian manifold, SparLow achieves state-of-the-art performance across unsupervised, supervised, and semi-supervised image classification tasks.

What Problem Does This Paper Address?

In computer vision, high-dimensional image data needs to be compressed into low-dimensional representations that retain important information (like an object's class) while discarding noise.

Historically, researchers have used sparse representation to find the underlying structure of images. However, this is usually a decoupled, two-step process: first, you learn a dictionary to extract sparse features, and then you feed those features into a separate classifier or dimensionality reduction tool (like PCA or LDA).

While some "task-driven" dictionary learning methods exist to combine these steps, they are mostly limited to supervised learning and require learning separate dictionaries for every single class, which becomes computationally massive for datasets with many categories. The authors wanted to create a single, generic, two-layer framework that jointly learns a compact dictionary and a task-specific projection simultaneously, applicable to any learning paradigm.

Methods

The authors propose the SparLow (SPARse LOW dimensional representation) framework, which consists of two interconnected layers:

  1. Layer 1 (Sparse Coding): Extracts underlying factors of variation using sparse coding. Crucially, the authors use convex sparsity priors (like the Elastic Net). They mathematically prove that doing this makes the sparse representations locally differentiable, which is required for the joint optimization to work.
  2. Layer 2 (Trace Quotient): Applies a linear projection to the sparse features to reduce their dimensionality. They use the Trace Quotient (TQ) criterion, a highly versatile mathematical formulation that generalizes many classic dimensionality reduction techniques.

The Optimization Engine: To train both layers simultaneously, the authors combine them into a single cost function. Because the projection matrix must remain orthogonal and the dictionary atoms must have a unit norm, standard gradient descent won't work. Instead, they develop a custom geometric Conjugate Gradient (CG) algorithm that operates on a Riemannian manifold (specifically, a product of unit spheres and a Grassmann manifold).

The "Warm Start" Regularizer: The authors found that purely task-driven optimization can "overfit" and ruin the underlying sparse representation. To fix this, they introduce a data regularizer that forces the learned dictionary to stay in the neighborhood of a purely data-driven dictionary (like one pre-learned via K-SVD).

Datasets

The framework was evaluated on several standard computer vision benchmarks:

  • Handwritten Digits: USPS and MNIST.
  • Faces: CMU-PIE (used to test disentanglement of pose, illumination, and identity).
  • Object/Scene Categorization: Caltech-101, Caltech-256, and 15-Scenes (used to test large-scale image processing capabilities).

Key Insights and Ideas

  • Differentiability is the Key to Joint Learning: By carefully choosing convex sparsity priors, the authors bypassed a major roadblock in dictionary learning. They proved that the first derivative of the sparse representation has a closed-form expression, enabling smooth, gradient-based joint optimization.
  • The Versatility of the Trace Quotient: The TQ criterion acts as a universal adapter. By simply swapping out the matrices in the TQ formula, SparLow instantly adapts to mimic PCA (for unsupervised learning), LDA (for supervised learning), or graph-based methods (for semi-supervised learning).
  • Balancing Data and Task: The paper highlights a fascinating tension in representation learning: if you optimize too hard for a specific task, you destroy the fundamental structure of the data. The "warm start" regularizer proves that balancing general data reconstruction with task-specific goals yields the most stable and accurate models.
  • Visual Disentanglement: The joint learning process naturally disentangles factors of variation. When visualizing the learned features of faces, SparLow cleanly separated identity, pose, and illumination much better than standard PCA or LLE.

Key Results

  • Classification Superiority: SparLow consistently outperformed state-of-the-art dictionary learning methods (like LC-KSVD, FDDL, and TDDL) across multiple datasets. For example, on the 15-Scenes dataset, supervised SparLow achieved ~98.4% accuracy, beating out competing methods hovering around 90-92%.
  • Semi-supervised Dominance: SparLow shines brightest when labeled data is scarce. On Caltech-101, using only 5 to 30 labeled images per class, the semi-supervised SparLow methods showed massive improvements over standard approaches by leveraging the unlabeled data to build a better sparsifying dictionary.
  • Clustering Proof: 3D visualizations of the CMU-PIE dataset showed that SparLow could perfectly cluster faces by identity in a 3D space, whereas traditional methods left the classes completely entangled and overlapping.

Limitations and Future Work

  • Computational Cost: The authors acknowledge that training a SparLow model can be computationally expensive due to the complex manifold optimization and the inherent cost of solving sparse coding problems at each step.
  • Hyperparameter Sensitivity: The framework's performance relies on careful tuning of several hyperparameters, including the targeted low dimensionality and the weights balancing the different regularizers.
  • Future Work: The authors suggest extending the SparLow framework to accommodate more general cases of low-dimensional representation learning models that rely on orthogonal constraints, further expanding its utility beyond the Trace Quotient criterion.

Summary updated

Abstract

This work studies the problem of learning appropriate low dimensional image representations. We propose a generic algorithmic framework, which leverages two classic representation learning paradigms, i.e., sparse representation and the trace quotient criterion, to disentangle underlying factors of variation in high dimensional images. Specifically, we aim to learn simple representations of low dimensional, discriminant factors by applying the trace quotient criterion to well-engineered sparse representations. We construct a unified cost function, coined as the SPARse LOW dimensional representation (SparLow) function, for jointly learning both a sparsifying dictionary and a dimensionality reduction transformation. The SparLow function is widely applicable for developing various algorithms in three classic machine learning scenarios, namely, unsupervised, supervised, and semi-supervised learning. In order to develop efficient joint learning algorithms for maximizing the SparLow function, we deploy a framework of sparse coding with appropriate convex priors to ensure the sparse representations to be locally differentiable. Moreover, we develop an efficient geometric conjugate gradient algorithm to maximize the SparLow function on its underlying Riemannian manifold. Performance of the proposed SparLow algorithmic framework is investigated on several image processing tasks, such as 3D data visualization, face/digit recognition, and object/scene categorization.
BibTeX
@article{wei2020trace,
  author = {Xian Wei and Hao Shen and Martin Kleinsteuber},
  title = {{Trace Quotient with Sparsity Priors for Learning Low Dimensional Image Representations}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2020},
  url = {https://openreview.net/forum?id=0A7PWPYi-6},
}

Loading related content...

Figure