Compressed sensing is a signal processing technique, which can accurately recover sparse signals from linear measurements with far fewer number of measurements than those required by the classical Shannon-Nyquist theorem. Block sparse signals, i.e., the sparse signals whose nonzero coefficients occur in few blocks, arise from many fields. Block orthogonal matching pursuit (BOMP) is a popular greedy algorithm for recovering block sparse signals due to its high efficiency and effectiveness. By fully using the block sparsity of block sparse signals, BOMP can achieve very good recovery performance. This letter proposes a sufficient condition to ensure that BOMP can exactly recover the support of block K-sparse signals under the noisy case. This condition is better than existing ones.
Total variation denoising has attracted considerable attention in 1-D and 2-D signal processing. For image denoising, the convex cost function can be viewed as the regularized linear least squares problem (ℓ1 regularizer for anisotropic case and ℓ2 regularizer for isotropic case). However, these convex regularizers often underestimates the high-amplitude components of the true image. In this paper, non-convex regularizers for 2-D TV denoising models are proposed. These regularizers are based on the Moreau envelop and minimax-concave penalty which can maintain the convexity of the cost functions. Then efficient algorithms based on forward-backward splitting are proposed to solve the new cost functions. Numerical results show the effectiveness of the proposed non-convex regularizers for both synthetic and real-world image.
In numerous applications from communications and signal processing, we often need to acquire a K -sparse binary signal from sparse noisy linear measurements. In this work, we first develop an algorithm called binary matching pursuit (BMP) to recover the K -sparse binary signal. According to whether the residual vector is explicitly formed or not at each iteration, we develop two implementations of BMP which are respectively called explicit BMP and implicit BMP. We then analyze their complexities and show that, compared to the batch-orthogonal matching pursuit (OMP), which is the fastest implementation of OMP, the improvements of the explicit and implicit BMP algorithms are respectively n /(2 K ) and K times when some quantities are pre-computed. Finally, we provide sharp sufficient conditions of stable recovery of the support of the sparse signal using mutual coherence and restricted isometry property of the sensing matrix. Simulation tests indicate that the implicit BMP algorithm is around or more than n /(2 K ) times faster than batch-OMP with around or more than 20% lower rates of missed detection and false alarm.
Given Y ∈ Rm×l and A ∈ Rm×n, the multiple measurement vector (MMV) problem aims to recover the support of K-row sparse matrix X from Y = AX+ E. In this paper, we present a sufficient condition for exact support recovery of K-row sparse matrices via the orthogonal matching pursuit for MMV (OMPMMV) algorithm in the noisy case. Furthermore, in the noiseless case, our proposed condition is optimal.
Orthogonal matching pursuit (OMP) is a widely used greedy algorithm for recovering the support of a sparse signal x from the underdetermined model y = Ax. In practice, we should analyze the performance of OMP under general perturbations, which means that both y and A are perturbed. In this paper, under general perturbations, we present necessary and sufficient conditions for the exact support recovery with the OMP. We also discuss the performance of OMP for recovering α strongly decaying sparse signals. Typically, in the noise-free case, we show that the upper bound of our sufficient condition is unrelated with K and is a sharp bound. Furthermore, we establish sufficient conditions for the recovery of OMP, which can guarantee that the recovery is in the order of the signal entries' magnitude.
14 September 2013 in Multidimensional Systems and Signal Processing