General PCA optimization problem

Question

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!

Answer 1

It is not "essential that $C$ be positive definite." This post focuses on explaining why.

Instead of maximizing $f_C(U)=\operatorname{tr}\left(U^\prime C U\right),$ let's maximize $f_C(U) + d\mu$ for some suitable constant $\mu$ to be determined later. (All optimization will be performed subject to the condition $U^\prime U = \mathbb{I}_d$ where $\mathbb{I}_d$ is the $d\times d$ identity matrix.)

The idea is that

$$d\mu = \operatorname{tr}(\mu\, \mathbb{I}_d) = \operatorname{tr}(\mu\, U U^\prime) = \operatorname{tr}(\mu\, U^\prime U) = \operatorname{tr}\left(U^\prime\,\mu\mathbb{I}_d\,U\right),$$

allowing the modified objective function to be expressed as

$$f_C(U) + d\mu = \operatorname{tr}\left(U^\prime C U\right) + \operatorname{tr}\left(U^\prime\,\mu\mathbb{I}_d\,U\right) = \operatorname{tr}\left(U^\prime\left(C + \mu\mathbb{I}_d\right)U\right) = f_{C + \mu\mathbb{I}_d}(U).$$

Let $\lambda_1\ge \lambda_2\ge \cdots \ge \lambda_n$ be the eigenvalues of $C.$ Choosing $\mu \gt -\lambda_n$ ensures that all eigenvalues of $C + \mu\mathbb{I}_d$ are positive, because (by the very definition of eigenvalue) when $\rho$ is an eigenvalue of $C$ there is a vector $e$ for which $Ce = \rho e$ and this is the case if and only if

$$(C + \mu\mathbb{I}_d)e = Ce + \mu\mathbb{I}_d e = \rho e + \mu e = (\rho + \mu)e,$$

showing that the eigenvalues of $C + \mu\mathbb{I}_d$ are $\lambda_1 + \mu \ge \lambda_2 + \mu \ge \cdots \ge \lambda_n + \mu \gt \lambda_n - \lambda_n = 0.$

Consequently, the results quoted in the question apply to $C + \mu\mathbb{I}_d:$ the maximum value of $f_{C + \mu\mathbb{I}_d}$ is the sum of its $d$ largest eigenvalues, equal to

$$\max(f_C) + \mu d = \max(f_{C + \mu\mathbb{I}_d}) = (\lambda_1 + \mu) + \cdots + (\lambda_d + \mu) = (\lambda_1 + \cdots + \lambda_d) + \mu d.$$

Subtracting $\mu d$ from both sides shows that these results continue to apply to any symmetric matrix $C,$ no matter what its eigenvalues might be.