Given a matrix C = A + B with A being an unknown sparse matrix and B an unknown
low-rank matrix, our goal is to decompose the specified matrix C into its
components A and B. Such a problem arises in model and system identification
settings, but in general is NP-hard to solve exactly. We consider a convex
optimization formulation for the decomposition problem. We develop a notion of
rank-sparsity incoherence - a condition under which matrices cannot be both
sparse and low-rank - to characterize fundamental identifiability as well as
sufficient conditions for exact recovery using our method.