Buffons Needle and Big Data: Theory and Applications of Conic Integral Geometry

Project: Research

View graph of relations

Description

Modern science and technology depends increasingly on the efficient representation, recovery, and processing of vast amounts of data. Surprisingly, for some problems there are simple heuristics, which work unexpectedly well in practice if the parameters of the algorithm are chosen favorably, while they almost certainly fail if the parameters are slightly off. A specific class of algorithms where this phenomenon is evident is found in the active field of compressed sensing and its relatives. A key concept is here that of convex regularization: the initial intractable problem is replaced by a convex surrogate, which is efficiently solvable. The important questions are then, if the solution of the relaxed problem in fact yields a solution for the initial problem, and if so, “how much” the original problem can be relaxed so that this approach works with high probability. The hope is that one can achieve in this way a complexity proportional to the information content of the data rather than its raw size. The goal of this research project is to work out the geometric foundations that underlie these phase transition phenomena in the space of parameters, and to elaborate simple tools that allow to exploit these phenomena algorithmically. These geometric foundations are found in the integral geometry of convex cones. In an earlier work, the principal investigator and coauthors have shown that in high dimensions convex regularization techniques in signal recovery and in signal demixing always exhibit a phase transition, which is determined by the statistical dimensions of the involved cones. The statistical dimension is the expectation of a discrete probability distribution, the conic intrinsic volumes, which broadly describe the statistical dimensionalities of a convex cone. These intrinsic volumes lie at the heart of the field of conic integral geometry and thus form the center of the proposed research project. It can be shown that, for example, the success probabilities of above-mentioned convex relaxation methods, are exactly expressible in terms the intrinsic volumes through the so-called kinematic formulas. Establishing a solid theory around these kinematic formulas (Buffon’s Needle) in their most general form, combining them with techniques from high-dimensional geometry, and applying the theory to the analysis of algorithms in fields like signal processing and statistics (Big Data) is the set goal for this project.

Detail(s)

Project number9048034
Grant typeECS
StatusFinished
Effective start/end date1/08/1517/07/18

    Research areas

  • geometric probability,high-dimensional statistics,convex regularization,phase transitions,