检索结果-内蒙古大学图书馆

Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

MATHEMATICAL PROGRAMMING 2017年第1-2期163卷 145-167页

作者： Bandeira, Afonso S. Boumal, Nicolas Singer, Amit NYU New York NY USA Princeton Univ Princeton NJ 08544 USA

Maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using convex relaxations. In some cases, the relaxation is tight: it recovers the true MLE. Most tightness proofs only apply to situations where the MLE exactly recovers a planted solution (known to the analyst). It is then sufficient to establish that the optimality conditions hold at the planted signal. In this paper, we study an estimation problem (angular synchronization) for which the MLE is not a simple function of the planted solution, yet for which the convex relaxation is tight. To establish tightness in this context, the proof is less direct because the point at which to verify optimality conditions is not known explicitly. angular synchronization consists in estimating a collection of n phases, given noisy measurements of the pairwise relative phases. The MLE for angular synchronization is the solution of a (hard) non-bipartite Grothendieck problem over the complex numbers. We consider a stochastic model for the data: a planted signal (that is, a ground truth set of phases) is corrupted with non-adversarial random noise. Even though the MLE does not coincide with the planted signal, we show that the classical semidefinite relaxation for it is tight, with high probability. This holds even for high levels of noise.

关键词： angular synchronization Semidefinite programming Tightness of convex relaxation Maximum likelihood estimation

来源：评论

学校读者我要写书评

暂无评论

Phase retrieval from local measurements: Improved robustness via eigenvector-based angular synchronization

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2020年第1期48卷 415-444页

作者： Iwen, Mark A. Preskitt, Brian Saab, Rayan Viswanathan, Aditya Michigan State Univ Dept Math E Lansing MI 48824 USA Michigan State Univ Dept Computat Math Sci & Engn CMSE E Lansing MI 48824 USA Univ Calif San Diego Dept Math La Jolla CA 92093 USA Univ Michigan Dept Math & Stat Dearborn MI 48128 USA

We improve a phase retrieval approach that uses correlation-based measurements with compactly supported measurement masks [30]. Our approach admits deterministic measurement constructions together with a robust, fast recovery algorithm that consists of solving a system of linear equations in a lifted space, followed by finding an eigenvector (e.g., via an inverse power iteration). Theoretical reconstruction error guarantees from [30] are improved as a result for the new and more robust reconstruction approach proposed herein. Numerical experiments demonstrate robustness and computational efficiency that compete with other approaches on large problems. Along the way, we show that this approach also trivially extends to phase retrieval problems based on windowed Fourier measurements. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Phase retrieval Ptychography Signal recovery angular synchronization

来源：评论

学校读者我要写书评

暂无评论

Inverting spectrogram measurements via aliased Wigner distribution deconvolution and angular synchronization

引用

INFORMATION AND INFERENCE-A JOURNAL OF THE IMA 2021年第4期10卷 1491-1531页

作者： Perlmutter, Michael Merhi, Sami Viswanathan, Aditya Iwen, Mark Michigan State Univ Dept Computat Math Sci & Engn CMSE E Lansing MI 48824 USA Michigan State Univ Dept Math E Lansing MI 48824 USA Univ Michigan Dept Math Dearborn MI 48128 USA Michigan State Univ Dept Computat Math Sci & Engn CMSE Dept Math E Lansing MI 48824 USA

We propose a two-step approach for reconstructing a signal x is an element of C-d from subsampled discrete short-time Fourier transform magnitude (spectogram) measurements: first, we use an aliased Wigner distribution deconvolution approach to solve for a portion of the rank-one matrix (x) over cap(x) over cap*. Secondly, we use angular synchronization to solve for (x) over cap (and then for x by Fourier inversion). Using this method, we produce two new efficient phase retrieval algorithms that perform well numerically in comparison to standard approaches and also prove two theorems;one which guarantees the recovery of discrete, bandlimited signals x is an element of C-d from fewer than d short-time Fourier transform magnitude measurements and another which establishes a new class of deterministic coded diffraction pattern measurements which are guaranteed to allow efficient and noise robust recovery.

关键词： phase retrieval spectrogram measurements short-time Fourier transform (STFT) Wigner distribution deconvolution angular synchronization ptychography

