0
$\begingroup$

As is known, the rank-1 PCA aims to solve the following optimization problem $$\min_{x\in\mathbb{R}^d}\quad -x^T \Sigma x\quad\quad\quad \text{s.t.}\quad \Vert x\Vert_{2}=1,$$ where $\Sigma\in\mathbb{S}^{d}$ is the covariance matrix. Thus the optimum $x^*$ of the PCA problem is the top unit eigenvector of $\Sigma$. Given an approximation $\tilde{x}$ (normalized), the error between the $\tilde{x}$ and $x^*$ is measured by the sine function $$\sin^{2}(\tilde{x}, x^*) = 1-(\tilde{x}^T x^*)^2.$$ I was wondering does there exist any analytical relationship between the objective function $\tilde{x}^\top\Sigma \tilde{x}$ and the error $\sin^2(\tilde{x}, x^*)$? Any help appreciated.

$\endgroup$
1
$\begingroup$

$\newcommand{\Si}{\Sigma}\newcommand{\R}{\mathbb R}\newcommand{\la}{\lambda}$Let us work in an orthonormal eigenbasis of $\Si$. Then without loss of generality $\Si$ is the diagonal matrix with diagonal entries $\la_1\ge\la_2\ge\cdots\ge\la_d\ge0$, $x_*:=x^*=[1,0,\dots,0]^T$, $x:=\tilde x=[x_1,x_2,\dots,x_d]\in\R^d$, $\|x\|_2=1$, $x_*^T\Si x_*=\la_1$, $x^T\Si x=\sum_1^d\la_j x_j^2$, \begin{equation} \sin^2(x, x_*)=1-(x^Tx_*)^2=1-x_1^2, \end{equation} and \begin{equation} 0\le x_*^T\Si x_*-x^T\Si x=\la_1(1-x_1^2)-\sum_2^d\la_j x_j^2\le\la_1(1-x_1^2)=\|\Si\|\sin^2(x,x_*), \end{equation} where $\|\Si\|:=\la_1$, the operator/spectral norm of $\Si$. Thus, the nonnegative error $x_*^T\Si x_*-x^T\Si x$ in the value of the objective function is bounded by the norm of $\Si$ times the error $\sin^2(x,x_*)$.

$\endgroup$
5
  • $\begingroup$ Thx! This answer really helps! Can this result be extended to rank-k PCA? In this case, the sine of the angle might be written as $\Vert sin(X, X^*)\Vert_{F}^2 = k-\Vert X^T X^*\Vert_{F}^2$. $\endgroup$
    – lazyleo
    May 14 at 16:04
  • $\begingroup$ @lazyleo : I am glad to hear this answer was helpful. Something like this should work in the more general setting. However, please ask any additional questions in separate posts. $\endgroup$ May 14 at 16:10
  • $\begingroup$ I have post the rank-$k$ case as another new question: link thx for help! $\endgroup$
    – lazyleo
    May 15 at 8:02
  • $\begingroup$ @lazyleo : So, does this answer satisfactorily address your question above? $\endgroup$ May 16 at 2:40
  • $\begingroup$ Yes. But I didn't find the answer to the rank-k case (posted in the new link). $\endgroup$
    – lazyleo
    May 16 at 6:38

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.