As is known, the rank1 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.
1 Answer
$\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=1x_1^2, \end{equation} and \begin{equation} 0\le x_*^T\Si x_*x^T\Si x=\la_1(1x_1^2)\sum_2^d\la_j x_j^2\le\la_1(1x_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_*)$.

$\begingroup$ Thx! This answer really helps! Can this result be extended to rankk 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$– lazyleoMay 14, 2021 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, 2021 at 16:10


$\begingroup$ @lazyleo : So, does this answer satisfactorily address your question above? $\endgroup$ May 16, 2021 at 2:40

$\begingroup$ Yes. But I didn't find the answer to the rankk case (posted in the new link). $\endgroup$– lazyleoMay 16, 2021 at 6:38