Counting faces of randomly projected polytopes when the projection radically lowers dimension

DOI10.1090/S0894-0347-08-00600-0zbMath1206.52010arXivmath/0607364MaRDI QIDQ3079190

Publication date: 2 March 2011

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0607364

Mathematics Subject Classification ID

62E20: Asymptotic distribution theory in statistics

52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

94A12: Signal theory (characterization, reconstruction, filtering, etc.)

94B35: Decoding

94B70: Error probability in coding theory

52A22: Random convex sets and integral geometry (aspects of convex geometry)

Related Items

NEIGHBORLINESS OF THE SYMMETRIC MOMENT CURVE, Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices, On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels, SLOPE is adaptive to unknown sparsity and asymptotically minimax, Deterministic convolutional compressed sensing matrices, The restricted isometry property for time-frequency structured random matrices, Centrally symmetric polytopes with many faces, Simple bounds for recovering low-complexity models, Sharp recovery bounds for convex demixing, with applications, Restricted isometries for partial random circulant matrices, On the geometry of random convex sets between polytopes and zonotopes, Generalized sampling and infinite-dimensional compressed sensing, Sparse signal recovery using a new class of random matrices, Phase transitions for greedy sparse approximation algorithms, Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Enhancing sparsity by reweighted \(\ell _{1}\) minimization, Hard thresholding pursuit algorithms: number of iterations, Compressed history matching: Exploiting transform-domain sparsity for regularization of nonlinear dynamic data integration problems, Sparse disjointed recovery from noninflating measurements, Analysis \(\ell_1\)-recovery with frames and Gaussian measurements, On the conditioning of random subdictionaries, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Random projections of smooth manifolds, The convex geometry of linear inverse problems, Universality in polytope phase transitions and message passing algorithms, Counting the faces of randomly-projected hypercubes and orthants, with applications, Compressed sensing for finite-valued signals, Intrinsic volumes of polyhedral cones: a combinatorial perspective, Greedy-like algorithms for the cosparse analysis model, A centrally symmetric version of the cyclic polytope, Compressive Sensing, Estimation in High Dimensions: A Geometric Perspective, Performance comparisons of greedy algorithms in compressed sensing, BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING, Monotonicity of expected 𝑓-vectors for projections of regular polytopes, Book Review: A mathematical introduction to compressive sensing, Iteratively reweighted least squares minimization for sparse recovery

Cites Work