Non-unique games over compact groups and orientation estimation in cryo-EM

Abstract

Let <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>𝒢</mml:mi></mml:math> be a compact group and let <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub><mml:mrow><mml:mi>f</mml:mi></mml:mrow> <mml:mrow><mml:mi>i</mml:mi> <mml:mi>j</mml:mi></mml:mrow> </mml:msub> <mml:mo>∈</mml:mo> <mml:mi>C</mml:mi> <mml:mo>(</mml:mo> <mml:mi>𝒢</mml:mi> <mml:mo>)</mml:mo></mml:math> . We define the <i>Non-Unique Games</i> (NUG) problem as finding <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub><mml:mrow><mml:mi>g</mml:mi></mml:mrow> <mml:mrow><mml:mn>1</mml:mn></mml:mrow> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:msub><mml:mrow><mml:mi>g</mml:mi></mml:mrow> <mml:mrow><mml:mi>n</mml:mi></mml:mrow> </mml:msub> <mml:mo>∈</mml:mo> <mml:mi>𝒢</mml:mi></mml:math> to minimize <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup><mml:mrow><mml:mo>∑</mml:mo></mml:mrow> <mml:mrow><mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>j</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn></mml:mrow> <mml:mrow><mml:mi>n</mml:mi></mml:mrow> </mml:msubsup> <mml:mspace></mml:mspace> <mml:msub><mml:mrow><mml:mi>f</mml:mi></mml:mrow> <mml:mrow><mml:mi>i</mml:mi> <mml:mi>j</mml:mi></mml:mrow> </mml:msub> <mml:mspace></mml:mspace> <mml:mfenced> <mml:mrow> <mml:msub><mml:mrow><mml:mi>g</mml:mi></mml:mrow> <mml:mrow><mml:mi>i</mml:mi></mml:mrow> </mml:msub> <mml:msubsup><mml:mrow><mml:mi>g</mml:mi></mml:mrow> <mml:mrow><mml:mi>j</mml:mi></mml:mrow> <mml:mrow><mml:mo>-</mml:mo> <mml:mn>1</mml:mn></mml:mrow> </mml:msubsup> </mml:mrow> </mml:mfenced> </mml:math> . We introduce a convex relaxation of the NUG problem to a <i>semidefinite program</i> (SDP) by taking the Fourier transform of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub><mml:mrow><mml:mi>f</mml:mi></mml:mrow> <mml:mrow><mml:mi>i</mml:mi> <mml:mi>j</mml:mi></mml:mrow> </mml:msub> </mml:math> over <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>𝒢</mml:mi></mml:math> . The NUG framework can be seen as a generalization of the <i>little Grothendieck</i> problem over the orthogonal group and the <i>Unique Games</i> problem and includes many practically relevant problems, such as the <i>maximum likelihood estimator</i> to registering bandlimited functions over the unit sphere in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math> -dimensions and orientation estimation of noisy cryo-Electron Microscopy (cryo-EM) projection images. We implement a SDP solver for the NUG cryo-EM problem using the alternating direction method of multipliers (ADMM). Numerical study with synthetic datasets indicate that while our ADMM solver is slower than existing methods, it can estimate the rotations more accurately, especially at low <i>signal-to-noise ratio</i> (SNR).