来源：评论

学校读者我要写书评

暂无评论

On Recovery Guarantees for angular synchronization

引用

JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS 2021年第2期27卷 1-26页

作者： Filbir, Frank Krahmer, Felix Melnyk, Oleh Helmholtz Ctr Munich Informat & Commun Technol Dept Math Imaging & Data Anal D-85764 Neuherberg Germany Tech Univ Munich Dept Math D-85748 Garching Germany

The angular synchronization problem of estimating a set of unknown angles from their known noisy pairwise differences arises in various applications. It can be reformulated as an optimization problem on graphs involving the graph Laplacian matrix. We consider a general, weighted version of this problem, where the impact of the noise differs between different pairs of entries and some of the differences are erased completely;this version arises for example in ptychography. We study two common approaches for solving this problem, namely eigenvector relaxation and semidefinite convex relaxation. Although some recovery guarantees are available for both methods, their performance is either unsatisfying or restricted to the unweighted graphs. We close this gap, deriving recovery guarantees for the weighted problem that are completely analogous to the unweighted version.

关键词： angular synchronization Graph Laplacian Ptychography Eigenvector relaxation Semidefinite programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Fast angular synchronization for Phase Retrieval via Incomplete Information 16

Fast Angular Synchronization for Phase Retrieval via Incompl...

引用

Conference on Wavelets and Sparsity XVI

作者： Viswanathan, Aditya Iwen, Mark Michigan State Univ Dept Math E Lansing MI 48824 USA Michigan State Univ Dept Elect & Comp Engn E Lansing MI 48824 USA

ISBN: (纸本)9781628417630

We consider the problem of recovering the phase of an unknown vector, x is an element of C-d, given (normalized) phase difference measurements of the form x(j),x*(k)/vertical bar x(j)x(k)vertical bar, and where j,k is an element of {1, . . . . d} denotes x(j)* the complex conjugate of x(j). This problem is sometimes referred to as the angular synchronization problem. This paper analyzes a linear-time-in-d eigenvector-based angular synchronization algorithm and studies its theoretical and numerical performance when applied to a particular class of highly incomplete and possibly noisy phase difference measurements. Theoretical results are provided for perfect (noiseless) measurements, while numerical simulations demonstrate the robustness of the method to measurement noise. Finally, we show that this angular synchronization problem and the specific form of incomplete phase difference measurements considered arise in the phase retrieval problem where we recover an unknown complex vector from phaseless (or magnitude) measurements.

关键词： angular synchronization eigen analysis phase retrieval

来源：评论

学校读者我要写书评

暂无评论

Exact Minimax Estimation for Phase synchronization

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第12期67卷 8236-8247页

作者： Gao, Chao Zhang, Anderson Y. Univ Chicago Dept Stat Chicago IL 60637 USA Univ Penn Dept Stat & Data Sci Philadelphia PA 19104 USA

study the phase synchronization problem with measurements Y = z* z*(H) + sigma W is an element of C-nxn, where z* is an n-dimensional complex unit-modulus vector and W is a complexvalued Gaussian random matrix. It is assumed that each entry Y-jk is observed with probability p. We prove that the minimax lower bound of estimating z* under the squared l(2) loss is (1-o(1)) sigma(2)/2p. We also show that both generalized power method and maximum likelihood estimator achieve the error bound (1+o(1)) sigma(2)/2p. Thus, sigma(2)/2p is the exact asymptotic minimax error of the problem. Our upper bound analysis involves a precise characterization of the statistical property of the power iteration. The lower bound is derived through an application of van Trees' inequality.

关键词： angular synchronization minimax risk power method maximum likelihood estimator

来源：评论

学校读者我要写书评

暂无评论

SDP Achieves Exact Minimax Optimality in Phase synchronization

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第8期68卷 5374-5390页

作者： Gao, Chao Zhang, Anderson Y. Univ Chicago Dept Stat Chicago IL 60637 USA Univ Penn Dept Stat & Data Sci Philadelphia PA 19104 USA

