Sparse Coding and Dictionary Learning

Intuition. In many cases, data is represented by a sum of commonly-existing components. For example, a number is simply a combination of pen strokes. We formalize these properties into the following:

• Each component is a element of a common language, i.e. a dictionary
• Data is constructed from a weighted sum of dictionary items
  • Often, only a few types of pen strokes are used for a single number. Thus we want to only choose (=weight) few components; i.e. enforce sparsity in latent representation

def. Sparse Coding & Dictionary Learning. Given a dictionary $D$, let ${\mathbf{x}}^{(n)}$ be a datapoint and ${\mathbf{h}}^{(n)}({\mathbf{x}}^{(n)})$ be the corresponding latent representation obtained by:

$${\mathbf{h}}^{(n)}:=arg\underset{h(\mathbf{x})}{\min }\underset{\text{ reconstruction loss }}{\underbrace{\frac{1}{2}\Vert \mathbf{x}-\stackrel{\text{ reconstruction }}{\overbrace{\mathbf{D}\cdot \mathbf{h}(\mathbf{x})}}{\Vert }_2^2}}+\stackrel{\text{ sparsity penalty }}{\overbrace{\lambda \Vert \mathbf{h}(\mathbf{x}){\Vert }_1}}$$

i.e., the latent representation $\mathbf{h}$ always minimizes the reconstruction loss. This is an odd way to define a latent representation, but it is useful in that given a dictionary $\mathbf{h}$ always minmizes reconstruction loss—part of the training is built into the inference.

• We also enforce that the columns of $\mathbf{D}$ is of norm $1$, because if we don’t the sparsity objective can ‘cheat’ and increase the numbers in $\mathbf{D}$ to compensate for the sparsity.
• This optimization is done by the Iterative Shrinkage and Thresholding Algorithm (ISTM) because the sparsity penalty makes it difficult to use standard tools. Objective. Now, how do we get $D$? Sometimes it’s obvious (e.g., sentences are composed of words) but in most cases not. We obtain optimal $D$ with the following objective:

$$\mathcal{L}=\underset{\mathbf{D}}{\min }{⟨\underset{h(x)}{\min }\frac{1}{2}\Vert \mathbf{x}-\mathbf{D}\cdot \mathbf{h}(\mathbf{x}){\Vert }_2^2+\lambda \Vert \mathbf{h}(\mathbf{x}){\Vert }_1⟩}_T$$

Site Unreachable