CIF: Small: Structured High-dimensional Data Recovery from Phaseless Measurements

相位检索（PR），或“从无相位测量中恢复信号”，是一个出现在许多信号/图像采集领域的问题，例如傅里叶平面摄影和亚衍射成像，其中只能测量信号或图像的某些线性投影的幅度（强度）。虽然PR是一个经典问题，但近年来，人们对PR重新产生了兴趣，目标是开发可证明正确且快速的算法。然而，大部分工作都没有假设信号的任何结构，因此必然需要比未知信号长度更多的测量。当向非常高分辨率成像移动时，这可能是一个挑战，因为这意味着数据采集成本（在时间、传感器数量或功耗方面）相应增加。动态成像的时变场景，例如，活的生物样本，提出了更大的挑战。我们通过利用两种常见的结构假设——稀疏性和低秩——来解决这一限制，从而实现快速、低成本的高分辨率成像。参与这项研究的有研究生和本科生。本项目开发了第一套可证明正确、快速和低样本复杂度的算法，用于两种情况下的无相低秩矩阵恢复。第一种方法涉及从矩阵每列的无相线性投影中恢复。当（矢量化的）图像序列被低秩矩阵很好地近似时，例如，缓慢变化的动态场景，这种方法在无相动态成像中得到应用。第二种设置涉及从整个矩阵的无相线性投影中恢复。当图像本身可以被建模为低秩时，这很有用。该项目还开发了可证明的快速和统计高效的稀疏PR算法，并探索了学习广义线性模型的扩展。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Phase retrieval (PR), or 'signal recovery from phaseless measurements', is a problem that occurs in numerous signal/image acquisition domains, such as Fourier ptychography and sub-diffraction imaging, in which only the magnitude (intensity) of certain linear projections of the signal or image can be measured. While PR is a classical problem, in recent years there has been renewed interest in PR with the goal of developing provably correct and fast algorithms. Much of this work, however, does not assume any structure on the signal, and as a result necessarily requires more measurements than the unknown signal's length. This can be a challenge when moving to very high resolution imaging because it implies a proportionally higher cost of data acquisition (in terms of time, number of sensors, or power consumption). Dynamic imaging of time-varying scenes, e.g., live biological samples, poses an even greater challenge. We address this limitation by exploiting two common classes of structural assumptions - sparsity and low-rank -- to enable fast and low cost high-resolution imaging. A diverse group of graduate and undergraduate students is involved in the research.This project develops the first set of provably correct, fast, and low-sample-complexity algorithms for phaseless low rank matrix recovery in two settings. The first involves recovery from phaseless linear projections of each column of the matrix. This finds applications in phaseless dynamic imaging when the (vectorized) image sequence is well approximated by a low rank matrix, e.g., slow changing dynamic scenes. The second setting involves recovery from phaseless linear projections of the entire matrix. This is useful when the image itself can be modeled as being low rank. This project also develops provably fast and statistically efficient sparse PR algorithms and explores extensions to learning generalized linear models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.