On the Invariance of Dictionary Learning and Sparse Representation to\n Projecting Data to a Discriminative Space

Mehrdad J. Gangeh, Ali Ghodsi

TL;DR

This paper proves that dictionary learning and sparse representation (DLSR) are invariant to linear transformations, including projections into discriminative spaces. This means learning a dictionary in a transformed space yields the same results as learning it in the original space, suggesting that projecting data first and then learning the dictionary is redundant. The authors advocate for using the learned projection basis directly as the dictionary.

What Problem Does This Paper Address?

Dictionary learning and sparse representation (DLSR) have become powerful tools for signal and image processing. However, for tasks like classification, a standard DLSR approach might not yield the most discriminative dictionary. Recently, supervised dictionary learning (SDL) methods have emerged, aiming to incorporate category information to improve discriminative power. Some SDL approaches propose projecting data into a "discriminative space" before learning the dictionary. This raises a crucial question: does learning the dictionary in this projected space offer any advantage over learning it in the original space? This paper addresses this by mathematically proving the invariance of DLSR to linear transformations, including such discriminative projections.

Methods

The core of this paper is a mathematical proof demonstrating the invariance of DLSR to linear transformations. The authors achieve this by:

  1. Formulating the DLSR problem: They start with the standard DLSR optimization problem, which aims to minimize reconstruction error while enforcing sparsity using an L1 norm penalty.
  2. Deriving the dictionary update step: They derive the closed-form solution for updating the dictionary in the original space using a least-squares approach.
  3. Introducing a linear transformation: They then consider a linear transformation applied to the data.
  4. Deriving the dictionary update in the transformed space: They derive the dictionary update step in this transformed space.
  5. Comparing the solutions: By comparing the derived solutions for the dictionary in both the original and transformed spaces, they show that the solutions are equivalent, regardless of the specific linear transformation. This includes transformations that project data into a discriminative space.

The proof is general and does not assume any special properties like orthonormality for the transformation matrix.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Invariance is Key: The most significant insight is the mathematical proof of DLSR's invariance to linear transformations. This is a fundamental property that simplifies how we think about DLSR in transformed spaces.
  • Projecting First is Redundant (for dictionary learning): The paper strongly suggests that projecting data into a discriminative space before learning the dictionary is not beneficial for the dictionary learning process itself. The learned dictionary will be the same as if it were learned in the original space.
  • Leveraging Projection Basis: Instead of learning a dictionary in the projected space, the authors advocate for using the basis vectors of the discriminative projection as the dictionary. This is a more direct and potentially more effective approach.
  • Implications for SDL: This finding has direct implications for supervised dictionary learning methods that involve projecting data. It clarifies that the benefit of projection lies in defining the directions of discrimination, which can then be directly used as dictionary atoms.

Key Results

The paper's primary result is the mathematical proof of invariance. Specifically, it shows that if $D_0$ is the dictionary learned in the original space and $D_t$ is the dictionary learned in a linearly transformed space $U^T X$, then $D_t$ can be expressed in terms of $D_0$ and the transformation $U$. In many cases, particularly when the transformation $U$ is such that $U^T U$ is the identity matrix (e.g., orthogonal projection), the learned dictionary $D_t$ is identical to $D_0$. Even in more general cases, the paper shows that $D_0$ remains a valid solution in the transformed space, and other solutions might exist but are equally good for reconstruction.

Limitations and Future Work

  • Focus on Linear Transformations: The proof specifically addresses linear transformations. Non-linear transformations are not covered.
  • Suboptimal Projection Learning: The paper critiques methods that learn the projection and dictionary simultaneously using gradient descent (like in [28]), arguing that this can lead to suboptimal solutions due to the non-convexity of the problem.
  • Future Work: The authors suggest that future work could explore how to compute the optimal projected space (based on discrimination criteria) without the need for alternating optimization with dictionary learning. They also imply that the focus should be on finding effective discriminative projection criteria, as the learning of the dictionary itself is invariant.

Summary updated

Abstract

In this paper, it is proved that dictionary learning and sparse\nrepresentation is invariant to a linear transformation. It subsumes the special\ncase of transforming/projecting the data into a discriminative space. This is\nimportant because recently, supervised dictionary learning algorithms have been\nproposed, which suggest to include the category information into the learning\nof dictionary to improve its discriminative power. Among them, there are some\napproaches that propose to learn the dictionary in a discriminative projected\nspace. To this end, two approaches have been proposed: first, assigning the\ndiscriminative basis as the dictionary and second, perform dictionary learning\nin the projected space. Based on the invariance of dictionary learning to any\ntransformation in general, and to a discriminative space in particular, we\nadvocate the first approach.\n
BibTeX
@misc{gangeh2015invariance,
  author = {Mehrdad J. Gangeh and Ali Ghodsi},
  title = {{On the Invariance of Dictionary Learning and Sparse Representation to\textbackslash\{\}n Projecting Data to a Discriminative Space}},
  year = {2015},
  eprint = {1503.02041},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1503.02041},
}

Loading related content...

Figure