We study the phase synchronization problem witnoisy measurements Y = z* z*(H) + sigma W is an element of C-nXn, where z* is an n-dimensional complex unit-modulus vector and W is a complex-valued Gaussian random matrix. It is assumed that each entry Y-jk is observed with probability p. We prove that an SDP relaxation of the MLE achieves the error bound (1+ o(1)) sigma(2)/2np under a normalized squared l(2) loss. This result matches the minimax lower bound of the problem, and even the leading constant is sharp. The analysis of the SDP is based on an equivalent non-convex programming whose solution can be characterized as a fixed point of the generalized power iteration lifted to a higher dimensional space. This viewpoint unifies the proofs of the statistical optimality of three different methods: MLE, SDP, and generalized power method. The technique is also applied to the analysis of the SDP for Z(2) synchronization, and we achieve the minimax optimal error exp (-(1 - o(1)) np/2 sigma(2)) with a sharp constant in the exponent.

关键词： angular synchronization minimax risk SDP Z(2) synchronization Burer-Monteiro factorization

来源：评论

学校读者我要写书评

暂无评论

NEAR-OPTIMAL BOUNDS FOR PHASE synchronization

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第2期28卷 989-1016页

作者： Zhong, Yiqiao Boumal, Nicolas Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA Princeton Univ Dept Math Princeton NJ 08544 USA Princeton Univ Program Appl & Computat Math Princeton NJ 08544 USA

The problem of estimating the phases (angles) of a complex unit-modulus vector z from their noisy pairwise relative measurements C = zz* + sigma W, where W is a complex-valued Gaussian random matrix, is known as phase synchronization. The maximum likelihood estimator (MLE) is a solution to a unit{modulus-constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite programming (SDP) relaxation or the generalized power method (GPM). Numerical experiments suggest that both of these methods succeed with high probability for sigma up to <(O)overtilde>(n(1/2)), yet existing analyses only confirm this observation for sigma up to <(O)overtilde>(n(1/2)). In this paper, we bridge the gap by proving that the SDP relaxation is tight for sigma = O(root n/log n), and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter l(infinity) bound for the MLE. A novel technique we develop in this paper is to (theoretically) track n closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an l(infinity) perturbation bound for leading eigenvectors. Our result also confirms predictions that use techniques from statistical mechanics.

关键词： angular synchronization nonconvex optimization semidefinite programming relaxation projected power method quadratically constrained quadratic program maximum likelihood estimator eigenvector perturbation bound

来源：评论

学校读者我要写书评

暂无评论

NONCONVEX PHASE synchronization

引用

SIAM JOURNAL ON OPTIMIZATION 2016年第4期26卷 2355-2377页

作者： Boumal, Nicolas Princeton Univ Dept Math Princeton NJ 08544 USA

We estimate n phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.

关键词： angular synchronization nonconvex optimization generalized power method projected power method sufficient optimality conditions quadratically constrained quadratic programming optimization on manifolds

来源：评论

学校读者我要写书评

暂无评论

Ranking and synchronization from pairwise measurements via SVD

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2021年第1期22卷 1-63页

作者： d'Aspremont, Alexandre Cucuringu, Mihai Tyagi, Hemant CNRS Paris France Ecole Normale Super Paris France Univ Oxford Dept Stat Alan Turing Inst London England Univ Oxford Math Inst Alan Turing Inst London England Univ Lille INRIA CNRS UMR 8524Lab Paul Painleve F-59000 Lille France

Given a measurement graph G = (V, E) and an unknown signal r is an element of R-n, we investigate algorithms for recovering r from pairwise measurements of the form r(i) - r(j);{i, j} is an element of E. This problem arises in a variety of applications, such as ranking teams in sports data and time synchronization of distributed networks. Framed in the context of ranking, the task is to recover the ranking of n teams (induced by r) given a small subset of noisy pairwise rank offsets. We propose a simple SVD-based algorithmic pipeline for both the problem of time synchronization and ranking. We provide a detailed theoretical analysis in terms of robustness against both sampling sparsity and noise perturbations with outliers, using results from matrix perturbation and random matrix theory. Our theoretical findings are complemented by a detailed set of numerical experiments on both synthetic and real data, showcasing the competitiveness of our proposed algorithms with other state-of-the-art methods.

关键词： ranking angular synchronization spectral algorithms matrix perturbation theory singular value decomposition random matrix theory low-rank matrix completion

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：