Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract


Rank-Sparsity Incoherence for Matrix Decomposition

Venkat Chandrasekaran
SSG, MIT


Given the sum of an unknown sparse matrix and an unknown low-rank matrix, we consider the problem of decomposing the specified matrix into its sparse and low-rank components. 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 - 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