## 3 The Proposed Algorithm and Its Applications
### An Initial Estimation Approach for the Signal Sparsity Level
Correspondingly, the following converse-negative proposition of the proposition 1 can be inferred, which is also true. \(\square\)  
**Proposition 2**: _Consider that \(\mathbf{A}\) satisfies the RIP with parameters \((2K,\ \delta_{2k})\). If the inequality_  
\[\left\|A_{\Lambda^{0}}^{T}\mathbf{y}\right\|_{2}^{2}>\frac{(1+\delta_{2k})^{2}}{1- \delta_{k}}\|\mathbf{y}\|_{2}^{2} \tag{13}\]  
_holds, then \(k_{0}>K\)._  
The RIC \(\delta_{K}\in(0,\ 1)\) increases monotonously as the sparsity level \(K\) increases, i.e., for any two positive integers \(K_{1}\) and \(K_{2}\) (\(K_{1}<<K_{2}\)), one has \(\delta_{K_{1}}\leq\ \delta_{K_{2}}\)[20]. Thus, proposition 2 can be rewritten as follows. **Proposition 3**: _Consider that \(\mathbf{A}\) satisfies the RIP with parameters \((2K,\ \delta_{2k})\). If the inequality_  
\[\left\|\mathbf{A}_{\Lambda^{0}}^{T}\mathbf{y}\right\|_{2}^{2}\leq\left\|\mathbf{A}_{ \Lambda^{0}}^{T}\mathbf{y}\right\|_{2}^{2}. \tag{7}\]0  
_holds, then \(k_{0}>K\)._  
**Proof of Proposition 3**: According to the monotonicity of RIC, since \(0<\delta<1\), we can obtain the inequality as  
\[ \begin{array}{rl}\frac{(1+\delta_{2k})^{2}}{1-\delta_{k}}\|\mathbf{y}\|_{2}^{2}& <\frac{(1+\delta_{2k})^{2}}{1-\delta_{2k}}\|\mathbf{y}\|_{2}^{2}\\ &\leq\frac{(1+\delta_{2k}+\delta_{2k}^{2}+\delta(\delta_{2k}^{2}))^{2}}{1- \delta_{2k}}\|\mathbf{y}\|_{2}^{2}\end{array}  \tag{15}\]  
based on the [PERSON] formula as  
\[\frac{1}{1-\delta_{2k}}=1+\delta_{2k}+\delta_{2k}^{2}+o(\delta_{2k}^{2}). \tag{16}\]Thus, it holds  
\[\frac{\left(1+\delta_{2k}\right)^{2}}{1-\delta_{k}}\|\mathbf{y}\|_{2}^{2}< \left(\frac{1}{1-\delta_{2k}}\right)^{2}\cdot\frac{1}{1-\delta_{2k}}\cdot\|\mathbf{y }\|_{2}^{2}. \tag{17}\]  
With the proposition 2, we can draw the conclusion that the proposition 3 is true. \(\square\)  
[PERSON] et al. indicated that reconstruction performance shows better when the sparsity level was around \((M/4)\)[27]. To make a preliminary estimation for the sparsity, we can preset the initial \(k_{0}\) as \((M/4)\) and exploit the proposition 3 for discrimination. According to [20, 28], boundary of \(\delta_{2k}\) is calculated as the value of \(\delta_{2k}\), and can be put into (14):  
1. If \(\left\|\mathbf{A}_{\Lambda^{0}}^{T}\cdot\mathbf{y}\right\|^{2}>\left[\|\mathbf{y}\|_{2}^{2 }/\left(1-\delta_{2k}\right)^{3}\right]\) holds, then \(k_{0}\) is larger than the actual sparsity level \(K\). Then \(k_{0}=k_{0}-1\) till the inequality (14) does not hold. This \(k_{0}\) is considered to be an estimation of the actual sparsity level \(K\). 2. If \(\left\|\mathbf{A}_{\Lambda^{0}}^{T}\cdot\mathbf{y}\right\|^{2}>\left[\|\mathbf{y}\|_{2}^{2 }/\left(1-\delta_{2k}\right)^{3}\right]\) does not hold, then \(k_{0}=k_{0}+1\) till the inequality (14) holds. This \(k_{0}\) is considered to be an estimation of the actual sparsity level \(K\). Initial step size can be set properly based on the preliminary estimation of the sparsity level. After numerous experiments, we suggest that a good reconstruction performance is achieved when initial step size is set to \(\left\lfloor k_{0}/2\right\rfloor\), where \(k_{0}\) is the estimated initial sparsity level. In following experiments, we set parameters according to this rule. Due to (14), the initial sparsity level obtained by this approach is larger than the actual level, which means that the sparsity obtained by variable step-size would be slightly larger than the actual level with a high probability. However, this problem can be well solved by taking a further filtering mechanism.