# Constrained Backtracking Matching Pursuit Algorithm for Image Reconstruction in Compressed Sensing
## 1 Introduction  
Image reconstruction is a significant application of multimedia signal processing. Compressed sensing (CS) is a technique that reconstructs sparse, compressible signals from under-determined random linear measurements. Over the past few decades, CS has been widely applied to image processing, including image reconstruction [1, 2, 3, 4, 5] and acquisition [6, 7, 8]. Various algorithms have been proposed for CS-based signal reconstruction with sparse constraints [9], which can be categorized into three classes. The first class is the non-convex optimization [10], such as re-weighted \(l_{1}\) norm minimization [11] and \(l_{q}\) norm minimization [12]. However, non-convex optimization is a non-deterministic polynomial (NP)-hard problem, which is hard to solve. The second class focuses on convex optimization based on the minimization of the \(l_{1}\) norm. The basis pursuit (BP) algorithm is typically used for convex optimization, but its \(l_{1}\) norm-based cost function is sometimes not differentiable. It also involves high computational complexity, thus limiting its practical applications [13, 14, 15]. The third category includes a set of greedy pursuit algorithms, which are to easy implement and have low computational complexity [13, 14, 15, 16, 17, 18, 19, 20, 21]. Specifically, orthogonal matching pursuit (OMP) [15, 16, 17], stage-wise OMP (StOMP) [18], and regularized orthogonal matching pursuit (ROMP) [19, 20] have been proposed. The reconstruction complexity of basicgreedy pursuit algorithms is roughly about O(\(k\)MN), which is much lower than that of BP algorithm. While the greedy pursuit algorithms show superiority in easy implementation and computational efficiency, they typically require additional measurements for reconstruction and lack stable reconstruction capability. The problem is alleviated when backtracking is introduced. For example, the subspace pursuit (SP) algorithm [21] and compressive sampling pursuit (CoSaMP) algorithm [22] have been proposed based on the backtracking scheme. The difference between SP and CoSaMP is that the latter chooses \(2k\) indices to combine the estimated support set from the previous iteration. However, it is necessary to estimate the sparsity level of signal \(k\) before applying SP and CoSaMP. Indeed, it is impractical to know the accurate sparsity level \(k\) of unknown signals in advance. Then, sparsity adaptive matching pursuit (SAMP), which can recover signals without knowing the sparsity level, was proposed by [PERSON] et al. [23]. It alternatively estimates the sparsity level when the residue's energy increases between two consecutive stages and updates the support set size of the signal using a fixed and small step size. SAMP has apparent advantages when processing one-dimensional sparse signals. However, since one is used as the initial step size, when processing high-dimensional signals, the small step size significantly affects the result and efficiency of reconstruction. To further improve the reconstruction performance, an energy-based adaptive matching pursuit (EAMP) has been proposed [24]. One limitation of EAMP is that it only focuses on the binary signal reconstruction. [PERSON] et al. used the structured Wilkinson matrix as the measurement matrix to improve the efficiency of SAMP [25]. More recently, the improved generalized sparsity adaptive matching pursuit (IGSAMP) algorithm has been proposed. This algorithm uses a nonlinear step size to approximate the sparsity level, and only a small initial step size can be selected. Meanwhile, it requires carefully choosing the parameters without referring to the sensitivity of a large step size [26]. To improve the reconstruction performance of the sparsity adaptive matching pursuit algorithm and make it less sensitive to the step size, we propose a composited constrained backtracking matching pursuit (CBMP) algorithm for image reconstruction. The main contributions of this paper are summarized as follows. 1.