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.
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)$