Max eigenvalue of block partitioned matrix

Question

I have a matrix which can be partitioned into 4 blocks as follows:

$$B = \left[\begin{matrix}A^{H}A + \gamma &A^{H}F \\ F^{H}A & FF^H\end{matrix}\right]$$

where the blocks $\in \mathbb{C}^{N \times N}, \mathbb{C}^{N \times M}, \mathbb{C}^{M \times N}$, and $\mathbb{C}^{M \times M}$ respectively, and $\gamma$ is a constant. Moreover, the matrix $F$ is a block diagonal matrix that has $k$ DFT matrices along its diagonal so the last block is the scaled identity matrix $mI_{M}$ where $m$ is the DFT size ($k \times m=M$).

I am interested in finding the maximum eigenvalue of the matrix $B$ (to be used as the step size for the gradient descend algorithm). To to reduce complexity, I had an intuition that it could be approximated by the maximum eigenvalue of the first block $A^{H}A +\gamma$ which found to be true by simulations. I tried to formulate and prove such a relationship but didn't succeed so far.

Accordingly, what I am trying to prove is: $$ \lambda_{\max}(B) \approx \lambda_{\max}(A^{H}A +\gamma)$$

I thought about approaching it in two ways:

1. Using the identity 3.1 from this page, since $FF^{H}$ is invertible, I wrote the characteristic polynomial:

   \begin{aligned} \mathbb{det}(\lambda I_{N+M} - B) & = \mathbb{det}(\lambda I_M - FF^{H})\times \mathbb{det}((\lambda I_N - (A^{H}A +\gamma)) - (A^HF) (\lambda I_M - FF^H)^{-1} (F^HA)) \\ & = \mathbb{det}(\lambda I_M - m I_M)\times \mathbb{det} ((\lambda I_N - (A^{H}A +\gamma)) - (A^HF) (\lambda I_M - mI_M)^{-1} (F^HA))\\ & = (\lambda - m)^M\times \mathbb{det} ((\lambda I_N - (A^{H}A +\gamma)) - m(\lambda - m)^{-1}(A^HA)) \end{aligned} The passages I tried to write after the last one seem to complicate not simplify the derivation so I would stop here. From the last line we can say that $\lambda_{max}(B)$ is the maximum between $m$ and the maximum root of the determinant term which I am not able to simplify anymore in a way I can compare it with the term$ \mathbb{det}(\lambda I_N -(A^{H}A +\gamma)$ being the characteristic polynomial for the first block.

2. Rearranging the matrix $B$: $$B = \left[\begin{matrix}A^{H}A + \gamma &\mathrm{0} \\ \mathrm{0} & FF^H\end{matrix}\right] + \left[\begin{matrix}\mathrm{0} &A^{H}F \\ F^{H}A & \mathrm{0}\end{matrix}\right] = B1 + B2 $$

   and considering the second off-diagonal matrix $B2$ as a perturbation to the first matrix $B1$. In this case I can say: $$\lambda_{\max}(B) = \lambda_{\max}(B1) \pm \epsilon$$ where: $$\lambda_{\max}(B1) = \max(\lambda_{\max}(A^{H}A +\gamma),m)$$ and $\epsilon$ is the perturbation error.

   However, I am not sure if the assumption is valid since the elements of B2 cannot be considered small. Further more, I am not aware of how to proceed to find $\epsilon$ (error due perturbation on $\lambda_{\max}$) and most of the pages and papers I found didn't help.

The last question, if such a relationship proved to exist, would it be possible to deduct some constraints on $\gamma$ that makes it valid? possibly on $N$ and $M$ too?

Any comment or hint would be highly appreciated.

Answer 1

I am afraid what you want to prove regarding $\lambda_{\text{max}}\approx \lambda_{\text{max}}(A^*A+\gamma)$ cannot hold in general. Luckily $FF^*=F^*F$

I assume $\gamma=0$ latter since the block matrix $B_{\gamma}$ is positive semi-definite (to see) $\lambda_{\text{max}}(B_{\gamma})\ge \lambda_{\text{max}}(B_{0})$ when $\gamma\ge 0$ (an approximation here is difficult)

So for that $B_0$ if $X=\begin{pmatrix}A&F\\0&0\end{pmatrix}$ $B_0=X^*X$ and if one assume also that the dimensions $N=M$, (you can complete block $A$ or block $F$ by zeros) you have $$\lambda_{\text{max}}(B_{0})=\lambda_{\text{max}}(X^*X)=\lambda_{\text{max}}(XX^*)=\lambda_{\text{max}}(AA^*+FF^*)$$