Neighborliness of randomly projected simplices in high dimensions
From MaRDI portal
Publication:5385847
DOI10.1073/PNAS.0502258102zbMath1135.60300OpenAlexW2170929819WikidataQ33892292 ScholiaQ33892292MaRDI QIDQ5385847
Publication date: 7 May 2008
Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1073/pnas.0502258102
phase transitionsneighborly polytopesunderdetermined systems of linear equationsconvex hull of Gaussian sampleuniformly distributed random projections
Related Items (60)
Convex cones spanned by regular polytopes ⋮ Face numbers of high-dimensional Poisson zero cells ⋮ Gaussian polytopes: a cumulant-based approach ⋮ Counting the faces of randomly-projected hypercubes and orthants, with applications ⋮ Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing ⋮ Sharp MSE bounds for proximal denoising ⋮ The restricted isometry property of block diagonal matrices for group-sparse signal recovery ⋮ Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods ⋮ Random sampling of sparse trigonometric polynomials ⋮ Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization ⋮ Performance comparisons of greedy algorithms in compressed sensing ⋮ Realizability and inscribability for simplicial polytopes via nonlinear optimization ⋮ Sharp recovery bounds for convex demixing, with applications ⋮ Unnamed Item ⋮ \(r\)-Lah distribution: properties, limit theorems and an application to compressed sensing ⋮ Phase transitions in semidefinite relaxations ⋮ The Lasso with general Gaussian designs with applications to hypothesis testing ⋮ Angle sums of random polytopes ⋮ A Rice method proof of the null-space property over the Grassmannian ⋮ Guarantees of total variation minimization for signal recovery ⋮ Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions ⋮ Null space conditions and thresholds for rank minimization ⋮ The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes ⋮ Compressive Sensing ⋮ BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING ⋮ Recovery of signals under the condition on RIC and ROC via prior support information ⋮ The restricted isometry property for random block diagonal matrices ⋮ Sparse nonnegative solution of underdetermined linear equations by linear programming ⋮ System identification in the presence of outliers and random noises: a compressed sensing approach ⋮ A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization ⋮ Statistical mechanics of complex neural systems and high dimensional data ⋮ Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing ⋮ A preconditioning approach for improved estimation of sparse polynomial chaos expansions ⋮ A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials ⋮ Overcoming the limitations of phase transition by higher order analysis of regularization techniques ⋮ Uniqueness of the minimal \(l_1\)-norm solution to the monotone linear complementarity problem ⋮ On tight bounds for the Lasso ⋮ Consistent parameter estimation for Lasso and approximate message passing ⋮ Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices ⋮ The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising ⋮ A simple and feasible method for a class of large-scale \(l^1\)-problems ⋮ A numerical exploration of compressed sampling recovery ⋮ Discussion of: Treelets -- an adaptive multi-scale basis for sparse unordered data ⋮ Linearized Bregman iterations for compressed sensing ⋮ A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers ⋮ Random Gale diagrams and neighborly polytopes in high dimensions ⋮ Counting faces of randomly projected polytopes when the projection radically lowers dimension ⋮ A coordinate descent homotopy method for linearly constrained nonsmooth convex minimization ⋮ The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning ⋮ Sparse recovery from extreme eigenvalues deviation inequalities ⋮ Random projections of smooth manifolds ⋮ An ℓ<sub>q</sub>- Seminorm Variational Model for Impulse Noise Reduction ⋮ Symmetry in data mining and analysis: a unifying view based on hierarchy ⋮ Universality in polytope phase transitions and message passing algorithms ⋮ Lah distribution: Stirling numbers, records on compositions, and convex hulls of high-dimensional random walks ⋮ Theory and applications of compressed sensing ⋮ Analysis of sparse recovery algorithms via the replica method ⋮ Thinking Ultrametrically, Thinking p-Adically ⋮ Empirical average-case relation between undersampling and sparsity in X-ray CT ⋮ The remarkable simplicity of very high dimensional data: application of model-based clustering
Cites Work
- Random projections of regular simplices
- Regular simplices and Gaussian samples
- Random projections of regular polytopes
- On the geometrical moments of skew-regular simplices in hyperspherical space, with some applications in geometry and mathematical statistics
- Non-linear angle-sum relations for polyhedral cones and polytopes
- Sparse nonnegative solution of underdetermined linear equations by linear programming
This page was built for publication: Neighborliness of randomly projected simplices in high dimensions
