3
$\begingroup$

I was looking at the PCA optimization problem, which is finding a matrix $U \in \mathbb{R}^{d\times n}$, $n \le d$, that solves the problem

$$\max{tr(U^TCU)},\ \ \ s.t. U^TU = I, $$

where $C$ is the covariance matrix of the data. The solution of this problem is to take the $n$ eigenvectors of $C$ corresponding to the largest eigenvalues of $C$ and add them as the columns of the matrix $U$. I have seen that this problem is very similar to other optimization problems used in other dimensionality reduction algorithms, such as LDA or ANMM.

So I was trying to find a general problem of trace maximization of this form:

$$\max{tr(U^TCU)},\ \ \ s.t. U^TU = I, $$

where $C$ is any symmetric matrix. I have looked at the proof of the PCA optimization problem in the book Understanding Machine Learning, where it is proved the following:

$$tr(U^TCU) \le \max_{\beta\in[0,1]^d, \|\beta_1\|\le n}\sum_{i=1}^d \lambda_i\beta_i \le \sum_{i=1}^n\lambda_i,$$

where $\lambda_1 \ge \dots \ge \lambda_d$ are the eigenvalues of $C$. But, in the last step of the inequality it is essential that $C$ is positive semidefinite, in order to have all the eigenvalues non negative, so I can't adapt this proof to a general problem where $C$ is only symmetric. Considering that in ANMM the matrix $C$ is the difference between two positive semidefinite matrices, which may not be positive semidefinite, the result should also be true for a less restrictive set of matrices, but how can it be proved?

Also, I'm interesting in generalizing the problem even more to make it valid for other methods like LDA. In this case, I'm interesting in the problem

$$\max{tr(U^TCU)},\ \ \ s.t. U^TBU = I, $$

where $C$ and $B$ are symmetric matrices with the less restrictions as possible. Many articles affirm that the solution of this problem is obtained taking the eigenvalues of $B^{-1}C$ so, I assume that $B$ is forced to be full-rank. But despite this, we're not guaranteed to have a real eigenvalue decomposition since $B^{-1}C$ may not be symmetric. How is this assured?

Finally, any hints to make the proof in any of these general problems will be apreciated. Thanks in advance!

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.