Robust overcomplete matrix recovery for sparse sources using a generalized Hough transform

Abstract

We propose an algorithm for recovering the matrix A in X = AS where X is a random vector of lower dimension than S. S is assumed to be sparse in the sense that S has less nonzero elements than the dimension of X at any given time instant. In contrast to previous approaches, the computational time of the presented algorithm is linear in the sample number and independent of source dimension, and the algorithm is robust against noise. Experiments confirm these theoretical results.