Instance-optimality in probability with an _1-minimization decoder
The purpose of the paper is to point out that a weaker geometric property of the studied already by A. Litvak et al. random matrices, when coupled with decoding by minimization will yield instance-optimality in probability for the large range of \(k\). The first sections of the paper concentrate on proving instance-optimality for Bernoulli matrices where the proofs are most transparent. In Section 3, a geometric mapping property of Bernoulli matrices is presented (Theorem 3.5). This property is used to prove in Section 4 that instance-optimality in probability holds for Bernoulli matrices. The arguments are organized to extract the essential properties of Bernoulli matrices that are needed for the proof. In Section 5, it is shown that these properties hold for quite general random families and thereby obtain a broad generalization of the Bernoulli case.
- Sparse recovery by non-convex optimization - instance optimality
- Instance optimal decoding by thresholding in compressed sensing
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- A simple proof of the restricted isometry property for random matrices
- Uniform uncertainty principle for Bernoulli and subgaussian ensembles
- A distribution-free theory of nonparametric regression
- A simple proof of the restricted isometry property for random matrices
- Compressed sensing
- Compressed sensing and best \(k\)-term approximation
- Decoding by Linear Programming
- Deterministic constructions of compressed sensing matrices
- scientific article; zbMATH DE number 3944477 (Why is no real title available?)
- scientific article; zbMATH DE number 3551404 (Why is no real title available?)
- scientific article; zbMATH DE number 713342 (Why is no real title available?)
- scientific article; zbMATH DE number 741240 (Why is no real title available?)
- scientific article; zbMATH DE number 3306375 (Why is no real title available?)
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Smallest singular value of random matrices and geometry of random polytopes
- Stability and instance optimality for Gaussian measurements in compressed sensing
- Stable signal recovery from incomplete and inaccurate measurements
- The Distribution of Rademacher Sums
- The restricted isometry property and its implications for compressed sensing
- Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\)
- On the robustness of minimum norm interpolators and regularized empirical risk minimizers
- On the robustness of noise-blind low-rank recovery from rank-one measurements
- Stability and instance optimality for Gaussian measurements in compressed sensing
- On the strong restricted isometry property of Bernoulli random matrices
- On some aspects of approximation of ridge functions
- New analysis of manifold embeddings and signal recovery from compressive measurements
- Capturing ridge functions in high dimensions from point queries
- Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
- Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
- On the sparsity of Lasso minimizers in sparse data recovery
- Restricted isometry property for matrices whose entries are random variables belonging to some Orlicz spaces L_U()
- Instance optimal decoding by thresholding in compressed sensing
- Learning functions of few arbitrary linear parameters in high dimensions
- Compressive sensing of analog signals using discrete prolate spheroidal sequences
- On the geometry of polytopes generated by heavy-tailed random vectors
- Robust recovery of a kind of weighted l1-minimization without noise level
- Orthogonal matching pursuit under the restricted isometry property
- Towards probabilistic robust and sparsity-free compressive sampling in civil engineering: a review
- Letter to the editor. Instance optimality in phase retrieval
- Restricted \(p\)-isometry property and its application for nonconvex compressive sensing
- Preserving injectivity under subgaussian mappings and its application to compressed sensing
This page was built for publication: Instance-optimality in probability with an \(\ell _1\)-minimization decoder
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q734324)
