A clustering based framework for dictionary block structure identification

Sparse representations over redundant dictionaries offer an efficient paradigm for signal representation. Recently block-sparsity has been put forward as a prior condition for some sparse representation applications, where the coefficients of the sparse representation occur in blocks rather than being distributed randomly over the sparse vector. Block-sparse representation algorithms, which are extensions of the regular sparse representation algorithms have been developed. However, these algorithms work under the assumption that both the dictionary and its corresponding block structure are known. In this paper, we consider the problem of recovering the optimally block-sparsifying block structure for a given data set and dictionary pair. We propose a block structure identification framework employing a clustering step which can be realized using the standard clustering schemes from the literature. The block structure identification algorithm works efficiently, and for synthetically generated block-sparse data the underlying block structure is retrieved even for comparably short data records.