Counting faces of randomly projected polytopes when the projection radically lowers dimension
From MaRDI portal
Publication:3079190
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
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, Typicall1-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices, Iteratively reweighted least squares minimization for sparse recovery
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extensions of compressed sensing
- Random projections of regular simplices
- High dimensional probability III. Third international conference on high dimensional probability, Sandjberg, Denmark, June 24--28, 2002. Selected papers
- Random projections of regular polytopes
- High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
- How neighborly can a centrally symmetric polytope be?
- On the geometrical moments of skew-regular simplices in hyperspherical space, with some applications in geometry and mathematical statistics
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Decoding by Linear Programming
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Neighbourliness of centrally symmetric polytopes in high dimensions
- On the inherent intractability of certain coding problems (Corresp.)
- Limit theorems for the convex hull of random points in higher dimensions
- Convex Polytopes
- Geometric Representation of High Dimension, Low Sample Size Data
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Neighborliness of randomly projected simplices in high dimensions
- For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution
- Diagrams for centrally symmetric polytopes
- Compressed sensing