# Is there a fast way to compute the lowest eigenvalue of this symmetric PD matrix in this specific scenario?

Consider

$$C = A^H D A + M$$

where

• $$A$$ is a $$m \times m$$ unitary matrix.

• $$D$$ is a $$m \times m$$ diagonal matrix with entries either $$0$$ or $$1$$. The number of $$1$$'s is $$n \ll m$$.

• $$M$$ is a $$m \times m$$ diagonal matrix with all non-negative entries.

It is known that $$C$$ is a positive definite matrix. Is there a fast way to compute the lowest eigenvalue (need not compute the eigenvector) of $$C$$?

Especially given $$n \ll m$$ and $$m$$ being very large I cannot afford to compute all $$m$$ eigenvalues. Also I would like to avoid storing a $$m \times m$$ matrix in memory if possible.

• @RodrigodeAzevedo : C is PD. (otherwise PSD means smallest eigen value is zero no?) Mar 14, 2019 at 4:50
• @RodrigodeAzevedo : if you are asking $C$ is symmetric, then yes. $C$ is symmetric positive definitive. (SPD) Mar 14, 2019 at 4:58
• How are you storing $A$ if you cannot store $m\times m$ matrices? Are you operating $Au$ implicitly? Mar 20, 2019 at 1:13
• @Y.S. : I have a closed form expression/formula to generate entries of A. Look at D. I dont need to store entire A due to D. matrices A and M are fixed constants, D is the input to the algorithm. D is the one that varies. Mar 20, 2019 at 1:16
• @Y.S. : some approach : $B=A^HDA$ is a $m\times m$ symmetric PSD with top $n$ eigen values equal to $1$ and the remaining $(m−n)$ being zero. $n<<m$ Mar 20, 2019 at 1:17

There are many ways to do this. One way would be inverse iteration, which is essentially power iteration with $$C^{-1}$$. However, this requires a solve at each step.
Another possibility is to observe that the matrix $$\alpha I - C$$ will has eigenvalues $$\alpha - \lambda_i$$ where $$\lambda_i$$ is an eigenvalue of $$C$$. Therefore, if we pick $$\alpha$$ so that $$|\alpha-\lambda_\min| > |\alpha - \lambda_i|$$ for all $$\lambda_i$$ except $$\lambda_{\min}$$ the top eigenvalue of $$\alpha I - C$$ will correspond to the bottom eigenvalue of $$C$$. We can then compute the top eigenvalue of $$I - \alpha C$$ which will give us the smallest eigenvalue of $$C$$.
A simple way to ensure this is to pick $$\alpha > \lambda_{\max}$$. If you want, you could compute the top eigenvalue of $$C$$ and use this. Otherwise you could use the fact that, $$\lambda_{\max}(C) \leq \lambda_\max(A^HDA) + \lambda_\max(M) \leq 1 + \lambda_\max(M)$$