On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements
From MaRDI portal
Abstract: Let A be an M by N matrix (M < N) which is an instance of a real random Gaussian ensemble. In compressed sensing we are interested in finding the sparsest solution to the system of equations A x = y for a given y. In general, whenever the sparsity of x is smaller than half the dimension of y then with overwhelming probability over A the sparsest solution is unique and can be found by an exhaustive search over x with an exponential time complexity for any y. The recent work of Cand'es, Donoho, and Tao shows that minimization of the L_1 norm of x subject to A x = y results in the sparsest solution provided the sparsity of x, say K, is smaller than a certain threshold for a given number of measurements. Specifically, if the dimension of y approaches the dimension of x, the sparsity of x should be K < 0.239 N. Here, we consider the case where x is d-block sparse, i.e., x consists of n = N / d blocks where each block is either a zero vector or a nonzero vector. Instead of L_1-norm relaxation, we consider the following relaxation min x | X_1 |_2 + | X_2 |_2 + ... + | X_n |_2, subject to A x = y where X_i = (x_{(i-1)d+1}, x_{(i-1)d+2}, ..., x_{i d}) for i = 1,2, ..., N. Our main result is that as n -> infty, the minimization finds the sparsest solution to Ax = y, with overwhelming probability in A, for any x whose block sparsity is k/n < 1/2 - O(epsilon), provided M/N > 1 - 1/d, and d = Omega(log(1/epsilon)/epsilon). The relaxation can be solved in polynomial time using semi-definite programming.
Recommendations
- Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
- A simple Gaussian measurement bound for exact recovery of block-sparse signals
- Block-Sparse Recovery via Convex Optimization
- A sufficient condition on recovery of block sparse signals via mixed minimization
- Estimation of block sparsity in compressive sensing
- Arbitrary block-sparse signal reconstruction based on incomplete single measurement vector
- On Recovery of Sparse Signals Via $\ell _{1}$ Minimization
- Recovery of sparsest signals via \(\ell^q \)-minimization
Cited in
(51)- Duality of nonconvex optimization with positively homogeneous functions
- An improved set-membership proportionate adaptive algorithm for a block-sparse system
- PROMP: a sparse recovery approach to lattice-valued signals
- Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
- A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit
- Compressed sensing of color images
- Block orthogonal greedy algorithm for stable recovery of block-sparse signal representations
- Recovery under side constraints
- Hierarchical isometry properties of hierarchical measurements
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- Block-sparse recovery of semidefinite systems and generalized null space conditions
- A perturbation analysis of nonconvex block-sparse compressed sensing
- A simple Gaussian measurement bound for exact recovery of block-sparse signals
- Optimization problems involving group sparsity terms
- Near oracle performance and block analysis of signal space greedy methods
- A new bound on the block restricted isometry constant in compressed sensing
- Globally sparse and locally dense signal recovery for compressed sensing
- Arbitrary block-sparse signal reconstruction based on incomplete single measurement vector
- On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
- A geometrical stability condition for compressed sensing
- Sharp MSE bounds for proximal denoising
- Robust classifier using distance-based representation with square weights
- Sparsity based methods for overparameterized variational problems
- A survey of compressed sensing
- Recovering structured signals in noise: least-squares meets compressed sensing
- Structured sparsity: discrete and convex approaches
- Improved FOCUSS method for reconstruction of cluster structured sparse signals in radar imaging
- Robust visual tracking with structured sparse representation appearance model
- Block-Based Methods for the Reconstruction of Finite-Length Signals From Nonuniform Samples
- Semidefinite Programming for Computable Performance Bounds on Block-Sparsity Recovery
- On the null space property of \(l_q\)-minimization for \(0 < q \leq 1\) in compressed sensing
- Estimation of block sparsity in compressive sensing
- Difference-of-Convex Algorithms for a Class of Sparse Group \ell₀ Regularized Optimization Problems
- Robust recovery of a kind of weighted l1-minimization without noise level
- Exploiting Prior Information in Block-Sparse Signals
- Surveying and comparing simultaneous sparse approximation (or group-lasso) algorithms
- On the Trade-Off Between Bit Depth and Number of Samples for a Basic Approach to Structured Signal Recovery From <inline-formula> <tex-math notation="LaTeX">$b$ </tex-math> </inline-formula>-Bit Quantized Linear Measurements
- Structured sparsity through convex optimization
- A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
- Grouped variable selection with discrete optimization: computational and statistical perspectives
- Local optimality for stationary points of group zero-norm regularized problems and equivalent surrogates
- Matrix-wise _0-constrained sparse nonnegative least squares
- Maximum turn‐off control for discrete‐time linear systems
- Improved stability conditions of BOGA for noisy block-sparse signals
- Stable recovery of approximately block \(k\)-sparse signals with partial block support information via weighted \(\ell_2/\ell_p\) (\(0 < p \leq 1\)) minimization
- High-order block RIP for nonconvex block-sparse compressed sensing
- Cardinality minimization, constraints, and regularization: a survey
- Accuracy guaranties for \(\ell_{1}\) recovery of block-sparse signals
- Sampling in the analysis transform domain
- From compression to compressed sensing
- The benefit of group sparsity
This page was built for publication: On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4569805)
