4
$\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 real non-negative entries, with atleast one positive entry.

It is known that $C$ is a symmetric 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.

PS : Inverse iteration, or Power iteration methods are generic and I don't find them taking any advantage of this specific scenario. So is Rayleigh Quotient method. Appreciate some leads for an efficient algorithm.

Improve this question
$\endgroup$
6
  • $\begingroup$ Is there something special about the unitary matrix $A$? Otherwise already the input needs $O(m^2)$ for storing. $\endgroup$
    – user35593
    Commented Mar 14, 2019 at 17:32
  • $\begingroup$ @user35593 : look at D. I dont need to store entire A due to D. $\endgroup$
    – Rajesh D
    Commented Mar 14, 2019 at 18:05
  • $\begingroup$ @user35593 : yes I have a closed form expression/formula to generate entries of A. $\endgroup$
    – Rajesh D
    Commented Mar 14, 2019 at 18:11
  • $\begingroup$ If you also have a fast algorithm for the matrix multiplication an iterative method (e.g. power or inverse) could make use of it. $\endgroup$
    – user35593
    Commented Mar 14, 2019 at 18:44
  • $\begingroup$ @user35593 : matrices A and M are fixed constants, D is the input to the algorithm. D is the one that varies $\endgroup$
    – Rajesh D
    Commented Mar 14, 2019 at 18:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .