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$
17
  • $\begingroup$ @RodrigodeAzevedo : C is PD. (otherwise PSD means smallest eigen value is zero no?) $\endgroup$
    – Rajesh D
    Mar 14, 2019 at 4:50
  • $\begingroup$ @RodrigodeAzevedo : if you are asking $C$ is symmetric, then yes. $C$ is symmetric positive definitive. (SPD) $\endgroup$
    – Rajesh D
    Mar 14, 2019 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, 2019 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 D
    Mar 20, 2019 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 D
    Mar 20, 2019 at 1:17

1 Answer 1

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