A geometric analysis of convex demixing Thesis by Michael B. McCoy In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 2013 (Defended May 13, 2013) ii (cid:13)c 2013 Michael B. McCoy All Rights Reserved iii To Anya. iv Acknowledgments Let me start by thanking my family. My father gave me an enthusiasm for knowledge and science, as well as the foolhardy belief that I really can do what I want. Without these enduring traits, the work here would not have come to fruition. My mother’s love and support, and her infinite patience, let me become much more than I thought possible. My wife, Anya, gave me constant support and encouragement during my graduate studies; I could not have succeeded without her. Second, I want to thank my friend and advisor Joel Tropp for his conscientious attention to my intellectual development. His broad perspective on research extends to many other facets of life, and this provided both confidence and freedom for me to choose my path both at Caltech and beyond. I have seen Joel extend his support and guidance generously to all of his students, which sets an aspirational standard for my own development as a mentor. Thank you. Thanks to Alex Gittens for letting me pester him with innumerable, mostly inane, questions. Theseinteractionsprovidedawelcomereleasefortheisolationthatinevitably accompanies mathematical pondering. It is good to have a friend like you around. My officemate, Keenan Crane, deserves similar thanks for serving as a sounding board for half-baked ideas; his sharp wit also makes him an extraordinary friend. To my good friends Andrew & Kelsey Homyk, and their wonderful children Natalie & Ashton, thanks for the many enjoyable evenings. My newest friends, Cole & Robin DeForest and Jessica Pfeilsticker, have made the last year spectacular. John Bruer and Trevor Fowler provided many nights of good cheer on the lawn of the Athenaeum. GuillaumeBouytgreatlyenrichedmyfirstyearherewithhisinquisitivespiritandardent French pride. v There are many, many more people who have influenced me during my time in Pasadena. Juhwan Yoo’s tenacity and persistence have opened up promising directions for my future, and I am glad to call him a friend. Thanks to Richard Chen, Simon Chien, and Brendan Farrell for many recent conversations, and to Tomek Tyranowski and Patrick Sanan for many older ones when we were just starting out. Thanks also to my food buddy Randy Clemens for his enviable prose, and to Mike & Andrea Reinhardt for their passion for life and wonderful spirits. The administrators in the CMS department make the life of all of the students extraordinary. I personally owe many thanks to Sydney Garstang, Sheila Shull, Maria Lopez, and Jeri Chittum for their diligent and friendly help over the past six years. Finally, I gratefully acknowledge the financial sources, under Joel’s aegis, in support of my education, including ONR awards N00014-08-1-0883 and N00014-11-1002, AFOSR award FA9550-09-1-0643, and funds from a Sloan Research Fellowship. vi Abstract Demixing is the task of identifying multiple signals given only their sum and prior information about their structures. Examples of demixing problems include (i) sepa- rating 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. vii Contents Acknowledgments iv Abstract vi 1 Introduction 1 1.1 Demixing archetype. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 A mixed signal model . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Constrained MCA demixing procedure . . . . . . . . . . . . . . . . 4 1.1.3 A probabilistic characterization of MCA . . . . . . . . . . . . . . . . 4 1.2 A recipe for demixing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Structured signals and atomic gauges . . . . . . . . . . . . . . . . . 6 1.2.2 Formulating convex demixing methods . . . . . . . . . . . . . . . . 9 1.2.2.1 Multiple demixing . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2.2 Compressed demixing . . . . . . . . . . . . . . . . . . . . . 10 1.2.2.3 Lagrangian counterparts . . . . . . . . . . . . . . . . . . . 11 1.2.3 The random alignement model of incoherence . . . . . . . . . . . 12 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 A survey of the literature 16 2.1 Mixed signal models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Moving beyond sparsity. . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Methods for demixing signals . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1 Convex demixing methods . . . . . . . . . . . . . . . . . . . . . . . . 19 viii 2.2.2 Greedy demixing methods . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Analyses of demixing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.1 Sparse + sparse demixing . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.2 Demixing beyond sparsity . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.3 Linear inverse problems . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.3.1 Asymptotic polytope angle computations . . . . . . . . . 29 2.3.3.2 Gaussian width analyses . . . . . . . . . . . . . . . . . . . 30 3 Mathematical preliminaries 33 3.1 Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2 Convex cones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Projections and distances . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.2 Descent cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3 The topology of convex cones. . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4 The geometry of demixing 51 4.1 Optimality conditions for constrained demixing . . . . . . . . . . . . . . . 52 4.2 Multiple demixing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3 Compressed demixing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.3.1 Linear inverse problems . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.4 Proof of Theorem 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.5 The Lagrangian formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5 Conic integral geometry 65 5.1 Conic intrinsic volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2 Steiner formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.3 Kinematic formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.3.1 Iterated kinematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.4 Rare events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.4.1 Cone intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.4.2 Closure issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 ix 6 The statistical dimension 81 6.1 Basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.2 Explicit computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2.1 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2.2 Self-dual cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.2.3 Circular cones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.2.4 Descent cones of the (cid:96) norm . . . . . . . . . . . . . . . . . . . . . . 93 ∞ 6.2.5 A recipe for general descent cones . . . . . . . . . . . . . . . . . . . 95 6.2.6 Descent cones of the (cid:96) norm . . . . . . . . . . . . . . . . . . . . . . 96 1 6.2.7 Descent cones of the Schatten 1-norm . . . . . . . . . . . . . . . . . 101 6.3 Relationship to the Gaussian width . . . . . . . . . . . . . . . . . . . . . . . 105 7 Concentration of intrinsic volumes 109 7.1 Parallels with Euclidean integral geometry. . . . . . . . . . . . . . . . . . . 110 7.2 Proof of Theorem 7.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 7.3 Proof of technical propositions . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.3.1 Concentration of projections onto cones . . . . . . . . . . . . . . . 114 7.3.2 An inequality for chi-square random variables . . . . . . . . . . . . 117 8 Kinematic consequences 120 8.1 Iterated approximate kinematics . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.2 Proof of Theorem 8.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 8.2.1 Proof of technical lemmas . . . . . . . . . . . . . . . . . . . . . . . . 124 9 Success and failure of demixing 127 9.1 Transition for extended demixing . . . . . . . . . . . . . . . . . . . . . . . . 129 9.2 Proof of Theorem 9.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 10 Applications and numerical examples 137 10.1 Sparse + sparse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 10.1.1 Strong bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 10.1.2 Undersampled sparse + sparse . . . . . . . . . . . . . . . . . . . . . 143 x 10.2 Sparse + sign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 10.2.1 Strong bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 10.2.2 Sparse + sparse + sign . . . . . . . . . . . . . . . . . . . . . . . . . . 149 10.3 Sparse + low-rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 10.4 Linear inverse problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 10.4.1 The sparse inverse problem . . . . . . . . . . . . . . . . . . . . . . . 152 A A general Steiner formula 156 A.1 Consequences of Theorem A.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 157 A.1.1 The conic Wills functional . . . . . . . . . . . . . . . . . . . . . . . . 161 A.2 Proof of the general Steiner formula . . . . . . . . . . . . . . . . . . . . . . 164 A.2.1 A tiling induced by a cone . . . . . . . . . . . . . . . . . . . . . . . . 165 A.2.2 Polytope angles & intrinsic volumes . . . . . . . . . . . . . . . . . . 166 A.2.3 Proof of Theorem A.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 B Proofs of results in Chapter 10 171 B.1 Sparse + sparse demixing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 B.1.1 Phase transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 B.1.2 Strong bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 B.1.3 Undersampled bounds . . . . . . . . . . . . . . . . . . . . . . . . . . 177 B.2 Sparse + sign demixing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 B.2.1 Phase transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 B.2.2 Strong bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 C Numerical details 180 C.1 Statistical dimension calculations . . . . . . . . . . . . . . . . . . . . . . . . 180 C.2 Experimental generalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 C.3 Sparse + sparse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 C.3.1 Undersampled sparse + sparse . . . . . . . . . . . . . . . . . . . . . 181 C.4 Sparse + sign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 C.4.1 Sparse + sparse + sign . . . . . . . . . . . . . . . . . . . . . . . . . . 182