text:
\newcommand{\matIdColor}[1]{\red{#1}}
\section{Explanation and Example for Theorem~\ref{thm:denseMoment} (Dense Moment Relaxation)}
\label{sec:supp-proof-denseRelaxation}
In this section, we provide a brief but self-contained explanation to shed light on Lasserre's hierarchy of dense moment relaxations in Theorem~\ref{thm:denseMoment} (Section~\ref{sec:explanation}). We also give an accessible example to demonstrate the application of the hierarchy to a simple but illustrative problem, namely 2D single rotation averaging (Section~\ref{sec:2DSRA}).

\subsection{Explanation}
\label{sec:explanation}
Our explanation of Lasserre's hierarchy is adapted from~\cite{lasserre10book-momentsOpt,Lasserre01siopt-LasserreHierarchy}. Let $\mu\parentheses{\xextend}$ be a probability measure supported on the feasible set $\calxextend$ of the POP~\eqref{eq:pop}, and let $\probin{\calxextend}$ be the set of all possible probability measures on $\calxextend$. Then the POP~\eqref{eq:pop} can be rewritten as a generalized moment problem.
\begin{theorem}[\bf POP as the Moment Problem~{\cite[Proposition 2.1]{Lasserre01siopt-LasserreHierarchy}}]
\label{thm:popMoment}
Let the feasible set of the POP~\eqref{eq:pop} be $\calxextend$, then the POP is equivalent to the following optimization:
\bea \label{eq:momentProblem}
f^\star_\mu = \min_{\mu \in \probin{\calxextend}} \int f(\xextend) d\mu,
\eea
in the sense that:
\begin{enumerate}[label=(\roman*)]
\item $f^\star_\mu = f^\star$;
\item if $\xextend^\star$ is a (potentially not unique) global minimizer of the POP~\eqref{eq:pop}, then $\mu^\star = \delta_{\xextend^\star}$ is a global minimizer of the moment problem~\eqref{eq:momentProblem}, where $\delta_{\xextend^\star}$ is the Dirac measure at $\xextend^\star$;
\item assuming the POP~\eqref{eq:pop} has a (potentially not unique) global minimizer with global minimum $f^\star$, then for every optimal solution $\mu^\star$ of the moment problem~\eqref{eq:momentProblem}, $f(\xextend) = f^\star$, $\mu^\star$-almost everywhere (\ie~$\mu^\star\parentheses{\cbrace{\xextend: f(\xextend) \neq f^\star}} = 0$ and $\mu^\star$ is supported only on the global minimizers of the POP);
\item if $\xextend^\star$ is the unique global minimizer of the POP~\eqref{eq:pop}, then $\mu^\star = \delta_{\xextend^\star}$ is the unique global minimizer of the moment problem~\eqref{eq:momentProblem}.
\end{enumerate}
\end{theorem}
Although the moment problem~\eqref{eq:momentProblem} is convex~\cite{lasserre10book-momentsOpt}, it is infinite-dimensional and still intractable. Therefore, the crux of making the optimization tractable is to relax the infinite-dimensional problem into a finite-dimensional one. Towards this goal, we introduce the notion of moments, moment matrices and localizing matrices.
\begin{definition}[\bf Moments, Moment Matrices, Localizing Matrices~{\cite[Chapter 3]{lasserre10book-momentsOpt}}]
\label{def:moments}
Given a probability measure $\mu$ supported on $\calxextend \subset \Real{\dimxextend}$, its moment of order $\valpha \in \nnint^\dimxextend$ is the scalar $\moment_{\valpha} \doteq \int_\calxextend \xextend^\valpha d\mu = \expect{\mu}{\xextend^\valpha} \in \Real{}$,~\ie~the integral (expected value) of the monomial $\xextend^\valpha$ over the set $\calxextend$~\wrt~$\mu$. In particular, if $\valpha = \zero$, then $\xextend^\valpha = p_1^{\alpha_1}\cdots p_{\dimxextend}^{\alpha_\dimxextend} = 1$, and $\moment_\zero = 1$. Now let $\moments = (\moment_\valpha)$ be an infinite sequence of moments (the order $\valpha$ can be unbounded), we define the linear functional $L_\moments: \polyringin{\xextend} \rightarrow \Real{}$:
\bea
f(\xextend) = \sum_{\valpha \in \calF} c(\valpha) \xextend^\valpha \mapstochar\rightarrow L_\moments(f) = \sum_{\valpha \in \calF} c(\valpha) \moment_\valpha,
\eea
that maps a polynomial $f$ to a real number $L_\moments(f)$ by replacing the monomials of $f$ with corresponding moments. With this linear functional, the moment sequence of degree up to $2\rorder$ is simply:
\bea
\moments_{2\rorder} \doteq L_\moments \parentheses{\monoleq{\xextend}{2\rorder}} \in \Real{\dimbasis{\dimxextend}{2\rorder}},\label{eq:defMoment}
\eea
where the linear functional $L_\moments$ applies component-wise to the vector of monomials $\monoleq{\xextend}{2\rorder}$, and the \emph{moment matrix} of degree $\rorder$ is:
\bea
\MM_{\rorder}(\moments_{2\rorder}) \doteq L_\moments \parentheses{\monoleq{\xextend}{\rorder}\monoleq{\xextend}{\rorder}\tran} \in \sym^{\dimbasis{\dimxextend}{\rorder}},
\eea
where $L_\moments$ also applies component-wise to the monomial matrix $\monoleq{\xextend}{\rorder}\monoleq{\xextend}{\rorder}\tran$, and $\MM_{\rorder}(\moments_{2\rorder})$ essentially assembles the vector of moments $\moments_{2\rorder}$ into a symmetric matrix. Finally, given a polynomial $h \in \polyringin{\xextend}$, we definite the \emph{localizing matrix} of order $\rorder$ with respect to $\moments$ and $h$ to be:
\bea
\MM_\rorder\parentheses{h \moments_{2\rorder}} \doteq L_\moments \parentheses{h \cdot \parentheses{\monoleq{\xextend}{\rorder}\monoleq{\xextend}{\rorder}\tran} } \in \sym^{\dimbasis{\dimxextend}{\rorder}},
\eea
where $L_\moments$ applies component-wise, and $h \cdot \parentheses{\monoleq{\xextend}{\rorder}\monoleq{\xextend}{\rorder}\tran}$ means multiplying $h$ with each entry of the monomial matrix $\monoleq{\xextend}{\rorder}\monoleq{\xextend}{\rorder}\tran$.
\end{definition}
With this definition, we can see that the cost function of the moment problem~\eqref{eq:momentProblem} is a linear function of the moments:
\bea
\int f(\xextend) d\mu = \int \sum_{\valpha \in \calF} c(\valpha) \xextend^\valpha d\mu = \sum_{\valpha \in \calF} c(\valpha) \int \xextend^\valpha d\mu = \sum_{\alpha \in \calF} c(\valpha) \moment_\valpha.
\eea
Therefore, instead of finding the probability measure $\mu$ directly in the infinite-dimensional space $\probin{\calxextend}$ as written in eq.~\eqref{eq:momentProblem}, we can equivalently search for the sequence of (possibly finite number of) moments $\moments$ and then recover the measure $\mu$ from the moments $\moments$. However, not every sequence of moments has a representing measure. In fact, in order to have a representing measure, the moment sequence has to satisfy the following conditions.

\begin{theorem}[\bf Necessary and Sufficient Condition for Representing Measure{~\cite[Theorem 3.8(b), p.~63]{lasserre10book-momentsOpt}}] Let $\moments = (\moment_\valpha)$ be a given infinite sequence of moments, and let $\calxextend$ be an Archimedean constraint set defined by the polynomial equality and inequality constraints in the POP~\eqref{eq:pop}. Then, the sequence $\moments$ has a representing measuring on $\calxextend$ if and only if:
\bea
\forall \rorder \in \mathbb{N}: \ \MM_{\rorder}(\moments_{2\rorder}) \succeq 0; \ \MM_{\rorder}(h\moments_{2\rorder}) = \zero, \forall h \in \vh; \ \MM_{\rorder}(g\moments_{2\rorder}) \succeq 0, \forall g \in \vg. \label{eq:representMeasure}
\eea
\end{theorem}
Enforcing the PSD constraints in~\eqref{eq:representMeasure} for every $\rorder \in \natural$ (potentially unbounded) is intractable due to the infinite moment sequence $\moments$. Therefore, a natural strategy is to enforce the constraints for a fix order $\rorder$ (called the relaxation order), which is precisely the optimization~\eqref{eq:denseMoment} in Theorem~\ref{thm:denseMoment}.\footnote{Because the constraint polynomials $\vh$ and $\vg$ have degree 2, the localizing matrices of order $\rorder-1$ is used to make sure every moment appearing in the localizing matrices also appears in the moment matrix $\MM_\rorder(\moments_{2\rorder})$. In a more general setting where the constraint polynomials $h_i$ (or $g_i$) have degree $2v_i$ or $2v_i-1$, then the localizing matrices of degree $\rorder - v_i$ should be used. } Problem~\eqref{eq:denseMoment} is a \emph{relaxation} of the moment problem~\eqref{eq:momentProblem} because the constraints at a fixed $\rorder$ only provide a \emph{necessary} condition for the existence of a representing measure, which in turn implies that the global minimum of the relaxation, $p^\star_\rorder$, is a \emph{lower bound} of the global minimum of the moment problem~\eqref{eq:momentProblem} (and thus the POP~\eqref{eq:pop}):
\bea
p^\star_\rorder \leq f^\star_\mu = f^\star. \label{eq:lowerBoundfixedK}
\eea
Lasserre's hierarchy is a hierarchy of moment relaxations with increasing relaxation orders $\rorder_1 < \rorder_2 < \dots$ (and increasing lower bounds $p^\star_{\rorder_1} \leq p^\star_{\rorder_2} < \dots$ ) until the relaxation is tight (\ie~$p^\star_{\rorder} = f^\star_\mu$). In general, Lasserre's hierarchy may achieve tightness only \emph{asymptotically} (\ie~$p^\star_{\rorder} \rightarrow f^\star_\mu$ as $\rorder \rightarrow \infty$). However, when the feasible set $\calxextend$ is Archimedean, Nie~\cite{Nie14mp-finiteConvergenceLassere} showed that the hierarchy terminates at a finite relaxation order, which is the case for our POP~\eqref{eq:pop} arising from a broad class of \perception problems (\cf claim~\ref{prop:pop-archimedean} in Proposition~\ref{prop:pop}).

Now a natural question is, how can one determine when the relaxation is tight (and terminate the hierarchy) without knowing the true global minimum $f^\star$? In other words, how to compute an \emph{optimality certificate}, and possibly recover the global minimizers of the POP~\eqref{eq:pop} from the solution of the moment relaxation~\eqref{eq:denseMoment}? Both questions boil down to checking if the solution of the moment relaxation, $\moments^\star_{2\rorder}$, has a representing measure on $\calxextend$, which is known as the \emph{truncated $\mathbb{K}$-moment problem}~\cite{Curto00TAMS-truncatedKmoment}. The following theorem states a sufficient condition.
\begin{theorem}[\bf Sufficient Condition for Truncated $\mathbb{K}$-Moment Problem~{\cite[Theorem 3.11, p.~66]{lasserre10book-momentsOpt}}] \label{thm:sufficientTruncatedK}
Let $\calxextend$ be the feasible set of the POP~\eqref{eq:pop}, where both $h_j$ and $g_k$ are quadratic polynomials. Let $\moments^\star_{2\rorder}$ be the solution of the moment relaxation~\eqref{eq:denseMoment}. Then $\moments^\star_{2\rorder}$ admits an $r$-atomic representing measure supported on $\calxextend$, with $r = \rank{\MM_{\rorder-1}\parentheses{\moments^\star_{2\rorder-2}}}$, if:
\bea
\rank{\MM_{\rorder-1}\parentheses{\moments^\star_{2\rorder-2}}} = \rank{\MM_{\rorder}\parentheses{\moments^\star_{2\rorder}}}.\label{eq:sufficientKMoment}
\eea
\end{theorem}
Theorem~\ref{thm:sufficientTruncatedK} is a special case of Theorem 3.11 in~\cite{lasserre10book-momentsOpt}, where we have used the fact that $\calxextend$ are defined by quadratic polynomials.\footnote{In the general case, suppose $\calxextend$ are defined by polynomials with degree $2v_i$ or $2v_i-1, i=1,\dots,\nrEq+\nrIneq$, then denote $v = \max_{i} v_i$, the sufficient condition becomes $\rank{\MM_{\rorder-v}\parentheses{\moments_{2\rorder-2v}}} = \rank{\MM_{\rorder}\parentheses{\moments_{2\rorder}}}$.} In particular, for the POP arising from \perception problems, at the minimum relaxation order $\rorder =2 $, we usually have $\rank{\MM_\rorder\parentheses{\moments^\star_{2\rorder}}} = 1$, which immediately implies that $r = \rank{\MM_{\rorder-1}\parentheses{\moments^\star_{2\rorder-2}}}=\rank{\MM_\rorder\parentheses{\moments^\star_{2\rorder}}} = 1$ (because $\MM_{\rorder-1}\parentheses{\moments^\star_{2\rorder-2}}$ is a nonzero principal sub-matrix of $\MM_\rorder\parentheses{\moments^\star_{2\rorder}}$), and $\moments^\star_{2\rorder}$ admits a $1$-atomic representing measure $\mu = \delta_{\xextend^\star}$. Therefore, from Theorem~\ref{thm:popMoment}, we have $\xextend^\star$ is the unique global minimizer of the POP~\eqref{eq:pop}.\footnote{The uniqueness of the solution comes from the fact that Interior Point Methods solvers (\eg~SeDuMi) output an optimal solution of \emph{maximum rank} if the SDP has more than one optimal solutions~\cite{Wolkowicz12book-handbookSDP}. Therefore, if $\xextend^\star$ is not unique, then the SDP will have multiple optimal solutions and the rank of the solution will be larger than 1 (\cf Theorem 6.18 in~\cite{Laurent09eaag-SOSMomentOptimization}).} Additionally, for $\mu = \delta_{\xextend^\star}$, it is straightforward to verify that $\moments^\star_{2\rorder} = \monoleq{\xextend^\star}{2\rorder}$ from eq.~\eqref{eq:defMoment}, and $\xextend^\star$ can be directly read off from the moments.

{\bf Rounding and Relative Duality Gap}. When the sufficient condition eq.~\eqref{eq:sufficientKMoment} does not hold and the moment matrix $\MM_\rorder\parentheses{\moments^\star_{2\rorder}}$ has rank larger than 1, we can first perform spectral decomposition on $\MM_\rorder\parentheses{\moments^\star_{2\rorder}}$, and extract its eigenvector corresponding to the largest eigenvalue, denoted as $\vv_\rorder \in \Real{\dimbasis{\dimxextend}{\rorder}}$. Then we normalize $\vv_\rorder$'s first entry, $\vv_\rorder(1)$, to be 1 by: $\vv_\rorder \leftarrow \frac{\vv_\rorder}{\vv_\rorder(1)}$. If the relaxation were tight, then $\vv_\rorder = \monoleq{\xextend^\star}{\rorder}$ is a vector of moments up to degree $\rorder$ and $\xextend^\star$ can be directly read off from $\vv_\rorder$. However, since the relaxation is not tight, we obtain a feasible point $\hatxextend$ by:
\bea
\hatxextend = \proj_{\calxextend}\parentheses{\vv_\rorder\parentheses{\xextend}}, \label{eq:projection}
\eea
where $\vv_\rorder\parentheses{\xextend}$ denotes the entries of $\vv_\rorder$ at indices corresponding to the locations of $\xextend$ in $\monoleq{\xextend}{\rorder}$, and $\proj_{\calxextend}$ performs the projection onto the feasible set $\calxextend$ (see Section~\ref{sec:projectionP} for details). Let $\hatf = f(\hatxextend)$, we have the following inequality:
\bea
p^\star_\rorder \leq f^\star \leq \hatf,
\eea
where the first inequality follows from eq.~\eqref{eq:lowerBoundfixedK}, and the second inequality holds because $f^\star$ is the global minimum of the POP~\eqref{eq:pop}. The relative duality gap can be computed as:
\bea
\eta_\rorder = \frac{\hatf - p^\star_\rorder}{\hatf}. \label{eq:relDualityGapDense}
\eea
A smaller $\eta_\rorder$ implies a tighter relaxation and $\eta_\rorder = 0$ if and only if the relaxation is tight.

\subsection{Example: 2D Single Rotation Averaging}
\label{sec:2DSRA}
To make our explanation of Lasserre's hierarchy in Section~\ref{sec:explanation} more accessible, we show an application of the hierarchy to 2D single rotation averaging, because the dimension of $\vxx$ is small and the constraint set $\calX$ is simple to characterize. 2D single rotation averaging follows the definition of 3D single rotation averaging in Example~\ref{eg:singleRotationAveraging}, except that the measurements $\MR_i,i=1,\dots,N$ and the unknown geometric model $\MR$ are 2D rotation matrices,~\ie~$\MR \in \SOtwo$. In this case, we describe a 2D rotation matrix using:
\bea
\MR \in \SOtwo \Longleftrightarrow \MR = \bmat{cc} x_1 & -x_2 \\ x_2 &  x_1 \emat, \quad \subject \quad h^x = 1-x_1^2 - x_2^2 = 0.
\eea
We then choose $N=2$, leading to two binary variables $\theta_1$ and $\theta_2$. Denote $\vxx = [x_1,x_2]\tran$, $\vtheta = [\theta_1,\theta_2]\tran$, and $\xextend = [\vxx\tran,\vtheta\tran]\tran$, the POP~\eqref{eq:pop} for 2D single rotation averaging with $N=2$ is:
\bea
\min_{\xextend = [x_1,x_2,\theta_1,\theta_2]\tran \in \Real{4}} & f(\xextend) \\
\subject & h^x = 1-x_1^2 - x_2^2 = 0, \label{eq:2DSRAhx} \\
  & h^{\theta_1} = 1 - \theta_1^2 = 0, \label{eq:2DSRAhtheta1} \\
  & h^{\theta_2} = 1 - \theta_2^2 = 0, \label{eq:2DSRAhtheta2}
\eea
where the objective function can be computed from eq.~\eqref{eq:TLSBinary}.

{\bf Moment matrices}. To describe the dense moment relaxation~\eqref{eq:denseMoment} at $\rorder = 2$, we first form the moment matrices $\MM_1\parentheses{\moments_2}$ and $\MM_2\parentheses{\moments_4}$. Towards this goal, let us write the vector of monomials $\monoleq{\xextend}{1}$ and $\monoleq{\xextend}{2}$:
\bea
& \monoleq{\xextend}{1} = [1,x_1,x_2,\theta_1,\theta_2]\tran \in \Real{5}, \label{eq:vecMono1} \\
& \monoleq{\xextend}{2} = [1,x_1,x_2,\theta_1,\theta_2,x_1^2,x_1 x_2, x_1 \theta_1,x_1 \theta_2,x_2^2,x_2 \theta_1,x_2\theta_2, \theta_1^2, \theta_1 \theta_2, \theta_2^2]\tran \in \Real{15}. \label{eq:vecMono2}
\eea
For notation simplicity, we use $\moment_{\xextend^\valpha}$, instead of $\moment_{\valpha}$, to denote the moment of order $\valpha$. For example, $\moment_{x_1 x_2} \doteq \int_{\calxextend} x_1x_2 d\mu$ for some probability measure $\mu$ supported on $\calxextend$. Then the vector of moments $\moments_1$ and $\moments_2$ directly follow from the vector of monomials in eq.~\eqref{eq:vecMono1} and~\eqref{eq:vecMono2}:
\bea
& \moments_1 = \bracket{\moment_1,\moment_{x_1},\moment_{x_2},\moment_{\theta_1},\moment_{\theta_2}}\tran \in \Real{5}, \\
& \hspace{-10mm} \moments_2 = \bracket{\moment_1,\moment_{x_1},\moment_{x_2},\moment_{\theta_1},\moment_{\theta_2},\moment_{x_1^2},\moment_{x_1 x_2}, \moment_{x_1 \theta_1},\moment_{x_1 \theta_2},\moment_{x_2^2},\moment_{x_2 \theta_1},\moment_{x_2\theta_2}, \moment_{\theta_1^2}, \moment_{\theta_1 \theta_2}, \moment_{\theta_2^2}} \in \Real{15}. \label{eq:momentVec2}
\eea
The vector of moments of degree up to 4, $\moments_4 \in \Real{\dimbasis{4}{4}=70}$ can be written in a similar way. We omit its full expression here, because it will soon appear in the moment matrix $\MM_2\parentheses{\moments_4}$. Then we are ready to form the moment matrix of order 1, with rows and columns indexed by $\monoleq{\xextend}{1}$:
\bea
& \MM_1\parentheses{\moments_2} = L_\moments\parentheses{\monoleq{\xextend}{1} \monoleq{\xextend}{1}\tran} =
\begin{blockarray}{cccccc}
& \matIdColor{1} & \matIdColor{x_1} & \matIdColor{x_2} & \matIdColor{\theta_1} & \matIdColor{\theta_2} \\
\begin{block}{c[ccccc]}
\matIdColor{1}   	 & \moment_1 & \moment_{x_1} & \moment_{x_2} & \moment_{\theta_1} & \moment_{\theta_2}\\
\matIdColor{x_1} 	 & \star & \moment_{x_1^2} & \moment_{x_1 x_2} & \moment_{x_1 \theta_1} & \moment_{x_1 \theta_2} \\
\matIdColor{x_2} 	 & \star & \star & \moment_{x_2^2} & \moment_{x_2 \theta_1} & \moment_{x_2 \theta_2} \\
\matIdColor{\theta_1} & \star & \star & \star & \moment_{\theta_1^2} & \moment_{\theta_1 \theta_2} \\
\matIdColor{\theta_2} & \star & \star & \star & \star & \moment_{\theta_2^2} \\
\end{block}
\end{blockarray}, \label{eq:momentMat1}
\eea
where we see that the moments appearing in $\MM_1\parentheses{\moments_2}$ are exactly $\moments_2$ (compare upper triangular entries in~\eqref{eq:momentMat1} with~\eqref{eq:momentVec2}, thus the expression $\MM_1\parentheses{\moments_2}$). Similarly, we form the moment matrix of order 2, with rows and columns indexed by $\monoleq{\xextend}{2}$:
\tiny
\input{eq-largeMomentMat}
\normalsize
where the upper triangular entries are exactly $\moments_4$, the vector of moments up to degree $4$ (thus the expression $\MM_2\parentheses{\moments_4}$). Moreover, the moment matrix is called a \emph{generalized Hankel matrix} because a moment of order $\valpha$ can appear multiple times in the matrix. For example, the moment $\moment_{x_1x_2\theta_1\theta_2}$ (highlighted in blue) appears three times in the upper triangular part of $\MM_2\parentheses{\moments_4}$.

{\bf Localizing matrices.} Using the moment matrix of order 1, $\MM_1\parentheses{\moments_2}$, the localizing matrix for $h^x = 1-x_1^2-x_2^2 = 0$ (eq.~\eqref{eq:2DSRAhx}) is:
\input{eq-largeLocalizeMat_x}
where the columns are indexed by $\monoleq{\xextend}{1}$, and the rows are indexed by $h^x\cdot \monoleq{\xextend}{1}$. The localizing matrix for $h^{\theta_1} = 1-\theta_1^2=0$ (eq.~\eqref{eq:2DSRAhtheta1}) is:
\input{eq-largeLocalizeMat_theta1}
where the columns are indexed by $\monoleq{\xextend}{1}$, and the rows are indexed by $h^{\theta_1}\cdot \monoleq{\xextend}{1}$. The localizing matrix for $h^{\theta_2} = 1-\theta_2^2=0$ (eq.~\eqref{eq:2DSRAhtheta2}) is:
\input{eq-largeLocalizeMat_theta2}
where the columns are indexed by $\monoleq{\xextend}{1}$, and the rows are indexed by $h^{\theta_2}\cdot \monoleq{\xextend}{1}$.

{\bf Dense Moment Relaxation.} With the expressions of the moment matrices and localizing matrices, the dense moment relaxation at $\rorder=2$ for 2D single rotation averaging is:
\bea \label{eq:SDP2DSRA}
p^\star_{2} = \min_{\moments_4 \in \Real{70}} & \sum_{\valpha \in \calF} c(\valpha) \moment_{\xextend^\valpha} \\
\subject & \MM_2\parentheses{\moments_4} \succeq 0 \nonumber \quad \text{(\cf~eq.~\eqref{eq:momentMat_4})} ,\\
		& \MM_1\parentheses{h^x \moments_2} = \zero \nonumber  \quad \text{(\cf~eq.~\eqref{eq:localizeMoment_x})} ,\\
		& \MM_1\parentheses{h^{\theta_1} \moments_2} = \zero \quad \text{(\cf~eq.~\eqref{eq:localizeMoment_theta_1})} ,\nonumber \\
		& \MM_2\parentheses{h^{\theta_2} \moments_2} = \zero \quad \text{(\cf~eq.~\eqref{eq:localizeMoment_theta_2})} .\nonumber
\eea
Now it is clearly that problem~\eqref{eq:SDP2DSRA} is an SDP because the entries of the moment matrix $\MM_2\parentheses{\moments_4}$, and the localizing matrices $\MM_1\parentheses{h^x \moments_2},\MM_1\parentheses{h^{\theta_1} \moments_2},\MM_1\parentheses{h^{\theta_2} \moments_2}$ depend \emph{linearly} on the optimization variables $\moments_4$, and the objective function is also a linear function of $\moments_4$.
\begin{remark}[\bf Moment Relaxation for POP \myversus SDP Relaxation for QCQP]
The expert reader may now see connections between the moment relaxation for POPs and Shor's SDP relaxation for quadratically constrained quadratic programs (QCQP): the moment relaxation can be seen as first performing a change of variables so that the POP becomes a QCQP (\ie~using $\monoleq{\xextend}{2}$ as the new set of variables, the POP can be seen as a QCQP because $\monoleq{\xextend}{2}$ contains monomials of degree higher than 1), and then apply standard SDP relaxations with \emph{redundant constraints}. The redundant constraints come from (i) the new set of variables $\monoleq{\xextend}{2}$ are not mutually independent,~\eg~$x_1x_2 = x_1 \cdot x_2$, and hence the moment matrix $\MM_2\parentheses{\moments_4}$ possess \emph{linear equality} constraints,~\eg~the term $\moment_{x_1x_2\theta_1\theta_2}$ appears multiple times; (ii) combinations of equality constraints,~\eg~$h^x = 0$ and $h^{\theta_1} = 0$ implies $h^x\cdot h^{\theta_1} =0$. Therefore, converting a POP to a QCQP and then applying SDP relaxation (see~\cite{Briales18cvpr-global2view,Yang19iccv-QUASAR} for two examples) has two drawbacks: first, carefully listing the complete set of redundant constraints can be time-consuming; second, it is challenging to handle \emph{inequality} constraints. On the contrary, the localizing matrices in moment relaxation provide a systematic way to include all redundant equality and inequality constraints.
\end{remark}
\subsection{Projection onto $\calxextend$}
\label{sec:projectionP}
Here we discuss how to project an estimate to the feasible set of the (POP): this is required to implement the rounding procedure
described in eq.~\eqref{eq:projection}.
Denote $\xextend_v = [\vxx_v\tran,\vtheta_v\tran]\tran = \vv_\rorder\parentheses{\xextend}$ as the entries of $\vv_\rorder$ at indices corresponding to the locations of $\xextend$ in $\monoleq{\xextend}{\rorder}$ (recall that $\vv_\rorder$ is obtained from the spectral decomposition of a moment matrix $\MM_\rorder\parentheses{\moments_4}$ with rank larger than 1, and in general $\xextend_v \not\in \calxextend$). To project $\xextend_v$ onto $\calxextend$ (eq.~\eqref{eq:projection}), we need to project $\vxx_v$ onto $\calX$ and project $\vtheta_v$ onto $\cbrace{\pm 1}_{i=1}^N$.

{\bf Project $\vtheta_v$ onto $\cbrace{\pm 1}_{i=1}^N$}. The projection of $\vtheta_v$ onto the set of binary variables $\cbrace{\pm 1}_{i=1}^N$, denoted $\hatvtheta$, is straightforward:
\bea
\bracket{\hatvtheta}_i = \proj_{\cbrace{\pm 1}} \parentheses{\bracket{\vtheta_v}_i} = \sgn{\bracket{\vtheta_v}_i}, i = 1,\dots,N,
\eea
where $\bracket{\cdot}_i$ denotes the $i$-th entry of a vector and $\sgn{\cdot}$ denotes the sign function.

{\bf Project $\vxx_v$ onto $\calX$}. Because Examples~\ref{eg:singleRotationAveraging}-\ref{eg:meshRegistration} have different feasible sets $\calX$ for the geometric models, the projections are different.

{\bf Example~\ref{eg:singleRotationAveraging} (Single Rotation Averaging)}. $\vxx = \MR \in \SOthree$, so the projection is:
\bea
\hatMR = \proj_{\SOthree} \parentheses{\vxx_v} = \MU \diag{1,1,\det\parentheses{\MU}\cdot\det\parentheses{\MV}} \MV\tran,
\eea
where $\vxx_v = \MU \MS \MV\tran, \MU,\MV \in \Othree$ is the singular value decomposition for $\vxx_v$ (first reshape $\vxx_v \in \Real{9}$ into a $3\times 3$ matrix)~\cite{Hartley13ijcv}.

{\bf Example~\ref{eg:shapeAlignment} (Shape Alignment)}. $\vxx = s\Pi\MR, s \in [0,\sub], \MR \in \SOthree$, so the projection is:
\bea
\hats = \min\cbrace{\sub, \frac{\sigma_1 + \sigma_2}{2} },
\hatMR = \bmat{c} \vr_1\tran \\ \vr_2\tran \\ \parentheses{\vr_1 \times \vr_2}\tran \emat,
\eea
where $\sigma_1,\sigma_2,\vr_1,\vr_2$ come from the singular value decomposition of $\vxx_v$ (first reshape $\vxx_v$ into a $2\times 3$ matrix):
\bea
\vxx_v = \MU \bmat{ccc} \sigma_1 & 0 & 0 \\ 0 & \sigma_2 & 0 \emat \MV\tran, \MU \in \Otwo, \MV \in \Othree,\quad  \bmat{c} \vr_1\tran \\ \vr_2\tran \emat = \MU \bmat{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \emat \MV\tran.
\eea

{\bf Example~\ref{eg:pointCloudRegistration}-\ref{eg:meshRegistration} (Point Cloud Registration and Mesh Registration)}. $\vxx = (\MR,\vt), \MR \in \SOthree, \| \vt \| \leq T$, so the projection is:
\bea
\hatMR = \proj_{\SOthree}\parentheses{\vxx_v^r}, \hatvt = \min\cbrace{\twonorm{\vxx_v^t},T} \frac{\vxx_v^t}{\twonorm{\vxx_v^t}},
\eea
where $\vxx_v^r$ denotes the entries of $\vxx_v$ corresponding to $\MR$, and $\vxx_v^t$ denotes the entries of $\vxx_v$ corresponding to $\vt$.