The stochastic geometry of unconstrained one-bit data compression

DOI10.1214/19-EJP389MaRDI QIDQ2279335zbMATH OpenOpenAlexFDO

Authors Eliza O'reilly, Francois Baccelli

Publication date 12 December 2019

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.06095, https://projecteuclid.org/euclid.ejp/1575342533

zbMATH Keywords

high dimensional Euclidean spaceone-bit compressed sensingPoisson hyperplane processPoisson point processsource codingzero cell: typical cell

Mathematics Subject Classification ID

Random convex sets and integral geometry (aspects of convex geometry) (52A22) Geometric probability and stochastic geometry (60D05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Rate-distortion theory in information and communication theory (94A34)

Abstract: A stationary stochastic geometric model is proposed for analyzing the data compression method used in one-bit compressed sensing. The data set is an unconstrained stationary set, for instance all of $mathbb{R}^n$ or a stationary Poisson point process in $mathbb{R}^n$. It is compressed using a stationary and isotropic Poisson hyperplane tessellation, assumed independent of the data. That is, each data point is compressed using one bit with respect to each hyperplane, which is the side of the hyperplane it lies on. This model allows one to determine how the intensity of the hyperplanes must scale with the dimension $n$ to ensure sufficient separation of different data by the hyperplanes as well as sufficient proximity of the data compressed together. The results have direct implications in compressive sensing and in source coding.

Recommendations

• Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing
• Stability of 1-bit compressed sensing in sparse data reconstruction
• One-bit compressed sensing by linear programming
• Dimension reduction by random hyperplane tessellations
• Stationary Stochastic Processes and Fractal Data Compression

Cites work

• Analysis of spherical symmetries in Euclidean spaces
• Beta polytopes and Poisson polyhedra: \(f\)-vectors and angles
• Capacity and error exponents of stationary point processes under random additive displacements
• Cones generated by random points on half-spheres and convex hulls of Poisson point processes
• Determinantal point process models and statistical inference
• Dimension reduction by random hyperplane tessellations
• Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On coding without restrictions for the AWGN channel
• On the volume of the zero cell of a class of isotropic Poisson hyperplane tessellations
• One-bit compressed sensing by linear programming
• One-Bit Compressive Sensing With Norm Estimation
• Poisson polyhedra in high dimensions
• Precise formulae for the distributions of the principal geometric characteristics of the typical cells of a two-dimensional Poisson-Voronoi tessellation and a Poisson line process
• Stochastic and Integral Geometry
• Stochastic geometry and its applications
• The distributions of the smallest disks containing the Poisson-Voronoi typical cell and the Crofton cell in the plane
• The limit shape of the zero cell in a stationary Poisson hyperplane tessellation.
• Thin-shell concentration for zero cells of stationary Poisson mosaics
• Volume degeneracy of the typical cell and the chord length distribution for Poisson-Voronoi tessellations in high dimensions

Cited in

(5)

• An informational approach to the problem of compressing random processes
• Faces in random great hypersphere tessellations
• Thin-shell concentration for zero cells of stationary Poisson mosaics
• Stochastic Tverberg theorems with applications in multiclass logistic regression, separability, and centerpoints of data
• Facets of spherical random polytopes

Describes a project that uses

Uses Software

• spatstat

This page was built for publication: The stochastic geometry of unconstrained one-bit data compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279335)