TY - JOUR
T1 - Solving Systems of Quadratic Equations via Exponential-Type Gradient Descent Algorithm
AU - Huang , Meng
AU - Xu , Zhiqiang
JO - Journal of Computational Mathematics
VL - 4
SP - 638
EP - 660
PY - 2020
DA - 2020/04
SN - 38
DO - http://doi.org/10.4208/jcm.1902-m2018-0109
UR - https://global-sci.org/intro/article_detail/jcm/16467.html
KW - Low-rank matrix recovery, Non-convex optimization, Phase retrieval.
AB - <p style="text-align: justify;">We consider the rank minimization problem from quadratic measurements, i.e., recovering a rank $r$ matrix $X \in \mathbb{R}^{n×r}$ from $m$ scalar measurements $y_i=a_i^T XX^T a_i,\;a_i\in \mathbb{R}^n,\;i=1,\ldots,m$. Such problem arises in a variety of applications such as quadratic regression and quantum state tomography. We present a novel algorithm, which is termed $exponential-type$ $gradient$ $descent$ $algorithm$, to minimize a non-convex objective function $f(U)=\frac{1}{4m}\sum_{i=1}^m(y_i-a_i^T UU^T a_i)^2$. This&nbsp; algorithm&nbsp; starts with a careful initialization, and then refines this initial guess by iteratively applying exponential-type gradient descent. Particularly,&nbsp; we can obtain a good initial guess of $X$ as long as the number of Gaussian random measurements is&nbsp; $O(nr)$, and&nbsp; our iteration algorithm can converge linearly to the true $X$ (up to an orthogonal matrix) with $m=O\left(nr\log (cr)\right)$ Gaussian random measurements.</p>