# Mixed Alternating Projections with Application to Hankel Low-Rank Approximation
## 2 Alternating Projections  
Consider the linear case where we are looking for a solution to an optimization problem  
\[\min_{S\in\mathcal{A}\cap\mathcal{B}}\|X-S\|, \tag{7}\]  
where \(\mathcal{A}\) and \(\mathcal{B}\) are linear subspaces of \(\mathbb{R}^{M}\) with a nonempty intersection of dimension \(m<M\). The solution to the problem can be found using the method of alternating projections with an initial value of \(S^{(0)}=X\) and the iteration step  
\[S^{(k+1)}=\mathbf{\Pi}_{\mathcal{A}}\mathbf{\Pi}_{\mathcal{B}}S^{(k)}. \tag{8}\]  
The following statement is known. **Theorem 1** ([15], Theorem 13.7). : \[(\mathbf{\Pi}_{\mathcal{A}}\mathbf{\Pi}_{\mathcal{B}})^{n}\xrightarrow[n \rightarrow+\infty]{}\mathbf{\Pi}_{\mathcal{A}\cap\mathcal{B}},\]  
_that is, the limit of the iterations is equal to the projection on the intersection of the subspaces \(\mathcal{A}\) and \(\mathcal{B}\)._  
This allows us to prove the following property. Denote \(\mathbf{P}_{\mathcal{A},\mathcal{B}}=\mathbf{\Pi}_{\mathcal{A}}\mathbf{\Pi}_ {\mathcal{B}}\). **Corollary 1**. : _All the eigenvalues of the matrix \(\mathbf{P}_{\mathcal{A},\mathcal{B}}\) lie within the unit circle; the eigenvalue \(\lambda=1\), which only has modulus \(1\), is semi-simple and has multiplicity equal to \(m=\dim\mathcal{A}\cap\mathcal{B}\); the corresponding eigenvectors form the basis of \(\mathcal{A}\cap\mathcal{B}\)._Proof. : The statement of the corollary is obviously true in the case of diagonalizable matrix \(\mathbf{P}_{\mathcal{A},\mathcal{B}}\), since by Theorem 1, \(\mathbf{P}_{\mathcal{A},\mathcal{B}}^{n}\) tends to a projection matrix of rank \(m\) whose eigenvalues (1 of multiplicity \(m\) and 0 of multiplicity \(M-m\)) are the limits of the powers of the eigenvalues of \(\mathbf{P}_{\mathcal{A},\mathcal{B}}\). In the general case, the result is based on the statement \"Limits of Powers\" in ([16], page 630), which, among other things, states that the eigenvalue 1 is semi-simple--i.e., its algebraic and geometric multiplicities coincide. The geometric multiplicity \(m\) of the unit root follows from the fact that the vectors from \(\mathcal{A}\cap\mathcal{B}\) (and only they) correspond to the eigenvalue 1 of the matrix \(\mathbf{P}_{\mathcal{A},\mathcal{B}}\). The following proposition establishes the convergence rate of alternating projections. **Proposition 1**. : _The following inequality holds:_  
\[\|(\mathbf{P}_{\mathcal{A},\mathcal{B}}^{n}-\mathbf{\Pi}_{\mathcal{A}\cap \mathcal{B}})X\|\leq C\|X\|(|\hat{\lambda}|+\delta)^{n}, \tag{9}\]  
_where \(C>0\) is some positive constant, \(\delta>0\) is an arbitrarily small real number and \(\hat{\lambda}\) is the largest non-unit (that is, \((m+1)\)-th) eigenvalue of the matrix \(\mathbf{P}_{\mathcal{A},\mathcal{B}}\)._  
Proof. : The theorem ([17], Theorem 2.12) implies that for a matrix \(\mathbf{D}\), the convergence rate of \(\mathbf{D}^{k}\) to the limit matrix \(\mathbf{D}^{\infty}\) is determined by the spectral radius \(\gamma=\rho(\mathbf{D}-\mathbf{D}^{\infty})\) of the difference matrix. Namely, for any \(\mu>\gamma\), there exists a constant \(C\) such that \(\|\mathbf{D}^{k}-\mathbf{D}^{\infty}\|\leq C\mu^{k}\), where \(\|\cdot\|\) is the induced norm. By Corollary 1, both matrices \(\mathbf{P}_{\mathcal{A},\mathcal{B}}\) and \(\mathbf{\Pi}_{\mathcal{A}\cap\mathcal{B}}\) have eigenvalue one corresponding to the same eigenspace. Since the other eigenvalues of \(\mathbf{\Pi}_{\mathcal{A}\cap\mathcal{B}}\) are zero, the spectral radius of the difference matrix is \(\hat{\lambda}\), which proves the statement. Thus, the convergence rate of the algorithm with iterations given by (8) is determined by the modulus of the eigenvalue \(|\hat{\lambda}|\): the closer it is to one, the slower the algorithm converges. **Remark 1**.