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

DOI10.1090/S0894-0347-08-00600-0zbMath1206.52010arXivmath/0607364OpenAlexW2115275122MaRDI 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

Asymptotic distribution theory in statistics (62E20) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Decoding (94B35) Error probability in coding theory (94B70) Random convex sets and integral geometry (aspects of convex geometry) (52A22)

Related Items (69)

Convex cones spanned by regular polytopes ⋮ SLOPE is adaptive to unknown sparsity and asymptotically minimax ⋮ Face numbers of high-dimensional Poisson zero cells ⋮ Improved bounds for sparse recovery from subsampled random convolutions ⋮ Gaussian polytopes: a cumulant-based approach ⋮ Book Review: A mathematical introduction to compressive sensing ⋮ Counting the faces of randomly-projected hypercubes and orthants, with applications ⋮ Compressed history matching: Exploiting transform-domain sparsity for regularization of nonlinear dynamic data integration problems ⋮ Deterministic convolutional compressed sensing matrices ⋮ The restricted isometry property of block diagonal matrices for group-sparse signal recovery ⋮ Compressed sensing for finite-valued signals ⋮ The restricted isometry property for time-frequency structured random matrices ⋮ Compressed sensing of data with a known distribution ⋮ Centrally symmetric polytopes with many faces ⋮ Intrinsic volumes of polyhedral cones: a combinatorial perspective ⋮ Simple bounds for recovering low-complexity models ⋮ The convex geometry of linear inverse problems ⋮ Performance comparisons of greedy algorithms in compressed sensing ⋮ Sparse disjointed recovery from noninflating measurements ⋮ Characterizing the SLOPE trade-off: a variational perspective and the Donoho-Tanner limit ⋮ Sharp recovery bounds for convex demixing, with applications ⋮ A theory of capacity and sparse neural encoding ⋮ Facets of spherical random polytopes ⋮ Restricted isometries for partial random circulant matrices ⋮ Elliptic polytopes and invariant norms of linear operators ⋮ A fixed-time converging neurodynamic approach with time-varying coefficients for \(l_1\)-minimization problem ⋮ Phase transitions for greedy sparse approximation algorithms ⋮ \(r\)-Lah distribution: properties, limit theorems and an application to compressed sensing ⋮ Facets of high-dimensional Gaussian polytopes ⋮ The Lasso with general Gaussian designs with applications to hypothesis testing ⋮ Angle sums of random polytopes ⋮ Analysis \(\ell_1\)-recovery with frames and Gaussian measurements ⋮ A Rice method proof of the null-space property over the Grassmannian ⋮ CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion ⋮ Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling ⋮ Compressive Sensing ⋮ BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING ⋮ Flavors of Compressive Sensing ⋮ Greedy-like algorithms for the cosparse analysis model ⋮ Unnamed Item ⋮ On the conditioning of random subdictionaries ⋮ Typicall₁-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices ⋮ Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control ⋮ On the geometry of random convex sets between polytopes and zonotopes ⋮ A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials ⋮ NEIGHBORLINESS OF THE SYMMETRIC MOMENT CURVE ⋮ Generalized sampling and infinite-dimensional compressed sensing ⋮ Sparse signal recovery using a new class of random matrices ⋮ Consistent parameter estimation for Lasso and approximate message passing ⋮ A centrally symmetric version of the cyclic polytope ⋮ Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices ⋮ An algebraic perspective on integer sparse recovery ⋮ Graphs, skeleta and reconstruction of polytopes ⋮ Estimation in High Dimensions: A Geometric Perspective ⋮ Enhancing sparsity by reweighted \(\ell _{1}\) minimization ⋮ Random Gale diagrams and neighborly polytopes in high dimensions ⋮ Hard thresholding pursuit algorithms: number of iterations ⋮ CoSaMP: Iterative signal recovery from incomplete and inaccurate samples ⋮ Sparse recovery from extreme eigenvalues deviation inequalities ⋮ Random projections of smooth manifolds ⋮ Sparse reconstruction with multiple Walsh matrices ⋮ Iteratively reweighted least squares minimization for sparse recovery ⋮ Absorption probabilities for Gaussian polytopes and regular spherical simplices ⋮ Monotonicity of expected 𝑓-vectors for projections of regular polytopes ⋮ Universality in polytope phase transitions and message passing algorithms ⋮ Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks ⋮ Analysis of sparse recovery algorithms via the replica method ⋮ On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels ⋮ Threshold phenomena for random cones

Cites Work

This page was built for publication: Counting faces of randomly projected polytopes when the projection radically lowers dimension