In this paper we explore properties of a family of probability density functions, called norm-induced densities, defined as
where K is a n-dimensional convex set that contains the origin, parameters t > 0 and p > 0, and is any norm. We also develop connections between these densities and geometric properties of K such as diameter, width of the recession cone, and others. Since
is log-concave only if
this framework also covers non-logconcave densities.
Moreover, we establish a new set inclusion characterization for convex sets. This leads to a new concentration of measure phenomena for unbounded convex sets. More precisely, we show that most points of an unbounded convex set are contained in any enlargement of the set's recession cone. In turn, when the recession cone has positive width, most points are actually in the recession cone itself.
Finally, these properties are used to develop an efficient probabilistic algorithm to test whether a convex set, represented only by membership oracles (a membership oracle for K and a membership oracle for its recession cone), is bounded or not, where the algorithm reports an associated certificate of boundedness or unboundedness.
By: Alexandre Belloni
Published in: RC24145 in 2006
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .