# A FEAST Algorithm for the Linear Response Eigenvalue Problem
## 3 The FEAST Algorithm for LREP
### Convergence Analysis  
Without loss of generality, we suppose in this subsection:  
\[|\tilde{f}(\lambda_{\ell_{1}}^{2})|\geq\cdots\geq|\tilde{f}(\lambda_{\ell_{ 1}}^{2})|>|\tilde{f}(\lambda_{\ell_{(+1)}}^{2})|\geq\cdots\geq|\tilde{f}( \lambda_{\ell_{N}}^{2})|,\]  
and use the following simplifying notation:  
\[ \begin{array}{ll}\Psi_{1}=\Psi_{{}_{(\ell_{1}+1)}},&\Psi_{2}=\Psi_{{}_{( \ell_{(+1)}+\ell_{N})}},\\ \Phi_{1}=\Phi_{{}_{(\ell_{1}+1)}},&\Phi_{2}=\Phi_{{}_{(\ell_{(+1)}+\ell_{N})}}, \\ \Lambda_{1}=\Lambda_{{}_{(\ell_{1}+1)}},&\Lambda_{2}=\Lambda_{{}_{(\ell_{(+1)}+ \ell_{N})}},\\ \widetilde{\varphi}_{{}_{(0)}}=[\tilde{\psi}_{1_{0}},\ldots,\tilde{\psi}_{{}_ {(0)}}],&\widetilde{\varphi}_{{}_{(0)}}=[\tilde{\varphi}_{1_{0}},\ldots, \tilde{\varphi}_{{}_{(0)}}].\end{array} \]  
In Algorithm 1, for a given scalar \(k\), naturally, we would use \(\widetilde{\Psi}_{{}_{(k)}}\) as approximations to \(\Psi_{1}\) and \(\widetilde{\Phi}_{{}_{(k)}}\) as approximations to \(\Phi_{1}\). In this subsection, we will investigate how good such approximations may be. Notice that \(\tilde{f}(\Lambda_{1}^{2})\) is invertible since \(\tilde{f}(\lambda_{\ell_{j}}^{2})>1/2\) for \(i=1,\ldots,s\) by (8). Lemma 5: _Suppose \(\Psi_{1}^{\mathrm{T}}MY_{{}_{(0)}}\) is nonsingular. Then, \(Y_{{}_{(0)}}\) is full column rank for all \(i\) in Algorithm 1._  
Proof: We prove this statement by induction. If \(\Psi_{1}^{\mathrm{T}}MY_{{}_{(0)}}\) is invertible for some \(j\), then:  
\[V_{{}_{(i\text{-}1)}} =\tilde{f}(KM)Y_{{}_{(0)}}=\tilde{f}(KM)\Psi\Phi^{\mathrm{T}}Y_{{ (0)}}\] \[=\tilde{f}(KM)(\Psi_{1}\Phi_{1}^{\mathrm{T}}+\Psi_{2}\Phi_{2}^{ \mathrm{T}})Y_{{}_{(0)}}\] \[=\left(\Psi_{1}\tilde{f}(\Lambda_{1}^{2})\Phi_{1}^{\mathrm{T}}+ \Psi_{2}\tilde{f}(\Lambda_{2}^{2})\Phi_{2}^{\mathrm{T}}\right)Y_{{}_{(0)}}\] \[=\left(\Psi_{1}+\Psi_{2}\tilde{f}(\Lambda_{2}^{2})\Phi_{2}^{ \mathrm{T}}Y_{{}_{(0)}}E_{{}_{(0)}}^{-1}\right)E_{{}_{(0)}},\]  
where \(E_{{}_{(0)}}=\tilde{f}(\Lambda_{1}^{2})\Phi_{1}^{\mathrm{T}}Y_{{}_{(0)}}=\tilde{ f}(\Lambda_{1}^{2})\Psi_{1}^{\mathrm{T}}MY_{{}_{(0)}}\) is nonsingular. Thus, \(V_{{}_{(i\text{-}1)}}\) has full column rank. This leads to \(R_{{}_{(i\text{-}1)}}\) and \(Q_{{}_{(i\text{-}1)}}\) both being invertible. By Step 5 of Algorithm 1, we have \(Y_{{}_{(i\text{-}1)}}=\widetilde{V}_{{}_{(i\text{-}1)}}Q_{{}_{(i\text{-}1)}}=V_ {{}_{(i\text{-}1)}}R_{{}_{(i\text{-}1)}}^{-1}Q_{{}_{(i\text{-}1)}}\) which is also full column rank. Furthermore,  
\[\Psi_{1}^{\mathrm{T}}MY_{{}_{(i\text{-}1)}} =\Psi_{1}^{\mathrm{T}}MV_{{}_{(i\text{-}1)}}R_{{}_{(i\text{-}1)}}^{ -1}Q_{{}_{(i\text{-}1)}}\] \[=\Psi_{1}^{\mathrm{T}}M\left(\Psi_{1}+\Psi_{2}\tilde{f}(\Lambda_{2}^ {2})\Phi_{2}^{\mathrm{T}}Y_{{}_{(0)}}E_{{}_{(0)}}^{-1}\right)E_{{}_{(0)}}R_{{}_{( 0)}}^{-1}Q_{{}_{(i\text{-}1)}}\] \[=E_{{}_{(0)}}R_{{}_{(i\text{-}1)}}^{-1}Q_{{}_{(i\text{-}1)}}\]is nonsingular. We conclude by induction that \(Y_{{}_{0}}\) is full column rank for \(i=1,2,\ldots\). Theorem 4.1: _Suppose the condition of Lemma 5 holds. For \(1\leq k_{1}\leq k_{2}\leq s\), there exist \(\widehat{Y}\in\mathbb{R}^{N\times(\ell_{k_{2}}-\ell_{k_{1}}+1)}\) where \(\mathcal{R}(\widehat{Y})\subseteq\mathcal{R}(Y_{{}_{0}})\) and \(\widehat{X}=M\widehat{Y}\) such that, for any \(k\),_  
\[\|\tan\Theta_{\mbox{\tiny{at}}}(Y_{{}_{(:},\ell_{k_{1}}:\ell_{k_{2 }})},V_{{}_{0}})\|_{\mathbb{F}} \leq\left(\frac{|\tilde{f}(\lambda_{\ell_{(s+1)}}^{2})|}{|\tilde{ f}(\lambda_{\ell_{2}}^{2})|}\right)^{k}\times\|\tan\Theta_{\mbox{\tiny{at}}}(Y_{{}_{(:}, \ell_{k_{1}}:\ell_{k_{2}})},\widehat{Y})\|_{\mathbb{F}}, \tag{11}\] \[\|\tan\Theta_{\mbox{\tiny{at}}^{-1}}(\Phi_{{}_{(:},\ell_{k_{1}}: \ell_{k_{2}})},U_{{}_{(k)}})\|_{\mathbb{F}} \leq\left(\frac{|\tilde{f}(\lambda_{\ell_{(s+1)}}^{2})|}{|\tilde{ f}(\lambda_{\ell_{2}}^{2})|}\right)^{k}\times\|\tan\Theta_{\mbox{\tiny{at}}^{-1}}( \Phi_{{}_{(:},\ell_{k_{1}}:\ell_{k_{2}})},\widehat{X})\|_{\mathbb{F}}. \tag{12}\]  
Proof.