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

174 Views Asked by At

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.

1

There are 1 best solutions below

5
On BEST ANSWER

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