Provable Low Rank Phase Retrieval
Provable Low Rank Phase Retrieval
复制标题
DOI：
10.1109/tit.2020.2984478
复制
发表时间：
2019-02
影响因子：
2.5
通讯作者：
Seyedehsara Nayer;Praneeth Narayanamurthy;Namrata Vaswani
中科院分区：
文献类型：
--
作者：
Seyedehsara Nayer;Praneeth Narayanamurthy;Namrata Vaswani
我们研究低秩相位检索（LRPR）问题，定义如下：从每列的不同且独立的$m$无相位（仅幅度）线性投影集恢复秩为$r$的$n \times q$矩阵${\boldsymbol {X}^{*}}$。准确地说，我们需要从 $\boldsymbol {y}_{k}:= | 恢复 ${ \boldsymbol {X}^{*}}$ \boldsymbol {A}_{k}{}' \boldsymbol {x}^{*}_{k}|, k=1,2, {\dots }, q$ 当测量矩阵 $\boldsymbol {A}_{k}$ 相互独立时。这里$\boldsymbol {y}_{k}$是一个$m$长度向量，$\boldsymbol {A}_{k}$是一个$n \times m$矩阵，$'$表示矩阵转置。问题是我们什么时候可以用 $m \ll n$ 求解 LRPR ？可靠的解决方案可以实现快速且低成本的无相动态成像，例如活体生物样本的傅立叶叠层成像。在这项工作中，我们开发了第一个可证明正确的方法来解决 LRPR 问题。我们提出的算法，低秩相位检索的交替最小化 (AltMinLowRaP)，是一种基于 AltMin 的解决方案，因此也被证明是快速的（几何收敛）。我们的保证表明，只要 $m q \ge C n r^{4} \log (1/\epsilon)$ ，矩阵 $\boldsymbol {A}_{k}$ 包含独立同分布，AltMinLowRaP 就能以很高的概率将 LRPR 求解到 $\epsilon $ 精度。标准高斯项和 ${ \boldsymbol {X}^{*}}$ 的右奇异向量满足矩阵补全文献中的不相干假设。这里 $C$ 是一个数值常数，仅取决于 ${ \boldsymbol {X}^{*}}$ 的条件数及其不相干参数。其时间复杂度仅为 $C mq nr \log ^{2}(1/\epsilon)$ 。由于即使上述问题的线性（带相位）版本也没有完全解决，因此上述结果也是线性情况的第一个完整解决方案和保证。最后，我们还为动态 LRPR 设置开发了结果的简单扩展。
We study the Low Rank Phase Retrieval (LRPR) problem defined as follows: recover an $n \times q$ matrix ${ \boldsymbol {X}^{*}}$ of rank $r$ from a different and independent set of $m$ phaseless (magnitude-only) linear projections of each of its columns. To be precise, we need to recover ${ \boldsymbol {X}^{*}}$ from $\boldsymbol {y}_{k}:= | \boldsymbol {A}_{k}{}' \boldsymbol {x}^{*}_{k}|, k=1,2, {\dots }, q$ when the measurement matrices $\boldsymbol {A}_{k}$ are mutually independent. Here $\boldsymbol {y}_{k}$ is an $m$ length vector, $\boldsymbol {A}_{k}$ is an $n \times m$ matrix, and $'$ denotes matrix transpose. The question is when can we solve LRPR with $m \ll n$ ? A reliable solution can enable fast and low-cost phaseless dynamic imaging, e.g., Fourier ptychographic imaging of live biological specimens. In this work, we develop the first provably correct approach for solving this LRPR problem. Our proposed algorithm, Alternating Minimization for Low-Rank Phase Retrieval (AltMinLowRaP), is an AltMin based solution and hence is also provably fast (converges geometrically). Our guarantee shows that AltMinLowRaP solves LRPR to $\epsilon $ accuracy, with high probability, as long as $m q \ge C n r^{4} \log (1/\epsilon)$ , the matrices $\boldsymbol {A}_{k}$ contain i.i.d. standard Gaussian entries, and the right singular vectors of ${ \boldsymbol {X}^{*}}$ satisfy the incoherence assumption from matrix completion literature. Here $C$ is a numerical constant that only depends on the condition number of ${ \boldsymbol {X}^{*}}$ and on its incoherence parameter. Its time complexity is only $C mq nr \log ^{2}(1/\epsilon)$ . Since even the linear (with phase) version of the above problem is not fully solved, the above result is also the first complete solution and guarantee for the linear case. Finally, we also develop a simple extension of our results for the dynamic LRPR setting.