10 Lectures and 42 Open Problems — Tightness of the Multireference Alignment SDP
Let , let be a fixed template, and let be fixed but unknown shifts. The observations are
where is cyclic shift by and is the noise level. For each realization, form the matrix with entries . The SDP maximizes over subject to
It is obtained by dropping the rank constraint from the corresponding nonconvex formulation. Call the SDP tight when it has an optimal solution encoding an integral shift assignment, as in the rank-constrained formulation. For fixed and shifts , the question is to characterize how
depends on ; in particular, at what noise levels, if any, does tightness hold with high probability? The shifts have no assumed prior distribution, and recovery of the noisy-data optimizer is distinct from exact recovery of the generating shifts. Multireference Alignment using Semidefinite Programming (arXiv:1308.5256)
The formulation has a global cyclic-shift ambiguity. After aligning the observations to the ground-truth shifts, so that , the paper represents the aligned integral solution by . A signal-dependent measure of separation from competing shifts is
Multireference Alignment using Semidefinite Programming (arXiv:1308.5256)
Background
Multireference alignment asks for a common template from noisy, cyclically shifted observations. Estimating the shifts is a natural intermediate task: once observations are unshifted, they can be averaged to estimate the template. Alignment also arises in structural biology, radar, crystalline simulations, and image registration. The SDP considered here adapts relaxations associated with Unique Games and cyclic-label constraint problems: lifting the shift choices produces a positive-semidefinite matrix optimization, while dropping its rank constraint makes the problem convex. Multireference Alignment using Semidefinite Programming (arXiv:1308.5256)
The tightness question is stronger than asking whether the SDP output is close to a planted integral solution. In the aligned model, the paper measures deviation by , the mass assigned away from the common-shift diagonal for the pair of observations . Small aggregate deviation gives a stability statement, but does not by itself establish that an optimum is integral. This distinction is central when interpreting the paper’s high-noise versus high-signal discussion. Multireference Alignment using Semidefinite Programming (arXiv:1308.5256)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.