Stochastic Systems Group  

RankSparsity Incoherence for Matrix Decomposition
Venkat Chandrasekaran
SSG, MIT
Given the sum of an unknown sparse matrix and an unknown lowrank matrix, we consider the problem of decomposing the specified matrix into its sparse and lowrank components. Such a problem arises in model and system identification settings, but in general is NPhard to solve exactly. We consider a convex optimization formulation for the decomposition problem. We develop a notion of ranksparsity incoherence  an uncertainty principle between the sparsity patterns of matrices and their row/column spaces  to characterize fundamental identifiability as well as sufficient conditions for exact recovery using our method.
Problems with this site should be emailed to jonesb@mit.edu