Computing sparse representations of multidimensional signals using Kronecker bases

Abstract

Recently, there is a great interest in sparse representations of signals under the assumption that signals (datasets) can be well approximated by a linear combination of few elements of a known basis (dictionary). Many algorithms have been developed to find such kind of representations for the case of one-dimensional signals (vectors) which involves to find the sparsest solution of an underdetermined linear system of algebraic equations. In this paper, we generalize the theory of sparse representations of vectors tomultiway arrays (tensors), i.e. signals with a multidimensional structure, by using the Tucker model. Thus, the problem is reduced to solve a large-scale underdetermined linear system of equations possessing a Kronecker structure, for which we have developed a greedy algorithm called Kronecker-OMP as a generalization of the classical Orthogonal Matching Pursuit (OMP) algorithm for vectors. We also introduce the concept of multiway block-sparse representation of N-way arrays and develop a new greedy algorithm that exploits not only the Kronecker structure but also block-sparsity. This allows us to derive a very fast and memory efficient algorithm called N-BOMP (N-way Block OMP). We theoretically demonstrate that, under the block-sparsity assumption, our N-BOMP algorithm has not only a considerably lower complexity but it is also more precise than the classical OMP algorithm. Moreover, our algorithms can be used for very large-scale problems which are intractable by using standard approaches. We provide several simulations illustrating our results and comparing our algorithms to classical algorithms such as OMP and BP (Basis Pursuit) algorithms. We also apply the N-BOMP algorithm as a fast solution for the Compressed Sensing (CS) problem with large-scale datasets, in particular for 2D Compressive Imaging (CI) and 3D Hyperspectral CI and we show examples with real world multidimensional signals.