← All problems

10 Lectures and 42 Open Problems — Tightness of the Multireference Alignment SDP

Let N,L≥1N,L\geq 1, let x∈RLx\in\mathbb{R}^L be a fixed template, and let ℓ1,…,ℓN∈ZL\ell_1,\ldots,\ell_N\in\mathbb{Z}_L be fixed but unknown shifts. The observations are

yi=Rℓix+ξi,ξi∼i.i.d.N(0,σ2IL),i=1,…,N,y_i=R_{\ell_i}x+\xi_i,\qquad \xi_i\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\sigma^2 I_L),\quad i=1,\ldots,N,

where RℓR_\ell is cyclic shift by ℓ\ell and σ\sigma is the noise level. For each realization, form the matrix C∈RNL×NLC\in\mathbb{R}^{NL\times NL} with entries Cik;jm=⟨R−kyi,R−myj⟩C_{ik;jm}=\langle R_{-k}y_i,R_{-m}y_j\rangle. The SDP maximizes tr⁡(CV)\operatorname{tr}(CV) over V∈RNL×NLV\in\mathbb{R}^{NL\times NL} subject to

∑k,m∈ZLVik;jm=1(i,j=1,…,N),Vik;im=0(k≠m),Vik;jm≥0(k≠m),V⪰0.\sum_{k,m\in\mathbb{Z}_L}V_{ik;jm}=1\quad(i,j=1,\ldots,N),\qquad V_{ik;im}=0\quad(k\ne m),\qquad V_{ik;jm}\geq 0\quad(k\ne m),\qquad V\succeq 0.

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 N,L,xN,L,x and shifts ℓi\ell_i, the question is to characterize how

Pξ{the SDP is tight\mathbb{P}_{\xi}\{\text{the SDP is tight}

depends on σ\sigma; 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 yi=x+ξiy_i=x+\xi_i, the paper represents the aligned integral solution by Vik;jmint=δk=m/LV^{\mathrm{int}}_{ik;jm}=\delta_{k=m}/L. A signal-dependent measure of separation from competing shifts is

Δ=∥x∥2−max⁡ℓ≠0⟨x,Rℓx⟩.\Delta=\|x\|^2-\max_{\ell\ne 0}\langle x,R_\ell x\rangle.

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 Dij=1−∑k∈ZLVik;jkD_{ij}=1-\sum_{k\in\mathbb{Z}_L}V_{ik;jk}, the mass assigned away from the common-shift diagonal for the pair of observations i,ji,j. 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)

References

Progress summary

Never refreshed

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.