3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Is $M>1$ really that different? It is still quadratic in $x$ so you can rewrite it to an $M=1$ case. $\endgroup$ – LinAlg Sep 13 '18 at 0:45
  • $\begingroup$ 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. $\endgroup$ – mghandi Sep 13 '18 at 1:02
  • $\begingroup$ I think if we switch $P$ and $Q$ then we could use Power method. $\endgroup$ – mghandi Sep 13 '18 at 1:11
  • $\begingroup$ I think you are confused with the absolute values. The smallest eigenvalue could be found by the Power method if it is very negative. $\endgroup$ – LinAlg Sep 13 '18 at 1:34
  • $\begingroup$ I meant we are given that C is always positive, hence all the eigenvalues should be positive. $\endgroup$ – mghandi Sep 13 '18 at 1:53
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ did you see that $x$ is a matrix? $\endgroup$ – LinAlg Sep 13 '18 at 0:42
  • $\begingroup$ Oops! Let me rethink this. $\endgroup$ – lynn Sep 13 '18 at 0:43
  • $\begingroup$ 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/… $\endgroup$ – mghandi Sep 13 '18 at 14:57
  • $\begingroup$ @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. $\endgroup$ – lynn Sep 14 '18 at 5:47
  • $\begingroup$ I realized that the $M$ smallest eigenvectors would be the solution if we use $X^TQX=I$ constraint (suggested by @loup-blanc). $\endgroup$ – mghandi Sep 20 '18 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.