It is stated in http://users.eecs.northwestern.edu/~yingwu/teaching/EECS510/Reading/Williams_NIPS01.pdf

that the PCA mapping from $h$-dimensional data to low $k$-dimensional space minimizes $$\sum_{i,~j} d_{ij}^2-g_{ij}^2,$$ subject to orthonormality of direction vectors. Distances $d_{ij}$ and $g_{ij}$ correspond to distances between items $i,j$ in a high and low-dimensional space, respectively. Can it be shown that PCA also minimizes $$\sum_{i,~j} (d_{ij}-g_{ij})^2,$$subject to orthonormality of direction vectors?

  • $\begingroup$ This is my favorite application of principal components (SVD). My hunch is the criteria are so different that optimizing one generally cannot also optimize the other, and that an example with just a few data points should suffice to show it. $\endgroup$
    – hardmath
    Dec 15 '12 at 15:37
  • $\begingroup$ @hardmath I agree; I found numerous papers (and two books) claiming the second criterion is optimized by PCA. Others claim it's the first. Please form your answer, possibly with derivation. $\endgroup$
    – usero
    Dec 15 '12 at 20:27

Consider, in some "high dimensional" Euclidean space $\mathbb{R}^n$, a set $\mathscr{S}$ of points and all the unordered distinct pairs (edges) $\mathscr{E}$ drawn from that set. Denote the usual Euclidean distance for each pair $e \in \mathscr{E}$ by $d_e$.

We ask about orthogonally projecting $\mathscr{S}$ onto a lower dimensional subspace, say of dimension $k$, so that the (reduced) distances $\delta_e$ between projected pairs $\pi(e)$ collectively best approximate the original distances $d_e$.

Two optimality criteria are described in this question, the first being minimization of:

$$ (1) \; \sum_{e \in \mathscr{E}} d_e^2 - \delta_e^2 $$

and the second being a least squares formulation, minimizing:

$$ (2) \; \sum_{e \in \mathscr{E}} (d_e - \delta_e)^2 $$

The question posed is whether a solution optimal for the first criterion is necessarily optimal in the second sense. We propose a simple example showing this is not the case, taking the 3-4-5 right triangle in the plane and orthogonally projecting it onto a line.

Since rigid motions (translation, rotation, reflection) preserve distances, a simple setup suffices. Letting $\mathscr{S} = \{ (0,0),(3,0),(0,4) \}$, we ask what (counterclockwise) rotations by angle $\theta$ (about the origin) yield the respective minimums of (1) and (2) if rotated points are orthogonally projected onto the $x$-axis. Notice that $\pi(0,0) = 0$ regardless of the angle chosen, but $\pi(3,0) = 3\cos(\theta)$ and $\pi(0,4) = -4\sin(\theta)$.

As a general observation (1) adds certain constants for the original distances $d_e^2$ and subtracts a sum of projected distances squared $\delta_e^2$ depending on the choice of projection. Thus minimizing (1) amounts to maximizing the latter sum. Because the projected distances are bounded above by the original distances (as alluded to earlier), maximizing the sum of squares of projected distances tends to produce reasonable approximations.

While a general method exists for solving (1) based on the "principal components" (eigenvectors) of a symmetric matrix (and we can circle back to that approach), let's first write out the subtracted part of (1) as a function of angle $\theta$ and perform its necessary maximization:

$$ f(\theta) = \sum \delta_e^2 = 9\cos^2(\theta) + 16\sin^2(\theta) + (3\cos(\theta) + 4\sin(\theta))^2 $$

Simplifying with familiar trigonometric identities reveals that the function has period $\pi$ (rather than $2\pi$):

$$ f(\theta) = 25 -7\cos(2\theta) +12\sin(2\theta) = 25 +\sqrt{193}\sin(2\theta -\alpha) $$

where $\alpha = \tan^{-1}(\frac{7}{12}) \approx 0.52807445$.

By inspection this function $f(\theta)$ has a maximum value $25 +\sqrt{193}$. The location of this (global) maximum (unique within a period $\pi$) is thus:

$$ 2\theta_1 - \alpha = \frac{\pi}{2} $$

$$ \theta_1 = \frac{\pi}{4} + \frac{\alpha}{2} \approx 1.04943539 $$

Thus an exact minimum of (1) (resp. maximum of $f(\theta)$) is known, so we next turn to its relationship with the minimization of (2).

Expanding (2) shows that it contains, among other terms, the same constant $\sum d_e^2$ that we previously pointed out in (1):

$$ \sum (d_e - \delta_e)^2 = \sum d_e^2 - 2\sum d_e \delta_e + \sum \delta_e^2 $$

Also the last summation is the same as term $f(\theta)$ whose maximum was found above. For the minimum of (2) to occur at the same location as (1) would require the middle term:

$$ g(\theta) = -2\sum d_e \delta_e $$

to have a "steeper" minimum there which overcomes the maximum of $f(\theta)$. For simplicity we only calculate whether $\theta_1$ is a critical point of $g(\theta)$. If not, then a minimum of $g(\theta)$ cannot occur there, and likewise (2) is not minimized at the same place as (1).

$$ g(\theta) = -2(9|\cos(\theta)| + 16|\sin(\theta)| + 5|3\cos(\theta) + 4\sin(\theta)|) $$

In a small neighborhood of $\theta_1$ the expressions within absolute values above are all positive (it's in the first quadrant). It follows that in such a neighborhood we can differentiate $g(\theta)$ with disregard for those absolute values, so:

$$ g'(\theta_1) = 48\sin(\theta_1) - 72\cos(\theta_1) \approx 5.76245102 $$

It follows that (2) does not have a critical point at $\theta_1$, so the optimality criteria (1) and (2) give different best projections in this case.

  • $\begingroup$ Thanks. You clarified that the claim of PCA minimizing (1) is true, and the one stating that PCA minimizes (2) is false. $\endgroup$
    – usero
    Dec 24 '12 at 11:02

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.