## 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)}
\]

- Has quadratic convergence.
- Can find complex zeroes.
- 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.

Quasi Newtown method:

\[
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}
\]