论文标题
连续的时间镜下降方法稀疏相检索
A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval
论文作者
论文摘要
我们分析了应用于稀疏相检索的连续时间镜下降，这是从一组仅幅度测量值中恢复稀疏信号的问题。我们使用正方形损失和方形测量值将镜下下降应用于无约束的经验风险最小化问题（批处理设置）。我们在此非凸面设置中对算法进行了融合分析，并证明，镜像下降将恢复任何$ k $ -sparse vector $ \ mathbf {x}}^\ star \ in \ mathbb {r} \ Mathbf {x}^\ star \ | _2/\ sqrt {k} $从$ k^2 $ Gaussian测量，Modulo Googarithmic项。这产生了一种简单的算法，该算法与大多数现有的稀疏相检索方法不同，可以适应稀疏水平，而无需包括阈值步骤或添加正则化项。我们的结果还为Hadamard Wirewtinger流量提供了原则上的理论理解[58]，因为可以将Hadamard参数化应用于经验风险问题的欧几里得梯度下降可以作为在离散时间内的镜像下降的一阶近似。
We analyze continuous-time mirror descent applied to sparse phase retrieval, which is the problem of recovering sparse signals from a set of magnitude-only measurements. We apply mirror descent to the unconstrained empirical risk minimization problem (batch setting), using the square loss and square measurements. We provide a convergence analysis of the algorithm in this non-convex setting and prove that, with the hypentropy mirror map, mirror descent recovers any $k$-sparse vector $\mathbf{x}^\star\in\mathbb{R}^n$ with minimum (in modulus) non-zero entry on the order of $\| \mathbf{x}^\star \|_2/\sqrt{k}$ from $k^2$ Gaussian measurements, modulo logarithmic terms. This yields a simple algorithm which, unlike most existing approaches to sparse phase retrieval, adapts to the sparsity level, without including thresholding steps or adding regularization terms. Our results also provide a principled theoretical understanding for Hadamard Wirtinger flow [58], as Euclidean gradient descent applied to the empirical risk problem with Hadamard parametrization can be recovered as a first-order approximation to mirror descent in discrete time.
