## Definitions

$PSDP: \min_{P\in S^n_{\geq}} ||F - PG||$
$SP: \min_{S\in S^n} ||F - SG||$

Here, $$F, G \in R^{\ n\times m}$$.

## Background

• $$\tilde{S}$$ denotes a minimizer for the SP problem.
• $$\tilde{P}$$ denotes a minimizer for the PSDP problem.
• $$\tilde{S}GG'+ GG'\tilde{S} = FG' + GF' = Q$$
• When $$rank(G) = n$$, a sufficient condition for $$\tilde{S}$$ to be in $$S^n_{\geq}$$ is that $$Q \in S^n_{\geq}$$.
• A sufficient condition for $$\tilde{S}$$ to be in $$S^n_{\geq}$$ is that $$FG' \in S^m_{\geq}$$.
• $$rank(G) = n$$ is also necessary and sufficient for uniqueness of minimizers in case of PSDP.

## Previous Approches

• The objective function and the feasible set in case of PSDP are both convex.
• We can use convex optimization which directly exploits the convexity of $$S^n_{\geq}$$.
• Solutions involve finite convergence towards global minimas bringing the approximate minimizer arbitrarily close to the unique global minimizer.

## Approach of this paper

$PSDP^*: \min_{E \in R^{n\times n}} ||F - E'EG||$
$\tilde{P}_{\text{global}} = \tilde{E}_{\text{local}}'\tilde{E}_{\text{local}}$

Algorithm ideas:

• Steepest descent (doesn’t converge, proven)
• Newton’s algorithm (modified, superior than known convex programs of that time)
• Where do we obtain the data? Take stuff, perturb by errors to make sure that $$\tilde{S} \neq \tilde{P}$$.

Newton’s method:

$x_{k + 1} = x_k - \frac{f'(x_k)}{f''(x_k)}$
• If you have $$n$$ variables, then $$n^2$$ operations is needed to find $$\nabla^2 f$$ (Hessian) and $$n^3$$ operations to find the inverse of the Hessian.
$GD:\ \ \ \ x_{k + 1} = x_k - \eta \cdot I\cdot \nabla f(x_k)$
$NM:\ \ \ \ x_{k + 1} = x_k - \eta \cdot \frac{1}{\nabla^{2}f(x_k)}\cdot \nabla f(x_k)$
$QNM:\ \ \ \ x_{k + 1} = x_k - \eta \cdot H_k\cdot \nabla f(x_k)$
A good choice for $$H$$ can be the following. This is the BFGS method and $$H_k$$ holds curvature information. Key idea is to match curvature along trajectory.
$H = \begin{bmatrix} 1& 1\\ \end{bmatrix}$