PSDP Problem

Definitions¶

P S D P : min_{P \in S_{\geq}^{n}} | | F - P G | |

S P : min_{S \in S^{n}} | | F - S G | |

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} G G^{'} + G G^{'} \tilde{S} = F G^{'} + G F^{'} = Q$
When $r a n k (G) = n$ , a sufficient condition for $\tilde{S}$ to be in $S_{\geq}^{n}$ is that $Q \in S_{\geq}^{n}$ .
A sufficient condition for $\tilde{S}$ to be in $S_{\geq}^{n}$ is that $F G^{'} \in S_{\geq}^{m}$ .
$r a n k (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_{\geq}^{n}$ .
Solutions involve finite convergence towards global minimas bringing the approximate minimizer arbitrarily close to the unique global minimizer.

Approach of this paper¶

P S D P^{*} : min_{E \in R^{n \times n}} | | F - E^{'} E G | |

{\tilde{P}}_{global} = {\tilde{E}}_{local}^{'} {\tilde{E}}_{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:

G D : x_{k + 1} = x_{k} - η \cdot I \cdot \nabla f (x_{k})

N M : x_{k + 1} = x_{k} - η \cdot \frac{1}{\nabla^{2} f (x_{k})} \cdot \nabla f (x_{k})

Q N M : x_{k + 1} = x_{k} - η \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{matrix} 1 & 1 \end{matrix}]