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

CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Flavors of Compressive Sensing, NEIGHBORLINESS OF THE SYMMETRIC MOMENT CURVE, Absorption probabilities for Gaussian polytopes and regular spherical simplices, Face numbers of high-dimensional Poisson zero cells, Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control, A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials, Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices, Sparse recovery from extreme eigenvalues deviation inequalities, On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels, Consistent parameter estimation for Lasso and approximate message passing, Unnamed Item, Characterizing the SLOPE trade-off: a variational perspective and the Donoho-Tanner limit, A theory of capacity and sparse neural encoding, Facets of spherical random polytopes, \(r\)-Lah distribution: properties, limit theorems and an application to compressed sensing, 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, Graphs, skeleta and reconstruction of polytopes, 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, Improved bounds for sparse recovery from subsampled random convolutions, Gaussian polytopes: a cumulant-based approach, Compressed sensing of data with a known distribution, A Rice method proof of the null-space property over the Grassmannian, The convex geometry of linear inverse problems, An algebraic perspective on integer sparse recovery, Random Gale diagrams and neighborly polytopes in high dimensions, Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks, Analysis of sparse recovery algorithms via the replica method, Threshold phenomena for random cones, Convex cones spanned by regular polytopes, The restricted isometry property of block diagonal matrices for group-sparse signal recovery, Sparse reconstruction with multiple Walsh matrices, 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, Typicall₁-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices, Iteratively reweighted least squares minimization for sparse recovery

Cites Work