A Caltech Library Service

Sharp Recovery Bounds for Convex Demixing, with Applications

McCoy, Michael B. and Tropp, Joel A. (2014) Sharp Recovery Bounds for Convex Demixing, with Applications. Foundations of Computational Mathematics, 14 (3). pp. 503-567. ISSN 1615-3375.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Demixing refers to the challenge of identifying two structured signals given only the sum of the two signals and prior information about their structures. Examples include the problem of separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis, and the problem of decomposing an observed matrix into a low-rank matrix plus a sparse matrix. This paper describes and analyzes a framework, based on convex optimization, for solving these demixing problems, and many others. This work introduces a randomized signal model that ensures that the two structures are incoherent, i.e., generically oriented. For an observation from this model, this approach identifies a summary statistic that reflects the complexity of a particular signal. The difficulty of separating two structured, incoherent signals depends only on the total complexity of the two structures. Some applications include (1) demixing two signals that are sparse in mutually incoherent bases, (2) decoding spread-spectrum transmissions in the presence of impulsive errors, and (3) removing sparse corruptions from a low-rank matrix. In each case, the theoretical analysis of the convex demixing method closely matches its empirical behavior.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle Paper ReadCube access
Tropp, Joel A.0000-0003-1024-1791
Additional Information:© 2014 SFoCM. Received: 19 May 2012; Revised: 22 November 2013; Accepted: 8 January 2014; Published online: 1 April 2014. This research was supported by ONR Awards N00014-08-1-0883 and N00014-11-1002, AFOSR Award FA9550-09-1-0643, DARPA Award N66001-08-1-2065, and a Sloan Research Fellowship.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0883
Office of Naval Research (ONR)N00014-11-1002
Air Force Office of Scientific Research (AFOSR)FA9550-09-1-0643
Defense Advanced Research Projects Agency (DARPA)N66001-08-1-2065
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:Demixing; Sparsity; Integral geometry; Convex optimization
Issue or Number:3
Classification Code:Mathematical Subject Classification: 60D05; 52B55; 52A22 (primary); 94B75 (secondary)
Record Number:CaltechAUTHORS:20140606-140701312
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:46134
Deposited By: Tony Diaz
Deposited On:06 Jun 2014 23:05
Last Modified:03 Oct 2019 06:41

Repository Staff Only: item control page