## 3 The Proposed Algorithm and Its Applications
### An Initial Estimation Approach for the Signal Sparsity Level  
Consider a sparse signal \(\mathbf{X}\in\mathbf{\mathbb{R}}^{N\times 1}\) of sparsity level \(K\) (\(K<<N\)). The true support set of sparse signals is denoted by \(\Lambda\), then we have \(|\Lambda|=K\). \(\mathbf{y}\in\mathbf{\mathbb{R}}^{M\times 1}\) is the measurement vector and \(\mathbf{A}\) is the sensing matrix. Support that \(\mathbf{v}=\mathbf{A}^{\mathrm{T}}\mathbf{y}\), the \(i\)-th element \(\mathbf{v}_{i}\) of \(\mathbf{v}\) is the inner product of \(\mathbf{A}_{i}\) (the \(i\)-th column of \(\mathbf{A}\)) and the measurement vector \(\mathbf{y}\), i.e., \(\mathbf{v}_{i}=\left\langle\mathbf{A}_{i},\ \mathbf{y}\right\rangle\). The indices of the \(k_{0}\) (\(1\leq k_{0}\leq N\)) largest absolute values in \(\left\{\mathbf{v}_{i}\right\}\) are merged into the identified support set \(\Lambda^{0}\), i.e., \(\left|\Lambda^{0}\right|=k_{0}\). \(\delta\) denotes the restricted isometry constant. Now we can have the proposition 1. **Proposition 1**: _Consider that \(\mathbf{A}\) satisfies the RIP with parameters \(\left(2K,\ \delta_{2\mathrm{K}}\right)\). For \(k_{0}\leq K\),_  
\[\left\|\mathbf{A}_{\Lambda^{0}}^{T}\mathbf{y}\right\|_{2}^{2}\leq\frac{\left(1+\delta _{2\mathrm{K}}\right)^{2}}{1-\delta_{k}}\|\mathbf{y}\|_{2}^{2}. \tag{6}\]  
**Proof of Proposition 1**: Put indices of the \(K\) (\(1\leq K\leq N\)) largest absolute values in \(\left\{\mathbf{v}_{i}\right\}\) to be \(\Lambda^{K}\). If \(k_{0}\leq K\), i.e., \(\Lambda^{0}\subset\Lambda^{K}\), we have  
\[\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}\]  
The measurement vector \(\mathbf{y}\) can be calculated as \(\mathbf{y}=\mathbf{A}_{\Lambda}\mathbf{\theta}_{\Lambda}\). Thus,  
\[\left\|\mathbf{A}_{\Lambda^{K}}^{T}\mathbf{y}\right\|_{2}=\left\|\mathbf{A}_{\Lambda^{K}}^ {T}\mathbf{A}_{\Lambda}\mathbf{\theta}_{\Lambda}\right\|_{2}\leq\left\|\mathbf{A}_{\Lambda ^{K}}^{T}\mathbf{A}_{\Lambda}\right\|_{2}\cdot\left\|\mathbf{\theta}_{\Lambda}\right\|_ {2} \tag{8}\]  
where \(\left|\Lambda^{K}\right|=\left|\Lambda\right|=K\) and \(\left|\Lambda^{K}\cup\Lambda\right|\leq 2K\). Suppose \(\Omega=\Lambda^{K}\cup\Lambda\), according to the property of spectral norm that norm of a subarray does not exceed norm of the original matrix, we have \(\left\|A_{\Lambda^{K}}^{T}\mathbf{A}_{\Lambda}\right\|_{2}\leq\left\|A_{\Omega}^{T} \mathbf{A}_{\Omega}\right\|_{2}\). According to the RIP, singular values of \(\mathbf{A}_{\Lambda}\) are between \(\sqrt{1-\ \delta_{k}}\) and \(\sqrt{1+\ \delta_{k}}\), where \(0<\delta_{k}<1\). Let \(\lambda\big{(}A_{\Lambda}^{T}\mathbf{A}_{\Lambda}\big{)}\) be eigenvalues of \(\mathbf{A}_{\Lambda}^{T}\mathbf{A}_{\Lambda}\), thus \(1-\ \delta_{k}\ \leq\ \lambda\big{(}\mathbf{A}_{\Lambda}^{T}\mathbf{A}_{\Lambda}\big{)}\ \leq\ 1+\ \delta_{k}\). \(A\) satisfies the RIP with parameters \((2K,\ \delta_{2k})\). Therefore, \(\lambda\big{(}\mathbf{A}_{\Omega}^{T}\mathbf{A}_{\Omega}\big{)}\ \leq\ 1+\ \delta_{2k}\). Thus,  
\[\left\|A_{\Lambda^{K}}^{T}\mathbf{A}_{\Lambda}\right\|_{2}\leq\left\|A_{\Omega}^{ T}\mathbf{A}_{\Omega}\right\|_{2}\leq 1+\delta_{2K}. \tag{9}\]  
According to the RIP, it holds \((1-\delta_{K})\|\theta_{\Lambda}\|_{2}^{2}\leq\|\mathbf{y}\|_{2}^{2}\), then  
\[\|\mathbf{\theta}_{\Lambda}\|_{2}^{2}\leq\frac{\|\mathbf{y}\|_{2}^{2}}{1-\delta_{K}}. \tag{10}\]  
Hence,  
\[\left\|A_{\Lambda^{K}}^{T}\mathbf{y}\right\|_{2}^{2} =\left\|\mathbf{A}_{\Lambda^{K}}^{T}\mathbf{A}_{\Lambda}\mathbf{\theta}_{ \Lambda}\right\|_{2}^{2} \tag{11}\] \[\leq\left\|\mathbf{A}_{\Lambda^{K}}^{T}\mathbf{A}_{\Lambda}\right\|_{2}^{ 2}\cdot\|\mathbf{\theta}_{\Lambda}\|_{2}^{2}\] \[\leq(1+\delta_{2K})^{2}\cdot\frac{\|\mathbf{y}\|_{2}}{1-\delta_{K}}\]  
Thus, it holds  
\[\left\|A_{\Lambda^{0}}^{T}\mathbf{y}\right\|_{2}^{2}\leq\frac{(1+\delta_{2k})^{2} }{1-\delta_{k}}\|\mathbf{y}\|_{2}^{2}. \tag{12}\]  
We have proven that the proposition 1 is true.