A Caltech Library Service

A geometric analysis of convex demixing


McCoy, Michael Brian (2013) A geometric analysis of convex demixing. Dissertation (Ph.D.), California Institute of Technology.


Demixing is the task of identifying multiple signals given only their sum and prior information about their structures. Examples of demixing problems include (i) separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis; (ii) decomposing an observed matrix into low-rank and sparse components; and (iii) identifying a binary codeword with impulsive corruptions. This thesis describes and analyzes a convex optimization framework for solving an array of demixing problems.

Our framework includes a random orientation model for the constituent signals that ensures the structures are incoherent. This work introduces a summary parameter, the statistical dimension, that reflects the intrinsic complexity of a signal. The main result indicates that the difficulty of demixing under this random model depends only on the total complexity of the constituent signals involved: demixing succeeds with high probability when the sum of the complexities is less than the ambient dimension; otherwise, it fails with high probability.

The fact that a phase transition between success and failure occurs in demixing is a consequence of a new inequality in conic integral geometry. Roughly speaking, this inequality asserts that a convex cone behaves like a subspace whose dimension is equal to the statistical dimension of the cone. When combined with a geometric optimality condition for demixing, this inequality provides precise quantitative information about the phase transition, including the location and width of the transition region.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:optimization, demixing, linear inverse problems, geometry, compressed sensing
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Tropp, Joel A.
Thesis Committee:
  • Tropp, Joel A. (chair)
  • Hassibi, Babak
  • Chandrasekaran, Venkat
  • Schulman, Leonard J.
Defense Date:13 May 2013
Funding AgencyGrant Number
Sloan Research FellowshipUNSPECIFIED
Record Number:CaltechTHESIS:05202013-091317123
Persistent URL:
McCoy, Michael Brian0000-0002-9479-2090
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7726
Deposited By: Michael McCoy
Deposited On:21 May 2013 18:26
Last Modified:10 Mar 2014 21:31

Thesis Files

PDF (Ph.D. thesis of Michael B. McCoy) - Final Version
See Usage Policy.


Repository Staff Only: item control page