# 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 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.

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