# Find $\mathbf{X}$ that minimizes ${tr(\mathbf{X}^T\mathbf{P}\mathbf{X})}/{tr(\mathbf{X}^T\mathbf{Q}\mathbf{X})}$

We have

$$C(\mathbf{X})=\frac{tr(\mathbf{X}^T\mathbf{P}\mathbf{X})}{tr(\mathbf{X}^T\mathbf{Q}\mathbf{X})}$$ where $\mathbf{X}$ is an $N$x$M$ matrix of unknowns and $\mathbf{P}$ and $\mathbf{Q}$ are $N$x$N$ constant matrices. We want to find $\mathbf{X}$ that minimizes $C$.

Solution for the special case of $M=1$ could be found here.

A corrected version of this question (adding orthonormality constraint on columns of $\mathbf{X}$ is posted here.

• Is $M>1$ really that different? It is still quadratic in $x$ so you can rewrite it to an $M=1$ case. – LinAlg Sep 13 '18 at 0:45
• btw, is there a way to calculate the smallest eigenvector efficiently ? (I know of the Power method for largest eigenvector). Here we could assume all the eigenvalues are positive I guess. – mghandi Sep 13 '18 at 1:02
• I think if we switch $P$ and $Q$ then we could use Power method. – mghandi Sep 13 '18 at 1:11
• I think you are confused with the absolute values. The smallest eigenvalue could be found by the Power method if it is very negative. – LinAlg Sep 13 '18 at 1:34
• I meant we are given that C is always positive, hence all the eigenvalues should be positive. – mghandi Sep 13 '18 at 1:53

Define some new variables \eqalign{ A &= \tfrac{1}{2}(P+P^T), \,\,\,\,\,B = \tfrac{1}{2}(Q+Q^T), \,\,\,\,\,M = B^{-1}A \cr \alpha &= {\rm tr}(X^TAX) \implies d\alpha=2AX:dX \cr \beta &= {\rm tr}(X^TBX) \implies d\beta=2BX:dX \cr } Write your function in terms of these new variables, then find the differential and gradient. \eqalign{ C(X) = \lambda &= \beta^{-1}\alpha \cr d\lambda &= \beta^{-1}(d\alpha-\lambda\,d\beta) = 2\beta^{-1}(AX-\lambda BX):dX \cr \frac{\partial C}{\partial X} = \frac{\partial \lambda}{\partial X} &= 2\beta^{-1}(AX-\lambda BX) \cr } Set the gradient to zero and solve \eqalign{ AX &= \lambda BX \cr MX &= \lambda X \cr Mv1^T &= \lambda v1^T \cr } This is the eigenvalue equation. So $\lambda\,$ is the smallest eigenvalue of the matrix $M$, $1$ is a vector of all ones, $v$ is the eigenvector corresponding to $\lambda$, and $X$ is a matrix whose columns are all identical and equal to $v$.
In the unlikely event that the matrix $M$ has several different eigenvectors all corresponding to the same minimal eigenvalue, then the columns of $X$ need not be identical but could consist of linear combinations of such eigenvectors.
NB: In some steps above, a colon denotes the trace/Frobenius product, i.e. $$A:B = {\rm tr}(A^TB)$$
• did you see that $x$ is a matrix? – LinAlg Sep 13 '18 at 0:42
• If we add the constraint that columns of $X$ are orthonormal, would the $M$ smallest eigenvectors be the solution? I posted it as a separate question to avoid confusion: math.stackexchange.com/questions/2915695/… – mghandi Sep 13 '18 at 14:57
• @mghandi If $M$ is hermitian (symmetric) then its eigenvectors are orthogonal, and your suggested solution is correct. In the more likely event that $M\ne M^*$ then the problem is much harder, and probably does not have a closed-form solution. – lynn Sep 14 '18 at 5:47
• I realized that the $M$ smallest eigenvectors would be the solution if we use $X^TQX=I$ constraint (suggested by @loup-blanc). – mghandi Sep 20 '18 at 20:30