Computing Sparse Representations of Multidimensional Signals Using Kronecker Bases
- 1 January 2013
- journal article
- research article
- Published by MIT Press in Neural Computation
- Vol. 25 (1) , 186-220
Abstract
Recently there has been great interest in sparse representations of signals under the assumption that signals (data sets) can be well approximated by a linear combination of few elements of a known basis (dictionary). Many algorithms have been developed to find such representations for one-dimensional signals (vectors), which requires finding the sparsest solution of an underdetermined linear system of algebraic equations. In this letter, we generalize the theory of sparse representations of vectors to multiway arrays (tensors)—signals with a multidimensional structure—by using the Tucker model. Thus, the problem is reduced to solving a large-scale underdetermined linear system of equations possessing a Kronecker structure, for which we have developed a greedy algorithm, 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 not only has a considerably lower complexity but is also more precise than the classic OMP algorithm. Moreover, our algorithms can be used for very large-scale problems, which are intractable 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 data sets, in particular, for 2D compressive imaging (CI) and 3D hyperspectral CI, and we show examples with real-world multidimensional signals.Keywords
This publication has 40 references indexed in Scilit:
- Block sparse representations of tensors using Kronecker bases2012
- Generalizing the column–row matrix decomposition to multi-way arraysLinear Algebra and its Applications, 2010
- Estimation of Sparse Nonnegative Sources from Noisy Overcomplete Mixtures Using MAPNeural Computation, 2009
- Nonnegative Matrix and Tensor Factorizations2009
- An Introduction To Compressive SamplingIEEE Signal Processing Magazine, 2008
- Sparsity and Morphological Diversity in Blind Source SeparationIEEE Transactions on Image Processing, 2007
- Sparsity and incoherence in compressive samplingInverse Problems, 2007
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationIEEE Transactions on Information Theory, 2006
- Atomic Decomposition by Basis PursuitSIAM Review, 2001
- Adaptive time-frequency decompositionsOptical Engineering, 1994