揭示下降式相位恢复算法的相变现象,解释其成功与失败的临界条件。
Phase transition of \emph{descending} phase retrieval algorithms
- 基于随机对偶理论构建通用分析框架,刻画算法性能。
- 样本量增加时,参数流形从多凹陷点转为单凹陷点,对应算法成败的相变。
- 提出混合梯度下降算法,理论预测与小规模模拟高度吻合。
我们研究了下降式相位恢复算法的理论极限。利用随机对偶理论(RDT),建立了一个通用分析程序,可对多种算法性能指标进行统计表征。通过该框架,识别出参数流形及其凹陷点是控制算法行为的关键数学对象。建立了单凹陷点流形与下降算法全局收敛之间的同构关系。通过普通和提升型RDT,研究了参数流形的结构、形状及其对样本复杂度的依赖性。观察到明显的相变现象:随着样本复杂度增加,参数流形从多凹陷点结构转变为单凹陷点结构,对应算法从普遍失败转为成功求解相位恢复。我们还提出并实现了一种混合交替算法,结合障碍函数与普通梯度下降。尽管理论针对无限维情形(无抖动流形),但在维度约为数百的小规模场景下,理论与模拟的相变预测仍表现出强烈一致性。
原文摘要 · Abstract (English)
We study theoretical limits of \emph{descending} phase retrieval algorithms. Utilizing \emph{Random duality theory} (RDT) we develop a generic program that allows statistical characterization of various algorithmic performance metrics. Through these we identify the concepts of \emph{parametric manifold} and its \emph{funneling points} as key mathematical objects that govern the underlying algorithms' behavior. An isomorphism between single funneling point manifolds and global convergence of descending algorithms is established. The structure and shape of the parametric manifold as well as its dependence on the sample complexity are studied through both plain and lifted RDT. Emergence of a phase transition is observed. Namely, as sample complexity increases, parametric manifold transitions from a multi to a single funneling point structure. This in return corresponds to a transition from the scenarios where descending algorithms generically fail to the scenarios where they succeed in solving phase retrieval. We also develop and implement a practical algorithmic variant that in a hybrid alternating fashion combines a barrier and a plain gradient descent. Even though the theoretical results are obtained for infinite dimensional scenarios (and consequently non-jittery parametric manifolds), we observe a strong agrement between theoretical and simulated phase transitions predictions for fairly small dimensions on the order of a few hundreds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。