# A Greedy Pursuit Hierarchical Iteration Algorithm
## 3 Greedy Pursuit Hierarchical Iterative Parameter Estimation Algorithm  
The sparsity property of the over-parameterized system model makes it possible to identify the multi-input system with limited sampled data according to the compressed sensing idea. System model (9) can be rewrote as  
\[\mathbf{Y}=\sum_{j=1}^{N}\mathbf{\phi}_{j}\theta_{j}+\mathbf{E}, \tag{11}\]  
where \(\mathbf{\phi}_{j}\) and \(\theta_{j}\) are the \(j\)-th column of \(\mathbf{\Phi}\) and the corresponding parameter in \(\mathbf{\theta}\). According to Equation (7), \(\mathbf{\theta}\) is sparse with a large number of zero elements and only contains a small number of non-zero key parameters. When the locations of the key parameters are found, the goal of reducing the dimensionality of the over-parameterized system model can be achieved. This provides the possibility of using limited sampling data to realize the parameters and time-delay estimation. In order to meet the sparse recovery conditions, the information matrix \(\mathbf{\Phi}\) should be normalized. Define the normalized transformation matrix \(\mathbf{T}\) as  
\[\mathbf{T}:= \begin{bmatrix}\Phi(1)&0&\cdots&0\\ 0&\Phi(2)&\cdots&0\\ \vdots&0&\ddots&\vdots\\ 0&0&\cdots\Phi(N)\end{bmatrix} ^{-1}\in\mathbb{R}^{N\times N} \tag{12}\]  
where \(\Phi(j)=\sqrt{\sum_{i=1}^{L}\Phi_{ij}^{2}}\) denotes the modulus of the \(j\)th column of \(\mathbf{\Phi}\). Introducing \(\mathbf{T}\) to Equation (9), the following can be obtained:  
\[\mathbf{Y}=\mathbf{\Psi}\mathbf{\phi}+\mathbf{E}, \tag{13}\]  
where \(\mathbf{\Psi}=\mathbf{\Phi}\mathbf{T},\mathbf{\vartheta}=\mathbf{T}^{-1}\mathbf{\theta}\). Let \(q\) be the inner iteration variable. Define the residual output as  
\[\mathbf{r}_{q}:=\mathbf{Y}-\mathbf{\Psi}_{\Lambda_{q}}\mathbf{\theta}_{\Lambda_{q}}. \tag{14}\]  
where \(\Lambda_{q}\) is an index set that is composed of the locations of the found key nonzero parameters, \(\mathbf{\Psi}_{\Lambda_{q}}\) is a sub-matrix of matrix \(\mathbf{\Psi}\), and \(\mathbf{\theta}_{\Lambda_{q}}\) is a non-zero parameter vector. Both \(\mathbf{\Psi}_{\Lambda_{q}}\) and \(\mathbf{\vartheta}_{\Lambda_{q}}\) are indexed by \(\Lambda_{q}\). The sub-matrix \(\mathbf{\Psi}_{\Lambda_{q}}\) is composed of the indexed columns of the information matrix \(\mathbf{\Psi}\). At the next internal iteration, define the following cost function and minimize it to find location of one key parameter. \[J(j):=\|\mathbf{r}_{q}-\mathbf{\psi}_{j}\theta_{j}\|_{2}, \tag{15}\]which lead to \(\hat{\phi}_{j}=\mathbf{\psi}_{j}\mathbf{r}_{q}/\|\mathbf{\psi}_{j}\|_{2}^{2}\). Plugged back \(\hat{\phi}_{j}\) into Equation (15), then we have  
\[ \begin{split} J(j)&=\min_{\mathbf{\phi}_{j}}\|\mathbf{\psi}_ {j}\hat{\phi}_{j}-\mathbf{r}_{q}\|_{2}^{2}=\|\frac{\mathbf{\psi}_{j}^{\mathrm{r}}\mathbf{r}_ {q}}{\|\mathbf{\psi}_{j}\|_{2}^{2}}\mathbf{\psi}_{j}-\mathbf{r}_{q}\|_{2}^{2}\\ &=\|\mathbf{r}_{q}\|_{2}^{2}-\frac{(\mathbf{\psi}_{j}^{\mathrm{r}}\mathbf{r}_ {q})^{2}}{\|\mathbf{\psi}_{j}\|_{2}^{2}}=\|\mathbf{r}_{q}\|_{2}^{2}-(\mathbf{\psi}_{j}^{ \mathrm{r}}\mathbf{r}_{q})^{2}.\end{split}  \tag{16}\]  
where \(\mathbf{\psi}_{j}(j=1,2,\cdots,N)\) is the column of the normalized matrix \(\mathbf{\
abla}\). From Equation (16), the column most relevant to the last iteration residual \(\mathbf{r}_{q}\) can be found at next iteration. That is, the minimum problem is equivalent to the largest inner product (in absolute value) between the columns of \(\mathbf{\
abla}\) and \(\mathbf{r}_{q}\). The location of found column can be indicated by the index  
\[\lambda_{q+1}=\arg\max_{j=1,2,\cdots,N}|\langle\mathbf{r}_{q},\mathbf{\psi}_{j}\rangle|. \tag{17}\]  
Then, the index set and the index matrix can be updated according to \(\Lambda_{q+1}:=\Lambda_{q}\cup\lambda_{q+1}\). **Remark 2**. : _Because \(w(d)\) and \(e(d)\) in the matrix \(\mathbf{\Phi}\) are unknown noise items.