2
$\begingroup$

I was reading a post about deriving PCA, So it considered an arbitrary row datum, $x_i$ and tried to maximize projection length for each row of data matrix, $X \in \mathbb{R}^{N\times D}$: $$\sum_{i=1}^N(u_1.x_i)^2=\sum_{i=1}^N(u_1.x_i)(u_1.x_i)=u_1^\top \Biggr[ \sum_{i=1}^Nx_ix_i^\top \Biggr] u_1\stackrel{*}{=}u_1^\top X^\top X u_1$$

Up to step *, everything is great, but I don't realize why the step * holds?

$\endgroup$
6
  • $\begingroup$ I only see step *, where is step ⋆? $\endgroup$
    – mhdadk
    Commented Jul 9, 2023 at 10:41
  • $\begingroup$ @mhdadk Just a wrong character, fixed! $\endgroup$ Commented Jul 9, 2023 at 10:43
  • $\begingroup$ "The goal of this thesis is to modify projection pursuit by trading accuracy for interpretability. The modification produces a more parsimonious and understandable model without sacrificing the structure which projection pursuit seeks." rand.org/pubs/external_publications/EP51086.html $\endgroup$
    – user78229
    Commented Jul 9, 2023 at 10:52
  • $\begingroup$ @MikeHunter Didn't catch that. I am a newbie. $\endgroup$ Commented Jul 9, 2023 at 10:59
  • $\begingroup$ @MikeHunter No, and I think it is way too complicated for me! I am just a junior student self-studying an introductory course to machine learning. $\endgroup$ Commented Jul 9, 2023 at 11:08

2 Answers 2

2
$\begingroup$

In my opinion, this may be easier to see with $D=2$. In this case, you have

\begin{align*} X^\top X & = \begin{bmatrix} 1 & 1 & \dots & 1 \\ x_{11} & x_{12} & \dots & x_{1N} \\ \end{bmatrix} \begin{bmatrix} 1 & x_{11}\\ 1 & x_{12}\\ \ldots\\ 1 & x_{1N}\\ \end{bmatrix} = \begin{bmatrix} \mathbb{1}^\top \mathbb{1} & x_{\bullet1}^\top\mathbb{1}\\ x_{\bullet1}^\top\mathbb{1} & x_{\bullet1}^\top x_{1\bullet}\\ \end{bmatrix}\\ & = \begin{bmatrix} 1+1+\cdots+1 & x_{11}+x_{12}+\cdots+x_{1N}\\ x_{11}+x_{12}+\cdots+x_{1N} & x_{11}^2+x_{12}^2+\cdots+x_{1N}^2\\ \end{bmatrix}\\ &= \begin{bmatrix} 1 & x_{11}\\ x_{11} & x_{11}^2\\ \end{bmatrix} + \begin{bmatrix} 1 & x_{12}\\ x_{12} & x_{12}^2\\ \end{bmatrix} + \cdots + \begin{bmatrix} 1 & x_{1N}\\ x_{1N} & x_{1N}^2\\ \end{bmatrix}\\ &= x_{1}x_1^{\top} + x_{2}x_2^{\top}+\cdots+x_{N}x_N^{\top}\\ &= \sum_{I=1}^N x_i x_i^\top. \end{align*}

Unless otherwise stated, all vectors are column vectors. I've used $x_{\bullet1}$ to denote the second column of $X = (x_{ij})$, $x_{j}$ to denote the $j$th row of $X$ (treated to be a column vector) and $\mathbb{1} = (1,1,\ldots,1)$ vector of length $N$.

$\endgroup$
2
  • $\begingroup$ I think $x_i x_i^\top$ is a scalar not a matrix, am I right? seems that the correct equality is $x_i^\top x_i$ but in this way I don't know how we can change the second equality in main question to $x_i^\top x_i$ instead of $x_i x_i^\top$ $\endgroup$ Commented Jul 9, 2023 at 11:05
  • $\begingroup$ @user21232681 t depends on how you see the $i$th row of $X$. If you see it as a column vector, as I do, then $x_i x_i^\top$ is the correct formula. mhdadk (+1) considers these to be row vectors, which explains the difference in notation. $\endgroup$
    – utobi
    Commented Jul 9, 2023 at 12:30
2
$\begingroup$

There must be a typo here since $x_ix_i^T$ is a scalar value if $x_i$ is a row vector. What the author likely meant is $$ \sum_{i=1}^N(u_1\cdot x_i)^2=\sum_{i=1}^N(u_1\cdot x_i)(u_1\cdot x_i)=u_1^\top \Biggr[ \sum_{i=1}^Nx_i^\top x_i \Biggr] u_1\stackrel{*}{=}u_1^\top X^\top X u_1 $$ where $x_i^\top x_i$ is an outer product ($D \times D$ matrix). In this case, we have \begin{align} X^\top X &= \begin{bmatrix}x_1^\top & x_2^\top & \cdots & x_N^T\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\ \vdots \\ x_N\end{bmatrix} \\ &= x_1^\top x_1 + \cdots + x_N^\top x_N \\ &= \sum_{i=1}^Nx_i^\top x_i \end{align}

$\endgroup$
5
  • $\begingroup$ Yes I think this makes sense, by the way how did you derive the second equality? $\endgroup$ Commented Jul 9, 2023 at 10:56
  • $\begingroup$ @user21232681 the second equality is just a result of the definition of matrix multiplication. $\endgroup$
    – mhdadk
    Commented Jul 9, 2023 at 11:59
  • $\begingroup$ The initial expression in the chain of equalities in the question makes sense only when $x_i$ is a column vector, not a row vector. $\endgroup$
    – whuber
    Commented Jul 9, 2023 at 17:21
  • $\begingroup$ @whuber which part are you referring to exactly? I'm a bit tied up with something, so feel free to edit my answer to make any corrections. $\endgroup$
    – mhdadk
    Commented Jul 9, 2023 at 21:07
  • $\begingroup$ "$u_i\cdot x_i.$" $\endgroup$
    – whuber
    Commented Jul 10, 2023 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.