Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices

DOI10.1109/TIT.2013.2288639MaRDI QIDQ5346146zbMATH OpenOpenAlexFDO

Authors Anru Zhang, T. Tony Cai

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis relies on a key technical tool which represents points in a polytope by convex combinations of sparse vectors. The technique is elementary while leads to sharp results. It is shown that for any given constant $tge4/3$, in compressed sensing $delt{a}_{tk}^A<sqrt(t-1)/t$ guarantees the exact recovery of all $k$ sparse signals in the noiseless case through the constrained $el{l}_1$ minimization, and similarly in affine rank minimization $delt{a}_{tr}^{m}athcalM<sqrt(t-1)/t$ ensures the exact reconstruction of all matrices with rank at most $r$ in the noiseless case via the constrained nuclear norm minimization. Moreover, for any $epsilon>0$, $delt{a}_{tk}^A<sqrtfract-1t+epsilon$ is not sufficient to guarantee the exact recovery of all $k$-sparse signals for large $k$. Similar result also holds for matrix recovery. In addition, the conditions $delt{a}_{tk}^A<sqrt(t-1)/t$ and $delt{a}_{tr}^{m}athcalM<sqrt(t-1)/t$ are also shown to be sufficient respectively for stable recovery of approximately sparse signals and low-rank matrices in the noisy case.

Cited in

(only showing first 100 items - show all)

• Signal recovery under cumulative coherence
• Sigma delta quantization with harmonic frames and partial Fourier ensembles
• Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP
• Analysis of the equivalence relationship between \(l_{0}\)-minimization and \(l_{p}\)-minimization
• A hierarchical framework for recovery in compressive sensing
• Sparsity and incoherence in orthogonal matching pursuit
• Recovery of signals under the condition on RIC and ROC via prior support information
• Signal recovery under mutual incoherence property and oracle inequalities
• Sparse recovery in probability via \(l_q\)-minimization with Weibull random matrices for \(0 < q\leq 1\)
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
• Facilitating OWL norm minimizations
• Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
• Low-rank matrix recovery via regularized nuclear norm minimization
• Memoryless scalar quantization for random frames
• Asymptotic analysis for extreme eigenvalues of principal minors of random matrices
• Robust sparse recovery via a novel convex model
• Perturbation analysis of \(L_{1-2}\) method for robust sparse recovery
• Inference for low-rank tensors -- no need to debias
• An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming
• On phaseless compressed sensing with partially known support
• Iterative hard thresholding for compressed data separation
• Analysis non-sparse recovery for relaxed ALASSO
• Signal separation under coherent dictionaries and _p-bounded noise
• Phaseless compressive sensing using partial support information
• Convergence and stability analysis of iteratively reweighted least squares for noisy block sparse recovery
• Sparse signals recovery from noisy measurements by orthogonal matching pursuit
• Uniform recovery from subgaussian multi-sensor measurements
• RIP-based performance guarantee for low-tubal-rank tensor recovery
• Truncated sparse approximation property and truncated \(q\)-norm minimization
• Optimal RIP bounds for sparse signals recovery via \(\ell_p\) minimization
• Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit
• A p-spherical section property for matrix Schatten-p quasi-norm minimization
• ROP: matrix recovery via rank-one projections
• Near oracle performance and block analysis of signal space greedy methods
• Stable recovery of analysis based approaches
• Optimal D-RIP bounds in compressed sensing
• The sparsest solution to the system of absolute value equations
• Refined analysis of sparse MIMO radar
• Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• A simple homotopy proximal mapping algorithm for compressive sensing
• Convergence analysis of projected gradient descent for Schatten-p nonconvex matrix recovery
• Stable recovery of low-rank matrix via nonconvex Schatten p-minimization
• The recovery of complex sparse signals from few phaseless measurements
• On the Schatten \(p\)-quasi-norm minimization for low-rank matrix recovery
• A necessary and sufficient condition for sparse vector recovery via \(\ell_1-\ell_2\) minimization
• Robust signal recovery via \(\ell_{1-2}/ \ell_p\) minimization with partially known support
• Covering point-sets with parallel hyperplanes and sparse signal recovery
• Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
• On sparse recovery algorithms in unions of orthonormal bases
• On the sparsity of Lasso minimizers in sparse data recovery
• The gap between the null space property and the restricted isometry property
• Noise-shaping quantization methods for frame-based and compressive sampling systems
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
• Stable signal recovery from phaseless measurements
• Improved bounds for the RIP of subsampled circulant matrices
• A novel compressed sensing scheme for photoacoustic tomography
• The restricted isometry property for signal recovery with coherent tight frames
• Quantization and compressive sensing
• A null-space-based weightedl₁minimization approach to compressed sensing
• Flavors of compressive sensing
• Stable recovery of sparse signals via \(\ell_p\)-minimization
• Structured random measurements in signal processing
• Perturbation analysis of low-rank matrix stable recovery
• The Dantzig selector: recovery of signal via ℓ ₁ − αℓ ₂ minimization
• A new sufficient condition for sparse vector recovery via _1- _2 local minimization
• Robust width: a characterization of uniformly stable and robust compressed sensing
• Color image inpainting via robust pure quaternion matrix completion: error bound and weighted loss
• Sparse phase retrieval via ℓp (0 < p ≤ 1) minimization
• Stable image reconstruction using transformed total variation minimization
• Performance analysis for unconstrained analysis based approaches
• Recovery analysis for block _p-_1 minimization with prior support information
• Robust recovery of a kind of weighted l1-minimization without noise level
• Robust recovery of signals with partially known support information using weighted BPDN
• Sparse Recovery via Partial Regularization: Models, Theory, and Algorithms
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
• Minimization of the difference of nuclear and Frobenius norms for noisy low rank matrix recovery
• 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
• Stable recovery of sparse signals with coherent tight frames via l_p-analysis approach
• Computing Sparse Representations of Multidimensional Signals Using Kronecker Bases
• On Theorem 10 in &#x201C;On Polar Polytopes and the Recovery of Sparse Representations&#x201D; [Sep 07 3188-3195]
• Recovery of low-rank matrices based on the rank null space properties
• Compressive time-of-flight 3D imaging using block-structured sensing matrices
• New restricted isometry property analysis for \(\ell_1-\ell_2\) minimization methods
• Robust signal recovery for \(\ell_{1-2}\) minimization via prior support information
• Weighted _p-minimization for sparse signal recovery under arbitrary support prior
• Compressed data separation via unconstrained l1-split analysis
• Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms
• The null space property of the weighted ℓr − ℓ1 minimization
• A Variable Density Sampling Scheme for Compressive Fourier Transform Interferometry
• \(\boldsymbol{L_1-\beta L_q}\) Minimization for Signal and Image Recovery
• Affine phase retrieval for sparse signals via \(\ell_1\) minimization
• Stable Recovery of Sparsely Corrupted Signals Through Justice Pursuit De-Noising
• k-Sparse Vector Recovery via $$\ell _1-\alpha \ell _2$$ Local Minimization
• Stable recovery of approximately block \(k\)-sparse signals with partial block support information via weighted \(\ell_2/\ell_p\) (\(0 < p \leq 1\)) minimization
• Matrix recovery from nonconvex regularized least absolute deviations
• Uniform RIP analysis for the _p- _q minimization
• High-order block RIP for nonconvex block-sparse compressed sensing
• Sparse recovery with coherent frames via \(\ell_{1-2}\)-analysis

This page was built for publication: Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices

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