Learning computationally efficient dictionaries and their implementation as fast transforms
This work addresses the scalability issue in dictionary learning for signal processing and machine learning, enabling faster computations for tasks like sparse coding.
The paper tackled the computational cost of dictionary learning by proposing a dictionary structure that allows cheaper manipulation and an algorithm to learn such dictionaries with fast implementations, demonstrated through experiments like factorizing the Hadamard matrix and synthetic tests.
Dictionary learning is a branch of signal processing and machine learning that aims at finding a frame (called dictionary) in which some training data admits a sparse representation. The sparser the representation, the better the dictionary. The resulting dictionary is in general a dense matrix, and its manipulation can be computationally costly both at the learning stage and later in the usage of this dictionary, for tasks such as sparse coding. Dictionary learning is thus limited to relatively small-scale problems. In this paper, inspired by usual fast transforms, we consider a general dictionary structure that allows cheaper manipulation, and propose an algorithm to learn such dictionaries --and their fast implementation-- over training data. The approach is demonstrated experimentally with the factorization of the Hadamard matrix and with synthetic dictionary learning experiments.