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. doi:10.7907/156S-EZ89.


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:04 Oct 2019 00:01

Thesis Files

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


Repository Staff Only: item control page