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.
