  We address the problem of sparse recovery using greedy compressed sensing
recovery algorithms, without explicit knowledge of the sparsity. Estimating the
sparsity order is a crucial problem in many practical scenarios, e.g., wireless
communications, where exact value of the sparsity order of the unknown channel
may be unavailable a priori. In this paper we have proposed a new greedy
algorithm, referred to as the Multiple Choice Hard Thresholding Pursuit
(MCHTP), which modifies the popular hard thresholding pursuit (HTP) suitably to
iteratively recover the unknown sparse vector along with the sparsity order of
the unknown vector. We provide provable performance guarantees which ensures
that MCHTP can estimate the sparsity order exactly, along with recovering the
unknown sparse vector exactly with noiseless measurements. The simulation
results corroborate the theoretical findings, demonstrating that even without
exact sparsity knowledge, with only the knowledge of a loose upper bound of the
sparsity, MCHTP exhibits outstanding recovery performance, which is almost
identical to that of the conventional HTP with exact sparsity knowledge.
Furthermore, simulation results demonstrate much lower computational complexity
of MCHTP compared to other state-of-the-art techniques like MSP.
