Suppose that we observe the sum of two structured signals, and we are asked to identify the two components in the mixture. For example, this setup includes the problem of separating two signals that are sparse in different bases, as well as the problem of separating a sparse matrix from a low-rank matrix. This talk describes a convex optimization framework for solving these demixing problems and many others. We present a randomized signal model that encapsulates the notion of "incoherence" between two structures. For this model, the calculus of spherical integral geometry provides exact formulas that describe when the optimization problem will succeed (or fail) to demix the component signals with high probability. This approach yields summary statistics that measure the complexity of a particular structure (such as a sparse vector or a low-rank matrix). We argue that our ability to separate two structured signals depends only on the total complexity of the two structures. As applications of these ideas, we consider several stylized problems. (1) Separating two signals that are sparse in mutually incoherent bases. (2) Decoding spread-spectrum transmissions in the presence of impulsive noise. (3) Removing sparse corruptions from a low-rank matrix. In each case, our theoretical prediction of the performance of convex demixing closely matches its empirical behavior. Joint work with Michael B. McCoy
Copyright. All Rights Reserved.