Unconstrained minimization of $X \mapsto \left\| A - X X^T \right\|_F^2$ I am studying the minimization problem:
$$\min_{X \in \mathbb{R}^{n \times d}} \quad f(X) := \left\| A - X X^T \right\|_F^2$$
where $n \times n$ matrix $A$ is positive semidefinite and $n > d$.

My work
Firstly, I observed that if $C$ is an ortogonal $d \times d$ matrix, and $X^{*}$ is a solution to the minimization problem, then $X^{*}C$ must also be a solution, since
$$f(XC) = ||A-XC(XC)^T||^2_F = ||A-XCC^TX^T||^2_F = ||A-XX^T||^2_F = f(X), \quad \forall X$$
Then, we have that $f(X) \geq 0 \ \ \forall X, \ $ so if $\ f(X_0)=0, \ $ $X_0 \ $ must be a local minimum, right?
So then we can have a minimum for an $X_0$ that satisfies $A = X_0X_0^T$. It is my understanding such $X_0$ exists given $A$ is semi-definite positive.
Does this prove $f(X)$ is non-convex since it appears to have multiple minima? Is my reasoning correct thus far?
 A: A couple of points:
First, convex functions can have multiple minima, so long as the minima form a convex set. It would prove $f$ is not strictly convex though.
Second, it's not immediately clear that we even get multiple values from $XC$. For example, if $X$ is the zero matrix, then $XC = 0$ for all $C$.
To clear this up, I would suggest considering $A = YY^\top$ for some non-zero $Y \in \Bbb{R}^{n \times d}$. Note that:

*

*$A$ is positive-semidefinite,

*$A$ is non-zero, and

*The problem is minimised at (at least) $X = Y$, with $f(X) = 0$.

Then, the problem is minimised at $X = -Y$ as well, for the reasons you outlined (take $C = -I$). If $f$ were convex, we would expect the midpoint of these minimisers, i.e. $X = 0$, to also be a minimum. But,
$$f(0) = \|A - 00^\top\|_F^2 = \|A\|_F^2 > 0 = f(X).$$
This is a contradiction, thus $f$ is indeed not convex.
A: $
\def\l{\left}
\def\r{\right}
\def\lr#1{\l(#1\r)}
\def\rnk#1{\operatorname{rank}\lr{#1}}
$Since $\;\rnk{X}\le d,\;$ it looks like you want the best rank-$d$ approximation of $A$ in factored form.
Start with the SVD $\,$and assume the singular values are ordered $(\sigma_1\ge\sigma_2\ge\ldots\ge\sigma_n)$
$$\eqalign{
A &= USU^T \quad\quad
Y &= US^{1/2} \\
}$$
The best rank-$d$ approximation (in the Frobenius sense)
comes from the first $d$-columns of $Y$
$$\eqalign{
Y &= \Big[\,y_1\;\;y_2\;\;\ldots\;y_d\;\;\ldots\;y_n\,\Big]
 \quad&\implies A &= YY^T\\
X &= \Big[\,y_1\;\;y_2\;\;\ldots\;y_d\,\Big]
 \quad&\implies A &\approx XX^T \\\\
}$$

Another approach is to consider the NMF problem
$$\min_{W,H}\;\Big\|A-WH^T\Big\|_F^2$$
If you initialize $W$ and $H$ to the same random matrix,
then the Lee-Seung iterations
$$\eqalign{
W_+ &= W\odot\lr{\frac{AH}{WH^TH}}, \qquad
H_+ &= H\odot\lr{\frac{A^TW}{HW^TW}} \\
}$$ will converge such that $\,\{W,H\}$ are linear multiples of each other. Then $X$ can be recovered as
$$W=\lambda^2H \quad\implies\quad X=\lambda H$$
A: Given $n \times n$ symmetric positive semidefinite matrix $\bf A$, let scalar field $f : \Bbb R^{n \times d} \to \Bbb R$ be defined by
$$f ({\bf X}) := \left\| {\bf X} {\bf X}^\top - {\bf A} \right\|_{\text{F}}^2 = \cdots = \mbox{tr} \left( \, {\bf X} {\bf X}^\top {\bf X} {\bf X}^\top \right) - 2 \, \mbox{tr} \left( {\bf X}^\top {\bf A} \, {\bf X} \right) + \left\| {\bf A} \right\|_{\text{F}}^2$$
Taking the gradient of $f$,
$$\nabla f ({\bf X}) = 4 \left( {\bf X} {\bf X}^\top - {\bf A} \right)  {\bf X}$$
and, finding where the gradient vanishes, we obtain the following cubic matrix equation
$$\boxed{\left( {\bf X} {\bf X}^\top - {\bf A} \right)  {\bf X} = {\bf O}_{n \times d}}$$
