Recovery analysis for weighted _1-minimization using the null space property

DOI10.1016/J.ACHA.2015.10.005MaRDI QIDQ2397162zbMATH OpenOpenAlexFDO

Authors Hassan Mansour, Rayan Saab

Publication date 29 May 2017

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.1565

zbMATH Keywords

compressed sensingGaussian widthsnull space propertysignal recoveryweighted \(\ell_1\) minimization

Mathematics Subject Classification ID

Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Abstract: We study the recovery of sparse signals from underdetermined linear measurements when a potentially erroneous support estimate is available. Our results are twofold. First, we derive necessary and sufficient conditions for signal recovery from compressively sampled measurements using weighted $el{l}_1$-norm minimization. These conditions, which depend on the choice of weights as well as the size and accuracy of the support estimate, are on the null space of the measurement matrix. They can guarantee recovery even when standard $el{l}_1$ minimization fails. Second, we derive bounds on the number of Gaussian measurements for these conditions to be satisfied, i.e., for weighted $el{l}_1$ minimization to successfully recover all sparse signals whose support has been estimated sufficiently accurately. Our bounds show that weighted $el{l}_1$ minimization requires significantly fewer measurements than standard $el{l}_1$ minimization when the support estimate is relatively accurate.

Recommendations

• Weighted \(\ell_1\)-minimization for sparse recovery under arbitrary prior information
• Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\)
• Weighted _p-minimization for sparse signal recovery under arbitrary support prior
• Sparse recovery of weighted nonconvex _q-minimization
• Robust signal recovery for \(\ell_{1-2}\) minimization via prior support information

Cites work

• A mathematical introduction to compressive sensing
• A short note on compressed sensing with partially known signal support
• Compressed sensing
• Compressed sensing and best \(k\)-term approximation
• scientific article; zbMATH DE number 4061904 (Why is no real title available?)
• Interpolation via weighted \(\ell_{1}\) minimization
• Modified-CS: Modifying Compressive Sensing for Problems With Partially Known Support
• On sparse reconstruction from Fourier and Gaussian measurements
• Recovering Compressively Sampled Signals Using Partial Support Information
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sparse signal reconstruction via iterative support detection
• Stable signal recovery from incomplete and inaccurate measurements
• The convex geometry of linear inverse problems

Cited in

(24)

• Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\)
• Sparse approximate reconstruction decomposed by two optimization problems
• Weighted \(\ell_p\) (\(0<p\le 1\)) minimization with non-uniform weights for sparse recovery under partial support information
• Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm
• Phaseless compressive sensing using partial support information
• New conditions on stable recovery of weighted sparse signals via weighted l₁ minimization
• Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery With Nonuniform Sparse Models
• Weighted \(\ell_1\)-minimization for sparse recovery under arbitrary prior information
• A null-space-based weightedl₁minimization approach to compressed sensing
• Joint sparse recovery based on variances
• Sufficient conditions on stable reconstruction of weighted problem
• Sparse recovery of weighted nonconvex _q-minimization
• Robust recovery of a kind of weighted l1-minimization without noise level
• Robust recovery of signals with partially known support information using weighted BPDN
• Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
• Robust signal recovery for \(\ell_{1-2}\) minimization via prior support information
• Weighted _p-minimization for sparse signal recovery under arbitrary support prior
• The null space property of the weighted ℓr − ℓ1 minimization
• Sparse reconstruction via the mixture optimization model with iterative support estimate
• Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms for signal recovery with partial support information
• AdaTL₁: an adaptive non-convex sparse solver with applications to CT reconstruction and image denoising
• Locality regularized reconstruction: structured sparsity and Delaunay triangulations
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Analysis _1-recovery with frames and Gaussian measurements

This page was built for publication: Recovery analysis for weighted \(\ell_{1}\)-minimization using the null space property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397162)