Geometric Conditions for Subspace-Sparse Recovery

Abstract

Given a dictionary \Pi and a signal ξ= \Pi \mathbf x generated by a few \textit{linearly} independent columns of \Pi, classical sparse recovery theory deals with the problem of uniquely recovering the sparse representation \mathbf x of ξ. In this work, we consider the more general case where ξlies in a low-dimensional subspace spanned by a few columns of \Pi, which are possibly \textit{linearly} dependent. In this case, \mathbf x may not unique, and the goal is to recover any subset of the columns of \Pi that spans the subspace containing ξ. We call such a representation \mathbf x \textit{subspace-sparse}. We study conditions under which existing pursuit methods recover a subspace-sparse representation. Such conditions reveal important geometric insights and have implications for the theory of classical sparse recovery as well as subspace clustering.