Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors

DOI10.1109/TSP.2008.927802zbMATH Open1390.94306arXiv0802.1311MaRDI QIDQ4569102FDOQ4569102

Authors: Moshe Mishali, Y. C. Eldar 

Publication date: 27 June 2018

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: The rapid developing area of compressed sensing suggests that a sparse vector lying in an arbitrary high dimensional space can be accurately recovered from only a small set of non-adaptive linear measurements. Under appropriate conditions on the measurement matrix, the entire information about the original sparse vector is captured in the measurements, and can be recovered using efficient polynomial methods. The vector model has been extended to a finite set of sparse vectors sharing a common non-zero location set. In this paper, we treat a broader framework in which the goal is to recover a possibly infinite set of jointly sparse vectors. Extending existing recovery methods to this model is difficult due to the infinite structure of the sparse vector set. Instead, we prove that the entire infinite set of sparse vectors can recovered by solving a single, reduced-size finite-dimensional problem, corresponding to recovery of a finite set of sparse vectors. We then show that the problem can be further reduced to the basic recovery of a single sparse vector by randomly combining the measurement vectors. Our approach results in exact recovery of both countable and uncountable sets as it does not rely on discretization or heuristic techniques. To efficiently recover the single sparse vector produced by the last reduction step, we suggest an empirical boosting strategy that improves the recovery ability of any given sub-optimal method for recovering a sparse vector. Numerical experiments on random data demonstrate that when applied to infinite sets our strategy outperforms discretization techniques in terms of both run time and empirical recovery rate. In the finite model, our boosting algorithm is characterized by fast run time and superior recovery rate than known popular methods.

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

Mathematics Subject Classification ID

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

Cited In (23)

• Reconstruction of jointly sparse vectors via manifold optimization
• Surveying and comparing simultaneous sparse approximation (or group-lasso) algorithms
• Sparsity based methods for overparameterized variational problems
• Sparse signal recovery for direction-of-arrival estimation based on source signal subspace
• Block-sparse recovery and rank minimization using a weighted \(l_p-l_q\) model
• Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\)
• Reducing effects of bad data using variance based joint sparsity recovery
• Joint sparse recovery based on variances
• Convergence and stability analysis of iteratively reweighted least squares for noisy block sparse recovery
• Estimation of block sparsity in compressive sensing
• Weighted \(l_p- l_1\) minimization methods for block sparse recovery and rank minimization
• Stochastic greedy algorithms for multiple measurement vectors
• Split Bregman algorithms for multiple measurement vector problem
• Randomization of data acquisition and \(\ell_{1}\)-optimization (recognition with compression)
• A mixed ℓ₁ regularization approach for sparse simultaneous approximation of parameterized PDEs
• Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP
• A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit
• A bimodal co-sparse analysis model for image processing
• Iteratively reweighted least squares for block sparse signal recovery with unconstrained \(l_{2,p}\) minimization
• On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
• Learning Reductions to Sparse Sets
• Arbitrary block-sparse signal reconstruction based on incomplete single measurement vector
• Compressive imaging and characterization of sparse light deflection maps

This page was built for publication: Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors

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