Orthogonal Matching Pursuit (OMP) and Basis Pursuit (BP) are two well-known recovery algorithms in compressed sensing. To recover a $d$ -dimensional $m$ -sparse signal with high probability, OMP needs $O(m\ln{d})$ number of measurements, whereas BP needs only $O\left(m\ln{{d\over m}}\right)$ number of measurements. In contrary, OMP is a practically more appealing algorithm due to its superior execution speed. In this piece of work, we have proposed a scheme that brings the required number of measurements for OMP closer to BP. We have termed this scheme as ${\rm OMP}_{\alpha}$ , which runs OMP for $(m+\lfloor\alpha{m}\rfloor)$ -iterations instead of $m$ -iterations, by choosing a value of $\alpha\in[0,1]$ . It is shown that ${\rm OMP}_{\alpha}$ guarantees a high probability signal recovery with $O\left(m\ln{{d\over\lfloor\alpha{m}\rfloor+1}}\right)$ number of measurements. Another limitation of OMP unlike BP is that it requires the knowledge of $m$ . In order to overcome this limitation, we have extended the idea of ${\rm OMP}_{\alpha}$ to illustrate another recovery scheme called ${\rm OMP}_{\infty}$ , which runs OMP until the signal residue vanishes. It is shown that ${\rm OMP}_{\infty}$ can achieve a close to $\ell_{0}$ -norm recovery without any knowledge of $m$ like BP.

Recent dictionary training algorithms for sparse representation like K-SVD, MOD, and their variation are reminiscent of K-means clustering, and this letter investigates such algorithms from that viewpoint. It shows: though K-SVD is sequential like K-means, it fails to simplify to K-means by destroying the structure in the sparse coefficients. In contrast, MOD can be viewed as a parallel generalization of K-means, which simplifies to K-means without perturbing the sparse coefficients. Keeping memory usage in mind, we propose an alternative to MOD; a sequential generalization of K-means (SGK). While experiments suggest a comparable training performances across the algorithms, complexity analysis shows MOD and SGK to be faster under a dimensionality condition.

This letter presents a variant of Orthogonal Matching Pursuit (OMP) method, called Backtracking-based Adaptive OMP (BAOMP), for compressive sensing and sparse signal reconstruction. As an extension of the OMP algorithm, the BAOMP method incorporates a simple backtracking technique to detect the previous chosen atoms' reliability and then deletes the unreliable atoms at each iteration. Through this modification, the BAOMP method achieves superior performance while maintaining the low complexity of OMP-type methods. Also, unlike its several predecessors, the BAOMP method does not require the sparsity level to be known a priori. The experiments demonstrate the proposed method's superior performance to that of several other OMP-type and l₁ optimization methods.

The problem of lossy compression of encrypted image data is considered in this paper. A method is proposed to achieve compression of the encrypted image data based on compressive sensing technique. Joint decoding/decryption is proposed with the modified basis pursuit decoding method to take care of encryption. Simulation results are provided to demonstrate the compression results of the proposed compression method based on compressive sensing.

Contraction coefficients are distribution dependent constants that are used to sharpen standard data processing inequalities for f-divergences (or relative f-entropies) and produce so-called “strong” data processing inequalities. For any bivariate joint distribution, i.e., any probability vector and stochastic matrix pair, it is known that contraction coefficients for f-divergences are upper bounded by unity and lower bounded by the contraction coefficient for χ²-divergence. In this paper, we elucidate that the upper bound is achieved when the joint distribution is decomposable, and the lower bound can be achieved by driving the input f-divergences of the contraction coefficients to zero. Then, we establish a linear upper bound on the contraction coefficients of joint distributions for a certain class of f-divergences using the contraction coefficient for χ²-divergence, and refine this upper bound for the salient special case of Kullback-Leibler (KL) divergence. Furthermore, we present an alternative proof of the fact that the contraction coefficients for KL and χ²-divergences are equal for bivariate Gaussian distributions (where the former coefficient may impose a bounded second moment constraint). Finally, we generalize the well-known result that contraction coefficients of stochastic matrices (after extremizing over all possible probability vectors) for all nonlinear operator convex f-divergences are equal. In particular, we prove that the so-called “less noisy” preorder over stochastic matrices can be equivalently characterized by any nonlinear operator convex f-divergence. As an application of this characterization, we also derive a generalization of Samorodnitsky’s strong data processing inequality.