Learning Multiplication-free Linear Transformations

Abstract--In this paper, we propose several dictionary learning algorithms for sparse representations that also impose specific structures on the learned dictionaries such that they are numerically efficientto use: reduced number of addition/multiplications and even avoiding multiplications altogether. We base our work on factorizations of the dictionary in highly structured basic building blocks (binary orthonormal, scaling and shear transformations) forwhich we can write closed-form solutions to the optimization problemsthat we consider. We show the effectiveness of our methods on image data where we can compare against wellknown numericallyefficient transforms such as the fast Fourier and the fast discrete cosine transforms. I. INTRODUCTION In many situations, the success of theoretical concepts in signal processing applications depends on there existing an accompanying algorithmic implementation that is numerically efficient, e.g., Fourier analysis and the fast Fourier transform (FFT) or wavelet theory and the fast wavelet transform (FWT). Unfortunately, in a machine learning scenario where linear transformations are learned they do not exhibit in general advantageous numerical properties, as do the examples just mentioned, unless we explicitly search for such solutions.