What is the difference between Karhunen-Loeve transform (KLT) and sparse dictionary learning?

Question

Both are data adaptive (unlike something like DCT), both can sparsely approximate data (KLT by truncation, dictionary learning by L1 sparsity), yet they different pretty significantly in its implementation.

In (discrete) KLT, PCA + truncation is performed on the expected covariance matrix. In sparse dictionary learning, an alternating optimization scheme is used to approximately solve the problem. In encoding, KLT is just a linear transform but for dictionary learning you solve sparse coding.

What tradeoffs do I make by choosing to use one over the other? Are there types of problems where one is more suitable than the other? Thanks!

Answer 1

KLT is basically PCA in infinite-dimensions and PCA learns an "orthogonal dictionary". If the dimension of the space is $d$ (in the case of finite-dimensional PCA), then you can have at most $d$ orthogonal vectors, i.e., the size of the dictionary is at most $d$.

Dictionary learning dispenses with the orthogonality assumption in favor of obtaining sparser representations for most vectors/signals of interest. You usually work with an overcomplete dictionary, one whose number of elements is larger (or much larger) than the dimension $d$ of the space.