2
$\begingroup$

Given a $p \times p$ positive definite matrix $\Sigma$, why eigenvectors of $\Sigma$, stacked as columns of a matrix $R \equiv [r_1 \, r_2 \, \ldots \, r_p]$, optimize the following orthogonally constrained minimization problems? $$ \mathrm{minimize}~~~~\log \det\big( I \odot (R^\mathsf{T}\Sigma R) \big)~~~~~\text{s.t.}~~~~~R^\mathsf{T}R = I~~, $$ where $\odot$ is Hadamard product, or equivalently, $$ \mathrm{minimize}~~~~\sum_{i=1}^p \log(r_i^\mathsf{T}\Sigma r_i)~~~~~\text{s.t.}~~~~~r_i^\mathsf{T}r_j = \delta_{ij}~~. $$

$\endgroup$

2 Answers 2

3
$\begingroup$

Your minimization problem is equivalent to \begin{equation*} \min_{R^TR=I}\quad\prod_{i=1}^p r_i^T\Sigma r_i, \end{equation*} and it can be shown (using Hadamard's determinant inequality and some more argumentation) that this minimum overall $p$ orthonormal tuples is achieved by choosing the $r_i$ corresponding to the smallest $p$ eigenvectors.

EDIT Here the details that complete my answer (because it seems that the OP already knew the answer and still posted this question...)

We know that for a semidefinite matrix $\Sigma$ with eigenvalues $\lambda_1,\ldots,\lambda_n$, and any orthonormal $R$,

\begin{equation*} \prod_{i=n-p+1}^n \lambda_i \le \det(R^T\Sigma R) \le \prod_{i=1}^p (R^T\Sigma R)_{ii} = \prod_{i=1}^p r_i^T\Sigma r_i. \end{equation*} We are trying to minimize the upper, bound and by choosing $R$ to be the matrix of the smallest $p$ eigenvectors, we can actually turn the first inequality into an equality. This proves the claim. The first inequality is a classic result on eigenvalues, while the second inequality is Hadamard's determinant theorem.

$\endgroup$
0
1
$\begingroup$

Because $r_i$ is supposed to be unit norm, one can replace $r_i$ with $\frac{r_i}{\lVert r_i \rVert}$ in the objective and obtain: $$ \mathrm{minimize}~~~~\sum_{i=1}^p \log \Big( \frac{r_i^\mathsf{T}\Sigma r_i}{r_i^\mathsf{T}r_i} \Big)~. $$ Now, taking the derivative of this objective with respect to $r_i$ (forgetting about orthogonality constraints for now), we get: $$ \frac{r_i}{r_i^\mathsf{T}r_i} = \frac{\Sigma r_i}{r_i^\mathsf{T}\Sigma r_i}~. $$ Obviously only eigenvectors of $\Sigma$ satisfy such constraints. Fortunately, they are orthogonal too, so the orthogonality constraints are automatically satisfied. Taking the $p$ smallest eigenvectors of $\Sigma$ when they are positive provides an answer.

$\endgroup$
6
  • $\begingroup$ looks like a nice proof, but if you already knew the answer how come you asked the question? $\endgroup$
    – Suvrit
    Nov 13, 2013 at 20:55
  • $\begingroup$ As I mentioned above, I didn't know the answer. After I posted the question, I solved it myself too. I like your answer better than mine though. Thanks! $\endgroup$
    – Norouzi
    Nov 13, 2013 at 21:17
  • $\begingroup$ @Norouzi: What you have shown is necessity. Should you not prove the convexity of the objective function in your answer to show the concluding condition is sufficient, too? $\endgroup$
    – Hans
    Nov 13, 2013 at 22:06
  • $\begingroup$ @Hansen: Good point! I think if we agree that the original objective (without log) is bounded below (it is bounded below by zero because of positive definiteness), and is differentiable everywhere, and is defined on a closed set, then the local and global minimas should be achieved at extrema points. The description above tries to find the extrema points by setting the gradient to zero. The objective is actually not convex at least when the matrix R is rectangular; any subset of eigenvectors is an extrema point. $\endgroup$
    – Norouzi
    Nov 14, 2013 at 15:59
  • $\begingroup$ @Norouzi: You are right for the most part. I did not think thoroughly through earlier regarding the convexity of the objective function. Restricted to the unit norm, the set of $R$ is the orthogonal group $O(n)$. It is compact and with no boundary. That is why the everywhere differentiable objective function can not be convex everywhere. By the way, by "rectangular" do you mean orthogonal? Also, it would be nice if you could complete your proof in the answer section with what we have discussed. I will up-vote your answer if you make it whole. $\endgroup$
    – Hans
    Nov 14, 2013 at 20:16

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.