0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @RodrigodeAzevedo : C is PD. (otherwise PSD means smallest eigen value is zero no?) $\endgroup$ – Rajesh Dachiraju Mar 14 at 4:50
  • $\begingroup$ @RodrigodeAzevedo : if you are asking $C$ is symmetric, then yes. $C$ is symmetric positive definitive. (SPD) $\endgroup$ – Rajesh Dachiraju Mar 14 at 4:58
  • $\begingroup$ How are you storing $A$ if you cannot store $m\times m$ matrices? Are you operating $Au$ implicitly? $\endgroup$ – Y. S. Mar 20 at 1:13
  • $\begingroup$ @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. $\endgroup$ – Rajesh Dachiraju Mar 20 at 1:16
  • $\begingroup$ @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$ $\endgroup$ – Rajesh Dachiraju Mar 20 at 1:17
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.