Fast Orthonormal Sparsifying Transforms Based on Householder Reflectors

Abstract--Dictionary learning is the task of determining a data-dependent transform that yields a sparse representation of some observed data. The dictionary learning problem is non-convex, and usually solved via computationally complex iterative algorithms. Furthermore, the resulting transforms obtained generally lack structure that permits their fast application to data. T o address this issue, this paper develops a framework for learning orthonormal dictionaries which are built from products of a few Householder reflectors. Two algorithms are proposed to learn the reflector coefficients: one that considers a sequential update of the reflectors and one with a simultaneous update of all reflectors that imposes an additional internal orthogonal constraint. The proposed methods have low computational complexity and are shown to converge to local minimum points which can be described in terms of the spectral properties of the matrices involved. Simulations of the proposed algorithms are shown in the image processing setting where well-known fast transforms are available for comparisons. The proposed algorithms have favorable reconstruction error and the advantage of a fast implementation relative to the classical, unstructured, dictionaries. Index Terms--sparsifying transforms, fast transforms, dictionary learning, compressed sensing. Sparsifying transforms [1] allow efficient representation of data when a data-dependent overcomplete dictionary is available. Overcomplete dictionaries are useful in image processing [2], [3], [4], speech processing [5] and wireless communications [6], [7]. Unfortunately, the selection of a sparsifying transform involves solving a non-convex optimization problem for a dictionary matrixD such that a real data set can be represented with a sparse representation matrixX whose sparsity level is constrained. Because direct solution of the optimization method is difficult [8], [9], proposed algorithms seek a suboptimal solution via alternating minimization. Most prior work considers alternating minimization for dictionaries that are overcomplete.