Certifying Euclidean sections and finding planted sparse vectors beyond the n dimension threshold
From MaRDI portal
Publication:6846215
Cites work
- A remark on compressed sensing
- A simple and sharper proof of the hypergraph Moore bound
- Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
- ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS
- Almost-Euclidean subspaces of _1N via tensor products: a simple approach to randomness reduction
- Approximability and proof complexity
- Compressed sensing
- Decoding by Linear Programming
- Dictionary learning and tensor decomposition via the sum-of-squares method
- Euclidean Sections of $\ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals
- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
- Hidden Cliques and the Certification of the Restricted Isometry Property
- High-dimensional probability. An introduction with applications in data science
- scientific article; zbMATH DE number 5485498 (Why is no real title available?)
- scientific article; zbMATH DE number 3551404 (Why is no real title available?)
- scientific article; zbMATH DE number 6026126 (Why is no real title available?)
- Hypercontractivity, sum-of-squares proofs, and their applications
- New SDP roundings and certifiable approximation for cubic optimization
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- On consistency and sparsity for principal components analysis in high dimensions
- Optimal spectral recovery of a planted vector in a subspace
- Rounding sum-of-squares relaxations
- Semialgebraic Proofs and Efficient Algorithm Design
- Sharp bounds on the rate of convergence of the empirical covariance matrix
- Sparse PCA: algorithms, adversarial perturbations and certificates
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Strongly refuting random CSPs below the spectral threshold
- Subexponential-time algorithms for sparse PCA
- Sum-of-squares certificates for maxima of random tensors on the sphere
- Sum-of-squares lower bounds for sparse independent set
- The Average-Case Time Complexity of Certifying the Restricted Isometry Property
- The dimension of almost spherical sections of convex bodies
- The Kikuchi hierarchy and tensor PCA
- Weak decoupling, polynomial folds and approximate optimization over the sphere
This page was built for publication: Certifying Euclidean sections and finding planted sparse vectors beyond the \(\sqrt{n}\) dimension threshold
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6846215)
