Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure
Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure
复制标题
DOI：
10.1109/isit.2018.8437770
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Gauri Jagatap;C. Hegde
中科院分区：
文献类型：
--
作者：
Gauri Jagatap;C. Hegde
我们考虑使用随机高斯二次样品估算结构化的高维参数矢量的问题。这个问题是对相位检索的经典问题的概括，并影响了计算成像中的许多问题。我们提供了一种基于交替最小化的通用算法，如果适当初始化，则可以实现理论上最佳样本复杂性。从本质上讲，我们表明，如果可以使用该解决方案的适当初始猜测，则求解具有结构性约束的随机二次方程系统（几乎）与求解具有相同约束的相应线性系统一样容易。作为直接的结果，我们的方法改善了相位检索的最著名的现有样品复杂性结果（结构化或其他方式）。我们通过几个数值实验来支持我们的理论。本文的完整版本可访问：https：//gaurijagatap.github.io/assets/isit18.pdf
We consider the problem of estimating a structured high-dimensional parameter vector using random Gaussian quadratic samples. This problem is a generalization of the classical problem of phase retrieval and impacts numerous problems in computational imaging. We provide a generic algorithm based on alternating minimization that, if properly initialized, achieves information-theoretically optimal sample complexity. In essence, we show that solving a system of random quadratic equations with structural constraints is (nearly) as easy as solving the corresponding linear system with the same constraints, if a proper initial guess of the solution is available. As an immediate consequence, our approach improves upon the best known existing sample complexity results for phase retrieval (structured or otherwise). We support our theory via several numerical experiments. A full version of this paper is accessible at: https://gaurijagatap.github.io/assets/ISIT18.pdf