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