Estimation under group actions: recovering orbits from invariants

arXiv:1712.10163v1 [] 29 Dec 2017

Afonso S. Bandeira∗1,2 , Ben Blum-Smith†1 , Amelia Perry‡3 , Jonathan Weed§3 , and
Alexander S. Wein¶k3
1

Department of Mathematics, Courant Institute of Mathematical Sciences, New York
University, New York NY, USA
2
Center for Data Science, New York University, New York NY, USA
3
Department of Mathematics, Massachusetts Institute of Technology, Cambridge MA, USA
January 1, 2018

Abstract
Motivated by geometric problems in signal processing, computer vision, and structural biology, we
study a class of orbit recovery problems where we observe noisy copies of an unknown signal, each acted
upon by a random element of some group (such as Z/p or SO(3)). The goal is to recover the orbit of the
signal under the group action. This generalizes problems of interest such as multi-reference alignment
(MRA) and the reconstruction problem in cryo-electron microscopy (cryo-EM). We obtain matching
lower and upper bounds on the sample complexity of these problems in high generality, showing that the
statistical difficulty is intricately determined by the invariant theory of the underlying symmetry group.
In particular, we determine that for cryo-EM with noise variance σ 2 and uniform viewing directions,
the number of samples required scales as σ 6 . We match this bound with a novel algorithm for ab initio
reconstruction in cryo-EM, based on invariant features of degree at most 3. We further discuss how to
recover multiple molecular structures from heterogeneous cryo-EM samples.

1

Introduction

Many computational problems throughout the sciences exhibit rich symmetry and geometry, especially in
fields such as signal and image processing, computer vision, and microscopy. This is exemplified in cryoelectron microscopy (cryo-EM) [ADLM84, SS11, Nog16], an imaging technique in structural biology that
was recently awarded the 2017 Nobel Prize in Chemistry. This technique seeks to estimate the structure
of a large biological molecule, such as a protein, from many noisy tomographic projections (2-dimensional
images) of the molecule from random unknown directions in 3-dimensional space.
In cryo-EM, our signal of interest is the density θ of the molecule, considered as an element of the
vector space of functions on R3 . We have access to observations of the following form: our microscopy
sample contains many rotated copies Ri θ of the molecule, where Ri ∈ SO(3) are random, unknown 3D
∗ E-mail address: bandeira@cims.nyu.edu. Supported in part by NSF grant DMS-1712730 and NSF grant DMS-1719545.
Part of this work was done while ASB was visiting the Simons Institute for the Theory of Computing, this visit was partially
supported by the DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization through NSF grant
#CCF-1740425.
† E-mail address: ben@cims.nyu.edu.
‡ E-mail address: ameliaperry@mit.edu. Supported in part by NSF CAREER Award CCF-1453261 and a grant from the
MIT NEC Corporation.
§ E-mail address: jweed@mit.edu. Supported in part by NSF Graduate Research Fellowship DGE-1122374.
¶ E-mail address: awein@mit.edu.
k Authors are ordered alphabetically, please direct correspondence to awein@mit.edu.

1

rotations, and we observe the noisy projections Π(Ri θ) + ξi , where Π denotes tomographic projection (in a
fixed direction) and ξi is a large noise contribution, perhaps Gaussian. This specific problem motivates the
following general abstraction.
Fix a compact group G acting (by orthogonal transformations) on a vector space V . Throughout, the
vector space will be taken to be Rp and the group can be thought of as a subgroup of O(p), the orthogonal
group1 . Let θ ∈ V be the signal we want to estimate. We receive noisy measurements of its orbit as follows:
for i = 1, . . . , n we observe a sample of the form
yi = gi · θ + ξi
where gi is drawn randomly (in Haar measure2 ) from G and ξi ∼ N (0, σ 2 I) is noise. The goal is to recover
the orbit of θ under the action of G. We refer to this task as the orbit recovery problem.
This abstraction, already a rich object of study, neglects the tomographic projection in cryo-EM; we
will also study a generalization of the problem which allows such a projection. We will also consider the
additional extension of heterogeneity [Jon16, LS16, LS17, BBLS17], where mixtures of signals are allowed:
we have K signals θ1 , . . . , θK , and each sample yi = gi · θki + ξi comes from a random choice 1 ≤ ki ≤ K
of which signal is observed. This extension is of paramount importance for cryo-EM in practice, since the
laboratory samples often contain one protein in multiple conformations, and understanding the range of
conformations is key to understanding the function of the protein.

1.1

Prior work

Several special cases of the orbit recovery problem have been studied for their theoretical and practical
interest. Besides cryo-EM, another such problem is multi-reference alignment (MRA) [BCSZ14, BRW17,
PWB+ 17], a problem from signal processing [ZvdHGG03, PZAF05] with further relevance to structural
biology [Dia92, TS12]. In this problem, one observes noisy copies of a signal θ ∈ Rp , each with its coordinates
permuted by a random cyclic shift. This is an example of the orbit recovery problem when G is taken to be
the cyclic group Z/p acting by cyclic permutations of the coordinates. Since the cyclic group Z/p is simpler
than SO(3), understanding MRA has been seen as a useful stepping stone towards a full statistical analysis
of cryo-EM.
Many prior methods for orbit recovery problems employ the so-called synchronization approach where the
unknown group elements gi are estimated based on pairwise comparison of the samples yi . If the samples
were noiseless, one would have gi gj−1 yj = yi ; thus noisy samples still give some weak information about
gi gj−1 . Synchronization is the problem of using such pairwise information to recover all the group elements
gi (up to a global right-multiplication by some group element). Once the group elements gi are known, the
underlying signal can often be easily recovered.
The synchronization approach to cryo-EM can be summarized as follows [VG86, VH87, SS11]. By the
Fourier projection–slice theorem, the Fourier transforms of the tomographic projections are 2D slices of the
Fourier transform of the molecule density. Given a hypothesis as to the angles of two slices, we can predict a
1D line of intersection along which those slices should agree. By measuring correlation along that common
line, we obtain some weak information by which to confirm or refute our hypothesized angles. Indeed, this
test only depends on the relative angle of the slices, thus providing weak information about the value of
gi gj−1 . We then use a synchronization algorithm to recover the gi using this information.
Methods to solve the synchronization problem over various groups include spectral methods [Sin11, SS11],
semidefinite programming [Sin11, SS11, BCSZ14, BCS15, Ban15, BZS15], and approximate message passing
(AMP) [PWBM16a]. A general Gaussian model for synchronization problems over any compact group is
studied in [PWBM16b, PWBM16a]; ideas from statistical physics suggest that for this model, AMP is
1 We alert the reader to the fact that we will use O(p) to refer to the group of orthogonal matrices in dimension p and
O(g(n)) as the standard big-O notation: f (n) = O(g(n)) if and only if there exists a constant C such that f (n) ≤ Cg(n) for all
n sufficiently large. It will be clear from context which one is meant.
2 We note that any distribution of g can be reduced to Haar by left multiplying y by a Haar-distributed group element.
i
i
However, as illustrated in [ABL+ 17], it is sometimes possible to exploit deviations from Haar measure.

2

optimal among all efficient algorithms [PWBM16a]. However, the model does not capture the underlying
signal θ and instead assumes that for every pair i, j of samples, independent noisy measurements of the
relative group elements gi gj−1 are observed. This independence does not correctly capture problems like
MRA and cryo-EM, which have independent noise on each sample, rather than on each pairwise comparison
of samples.
The synchronization approach has proven to be effective both in theory and practice when the noise is
sufficiently small. However, once the noise level is large, no consistent estimation of the group elements
gi is possible [ADBS16]. Moreover, it is the high-noise regime that is the practically relevant one for
many applications, including cryo-EM, where the presence of large noise is a primary obstruction to current
techniques [Sig16]. As a result, recent work has focused on approaches to cryo-EM and MRA which provably
succeed even in the large-noise limit. One striking finding of this line of work is that the sample complexity
of the statistical estimation problem increases drastically as the noise level increases. For instance, for the
multi-reference alignment problem with noise variance σ 2 , consistent estimation of typical signals requires
Ω(σ 6 ) samples [BRW17, APS17], with significantly worse rates for atypical signals. By contrast, when σ 2
is smaller than some threshold, only O(σ 2 ) samples are required. Moreover, in contrast with the O(σ 2 )
rate—which would hold even in the absence of a group action—the Ω(σ 6 ) bound obtained in previous works
depends on particular properties of the cyclic group. In this work, we significantly extend this prior work by
determining the sample complexity of the estimation problem in the high-noise regime for general groups.
The leading theoretical framework for the high-noise regime is the invariant features approach [BRW17,
BBM+ 17, PWB+ 17, BBLS17, LBB+ 17]. This approach has a long history in the signal processing literature [Kam80, Sad89, SG92] and is analogous to the well known “method of moments” in statistics [vdV98].
In brief, the invariant features approach bypasses entirely the problem of estimating the group elements and
focuses instead on estimating features of the signal which are preserved by the action of the group. So long as
these invariant features uniquely specify the orbit of the original signal, the invariants are sufficient statistics
for the problem of recovering the orbit of the original signal. This simple approach yields optimal dependence
of the sample complexity on the noise level for the multi-reference alignment problem [BRW17, PWB+ 17].
The application of invariant features to cryo-EM dates back to 1980 with the work of Kam [Kam80], who
partially solved cryo-EM by means of degree-2 invariant features, reducing the unknown molecule structure
to a collection of unknown orthogonal matrices. Subsequent work has explored methods to estimate these
orthogonal matrices [BZS15], including recent work showing how two noiseless tomographic projections
suffice to recover these orthogonal matrices [LBB+ 17]. Our work can be viewed as a degree-3 extension of
Kam’s method that fully solves cryo-EM while circumventing the orthogonal retrieval issue, and without
requiring any noiseless projections. Our approach is ab initio, i.e. it does not require an initial guess of what
the molecule looks like and thus cannot suffer from model bias, which is a documented phenomenon [Coh13]
where the initial guess can have a significant effect on the result. Ab initio estimates are particularly useful
to serve as a model-free starting point for popular iterative refinement algorithms such as RELION [Sch12].
Throughout, we focus on the case where the group elements are Haar-distributed. In the basic orbit
recovery problem (projection), any distribution of gi can be reduced to Haar by left-multiplying each sample
yi by a Haar-distributed group element. However, as illustrated in [ABL+ 17], it is sometimes possible to
exploit deviations from Haar measure. The situation is different when we add projection to the problem
setup, as is the case with Cryo-EM; if the viewing direction is not distributed uniformly then there may exist
parts of the molecule that are systematically imaged less than others, which can cause serious difficulties in
reconstruction.
The present paper connects the orbit recovery problem to the invariant theory of groups, a classical
and well-developed branch of algebra (see for example [Kač94, Dol03, Stu08, DK15]). Invariant theory’s
traditional goal is to describe the ring of all polynomial functions on a vector space that are invariant under
the action of a group – the invariant algebra. Since the 19th century, culminating in the pioneering work of
David Hilbert [Hil90, Hil93], it has been known that the invariant algebra is finitely generated in many cases
of interest, and so a fundamental problem has been to bound the degrees of the generators. In 2002, Derksen
and Kemper [DK15] introduced the notion of a separating algebra – a subring of the invariant algebra that
separates all orbits of the group action which are separated by the full invariant algebra. Our connection

3

to orbit recovery motivates the question of bounding the degree required to generate a separating algebra
(see Section 4.4), a problem which has been recently studied [KK10, Dom16]. Our work also motivates the
question of bounding the degree at which the field of invariant rational functions is generated as a field (see
Section 4.3), which does not appear to have been the focus of research attention before.

1.2

Our contributions

In this paper we extend the results of [BRW17] and show that the method of moments yields optimal sample
complexity for orbit recovery problems over any compact group. Specifically, we show that optimal sample
complexity is achieved by an algorithm that estimates the moments from the samples and then solves a
polynomial system of equations in order to find a signal θ that would produce such moments. As the sample
complexity depends on the number of moments used, this gives rise to the algebraic question of how many
moments suffice to determine the orbit of θ. Using tools from invariant theory and algebraic geometry, we
investigate this question for various success criteria and obtain sharp results in a number of settings. Our
main focus is on the case where the signal is assumed to be generic and the goal is to output a finite list
of signals, one of which is the truth. In this case we give a simple efficient algorithm for determining the
number of moments required for any given orbit recovery problem. The main step of the algorithm is to
compute the rank of a particular Jacobian matrix.
We note that ours is an information-theoretic result rather than a computational one because even with
knowledge of the number of moments required, estimating the original signal still requires solving a particular
polynomial system of equations and we do not attempt to give a computationally-efficient method for this.
There are fast non-convex heuristic methods to solve these systems in practice [BBLS17] but we leave for
future work the question of analyzing such methods rigorously and exploring whether or not they reach the
information-theoretic limits determined in this paper. For the case of finite groups, another efficient method
for solving the polynomial system is via tensor decomposition, which has been analyzed for MRA [PWB+ 17].
Concrete results for problems such as MRA and cryo-EM are in Section 5.

1.3

Motivating examples

In addition to the examples of MRA and cryo-EM, it is helpful to have the following motivating examples
in mind:
1. Learning a “bag of numbers”: let G be the symmetric group Sp , acting on V = Rp by permutation
matrices. Thus we observe random rearrangements of the entries of a vector, plus noise.
2. Learning a rigid body: let G be the rotation group SO(p), acting on the matrix space V = Rp×m by
left-multiplication. We imagine the columns of our matrix as vertices defining a rigid body; thus we
observe random rotations of this rigid body (with vertices labeled) plus noise.
3. S 2 registration: Let S 2 ⊆ R3 be the unit sphere. Let V be the finite-dimensional vector space of
functions on S 2 → R that are band-limited, i.e. linear combinations of spherical harmonics up to some
fixed degree (spherical harmonics are the appropriate “Fourier basis” for functions on the sphere); let
θ ∈ V be such a function S 2 → R. Let G = SO(3), acting on the sphere by 3-dimensional rotation;
this induces an action on V via (g · θ)(x) = θ(g −1 · x). Thus we observe many noisy copies of a fixed
function on the sphere, each rotated randomly.

1.4

Problem statement

Throughout, we consider a compact (topological) group G acting linearly, continuously, and orthogonally
on a finite-dimensional real vector space V = Rp . In other words, G acts on V via a linear representation
ρ : G → O(V ), and ρ itself is a continuous function. Here O(V ) denotes the space of real orthogonal p × p
matrices. Let Haar(G) denote Haar measure (i.e., the “uniform distribution”) on G. We define the orbit
recovery problem as follows.
4

Problem 1.1 (orbit recovery). Let V = Rp and let θ ∈ V be the unknown signal. Let G be a compact group
that acts linearly, continuously, and orthogonally on V . For i ∈ [n] = {1, 2, . . . , n} we observe
yi = gi · θ + ξi
where gi ∼ Haar(G) and ξi ∼ N (0, σ 2 Ip×p ), all independently. The goal is to estimate θ. Note that we can
only hope to recover θ up to action by G; thus we aim to recover the orbit {g · θ : g ∈ G} of θ.
In practical applications, σ is often known in advance and, when it is not, it can generally be estimated
accurately on the basis of the samples. We therefore assume throughout that σ is known and do not pursue
the question of its estimation in this work.
Our primary goal is to study the sample complexity of the problem: how must the number of samples n
scale with the noise level σ (as σ → ∞ with G and V fixed) in order for orbit recovery to be statistically
possible? All of our results will furthermore apply to a generalized orbit recovery problem (Problem 2.3)
allowing for projection and heterogeneity (see Section 1.6).
Our work reveals that it is natural to consider several different settings in which to state the orbit recovery
problem. We consider the following two decisions:
1. Do we assume that θ is a generic signal, or do we allow for a worst-case signal? (Here generic means
that there is a measure-zero set of disallowed signals.)
2. Do we want to output a θ′ such that θ′ (approximately) lies in the orbit of θ (unique recovery), or
simply a finite list θ1 , . . . , θs of candidates such that one of them (approximately) lies in the orbit of θ
(list recovery)?
The terminology “list recovery” is borrowed from the idea of list decoding in the theory of error-correcting
codes [Eli57]. By taking all combinations of the two options above, there are four different recovery criteria.
Strikingly, these different recovery criteria can be very different in terms of sample complexity, as the following
examples show (see Section 5 for more details):
1. Multi-reference alignment (MRA): Recall that this is the case G = Z/p acting on V = Rp by cyclic
shifts. It is known [PWB+ 17] that if θ is generic then unique recovery is possible with O(σ 6 ) samples.
However, for a worst-case θ, many more samples are required (even for list recovery); as shown in
[BRW17], there are some very particular infinite families of signals that cannot be distinguished without
Ω(σ 2p ) samples. This illustrates a large gap in difficulty between the generic and worst-case problems.
2. Learning a rigid body: Let G be the rotation group SO(p) acting on the matrix space Rp×m by left
multiplication. We imagine the columns of our matrix as vertices defining a rigid body; thus we observe
random rotations of this rigid body (with vertices labeled) plus noise. With O(σ 4 ) samples it is possible
to recover the rigid body up to reflection, so that list recovery (with a list of size 2) is possible. However,
unique recovery (even for a generic signal) requires drastically more samples: Ω(σ 2p ).
We will address all four recovery criteria but our main focus will be on the case of generic list recovery,
as it is algebraically the most tractable to analyze. For the following reasons we also argue that it is perhaps
the most practically relevant case. Clearly real-world signals are generic. Also, unique recovery is actually
impossible in some practical applications; for instance, in cryo-EM it is impossible to determine the chirality
of the molecule. Furthermore, one could hope to use application-specific clues to pick the true signal out
from a finite list; for instance, in cryo-EM we might hope that the spurious solutions in our finite list do not
look like “reasonable” molecules and can be thrown out.

1.5

Method of moments

Our techniques rely on estimation of the following moments:
Definition 1.2 (moment tensor). The order-d moment tensor is Td (θ) := Eg [(g · θ)⊗d ] where g ∼ Haar(G).
5

Pn
We can estimate Td (θ) from the samples by computing n1 i=1 yi⊗d plus a correction term to cancel bias
from the noise terms (see Section 7 for details). The moments Td (θ) are related to polynomials that are
invariant under the group action, which brings us to the fundamental object in invariant theory:
Definition 1.3 (invariant ring). Let x = (x1 , . . . , xp ) be a set of coordinate functions on V = Rp , i.e. a basis
for the dual V ∗ , so that R[x] := R[x1 , . . . , xp ] is the ring of polynomial functions V → R. We have an action
of G on R[x] given by (g · f )(·) = f (g −1 (·)). (If we fix a basis for V , we can think of x as indeterminate
variables corresponding to the entries of θ ∈ V .) The invariant ring R[x]G ⊆ R[x] is the ring consisting of
polynomials f that satisfy g · f = f for all g ∈ G. An element of the invariant ring is called an invariant
polynomial (or simply an invariant ). Invariant polynomials can be equivalently characterized as polynomials
of the form Eg [g · f ] where f ∈ R[x] is any polynomial and g ∼ Haar(G).
The two objects above are equivalent in the following sense. The moment tensor Td (θ) contains the same
information as the set of evaluations f (θ) for all f ∈ R[x]G that are homogeneous of degree d. In particular,
for any such polynomial f , f (θ) is a linear combination of the entries of Td (θ).
The following algebraic question will be of central importance: when do the values of invariant polynomials
(of degree ≤ d) of θ determine the orbit of θ (in the appropriate sense)? As we see below, the sample
complexity of the statistical problem is completely characterized by the answer to this question.
1.5.1

Warm up: hypothesis testing

Consider for now the simple problem of distinguishing between two fixed hypotheses θ = τ1 and θ = τ2 ,
where τ1 and τ2 are two fixed vectors in V . One method is to find an invariant polynomial f for which
f (τ1 ) 6= f (τ2 ) and to estimate f (θ) using the samples. The sample complexity of this procedure depends
on the degree of f because if f has degree d, we need O(σ 2d ) samples to accurately estimate f (θ). We will
prove the following (see Section 3).
Theorem 1.4 (distinguishing upper bound). Fix τ1 , τ2 ∈ V . If there exists a degree-d invariant polynomial
f ∈ R[x]G with f (τ1 ) 6= f (τ2 ) then, using O(σ 2d ) samples, it is possible to distinguish between θ = τ1 and
θ = τ2 with type-I and type-II error probabilities each at most 1/3.
Here, O(· · · ) hides factors that depend on G (and its action on V ), τ1 , and τ2 , but not σ; we are most
interested in how the sample complexity scales as σ becomes large (with everything else held fixed). The
error probability 1/3 is arbitrary and can be boosted by taking more samples (see Theorem 3.2).
Furthermore, we have a matching lower bound to show that the method of moments is optimal: the
sample complexity is driven by the minimum degree of an invariant polynomial that separates τ1 and τ2 .
Theorem 1.5 (distinguishing lower bound). Fix τ1 , τ2 ∈ V . Let d∗ be the smallest positive integer d for
∗
which Td (τ1 ) 6= Td (τ2 ). Then Ω(σ 2d ) samples are required to distinguish between θ = τ1 and θ = τ2 with
type-I and type-II error probabilities each at most 1/3.
See Section 3 for more details.
1.5.2

Recovery

We now address the problem of recovering the signal θ from the samples. Our goal is to recover the orbit of
θ, defined as follows.
G

G

Definition 1.6. For θ1 , θ2 ∈ V , define an equivalence relation ∼ by letting θ1 ∼ θ2 if there exists g ∈ G
G
such that g · θ1 = θ2 . The orbit of θ (under the action of G) is the equivalence class of θ under ∼, i.e. the
set {g · θ : g ∈ G}. Denote by V /G the set of orbits of V , that is, the equivalence classes of V modulo the
G
relation ∼.
We need the following definitions to capture the notion of approximately recovering the orbit of θ.

6

Definition 1.7. For θ1 , θ2 ∈ V , let
dG (θ1 , θ2 ) = min kθ1 − g · θ2 k2 .
g∈G

This pseudometric induces a metric on the quotient space V /G in the obvious way, so we can write dG (o1 , o2 )
for o1 , o2 ∈ V /G. By slight abuse of notation, we write dG (θ1 , o2 ) for dG (o1 , o2 ), where o1 is the orbit of θ1 .
Theorem 1.5 already shows that if the orbit of θ is not determined by knowledge of the first d − 1 moment
tensors, then at least Ω(σ 2d ) samples are required to recover the orbit of θ. We are now ready to (informally)
state our main result on recovery (see Section 3 for more details), which provides a matching upper bound.
Theorem 1.8 (recovery upper bound, informal). Fix θ ∈ V . If the moments T1 (θ), · · · , Td (θ) uniquely
b ≤ε
determine the orbit of θ, then using O(σ 2d ) samples, we can produce an estimator θb such that dG (θ, θ)
with high probability.

The analogous result holds for list recovery (see Section 3): if the moments determine a finite number of
possibilities for the orbit of θ then we can output a finite list of estimators, one of which is close to the orbit
of θ.
Thus, we have reduced to the algebraic question of determining how many moments are necessary to
determine the orbit of θ (either uniquely or in the sense of list recovery). In Section 4 we will use tools from
invariant theory and algebraic geometry in order to address these questions.

1.6

Extensions: projection and heterogeneity

We now consider some extensions to the basic orbit recovery problem (Problem 1.1), motivated by the
application of cryo-EM:
1. Projection: In cryo-EM, we do not observe a noisy 3-dimensional model of the rotated molecule;
we only observe a 2-dimensional projection of it. We will model this projection by a linear map
Π : Rp → Rq that maps a 3-dimensional model to its 2-dimensional projection (from a fixed viewing
direction). The samples are then given by yi = Π(gi · θ) + ξi where ξi ∼ N (0, σ 2 I).
2. Heterogeneity: In cryo-EM we observe images of many different copies of the same molecule, each
rotated differently. However, if our sample is not pure, we may have a mixture of different molecules
and want to recover the structure of all of them. We will model this by taking K different unknown
signals θ1 , . . . , θK along with positive mixing weights w1 , . . . , wK which sum to 1. Each sample takes
the form yi = gi · θki + ξi where ki is chosen at random according to the mixing weights.
In Section 2 we will formally define a generalization of the orbit recovery problem that allows for either (or
both) of the above extensions. All of our methods will apply to this general case.

1.7

Organization of the remainder of the paper

In Section 2, we define a generalization of Problem 1.1 which encompasses projection and heterogeneity,
and specify the basic algebraic objects which relate to our generalized problem. In Section 3, we formally
state statistical upper and lower bounds for the generalized orbit recovery problem in terms of invariants. In
Section 4, we establish our basic algebraic results and specify the algebraic criteria that correspond to the
different recovery criteria defined in Section 1.4. We also give an efficient algorithm to decide the algebraic
criterion corresponding to generic list recovery. Finally, in Section 5, we apply our work to several examples
of the orbit recovery problem, including MRA and cryo-EM. We conclude in Section 6 with questions for
future work.
Sections 7–9 contain proofs of results from preceding sections. Appendix A contains an account of the
invariant theory of SO(3), and Appendix B contains a proof (using Galois theory) of generic unique recovery
in a particular special case of the orbit recovery problem (the regular representation of a finite Abelian
group).
7

2

General problem statement

Our results will apply not only to the basic orbit recovery problem (Problem 1.1) but to a generalization
(Problem 2.3 below) that captures the projection and heterogeneity extensions discussed in Section 1.6. We
first define mixing weights for heterogeneous problems.
PK
Definition 2.1 (mixing weights). Let w = (w1 , . . . , wK ) ∈ ∆K := {(z1 , . . . , zK ) : zk ≥ 0 ∀k, k=1 zk = 1}.
w
Let k ∼ [K] indicate that k is sampled from [K] = {1, . . . , K} such that k = ℓ with probability wℓ . We
will sometimes instead parametrize the mixing weights by w k = wk − 1/K so that w lies in the vector space
PK
∆ := {(z1 , . . . , zK ) :
k=1 zk = 0}.

In a heterogeneous problem with K different signals, we can only hope to recover the signals up to permutation. To formalize this, our compound signal will lie in a larger vector space V and we will seek to recover
its orbit under a larger group G.

Definition 2.2 (setup for heterogeneity). Let G̃ be a compact group acting linearly, continuously, and
orthogonally on Ṽ = Rp . Let V = Ṽ ⊕K ⊕ ∆K , so that θ ∈ V encodes K different signals along with mixing
weights: θ = (θ1 , . . . , θK , w). We let an element (g1 , . . . , gK , π) of the Cartesian product set G̃K × SK act on
V as follows: first, each gk acts on the corresponding θk , and then π permutes the θk and the coordinates of
w. Note that this action is linear and orthogonal (where ∆ uses the usual inner product inherited from RK ).
There is a natural group structure G on the set G̃K × SK such that the action just described is actually a
group action by G: the semidirect product G = G̃K ⋊ϕ SK , where ϕ denotes the action of SK on G̃K by
permutations of the factors. This is also called the wreath product of G̃ by SK and written G̃ ≀ SK . The
product topology on G̃K × SK makes G a topological group; it is compact with respect to this topology since
all the factors are compact, and the action described above is continuous.
Of course, by taking K = 1 we recover the basic setup (without heterogeneity) as a special case. We are
now ready to give the general problem statement.
Problem 2.3 (generalized orbit recovery). Let Ṽ = Rp and W = Rq . Let G̃ be a compact group acting
linearly, continuously, and orthogonally on Ṽ . Let Π : Ṽ → W be a linear map. Let θ = (θ1 , . . . , θK , w) ∈
V := Ṽ ⊕K ⊕ ∆K be an unknown collection of K signals with mixing weights w ∈ ∆K . For i ∈ [n] =
{1, 2, . . . , n} we observe
yi = Π(gi · θki ) + ξi
w

where gi ∼ Haar(G̃), ki ∼ [K], ξi ∼ N (0, σ 2 Iq×q ), all independently. The goal is to estimate the orbit of θ
under G := G̃K ⋊ SK .
Note that this serves as a reduction from the heterogeneous setup to the basic setup in the sense that we are
still only concerned with recovering the orbit of a vector θ under the action of some compact group.
As discussed previously, we apply the method of moments. The moments are now defined as follows.
Definition 2.4 (moment tensor). For the generalized orbit recovery problem (Problem 2.3), the order-d
w
moment tensor is Td (θ) := Eg,k [(Π(g · θk ))⊗d ] where g ∼ Haar(G̃) and k ∼ [K]. Equivalently, Td (θ) =
PK
⊗d
].
k=1 wk Eg [(Π(g · θk ))

The invariant ring is defined as in Definition 1.3 but now for the larger group G acting on the larger V :

Definition 2.5 (invariant ring). Note that dim(V ) = Kp + K − 1 and let x = (x1 , . . . , xdim(V ) ) be a basis
for V ∗ ; here the last K − 1 variables correspond to ∆, e.g. they can correspond to w 1 , . . . , w K−1 . We then
let R[x]G ⊆ R[x] be the polynomials in x that are invariant under the action of G (as in Definition 1.3).
Recall that in the basic orbit recovery problem, Td (θ) corresponds precisely to the homogeneous invariant
polynomials of degree d; now Td (θ) corresponds to a subspace of the homogeneous invariant polynomials of
degree d. Specifically, the method of moments gives us access to the following polynomials (evaluated at θ):
8

Definition 2.6. Let UdT be the subspace (over R) of the invariant ring R[x]G consisting of all R-linear
T
combinations of entries of Td (x). Let U≤d
= U1T ⊕ · · · ⊕ UdT ⊆ R[x]G . Here we write Td (x) for the collection
of polynomials (one for each entry of Td (θ)) that map θ to Td (θ).
T
We will be interested in whether the subspace U≤d
contains enough information to uniquely determine
the orbit of θ (or determine a finite list of possible orbits) in the following sense.

Definition 2.7. A subspace U ⊆ R[x]G resolves θ ∈ V if there exists a unique o ∈ V /G such that f (θ) = f (o)
for all f ∈ U . Similarly, U list-resolves θ if there are only finitely many orbits o1 , . . . , os such that f (θ) = f (oi )
for all f ∈ U .
Here we have abused notation by writing f (o) to denote the (constant) value that f takes on every θ ∈ o.
The following question is of central importance.
T
Question 2.8. Fix θ ∈ V . How large must d be in order for U≤d
to uniquely resolve θ? How large must d
T
be in order for U≤d to list-resolve θ?

The answer depends on G and V but also on whether θ is a generic or worst-case signal, and whether
we ask for unique recovery or list recovery. Our statistical results in Section 3 will show that the sample complexity of the generalized orbit recovery problem is Θ(σ 2d ) where d is the minimal d from Question 2.8. More specifically, the recovery procedure that obtains this bound is based on estimating the
moments T1 (θ), . . . , Td (θ) and solving a system of polynomial equations to (approximately) recover θ. Our
algebraic results in Section 4 will give general methods to answer Question 2.8 for any G and V .

3

Statistical results

In this section, we state upper and lower bounds on the performance of optimal estimators for the orbit
recovery problem. Proofs are deferred to Section 7. Our approach will be the method of moments introduced
in Section 1.5. We assume for normalization purposes that there exists a constant c ≥ 1 such that c−1 ≤
kθk ≤ c, so that σ captures entirely the signal-to-noise ratio of the problem. We denote by Θ the subset of
V consisting of vectors satisfying this requirement.
Denote by Pθ the distribution of a sample arising from the generalized orbit recovery problem (Problem 2.3) with parameter θ.
Definition 3.1. Given θ ∈ Θ, the order-d matching set for θ, Mθ,d, is the set consisting of all τ ∈ V such
T
.
that f (τ ) = f (θ) for all f ∈ U≤d
T
T
list-resolves θ when
resolves θ exactly when Mθ,d contains a single orbit, and U≤d
We note that U≤d
Mθ,d is the union of a finite number of orbits.
We are now ready to state a formal theorem justifying Theorems 1.4 and 1.8, above. The following
theorem establishes that we can approximately learn the order-d matching set for θ with probability at least
1 − δ on the basis of O(σ 2d log(1/δ)) samples. Denote by Mεθ,d the ε-fattening of Mθ,d, i.e., the set of all
φ ∈ Θ such that minτ ∈Mθ,d kφ − τ k ≤ ε.

Theorem 3.2. For any positive integer n, noise level σ ≥ maxθ∈Θ kθk, and accuracy parameter δ > 0, there
cn = M
cn (y1 , . . . , yn ) ⊆ V such that, for any positive constant ε, if y1 , . . . , yn ∼ Pθ i.i.d.
exists an estimator M
and n ≥ cθ,ε,d log(1/δ)σ 2d , then with probability at least 1 − δ,
cn ⊆ Mεθ,d .
Mθ,d ⊆ M

The constant cθ,ε,d in Theorem 3.2 can be replaced by cθ,d ε−2 in the unique recovery setting if θ is
suitably generic, but the dependence on ε can be worse in general. What is key is that cθ,ε,d does not depend
on σ, so that Theorem 3.2 captures the behavior of the sample complexity in the large σ limit.

9

Theorem 3.2 essentially follows from the observation that, since the variance of yi is O(σ 2 ), a degree-d
T
polynomial in the entries of yi has variance O(σ 2d ). This implies that for any f ∈ U≤d
, the evaluation f (θ)
2d
can be accurately estimated on the basis of O(σ ) samples. By inverting a suitable polynomial system, we
can thereby identify Mθ,d , at least approximately. A full proof of Theorem 3.2 appears in Section 7.
Theorem 3.2 captures the behavior described in both Theorem 1.4 and Theorem 1.8. Indeed, if τ1 and τ2
differ on some f ∈ UdT , then Mτ1 ,d is separated from Mτ2 ,d , and Theorem 3.2 implies that we can therefore
distinguish between the two distributions when ε is sufficiently small. Moreover, as the following corollary
cn allows us to recover or list-recover the orbit of θ.
shows, Theorem 3.2 implies that the confidence set M

Corollary 3.3. Suppose that Mθ,d is the union of M orbits o1 , . . . , oM , where M is finite. There exists an
εθ such that, for ε < εθ , if n ≥ cθ,ε,d log(1/δ)σ 2d , then on the basis of n i.i.d. samples from Pθ we can produce
M estimators θb1 , . . . θbM such that, with probability at least 1 − δ, there exists a permutation π : [M ] → [M ]
satisfying
dG (θbi , oπ(i) ) ≤ ε
for all i ∈ [N ].

Proof. Since G is a compact group acting continuously on V , the orbits are compact. By assumption Mθ,d ,
is a union of a finite number of orbits, so there exists an εθ such that dG (oi , oj ) ≥ 4εθ for any i 6= j. For
cn as in Theorem 3.2. Theorem 3.2 implies the
any ε < εθ , let N be an ε/2-net of V /G, and construct M
existence of a constant cθ,ε,d such that as long as n ≥ cθ,ε,d log(1/δ)σ 2d , with probability at least 1 − δ,
cn ⊆ Mε/2 .
Mθ,d ⊆ M
θ,d
cn ) ≤ ε/2. With probability 1 − δ, any element
Consider the set C consisting of o ∈ N such that dG (o, M
of C is within ε of oi for some i ∈ [M ], and for each oi there exists an o ∈ C that is at most ε away. By
assumption, distinct orbits in Mθ,d are separated by more than 4ε, so if any two elements of C are separated
by at most 2ε, then they are close to the same element of Mθ,d . As a result, it is possible to partition C
into M sets C1 , . . . , CM such that dG (o, o′ ) ≤ 2ε if o, o′ are in the same set, and dG (o, o′ ) > 2ε if o and o′
are in different sets. For i ∈ [M ], let θbi be any element of V such that the orbit of θbi lies in Ci . The claim
follows.

The constant εθ in the statement of Corollary 3.3 will not be known in general. However, a weaker
cn under the projection V 7→ V /G.
statement still holds when ε ≥ εθ . Indeed, consider the image of the set M
There exists a finite partition of the resulting set such that any two orbits in the same cluster are closer
than any two orbits in different clusters. (Note that the clustering into a single set always satisfies this
requirement.) If we are able to choose this partition such that the diameter of each set is at most ε′ , then
by choosing a representative from each cluster, we obtain a finite set of estimators, at least one of which is
guaranteed to be ε′ -close to θ with high probability. Corollary 3.3 implies that this partition can be taken
to consist of at most M clusters for ε′ arbitrarily small, as long as n ≥ Cε′ σ 2d .
We now prove a lower bound showing that the dependence on σ in Theorem 3.2 is tight. We show that
T
if U≤d−1
fails to resolve (or list-resolve) θ, then Ω(σ 2d ) samples are necessary to recover (or list-recover) the
orbit of θ. Together with Theorem 3.2, this lower bound implies that if d∗ is the smallest positive integer
∗
for which UdT∗ resolves (or list-resolve) θ, then Θ(σ 2d ) samples are required to recover (or list-recover) the
orbit of θ. We make this lower bound precise in Theorem 3.4.
Theorem 3.4. For any positive integer d, there exists a constant cd such that if τ1 and τ2 are elements
in Mθ,d−1 lying in different orbits, then no procedure can distinguish between Pnτ1 and Pnτ2 with probability
greater than 2/3 if n ≤ cd σ 2d .
Note that via Le Cam’s method [LeC73], Theorem 3.4 translates into lower bounds for the problem of
recovering θ. The proof of Theorem 3.4 relies on a tight bound for the Kullbeck-Leibler divergence between
the distributions Po1 and Po2 established in [BRW17]. More details appear in Section 7.

10

4

Algebraic results

In this section, we will consider the four recovery criteria defined in Section 1.4, and give algebraic characterizations of each case. The results of Section 3 imply that it suffices to focus our attention on deciding
when a subspace U resolves (or list-resolves) a parameter θ. We show below how to answer this question
by purely algebraic means. Moreover, for generic list recovery, we show how this question can be answered
algorithmically in polynomial time. For generic and worst-case unique recovery, we also give algorithms to
decide the corresponding algebraic condition; however, these algorithms are not efficient.
Throughout, we assume the setup defined in Section 2 for the generalized orbit recovery problem. In
particular, G is a compact group acting linearly and continuously on a finite-dimensional real vector space
V (although we do not require in this section that the action be orthogonal). We have the invariant ring
T
R[x]G corresponding to the action of G on V , and a subspace U ⊆ R[x]G (e.g. U≤d
) of invariants that we
have access to. We are interested in whether the values f (θ) for f ∈ U determine the orbit of θ ∈ V under
T
G. The specific structure of G and U≤d
(as defined in Section 2) will be largely unimportant and can be
abstracted away.

4.1

Invariant theory basics

We will often need the following basic operator that averages a polynomial over the group G.
Definition 4.1 (Reynolds operator). The Reynolds operator R : R[x] → R[x]G is defined by
R(f ) =

E

[g · f ].

g∼Haar(G)

Note that the Reynolds operator is a linear projection from R[x] to R[x]G that preserves the degree of
homogeneous polynomials (i.e. a homogeneous polynomial of degree d gets mapped either to a homogeneous
polynomial of degree d or to zero).
Observation 4.2. Let R[x]G
d denote the vector space consisting of homogeneous invariants of degree d. We
can obtain a basis for R[x]G
d by applying R to each monomial in R[x] of degree d. (This yields a spanning
set which can be pruned to a basis if desired.)
In our setting, we have the following basic fact from invariant theory.
Theorem 4.3 (e.g. [Kač94] Theorem 4.1-3). The invariant ring R[x]G is finitely generated as an R-algebra.
In other words, there exist generators f1 , . . . , fm ∈ R[x]G such that R[f1 , . . . , fm ] = R[x]G .
Furthermore, there is an algorithm to find a generating set; see Section 8.1. Another basic fact from invariant
theory implies that the entire invariant ring is sufficient to determine the orbit of θ. (This is not always true
for non-compact groups; see Example 2.3.1 in [DK15].)
Theorem 4.4 ([Kač94] Theorem 6-2.2). The full invariant ring R[x]G resolves every θ ∈ V .
Proof. Let o1 , o2 ∈ V /G be distinct (and therefore disjoint) orbits. Since G is compact and acts continuously,
o1 and o2 are compact subsets of V . Thus by Urysohn’s lemma there exists a continuous function f˜ : V → R
such that f˜(τ ) = 0 ∀τ ∈ o1 and f˜(τ ) = 1 ∀τ ∈ o2 . The Stone–Weierstrass theorem states that a continuous
function on a compact domain can be uniformly approximated to arbitrary accuracy by a polynomial. This
means there is a polynomial f ∈ R[x] with f (τ ) ≤ 1/3 ∀τ ∈ o1 and f (τ ) ≥ 2/3 ∀τ ∈ o2 . It follows that
h = R(f ) is an invariant polynomial that separates the two orbits: h(o1 ) ≤ 1/3 and h(o2 ) ≥ 2/3.
Thus, in order to determine the orbit of θ it is sufficient to determine the values of all invariant polynomials.
(This condition is clearly also necessary in the sense that if the orbit is uniquely determined then so are the
values of all invariants.)

11

Remark 4.5. In what follows we will be discussing algorithms that take the problem setup as input (includT
ing G̃ and its action on Ṽ , along with Π, K) and decide whether or not U≤d
(for some given d) is capable of a
particular recovery task (e.g. list recovery of a generic θ ∈ V ). We will always assume that these algorithms
have a procedure to compute a basis for UdT (for any d) in exact symbolic arithmetic. This is non-trivial
in some cases because Td (x) (and thus UdT ) involves integration over the group (and may involve irrational
values), but we will not worry about these details here. For the important case of SO(3), it is possible to
write down a basis for the invariants in closed form (see Appendix A).
Remark 4.6. We will draw from various references for algorithmic aspects of invariant theory. The case of
finite groups is treated by [Stu08]. Although the invariant ring is sometimes taken to be C[x]G instead of
R[x]G , this is unimportant in our setting because the two are essentially the same: since our group action
is real, a basis for R[x]G (over R) is a basis for C[x]G (over C). The case of infinite groups is covered by
[DK15]. Here the group is assumed to be a reductive group over C (or another algebraically-closed field).
This means in particular that the group is a subset of complex-valued matrices that is defined by polynomial
constraints. Although compact groups such as SO(3) do not satisfy this, the key property of a reductive
group is the existence of a Reynolds operator satisfying certain properties; since this exists for compact
groups (Definition 4.1), some (but not all) results still hold in our setting.

4.2

Generic list recovery

We will see that the case of list recovery of a generic signal is governed by the notion of algebraic independence.
Definition 4.7. Polynomials f1 , . . . , fm ∈ R[x] are algebraically dependent if there exists a nonzero polynomial P ∈ R[y1 , . . . , ym ] such that P (f1 , . . . , fm ) = 0 (i.e. P (f1 (x), . . . , fm (x)) is equal to the zero polynomial).
Otherwise, they are algebraically independent.
Definition 4.8. The transcendence degree of a subspace U ⊆ R[x], denoted trdeg(U ) is the maximum value
of m for which there exist algebraically independent f1 , . . . , fm ∈ U . A set of trdeg(U ) such polynomials is
called a transcendence basis of U .
We now present our algebraic characterization of the generic list recovery problem.
Theorem 4.9 (generic list recovery). Let U ⊆ R[x]G be a finite-dimensional subspace. If trdeg(U ) =
trdeg(R[x]G ) then there exists a set S ⊆ V of full measure such that if θ ∈ S then U list-resolves θ.
Conversely, if trdeg(U ) < trdeg(R[x]G ) then there exists a set S ⊆ V of full measure such that if θ ∈ S then
U does not list-resolve θ.
The proof is deferred to Sections 8.2 and 8.3. A set has full measure if its complement has measure zero.
The intuition behind Theorem 4.9 is that trdeg(R[x]G ) is the number of degrees of freedom that need to be
pinned down in order to learn the orbit of θ, and so we need this many algebraically independent constraints
(invariant polynomials). Note that we have not yet given any bound on how large the finite list might be;
we will address this in Section 4.3.
In order for Theorem 4.9 to be useful, we need a way to compute the transcendence degree of both
R[x]G and U . In what follows, we will discuss methods for both of these: in Section 4.2.1 we show how to
compute trdeg(R[x]G ) analytically, and in Section 4.2.2 we give an efficient algorithm to compute trdeg(U )
T
for a subspace U . By taking U = U≤d
this yields an efficient algorithm to determine the smallest degree d
T
at which U≤d list-resolves a generic θ (thereby answering Question 2.8 for the case of generic list recovery).
4.2.1

Computing the transcendence degree of R[x]G .

Intuitively, the transcendence degree of R[x]G is the number of parameters required to describe an orbit of
G. For finite groups, this is simply the dimension of V :
Proposition 4.10 ([Stu08] Proposition 2.1.1). If G is a finite group, trdeg(R[x]G ) = dim(V ).
12

For infinite groups, the situation may be slightly different. For instance, if SO(3) acts on V = R3 in
the standard way (rotations in 3 dimensions), then a generic orbit is a sphere, with dimension two. This
means there is only one parameter to learn, namely the 2-norm, and we expect R[x]G to have transcendence
degree 1 accordingly. On the other hand, if SO(3) acts on a rich class of functions S 2 → R (as in the S 2
registration problem; see Section 5.4) then each orbit resembles a copy of SO(3) which has dimension 3. This
is formalized in the following.
Proposition 4.11 ([Dol03] Corollary 6.2). If G is an algebraic group, then
trdeg(R[x]G ) = dim(V ) − dim(G) + min dim(Gv ),
v∈V

where Gv is the stabilizer at v of the action of G (that is, the subgroup of all g ∈ G fixing v).
An alternate approach to the transcendence degree of R[x]G uses a central object in invariant theory:
the Hilbert series (see e.g. [DK15]).
G
Definition 4.12. Let R[x]G
consisting of homogeneous invariants of
d be the subspace (over R) of R[x]
G
degree d. The Hilbert series of R[x] is the formal power series

H(t) :=

∞
X

d
dim(R[x]G
d )t .

d=0

For a given G acting on V , there is an explicit formula (Molien’s formula) for the Hilbert series:
Proposition 4.13 ([Kač94] Remark 3-1.8). Let ρ : G → GL(V ) be the representation by which G acts on
V . Then for |t| < 1, H(t) converges and we have
H(t) =

E

g∼Haar(G)

det(I − t ρ(g))−1 .

This formula is tractable to compute, even for complicated groups; see Section 5.4 for details in the case of
SO(3). Once we have the Hilbert series, it is easy to extract trdeg(R[x]G ) as follows.
Proposition 4.14. The order of the pole at t = 1 of H(t) is equal to trdeg(R[x]G ).
The proof comes from [DK15]; see Section 8.4 for more details.
For heterogeneous problems (K > 1), the transcendence degree can be computed easily from the transcendence degree of the corresponding homogeneous (K = 1) problem.
Proposition 4.15. Let G̃ be a compact group acting linearly and continuously on Ṽ , and let G = G̃K ⋊ SK
act on V = Ṽ ⊕K ⊕ ∆K as in Definition 2.2. Let R[x]G be the invariant ring corresponding to the action of
G on V , and let R[x̃]G̃ be the invariant ring corresponding to the action of G̃ on Ṽ (i.e. the K = 1 problem).
Then trdeg(R[x]G ) = K · trdeg(R[x̃]G̃ ) + K − 1.
The proof can be found in Section 8.5. Note, however, that the result is intuitively reasonable by counting
parameters. We know trdeg(R[x̃]G̃ ) is the number of parameters required to describe an orbit of G̃ acting
on Ṽ . Thus, in the heterogeneity problem we have trdeg(R[x̃]G̃ ) parameters for each of the K signals, plus
an additional K − 1 parameters for the K mixing weights (since they sum to 1).
4.2.2

Algorithm for transcendence basis of U .

In this section we prove the following.
Theorem 4.16. There is an efficient algorithm to perform the following task. Given a basis {u1 , . . . , us }
for a finite-dimensional subspace U ⊆ R[x], output a transcendence basis for U .
13

Our first ingredient is the following simple classical test for algebraic independence (see, e.g., [ER93,
BMS13] for a proof).
Definition 4.17 (Jacobian). Given polynomials f1 , . . . , fm ∈ R[x] = R[x1 , . . . , xp ], we define the Jacobian
matrix Jx (f1 , . . . , fm ) ∈ (R[x])m×p by (Jx (f1 , . . . , fm ))ij = ∂xj fi where ∂xj denotes formal partial derivative
with respect to xj .
Proposition 4.18 (Jacobian criterion for algebraic independence). Polynomials f = (f1 , . . . , fm ) are algebraically independent if and only if the Jacobian matrix Jx (f ) has full row rank (over the field R(x)).
It suffices to test the rank of the Jacobian at a generic point x.
Corollary 4.19. Fix f = (f1 , . . . , fm ). Let z ∼ N (0, Ip×p ). If f is algebraically dependent then Jx (f )|x=z
does not have full row rank. If f is algebraically independent then Jx (f )|x=z has full row rank with probability
1.
Proof. An m × p matrix has deficient row rank if and only if either m > p or every maximal square
submatrix has determinant zero. Every such determinant of Jx (f ) is a polynomial in x; if this polynomial is
not identically zero then plugging in generic values for x will not cause it to vanish.
Remark 4.20. In practice we may choose to plug in random rational values for x so that the rank computation can be done in exact symbolic arithmetic. The Jacobian test will still succeed with overwhelming
probability (provided we use a fine enough mesh of rational numbers). Also note that if we find any value
of x for which the Jacobian has full row rank, this constitutes a proof of algebraic independence.
Remark 4.21. In some cases (e.g. if the polynomials involve irrational values) it may be slow to compute the
Jacobian rank in exact symbolic arithmetic. We can alternatively compute the singular values numerically
and count how many are reasonably far from zero. This method works reliably in practice (i.e., it is
extremely clear how to separate the zero and nonzero singular values) but does not constitute a rigorous
proof of algebraic independence.
Curiously, although the Jacobian criterion gives an efficient test for algebraic dependence, it is much
harder (#P -hard) to actually find the algebraic dependence (i.e., the polynomial relation) when one exists
[Kay09].
The Jacobian criterion implies the well-known fact that the collection of algebraically independent subsets
of R[x] form a matroid ; this is called an algebraic matroid (see e.g. [Sch03]). In particular, we have the
following exchange property:
Proposition 4.22. Let I, J be finite subsets of R[x], each algebraically independent. If |I| < |J| then there
exists f ∈ J r I such that I ∪ {f } is algebraically independent.
We next note that in the task from Theorem 4.16, a transcendence basis can always be taken from the
basis {u1 , . . . , us } itself.
Lemma 4.23. Let U be a finite-dimensional subspace of R[x] with basis B = {u1 , . . . , us }. If U contains r
algebraically independent elements, then so does B.
Proof. Let B ′ ⊆ B be a maximal set of algebraically independent elements of B. If |B| < r then by the
exchange property
(Proposition 4.22) there exists v ∈ U r B ′ such that B ′ ∪ {v} is algebraically independent.
Ps
Write v = i=1 αi ui . Since B ′ is maximal, we have from the Jacobian criterion (Proposition 4.18) that
for all 1 P
≤ i ≤ s, the row vector Jx (ui ) lies in the R(x)-span of B := {Jx (b)}b∈B ′ . But this means that
Jx (v) = si=1 αi Jx (ui ) lies in the R(x)-span of B. By the Jacobian criterion this contradicts the fact that
B ′ ∪ {v} is algebraically independent.
Proof of Theorem 4.16.
Let {u1 , . . . , us } be a basis (or spanning set) for U . From above we have that the transcendence degree of U
14

is the row rank of the Jacobian Jx (u1 , . . . , us ) evaluated at a generic point x. A transcendence basis for U
is the set of ui corresponding to a maximal linearly independent set of rows
We can use the following simple greedy algorithm to construct a transcendence basis. As input, receive
a list of polynomials {u1 , . . . , us }. Initialize I = ∅. For i = 1, . . . , s, add {ui } to I if I ∪ {ui } is algebraically
independent, and do nothing otherwise. (Note that this condition can be efficiently tested by Corollary 4.19.)
Output the resulting set I.
We now show correctness. Let Ii be the set after item ui has been considered (and possibly added), and
set I0 = ∅. It suffices to show that for each i ∈ {0, . . . , s}, Ii is a maximal independent subset of {u1 , . . . , ui }.
We proceed by induction. The claim is vacuously true when i = 0. Assume it holds for i − 1. If Ii is not
a maximal independent subset of {u1 , . . . , ui }, then there exists an independent set J ⊆ {u1 , . . . , ui } with
|J| > |I|, so by the exchange property (Proposition 4.22) there exists a uj with j ≤ i such that uj ∈
/ Ii and
Ii ∪ {uj } is independent. In particular, the subset Ij−1 ∪ {uj } of Ii ∪ {uj } is independent. But the fact that
uj was not added at the (j − 1)th step implies that Ij−1 ∪ {uj } is not independent, a contradiction. So Ii is
indeed maximal.
We obtain that I = Is is a maximal independent subset of {u1 , . . . , us }, and hence by Lemma 4.23 a
transcendence basis of U .

4.3

Generic unique recovery

For list recovery problems, the following gives an explicit upper bound on the size of the list.
Theorem 4.24. Let U be a subspace of the invariant ring R[x]G . Let FG be the field of fractions of R[x]G .
If [FG : R(U )] = D < ∞ then there exists a set S ⊆ V of full measure such that for any θ ∈ S, U list-resolves
θ with a list of size ≤ D.
The proof is deferred to Section 8.2. Here R(U ) is the smallest subfield of FG containing both R and U , and
[FG : R(U )] denotes the degree of a field extension; see Section 8.2 for more details. Since [FG : R(U )] = 1
is equivalent to R(U ) = FG , we have the following criterion for unique recovery.
Corollary 4.25 (generic unique recovery). If R(U ) = FG then there exists a set S ⊆ V of full measure such
that if θ ∈ S then U resolves θ.
The intuition here is that we want to be able to learn every invariant polynomial by adding, multiplying,
and dividing polynomials from U (and scalars from R). We need θ to be generic so that we never divide by
zero in the process.
Theorem 4.26. For a finite-dimensional subspace U ⊆ R[x]G , there is an algorithm to compute the degree
of the field extension from Theorem 4.24. As input, the algorithm requires a basis for U and the ability to
compute the Reynolds operator (Definition 4.1).
We give the algorithm and the proof in Section 8.6. The algorithm uses Gröbner bases and is unfortunately
inefficient to run in practice.
Additionally, in Appendix B we present a method for proving field generation using Galois theory. There
we use it to show generic unique recovery in the case where G is a finite Abelian group and V is its regular
representation (over R). These ideas may be helpful for proving generic unique recovery in other settings.

4.4

Worst-case unique recovery

We give a sufficient algebraic condition for worst-case unique recovery:
Theorem 4.27 (worst-case unique recovery). Let U ⊆ R[x]G be a finite-dimensional subspace with basis
{f1 , . . . , fm }. If U generates R[x]G as an R-algebra (i.e. R[f1 , . . . , fm ] = R[x]G ) then U resolves every θ ∈ V .

Proof. Every element of R[x]G can be written as a polynomial in the fi (with coefficients in R). This means
the values f1 (θ), . . . , fm (θ) uniquely determine all the values f (θ) for f ∈ R[x]G and so the result follows
because R[x]G resolves every θ ∈ V (Theorem 4.4).
15

Theorem 4.28. There is an algorithm to test whether or not U generates R[x]G as an R-algebra. As input,
the algorithm requires a basis for U and the ability to compute the Reynolds operator (Definition 4.1).
We give the algorithm and the proof in Section 8.6. The algorithm uses Gröbner bases and is unfortunately
inefficient to run in practice.
If G is a finite group, it is known that R[x]G has a generating set for which all elements have degree at
most |G| (this is Noether’s degree bound ; see Theorem 2.1.4 in [Stu08]). It follows that R[x]G
≤|G| resolves
every θ ∈ V . Recall (from Section 1.4) that this is tight for MRA: degree |G| is necessary for worst-case
signals.
A precise characterization of when U resolves every θ ∈ V is (by definition) that U should be a separating
set or (equivalently) should generate a separating algebra (see [DK15] Section 2.4). The notions of generating and separating sets do not always coincide, as illustrated by Example 2.4.2 in [DK15]. Furthermore,
generating sets may require strictly higher maximum degree [Dom16].

4.5

Worst-case list recovery

We give a sufficient algebraic condition for worst-case list recovery:
Theorem 4.29 (worst-case list recovery). Let U ⊆ R[x]G be a subspace with finite basis {f1 , . . . , fm }. If
R[x]G is finitely generated as a R[f1 , . . . , fm ]-module, then U list-resolves every θ ∈ V .
In other words, this condition says that there exists a basis g1 , . . . , gs ∈ R[x]G such that every element of
R[x]G can be written as a linear combination of g1 , . . . , gs with coefficients from R[f1 , . . . , fm ]. It is sufficient
to take U to be a set of primary invariants from a Hironaka decomposition (see Section 8.4).
Proof. Since R[x]G finitely generated as an R-algebra (Theorem 4.3), if R[x]G is finitely generated as a
R[f1 , . . . , fm ]-module then it follows that (see [Sha94] Section 5.3) every h ∈ R[x]G satisfies a monic polynomial
hk + ck−1 hk−1 + · · · + c1 h + c0 = 0

with ci ∈ R[f1 , . . . , fm ]. Letting h1 , . . . , hs be generators for R[x]G (as an R-algebra), we have that the values
f1 (θ), . . . , fm (θ) determine a finite set of possible values for h1 (θ), . . . , hs (θ), each of which determines (at
most) one orbit for θ.

5

Examples

In this section we work out some specific examples, determining the degree at which generic list recovery is
possible using the methods of Section 4.2. (We focus on generic list recovery because our algorithms for the
other recovery criteria are unfortunately too slow even for quite small examples.) We obtain several recovery
theorems for problems such as MRA and cryo-EM within finite ranges of parameters where we have verified
the Jacobian criterion using a computer, and beyond these parameter ranges, we state conjectural patterns.
The following themes emerge in the examples studied in this section. First, we see that many problems
are possible at degree 3, which is promising from a practical standpoint. Second, we do not encounter any
unexpected algebraic dependencies, and so we are able to show that heuristic parameter-counting arguments
are correct. In particular, we see that if there are enough linearly independent invariants, there are also
enough algebraically independent invariants.

5.1

Learning a bag of numbers

Let G be the symmetric group Sp acting on V = Rp by permutation matrices. The invariant ring consists of
the symmetric polynomials, which are generated by the elementary symmetric polynomials e1 , . . . , ep where
ei has degree i. Worst-case unique recovery is possible at degree p since R[x]G
≤p generates the full invariant
ring. Furthermore, degree p is actually required, even for generic list recovery. This is because any invariant
16

of degree ≤ p − 1 can be expressed as a polynomial in e1 , . . . , ep−1 and thus trdeg(R[x]G
≤p−1 ) = p − 1. So
this problem has a steep sample complexity of order σ 2p .

5.2

Learning a rigid body

Let G be the rotation group SO(p) acting on the matrix space Rp×m by left multiplication. We imagine
the columns of our matrix as vertices defining a rigid body; thus we observe random rotations of this rigid
body (with vertices labeled) plus noise. Let U ∈ Rp×m be such a matrix signal. With O(σ 4 ) samples,
we can estimate the degree-2 Gram matrix U ⊤ U ; taking a Cholesky factorization, we recover U up to left
action by an element of the larger group O(p). Thus we recover the rigid body up to a reflection ambiguity,
demonstrating list recovery (with a list of size 2). Surprisingly, assuming m ≥ p, we do not uniquely resolve
a generic signal until degree p, where with O(σ 2p ) samples we can estimate a p × p minor of U , which is a
degree-p invariant that changes sign under reflection.
The impossibility of unique recovery until degree p is a consequence of the “first fundamental theorem”
for the special orthogonal group SO(p), which asserts that the invariant ring is generated by the entries of
the Gram matrix U ⊤ U together with the p × p minors of U (see for instance [Kač94]); thus the invariants of
degree 3, . . . , p − 1 carry no information in addition to the degree-2 invariants.

5.3

Multi-reference alignment (MRA)

Recall that this is the case of G = Z/p acting on V = Rp by cyclic shifts. It is already known that for the
basic MRA problem (without projection or heterogeneity), generic unique recovery is possible at degree 3 for
any p [BRW17]. The methods of Section 4.2 confirm the weaker result that generic list recovery is possible
at degree 3 (at least for the values of p that we tested). Note the stark contrast in difficulty from the case
of the full symmetric group G = Sp above.
Remark 5.1. This result for MRA is actually a special case of a more general phenomenon. Let G be any
finite group and let V be the regular representation i.e. the space of functions f : G → R with the action
(g · f )(h) = f (g −1 h). (Note that for G = Z/p this is precisely the MRA problem.) It is known [Kak09]
that for this setup, the triple correlation (a collection of degree-3 invariants) is sufficient to resolve a generic
signal, and thus generic unique recovery is possible at degree 3. In Appendix B we give a short proof for the
special case where the group is Abelian; our proof illustrates a method based on Galois theory which may
be useful to prove generic unique recovery in other settings.
We can also verify that for MRA with p ≥ 3, generic list recovery is impossible at degree 2. This follows
from Theorem 4.9 because trdeg(R[x]G ) = p (since G is finite) but the number of algebraically independent
invariants of degree ≤ 2 is at most ⌊p/2⌋+1. We can see this as follows. A basis for the invariants of degree ≤ 2
is {R(x1 ), R(x21 ), R(x1 x2 ), R(x1 x3 ), . . . , R(x1 xs )} with s = ⌊p/2⌋+1. Here R denotes the Reynolds operator,
which averages over cyclic shifts of the variables. For instance, R(x1 x2 ) = p1 (x1 x2 +x2 x3 +x3 x4 +· · ·+xp x1 ).
Note that the basis above has size ⌊p/2⌋ + 2 but there is an algebraic dependence within it because R(x1 )2
can be written in terms of the other basis elements. The claim now follows.
Generic list recovery is possible at degree 1 for p = 1 and at degree 2 for p = 2. (This is true even for
worst-case unique recovery; recall from Section 4.4 that degree |G| is always sufficient for this.)
We now move on to variants of the MRA problem.
5.3.1

MRA with projection

We now consider MRA with a projection step. We imagine that the coordinates of the signal are arranged
in a circle so that G acts by rotating the signal around the circle. We then observe a projection of the circle
onto a line so that each observation is the sum of the two entries lying “above” it on the circle. This is
intended to resemble the tomographic projection in cryo-EM. We formally define the setup as follows.

17

Problem 5.2 (MRA with projection). Let p ≥ 3 be odd. Let V = Rp and G = Z/p acting on V by cyclic
shifts. Let q = (p − 1)/2 and W = Rq . Let Π : V → W be defined by
Π(v1 , . . . , vp ) = (v1 + vp , v2 + vp−1 , . . . , v(p−1)/2 + v(p+3)/2 ).
We call the associated generalized orbit recovery problem (Problem 2.3) MRA with projection. (We consider
the homogeneous case K = 1.)
Note that since p is odd, there is one entry v(p+1)/2 which is discarded by Π. The reason we consider the
odd-p case rather than the seemingly more elegant even-p case is because generic list recovery is actually
impossible in the even-p case. This is because the signals θ and θ + (c, −c, c, −c, . . .) cannot be distinguished
from the samples, even if there is no noise.
Restricting now to odd p, note that we cannot hope for generic unique recovery because it is impossible to
tell whether the signal is wrapped clockwise or counterclockwise around the circle. In other words, reversing
the signal via (θ1 , . . . , θp ) 7→ (θp , . . . , θ1 ) does not change the distribution of samples. We can still hope for
generic list recovery, hopefully with a list of size exactly 2. This degeneracy is analogous to the chirality
issue in cryo-EM: it is impossible to determine the chirality of the molecule (i.e. if the molecule is reflected
about some 2-dimensional plane through the origin, this does not change the distribution of samples).
It appears that, as in the basic MRA problem, generic list recovery is possible at degree 3. We proved
this for p up to 21 by checking the Jacobian criterion (see Section 4.2) on a computer, and we conjecture
that this trend continues.
Conjecture 5.3. For MRA with projection, for any odd p ≥ 3, generic list recovery is possible at degree 3.
Note that generic list recovery is impossible at degree 2 because the addition of the projection step to basic
T
MRA can only make it harder for U≤d
to list-resolve θ.
5.3.2

Heterogeneous MRA

We now consider heterogeneous MRA, i.e. the generalized orbit recovery problem (Problem 2.3) with G̃ = Z/p
acting on Ṽ = Rp by cyclic shifts, K ≥ 2 heterogeneous components, and no projection (i.e., Π is the identity).
We will see that generic list recovery is possible at degree 3 provided that p is large enough compared
to K. First note that the number of degrees of freedom to be recovered is trdeg(R[x]G ) = Kp + K − 1 (see
Propositions 4.10 and 4.15). Let us now count the number of distinct entries of Td (x) for d ≤ 3. Note that
Td (x) is symmetric (under permutations of indices) but we also have additional symmetries given by cyclic
shifts, e.g. (T3 (x))i,j,k = (T3 (x))i+c,j+c,k+c where c is an integer and the sums i + c, j + c, k + c are computed
modulo p. One can compute that T1 (x) has 1 distinct entry, T2 (x) has ⌊p/2⌋ + 1 distinct entries, and T3 (x)
has p + ⌈(p − 1)(p − 2)/6⌉ distinct entries. The total number of distinct entries is
U := p + 2 + ⌊p/2⌋ + ⌈(p − 1)(p − 2)/6⌉.
By Theorem 4.9, list recovery is impossible when U < Kp + K − 1. By testing the Jacobian condition, we
observe that the converse also appears to hold. We tested this up to K = 15 and up to the corresponding
critical p value.
Conjecture 5.4. For heterogeneous (K ≥ 2) MRA, generic list recovery is possible at degree 3 precisely if
U ≥ Kp + K − 1. This condition on U can be stated more explicitly as follows:
• K = 2 requires p ≥ 1.
• K = 3 requires p ≥ 12.
• K = 4 requires p ≥ 18.
• Each K ≥ 5 requires p ≥ 6K − 5.
18

Recent work [BBLS17] also studies the heterogeneous MRA problem. Similarly to the present work, they
apply the method of moments and solve a polynomial system of equations in order to recover the signals.
To solve the system they use an efficient heuristic method that has no provable guarantees but appears to
work well in practice. Their experiments suggest that if the signals have i.i.d. Gaussian entries, this method
√
succeeds only when (roughly) K ≤ p instead of the condition (roughly) K ≤ p/6 that we see above (and
that [BBLS17] also identified based on parameter-counting). Exploring this discrepancy is an interesting
direction for future work.
One question of particular interest is whether this example evinces a statistical-computational gap,
√
whereby all polynomial-time methods fail to succeed once K exceeds p. Some evidence for why we might
expect this is as follows. Recent work on tensor decomposition [MSS16] gives a polynomial-time algorithm
PN
p
to decompose a third order tensor of the form i=1 a⊗3
i + E where ai ∈ R are i.i.d. from the unit sphere
1.5
and E is noise, provided N ≤ p (up to factors of log p). The heterogeneous MRA problem can be cast as
such a tensor decomposition problem with N = Kp components ai ; the components are the p cyclic shifts
of each of the K signals. Although these ai are not independent, we expect that if the signals are random
then the ai are “random enough” for the same tensor decomposition result to hold, which exactly yields the
√
condition K ≤ p (up to factors of log p).

5.4

S 2 registration

Recall that this is the case where the signal θ is a real-valued function defined on the unit sphere S 2 in R3 .
The formal setup is as follows.
Let G = SO(3). For each ℓ = 0, 1, 2, . . . there is an irreducible representation Vℓ of SO(3) of dimension
2ℓ + 1. These representations are of real type, i.e. they can be defined over the real numbers so that
Vℓ = R2ℓ+1 . Let F be a finite subset of {0, 1, 2, . . .} and consider the orbit recovery problem in which G acts
on V = ⊕ℓ∈F Vℓ .
As intuition for the above setup, Vℓ is a basis for the degree-ℓ spherical harmonic functions S 2 → R
defined on the surface of the unit sphere S 2 ⊆ R3 . The spherical harmonics are a complete set of orthogonal
functions on the sphere and can be used (like a “Fourier series”) to represent a function S 2 → R. Thus the
signal θ ∈ V can be thought of as a function on the sphere, with SO(3) acting on it by rotating the sphere.
See Appendix A for details on spherical harmonics.
The primary case of interest is F = {1, . . . , F } for some F (the number of “frequencies”). We will see
that generic list recovery is possible at degree 3 so long as F ≥ 10. We will see that it is convenient to not
include 0 ∈ F , but we now justify why this is without loss of generality. V0 is the trivial representation, i.e.
the 1-dimensional representation on which every group element acts as the identity. In the interpretation of
spherical harmonics, the V0 -component is the mean value of the function over the sphere. We claim that the
S 2 registration problem with 0 ∈ F can be easily reduced to the problem with F ′ = F r {0}. This is because
the V0 -component is itself a degree-1 invariant; given the value of this invariant, one can subtract it off and
reduce to the case without a V0 -component (i.e. the case where the function on the sphere is zero-mean).
Thus we have that e.g. generic list recovery is possible (at a given degree) for F if and only if it is possible
for F ′ .
Using Proposition 4.11 we compute that trdeg(R[x]G ) = p − p′ , where
X
p = dim(V ) =
(2ℓ + 1)
ℓ∈F

and


 0 ℓmax = 0
2 ℓmax = 1
where ℓmax = max ℓ.
p′ =
ℓ∈F

3 ℓmax ≥ 2
After all, V0 is the trivial representation on the 1-dimensional vector space, with 3-dimensional stabilizer
SO(3), and V1 is the standard 3-dimension representation of SO(3) on R3 by rotations, which yields a onedimensional SO(2) stabilizer at each nonzero point. When ℓmax ≥ 2, the representation V is known to have
zero-dimensional stabilizer at some points (see e.g. [Ete96]).
19

In the following we restrict to the case 0 ∈
/ F for simplicity (but recall that this is without loss of
G
generality). There are therefore no degree-1 invariants, i.e. R[x]G
1 is empty. By Theorem 4.9, if dim(R[x]2 ) +
G
G
dim(R[x]3 ) < trdeg(R[x] ) then generic list recovery is impossible at degree 3; this rules out generic list
recovery for F = {1, 2, . . . , F } when F ≤ 9. (We will see below how to compute dim(R[x]G
d ).) Beyond this
threshold, the situation is more hopeful:
Theorem 5.5. If F = {1, 2, . . . , F } and 10 ≤ F ≤ 16 then the degree-3 method of moments achieves generic
list recovery.
This theorem is based on computer verification of the Jacobian criterion for 10 ≤ F ≤ 16 using exact
arithmetic in a finite extension of Q. This result lends credence to the following conjecture.
Conjecture 5.6. Consider the S 2 registration problem with 0 ∈
/ F . We conjecture the following.
G
G
• Generic list recovery is possible at degree 3 if and only if dim(R[x]G
2 ) + dim(R[x]3 ) ≥ trdeg(R[x] )
G
G
(where trdeg(R[x] ) is computed above and dim(R[x]d ) can be computed from Proposition 5.7 below).

• In particular, if F = {1, 2, . . . , F } then generic list recovery is possible at degree 3 if and only if F ≥ 10.
The reason it is convenient to exclude the trivial representation is because it simplifies the parametercounting: if we use the trivial representation then we have a degree-1 invariant f and so there is an algebraic
relation between the degree-2 invariant f 2 and the degree-3 invariant f 3 .
We now discuss how to compute dim(R[x]G
d ). Using the methods in Section 4.6 of [DK15], we can give a
formula for the Hilbert series of R[x]G ; see Section 9.1. However, if one wants to extract a specific coefficient
dim(R[x]G
d ) of the Hilbert series, we give an alternative (and somewhat simpler) formula:
Proposition 5.7. Consider S 2 registration with frequencies F . Let χd (φ) : R → R be defined recursively by
χ0 (φ) = 1,
χ1 (φ) =

X

ℓ∈F

"

1+2

ℓ
X

m=1

#

cos(m φ) , and

d

χd (φ) =
Then we have
dim(R[x]G
d) =

1X
χ1 (iφ)χd−i (φ).
d i=1
1
π

Z

π

0

(1 − cos φ)χd (φ) dφ.

We give the proof in Section 9.2. Additionally, in Appendix A.6 we give explicit formulas for the invariants
(up to degree 3), which yields a combinatorial analogue of Proposition 5.7 (up to degree 3).

5.5

Cryo-EM

We adapt the following simple model for the cryo-EM reconstruction problem. We will use properties of the
3-dimensional Fourier transform, including the projection-slice theorem; see e.g. [Osg07] for a reference.
The signal is a 3-dimensional molecule, which we can think of as encoded by a density function f : R3 → R.
The 3-dimensional Fourier transform of f is fb : R3 → C given by
Z ∞Z ∞Z ∞
b
f (kx , ky , kz ) =
e−2πi(xkx +yky +zkz ) f (x, y, z) dx dy dz.
(1)
−∞

−∞

−∞

It is sufficient to learn fb because we can then recover f using the inverse Fourier transform. SO(3) acts
on the molecule by rotating it in 3-dimensional space (keeping the origin fixed). When f is rotated in
20

(x, y, z) coordinates, fb is also rotated in (kx , ky , kz )-coordinates by the same rotation. Each observation is
a 2-dimensional image obtained by first rotating f by a random element of SO(3) and then projecting f
parallel to the z axis. Specifically, the projection of f is fproj : R2 → R given by
Z ∞
fproj(x, y) =
f (x, y, z) dz.
−∞

By the projection-slice theorem, the 2-dimensional Fourier transform of fproj is equal to the slice fbslice : R2 →
C given by
fbslice (kx , ky ) = fb(kx , ky , 0).

Thus we think of fb as our unknown signal with SO(3) acting by rotation, and with post-projection which
reveals only the slice of fb lying in the plane kz = 0.
This does not yet conform to our definition of a (generalized) orbit recovery problem because the signal
needs to lie in a finite-dimensional real vector space. Instead of thinking of fb as a function on R3 , we fix a
finite number S of nested spherical shells in R3 , each of different radius and all centered at the origin. We
consider only the restriction of fb to these shells. We fix a finite number F of frequencies and on each shell
we expand fb (restricted to that shell) in the basis of spherical harmonics, truncated to 1 ≤ ℓ ≤ F . (As in S 2
registration, we can discard the trivial representation ℓ = 0 without loss of generality, and it is convenient
to do so.) Being the Fourier transform of a real-valued function, fb satisfies
fb(−kx , −ky , −kz ) = fb(kx , ky , kz )

(2)

(see (1)) and so we can use a particular basis Hℓm of spherical harmonics for which the expansion coefficients
are real; see Appendix A. We have now parametrized our signal by a finite number of real values θsℓm with
1 ≤ s ≤ S, 1 ≤ ℓ ≤ F , and −ℓ ≤ m ≤ ℓ. In particular, the restriction of fb to shell s has expansion
X
X
θsℓm Hℓm .
1≤ℓ≤F −ℓ≤m≤ℓ

SO(3) acts on each shell by 3-dimensional rotation; see Section A for the details of how SO(3) acts on spherical
harmonics. The projection Π reveals only the values on the equator z = 0 (or in spherical coordinates,
θ = π/2) of each shell. Using again the property (2), the output of Π on each shell has an expansion with
real coefficients in a particular finite basis hm ; see Section A.4.
Remark 5.8. There are various other choices one could make for the basis in which to represent the
(Fourier transform of the) molecule. Each of our basis functions is the product of a spherical harmonic and
a radial delta function (i.e. a delta function applied to the radius, resulting in a spherical shell). Another
common basis is the Fourier–Bessel basis (used in e.g. [LBB+ 17]) where each basis function is the product
of a spherical harmonic and a radial Bessel function. More generally we can take the product of spherical
harmonics with any set of radial basis function. It turns out that the choice of radial basis is unimportant
because the resulting problem will be isomorphic to our case (spherical shells) and so the same results hold.
We now present our results on the above cryo-EM model. We focus on identifying the regime of parameters
for which generic list recovery is possible at degree 3. Again using Proposition 4.11, we have for F ≥ 2:
trdeg(R[x]G ) = dim(V ) − 3 = S

F
X
ℓ=1

(2ℓ + 1) − 3 = S(F 2 + 2F ) − 3

(3)

where again we have a zero-dimensional stabilizer.
T
In Appendix A we give an explicit construction of the invariant polynomials in U≤3
. By testing the
Jacobian criterion in exact arithmetic on small examples, we arrive at the following theorem:
Theorem 5.9. Consider the homogeneous (K = 1) cryo-EM problem with S shells and F frequencies.
21

• If S = 1 then for any F ≥ 2, generic list recovery is impossible at degree 3.
• If 2 ≤ S ≤ 4 and 2 ≤ F ≤ 6, the degree-3 method of moments achieves generic list recovery.
The first assertion results from a simple counting argument: there are fewer invariants at degree ≤ 3 than
degrees of freedom. The second part is by confirming that the Jacobian of the invariants has rank equal to
trdeg(R[x]G ), through computer-assisted exact arithmetic over an appropriate finite extension of Q.
In floating-point arithmetic, we have further verified that the Jacobian appears to have appropriate rank
for 2 ≤ S ≤ 10 and 2 ≤ F ≤ 10, leading us to conjecture the following:
Conjecture 5.10. If S ≥ 2 then the degree-3 method of moments achieves generic list recovery (regardless
of F ).
T
Intuitively, when there is a single shell (S = 1) there are simply not enough invariants in U≤3
. However,
when S ≥ 2, the number of invariants increases dramatically due to cross-terms that involve multiple shells.

5.5.1

Heterogeneous cryo-EM

We now consider heterogeneous cryo-EM (K ≥ 2). By combining (3) with Proposition 4.15 we can compute
trdeg(R[x]G ). Based on testing the Jacobian criterion on small examples, we conjecture that the degree-3
method of moments achieves generic list recovery if and only if dim(U2T ) + dim(U3T ) ≥ trdeg(R[x]G ). In
T
other words, we expect no unexpected algebraic dependencies among U≤3
. (Recall that there are no degree-1
invariants since we are not using the trivial representation ℓ = 0).
In Section A.6 we give a conjectured formula for the exact value of dim(U2T )+dim(U3T ) for all S ≥ 1, F ≥ 2.
As a result we can determine for any given S ≥ 1 and F ≥ 2, the exact condition on K for which we believe
generic list recovery is possible. For S and F large, this condition is approximately K ≤ S 2 /4.

6

Open questions

We leave the following as directions for future work.
1. Our methods require testing the rank of the Jacobian on a computer for each problem size. It would
be desirable to have analytic results for e.g. (variants of) MRA in any dimension p.
2. We have given an efficient test for whether generic list recovery is possible, but have not given a
similarly efficient test for generic unique recovery. In cases where unique recovery is impossible, it
would be nice to give a tight bound on the size of the list; for instance, for MRA with projection, we
conjecture that the list has size exactly 2 (due to “chirality”), but we lack a proof for this fact. Our
algorithms for testing generic unique recovery are based on Gröbner bases, the calculation of which is
known to be computationally hard in the worst case [Huỳ86]. Unfortunately, the algorithms we have
proposed are also extremely slow in practice, though a faster implementation may be possible.
3. Our procedure for recovering θ from the samples involves solving a polynomial system of equations.
While solving polynomial systems is NP-hard in general, the fact that the polynomials used in the orbit
recovery problem have special structure leaves open the possibility of finding an efficient (polynomial
time) method with rigorous guarantees. Possible methods include tensor decomposition [PWB+ 17]
and non-convex optimization [BBLS17].
4. We have addressed the statistical limits of orbit recovery problems. However, prior work has indicated
the presence of statistical-to-computational gaps in related synchronization problems [PWBM16a], and
we expect such gaps to appear in orbit recovery problems too. As discussed in Section 5.3.2, the results
of [BBLS17] suggest a possible gap of this kind for heterogeneous MRA.

22

7

Proofs for Section 3: statistical results

We first prove Theorem 3.2. This theorem in fact holds for more general mixture problems, not merely those
arising from the orbit recovery problems defined in Problem 2.3. For convenience, we will state and prove
the theorem in its general form.
Problem 7.1 (mixture recovery). Let V = Rp , and let Θ ⊂ V be compact. For θ ∈ Θ, let µθ be a measure
on Rp whose support is contained in the unit ball, and assume the map θ 7→ µθ is continuous with respect to
the weak topology. Let D be a known distribution on R with finite moments of all orders, and let σ ≥ 1. For
i ∈ [n] = {1, 2, . . . , n}, we observe
yi = xi + σξi ,
where xi ∼ µθ and the entries of ξi are independently drawn from D. The goal is to estimate θ.
Write Pθ for the distribution arising from the parameter θ, and let Eθ be expectation with respect to
this distribution. We denote by Enθ the expectation taken with respect to n i.i.d. samples from Pθ . Where
there is no confusion, we also write Eθ for expectation with respect to the distribution µθ .
We require that µθ have bounded support; the requirement that it be supported in the unit ball is
for normalization purposes only. We assume throughout that σ ≥ 1. The following definiton gives the
generalization of Definition 3.1 to the mixture recovery problem.
Definition 7.2. Given a positive integer d and θ ∈ V , the order-d matching set Mθ,d is the set consisting of
all φ ∈ V such Eθ [x⊗k ] = Eφ [x⊗k ] for k = 1, . . . , d, where Eζ represents expectation with respect to x ∼ µζ .
Problem 7.1 generalizes Problem 2.3 by allowing the random vector xi to arise from more general mixtures
than those arising from group actions. Note that when the mixtures do arise from a generalized orbit recovery
problem, i.e., when xi = Π(gi · θki ), where gi and ki are distributed as in Problem 2.3, then Definition 7.2
reduces to Definition 3.1.
Having made these definitions, our goal in this section is to show that Theorem 3.2 holds word-for-word
in the setting of mixture recovery. To do so, we show that entries of the moment tensors Eθ [x⊗k ] can be
estimated on the basis of O(σ 2k ) samples from Pθ .

7.1

Estimation of moments

Our estimators will be based on a system of orthogonal univariate polynomials under the measure corresponding to D. Let H0 (x) = 1, and for k ≥ 1, define
Hk (x) = xk −

k−1
X
Eξ∼D [ξ k Hj (ξ)]
j=0

Eξ∼D [Hj (ξ)2 ]

Hj (x) .

It is easy to check that these polynomials are orthogonal under the inner product given by hf, gi =
Eξ∼D [f (ξ)g(ξ)] and that the polynomials H0 , . . . , Hk form a basis for the space of polynomials of degree
at most k. We denote them by Hk because they coincide with the classic Hermite polynomials when D is
Gaussian.
Like the Hermite polynomials, they satisfy the identity
Eξ∼D [Hk (x + ξ)] = xk .
Indeed, we can expand Hk (x + ξ) in the basis of the orthogonal polynomials as
Hk (x + ξ) =

k
X
j=0

23

αj (x)Hj (ξ) ,

(4)

where αj (x) is a polynomial in x of degree at most k−j. Since Hj (ξ) has zero mean for j ≥ 1 by construction,
we obtain
E[Hk (x + ξ)] = α0 (x) ,
and since Hk is a monic polynomial of degree k, we must have α0 (x) = xk .
We briefly review multi-index notation.
Definition 7.3. Q
A p-dimensional multi-index is a tuple α = (α1 , . . . , αp ) of nonnegative integers. For
α
p
x ∈ Rp , let xα = j=1 xj j .
Pp
For any multi-index α, we write |α| = j=1 αj . Given independent samples y1 , . . . , yn from Pθ , consider
the estimate for Ex∼µθ [xα ] given by
n

α :=
xf

α is unbiased.
We first show that xf

p

1 X Y αj
σ Hαj (σ −1 yi ) .
n i=1 j=1

α ] = E [xα ].
Lemma 7.4. For all θ ∈ Θ, Enθ [xf
θ

α is a sum of i.i.d. terms, it suffices to prove the claim for a single sample. By (4),
Proof. Since xf

Eθ

p
hY

j=1

h
i
σ αj Hαj (σ −1 yi ) = E
x∼µθ

= E

x∼µθ

= E

x∼µθ

E

ξ1 ,...,ξp ∼D

p
hY

E

ξj ∼D

j=1
p
hY



p
Y

j=1

i
σ αj Hαj (σ −1 (xj + σξj )) x

i
σ αj Hαj (σ −1 xj + ξj ) x

i
σ αj (σ −1 xj )αj = Eθ [xα ] .

j=1

It remains to bound the variance.
α] ≤
Proposition 7.5. For any multi-index α, there exists a constant cα such that for all θ ∈ Θ, Varθ [xf
−1 2|α|
cα n σ .

α is a sum of i.i.d. terms, it suffices to prove the claim for n = 1. Given a multi-index α, let
Proof.QSince xf
p
cα = j=1 supxj ∈[−1,1] Eξj ∼D [Hαj (xj + ξj )2 ], and note that cα is independent of σ. We obtain
α] ≤
Varθ [xf
E

x∼µθ

≤

p
hY

sup

E

ξ ∼D
j=1 j
p
Y

E



x:kxk≤1 j=1 ξj ∼D

≤ cα σ 2|α| ,

i
σ 2αj Hαj (σ −1 xj + ξj )2 x


 2αj
σ Hαj (σ −1 xj + ξj )2

as claimed.
Finally, we apply the “median-of-means” trick [NY83] to show that we can combine the estimators defined
above to obtain estimates for the moment tensors Eθ [x⊗k ] for k ≤ d which are close to their expectation
with high probability.

24

Proposition 7.6. Let y1 , . . . , yn be i.i.d. samples from Pθ . For any degree d and accuracy parameter δ,
α = x
α (y , . . . , y ) for all α with |α| ≤ d such that with probability at least 1 − δ,
c
there exist estimators xc
1
n
r
log(p/δ)
α
d
α
c
max |Eθ [x ] − x | ≤ cd σ
,
α:|α|≤d
n
for some constant cd .

Proof. Split the samples into m subsamples of equal size, for some m to be specified, and for each α construct
α, . . . , x
α on the basis of the m subsamples. (We assume for convenience that m divides
f
the m estimators xf
m
1
α, . . . , x
α
α.
c
f
n.) Let x be the median of xf
m
1
Chebyshev’s inequality together with Proposition 7.5 implies that there exists a constant cd such that,
for each j = 1, . . . , m and multi-index α,
r i
h
m
α
d
α
Pr |xf
≤ 1/4 ,
j − Eθ [x ]| > cd σ
n

α, . . . , x
α are independent, a standard concentration argument shows that
f
and since the estimators xf
m
1
r i
h
m
α − E [xα ]| > c σ d
≤ e−m/4 .
Pr |xc
θ
d
n

By a “stars-and-bars” counting argument [Fel68], there are p+d
multi-indices α satisfying |α| ≤ d, so taking
d
a union bound over all choices of α yields
r
m
cα | ≤ cd σ d
max |Eθ [xα ] − x
α:|α|≤d
n


−m/4
with probability at least 1 − p+d
. Choosing m = 4 log( p+d
d e
d /δ) and taking cd sufficiently large in
the statement of the theorem yields the claim.

Note that the constant cd in the statement of Proposition 7.6 can be made explicit, given knowledge of
the distribution D.

7.2

Robust solutions to polynomial systems

We now show that approximate knowledge of the moment tensors Eθ [x⊗k ] for k = 1, . . . , d suffices to
approximately recover θ.
Lemma 7.7. For all θ ∈ Θ and ε > 0, there exists a ε′ > 0 such that, if φ ∈ Θ satisfies maxk≤d kEθ [x⊗k ] −
Eφ [x⊗k ]k∞ < ε′ , then there exists a τ ∈ Mθ,d such that kφ − τ k < ε.
Proof. We employ a simple compactness argument. Consider the set F = {φ ∈ Θ : ∀ τ ∈ Mθ,d kφ − τ k ≥ ε}.
Since Θ is compact, so is F . Set
ε′ = min max kEθ [x⊗k ] − Eφ [x⊗k ]k∞ .
φ∈F k≤d

⊗k

⊗k

Clearly if maxk≤d kEθ [x ] − Eφ [x ]k∞ < ε′ for some φ ∈ Θ, then there exists a τ ∈ Mθ,d such that
kφ − τ k < ε, so it remains to check that ε′ > 0.
Since θ 7→ µθ is continuous with respect to the weak topology and µθ is supported on a compact set
for all θ ∈ Θ, the moment map θ 7→ Eθ [x⊗k ] is also continuous for all k ≤ d. If φ ∈ F , then in particular
φ∈
/ Mθ,d, so there exists a k ≤ d for which Eθ [x⊗k ] 6= Eφ [x⊗k ]. Therefore ε′ > 0, as desired.
Lemma 7.7 is simply stating that the function φ 7→ minτ ∈Mθ,d kφ − τ k is continuous at θ with respect to
the topology induced by the moment maps. Note that, for generic θ when µθ arises from an orbit recovery
problem, the moment map will be continuously differentiable with a nonsingular Jacobian, so the inverse
function theorem implies ε′ can be taken to be Ω(ε). In general, however, the dependence could be worse.
25

7.3

Proof of Theorem 3.2

cα as in Proposition 7.6, and let
Construct the estimators x
(
)
r
log(p/δ)
α | ≤ c σd
cn = φ ∈ Θ : max |Eφ [xα ] − xc
M
d
n
α:|α|≤d

cn and that, for all
Applying Proposiiton 7.6, we have with probability at least 1 − δ that Mθ,d ⊆ M
c
φ ∈ Mn ,
r
log(p/δ)
⊗k
⊗k
α
α
d
.
max kEφ [x ] − Eθ [x ]k = max |Eφ [x ] − Eθ [x ]| ≤ 2cd σ
k≤d
n
α:|α|≤d
q
By Lemma 7.7, there exists an ε′θ,ε such that, as long as 2cd σ d log(p/δ)
< ε′θ,ε , then with probability at
n
cn ⊆ Mε .
least 1 − δ, we have the desired inclusion M
θ,d

Therefore taking n > (2cd /ε′θ,ε )2 log(p/δ)σ 2d = cθ,ε,d log(1/δ)σ 2d suffices.

7.4

Information geometry of gaussian mixtures

In this section, we establish an upper bound on the Kullbeck-Leibler divergence between different gaussian
mixtures, which we denote by D(· k ·).
The proof follows the outline used in [BRW17], based off a technique developed in [LNS99, CL11].
Proposition 7.8. Let θ, φ ∈ Θ, let the distribution D be N (0, 1) for some σ ≥ 1, and let d be any positive
integer.
There exist universal constants C and c such that if Eθ [x⊗k ] = Eφ [x⊗k ] for k ≤ d − 1, then
D(Pθ k Pφ ) ≤ C

(cσ)−2d
.
d!

Proof. We first establish the claim when d = 1. Note that the condition on the moment tensors is vacuous
in this case. By the convexity of the divergence,
D(Pθ k Pφ ) ≤

2
′
2
E D(N (x, σ ), N (x , σ )) =
x∼µ
θ

x′ ∼µφ

E
x∼µ

θ

x′ ∼µφ

kx − x′ k2
≤ 2σ −2 ,
2σ 2

where in the last step we used the fact that x and x′ lie in the unit ball almost surely.
Now, assume d > 1, so in particular Eθ [x] = Eφ [x]. Denote their common mean by v. For ζ ∈ {θ, φ}
denote by µζ the distribution of x − v when x ∼ µζ , and let Pζ denote distribution of y when y = x + ξ
for x ∼ µζ and ξ ∼ N (0, σ 2 I). Since this transformation is a deterministic bijection, the data processing
inequality implies D(Pθ k Pφ ) = D(Pθ k Pφ ).
Note that Eµθ [x] = Eµθ [x] = 0 and Eµθ [x⊗k ] = Eµφ [x⊗k ] for k ≤ d − 1. Hence without loss of generality
we can reduce to the case where µθ and µφ are both centered and are supported in a ball of radius 2.
We bound the χ2 -divergence between Pθ and Pφ . Let f be the density of a standard p-dimensional
Gaussian and for ζ ∈ Θ, let fζ be the density of Pζ , which can be written explicitly as
1

fζ (y) = Ex∼µζ σ −p f (σ −1 (y − x)) = σ −p f (σ −1 y)Ex∼µζ e− 2σ2 (x

2

−2y ⊤ x)

.

Since kxk ≤ 2 almost surely with respect µζ , Jensen’s inequality implies that
1

fζ (y) ≥ σ −p f (σ −1 y)e− 2σ2 (4−2y

⊤

Eζ x)

Recall that the χ2 divergence is defined by
χ2 (Pθ , Pφ ) =

Z

(fθ (y) − fφ (y))2
dy .
fθ (y)
26

2

= σ −p f (σ −1 y)e− σ2 .

(5)

Applying (5) to the denominator, expanding the definitions of fθ and fφ , and applying a change of variables
yields
Z
2
⊤
2
⊤
1
1
2
χ2 (Pθ , Pφ ) ≤ e2/σ
(Eθ e− 2σ2 (x −2y x) − Eφ e− 2σ2 (x −2y x) )2 σ −p f (σ −1 y) dy
Z
⊤
−1
−1
2
⊤
−1
−1
2
1
1
2/σ2
=e
(Eθ ey (σ x)− 2 kσ xk − Eφ ey (σ x)− 2 kσ xk )2 f (y) dy
2

= e2/σ E(Eθ eg

⊤

(σ−1 x)− 12 kσ−1 xk2

− Eφ eg

⊤

(σ−1 x)− 12 kσ−1 xk2 2

g ∼ N (0, I) .

) ,

(6)

Given ζ, ζ ′ ∈ Θ, let x ∼ µζ and x′ ∼ µζ ′ be independent. Then interchanging the order of expectation
and using the expression for the moment generating function of a standard Gaussian random variable, we
obtain
x⊤ x′
⊤
−1
′
−1
2
−1 ′ 2
1
Eζ,ζ ′ Eg eg (σ (x+x ))− 2 (kσ xk +kσ x k ) = Eζ,ζ ′ e σ2 .
Applying this expression to (6) after expanding the square produces

2 
χ2 (Pθ , Pφ ) ≤ e2/σ  E e
x∼µ

x⊤ x′
σ2

θ

−2 E e
x∼µ
θ

x′ ∼µθ

x′ ∼µφ

x⊤ x′
σ2

+

E e

x⊤ x′
σ2

x∼µφ
x′ ∼µφ




,

where in each expectation the random variables x and x′ are independent. Since µθ and µφ are compactly
supported, Fubini’s theorem implies we can expand each term as a power series and interchange expectation
and summation to produce


∞
−2k
2 X σ
 E (x⊤ x′ )k − 2 E (x⊤ x′ )k + E (x⊤ x′ )k 
χ2 (Pθ , Pφ ) ≤ e2/σ
x∼µφ
x∼µθ
x∼µθ
k!
′
′
′
k=0

= e2/σ
= e2/σ
= e2/σ

2

2

2

∞
X

k=0
∞
X

k=0
∞
X

k=d

x ∼µφ

x ∼µθ

σ

−2k

k!

x ∼µp hi


hEθ x⊗k , Eθ x⊗k i − 2hEθ x⊗k , Exφ x⊗k i + hEφ x⊗k , Eφ x⊗k i

σ −2k
kEθ [x⊗k ] − Eφ [x⊗k ]k2HS
k!

σ −2k
kEθ [x⊗k ] − Eφ [x⊗k ]k2HS ,
k!

where h·, ·i denotes the Frobenius inner product between tensors and k · kHS denotes the Hilbert-Schmidt
norm. Since under both µθ and µφ , kxk ≤ 2 almost surely, we have for all k ≥ 2,
kEθ [x⊗k ] − Eφ [x⊗k ]k2HS ≤ 2kEθ [x⊗k ]k2HS + 2kEφ [x⊗k ]k2HS ≤ 4k+1 .
Therefore
χ2 (Pθ , Pφ ) ≤ 4e2/σ
2

2

∞
d −2d
X
2 4 σ
4k σ −2k
≤ 4e6/σ
,
k!
d!

k=d

and applying the inequality D(Pθ k Pφ ) ≤ χ (Pθ , Pφ ) [Tsy09] proves the claim.

7.5

Proof of Theorem 3.4

If τ1 and τ2 are both in Mθ,d−1, then by Proposition 7.8, the corresponding distributions Pτ1 and Pτ2 satisfy
D(Pτ1 k Pτ2 ) ≤ (cσ)C2d d! . By the Neyman-Pearson lemma, for any test ψ using n samples,
s
r
1
Cn
n
n
Pr(ψ = 2) + Pr(ψ = 1) ≥ 1 − dTV (Pτ1 , Pτ2 ) ≥ 1 −
D(Pnτ1 k Pnτ2 ) = 1 −
,
τ2
τ1
2
2(cσ)2d d!
27

where we have applied Pinsker’s inequality and the chain rule for divergence. Therefore, to achieve an error
probability of at most 1/3, we must have n ≥ 2(cσ)2d d!/(9C) = cd σ 2d , as claimed.

8
8.1

Proofs for Section 4: algebraic results
Algorithm for generators of R[x]G

We know that R[x]G is finitely generated as an R-algebra (Theorem 4.3). There are various algorithms to
compute a finite set of generators for R[x]G [Stu08, DK15]. However, some require the group to be finite or to
be reductive over an algebraically-closed field. One algorithm that certainly works in our context (compact
groups) is Algorithm 2.2.5 in [Stu08]. As input it requires the Hilbert series of R[x]G (which can be computed
by Proposition 4.13) and a procedure to compute a basis for R[x]G
d (which can be done with the Reynolds
operator by Observation 4.2). The idea is as follows. We keep a set of proposed generators f1 , . . . , fm .
At each step we compare the Hilbert series of R[x]G with the Hilbert series of R[f1 , . . . , fm ] (which can be
computed using Gröbner bases). If these series differ at the td term, this means we are missing an invariant
at degree d. To remedy this, we create a new homogeneous invariant of degree d using the Reynolds operator,
and add it to our set of proposed generators. We repeat until the Hilbert series match.

8.2

Bounding the list size for generic signals

In this section we prove Theorem 4.24 and the first part of Theorem 4.9 (see Section 8.3 for the second part).
Recall the following basic definitions and facts from field theory.
Definition 8.1. If F2 is a subfield of F1 , we write F1 /F2 and call this a field extension. The degree of the
extension, denoted [F1 : F2 ], is the dimension of F1 as a vector space over F2 .
Proposition 8.2. Let R ⊆ F2 ⊆ F1 with F1 finitely generated (as a field) over R. Let r be the transcendence
degree of F1 (over R). The field extension F1 /F2 has finite degree if and only if F1 contains r algebraically
independent elements.
Proof. This is a basic fact of field theory. If F1 contains r algebraically independent elements then the
extension F1 /F2 is algebraic and finitely generated, and therefore has finite degree. Otherwise, the extension
is transcendental and has infinite degree.
In light of the above (and using the fact that R[x]G is finitely generated), Theorem 4.24 implies the first
part of Theorem 4.9 and so it remains to prove Theorem 4.24 (i.e. list size is bounded by D := [FG : R(U )]).
Proof of Theorem 4.24.
Write FU := R(U ). In characteristic zero, every algebraic extension is separable, so by the primitive element
theorem, FG = FU (α) for some α ∈ FG . Since α generates a degree-D extension, α is the root of a degree-D
polynomial
αD + bD−1 αD−1 + · · · + b1 α + b0
(7)
with coefficients bi ∈ FU . Furthermore, every element of FG can be expressed as
c0 + c1 α + · · · + cD−1 αD−1
with ci ∈ FU . In particular, let g1 , . . . , gk be generators for R[x]G (as an R-algebra) and write
(i)

(i)

(i)

gi = c0 + c1 α + · · · + cD−1 αD−1 .

(8)
(i)

Let S ⊆ V be the subset for which α and all the (finitely-many) coefficients bi , cj have nonzero denominators;
S is a non-empty Zariski-open set and thus has full measure. Now fix θ ∈ S. Given the values f (θ) for all
f ∈ U , each bi takes a well-defined value in R and so from (7) there are at most D possible values that α(θ)
can take. From (8), each value of α(θ) uniquely determines all the values gi (θ) and thus uniquely determines
all the values f (θ) for f ∈ R[x]G . Since R[x]G resolves θ (Theorem 4.4), this completes the proof.
28

8.3

Generic list recovery converse

In this section we prove the second part of Theorem 4.9 (the converse).
Let p = dim(V ), trdeg(U ) = q, and trdeg(R[x]G ) = r so that q < r ≤ p. Let f = {f1 , . . . , fm } be a basis
for U , and let g = {g1 , . . . , gr } be a transcendence basis for R[x]G . Let S ⊆ V be the set of points θ for
which the Jacobian Jx (f )|x=θ has row rank q and the Jacobian Jx (g)|x=θ has row rank r; by the Jacobian
criterion (see Corollary 4.19), S is a non-empty Zariski-open set and thus has full measure.
Fix θ ∈ S. For a sufficiently small open neighborhood X ⊆ S containing θ we have the following. The
Jacobian criterion on f implies that {τ ∈ X : f (τ ) = f (θ)} has dimension p − q. The Jacobian criterion on
g implies that every z ∈ g(X) has a preimage g−1 (z) := {τ ∈ X : g(τ ) = z} of dimension p − r. Since
p − q > p − r it follows that there are infinitely many θ1 , θ2 , . . . ∈ X such that f (θi ) = f (θ) but the values
g(θ1 ), g(θ2 ), . . . are all distinct (and thus the θi belong to distinct orbits). Therefore U does not list-resolve
θ.

8.4

Hilbert series and Hironaka decomposition

In this section we prove Proposition 4.14 on extracting the transcendence degree from the Hilbert series
(as the pole order at t = 1). While this is a general property of finitely generated algebras over a field,
there is an easy proof for invariant rings stemming from a key structural property of such rings called the
Cohen-Macaulay property or Hironaka decomposition.
Theorem 8.3 ([DK15] Section 2.6). The invariant ring R[x]G has the following structure. There exist
homogeneous primary invariants f1 , . . . , fr ∈ R[x]G and homogeneous secondary invariants g1 , . . . , gs ∈
R[x]G such that
• {f1 , . . . , fr } are algebraically independent, and
• any element of R[x]G can be written uniquely as a linear combination of g1 , . . . , gs with coefficients
from R[f1 , . . . , fr ].
The proof can be found in Section 2.6 of [DK15]; note that the only property of the group that is used is
the existence of a Reynolds operator (and so the proof is valid for compact groups).
Proof of Proposition 4.14.
The Hironaka decomposition above implies that the Hilbert series takes the form
Ps
tdeg(gj )
Qr j=1 deg(f )
i )
i=1 (1 − t

(this is equation (2.7.3) in [DK15]). It is now clear that the order of the pole at t = 1 is precisely r. But
we can see as follows that f1 , . . . , fr is a transcendence basis for R[x]G and so r = trdeg(R[x]G ). As in the
proof of Theorem 4.29, since R[x]G is a finitely generated R[f1 , . . . , fr ]-module, every h ∈ R[x]G satisfies a
polynomial with coefficients in R[f1 , . . . , fr ], which is an algebraic dependence among {f1 , . . . , fr , h}.

8.5

Transcendence degree for heterogeneity

In this section we prove Proposition 4.15. To recall the setup, we have G̃ acting on Ṽ with associated
variables x̃. We also have G = G̃K ⋊ SK acting on V = Ṽ ⊕K ⊕ ∆K with associated variables x. Let us also
introduce an intermediate group: G′ = G̃K , acting on V (with associated variables x).
(k)
(k)
Partition the variables x as follows. For k = 1, . . . , K, let x(k) = (x1 , . . . , xp ) be the variables
corresponding to signal k. Let z = (z1 , . . . , zK−1 ) be the variables corresponding to the mixing weights
PK−1
w 1 , . . . , w K−1 . Whenever we refer to zK , this is just shorthand for − k=1 zk .
We first prove a simpler version of the result without the action of SK .

29

Lemma 8.4. Let r̃ = trdeg(R[x̃]G̃ ) and let r = K r̃ + K − 1. Then
′

trdeg(R[x]G ) = r.
′

Proof. To show ‘≥’ we need to exhibit r algebraically independent elements of R[x]G . Letting f1 , . . . , fr̃ be
a transcendence basis for R[x̃]G̃ , it suffices to take
I := {fi (x(k) )}1≤i≤r̃,1≤k≤K ∪ {z1 , . . . , zK−1 }.
′

To show ‘≤’ we first recall that we can obtain a spanning set for the subspace R[x]G
d by applying the
Reynolds operator R (for G′ ) to each degree-d monomial (in the variables x). Such a monomial takes the
form
K
Y
mk (x(k) )
m(x) = M (z)
k=1

where M, mk are monomials. Applying the Reynolds operator yields
R(m(x)) =

E
g1 ,...,gk ∼G̃

M (z)

K
Y

k=1

mk (gk · x(k) ) = M (z)

K
Y

(k)
E mk (gk · x ).

k=1 gk ∼G̃

Note that R(m(x)) is the product of pure invariants, i.e. invariants that only involve variables from a single
one of the blocks x(1) , . . . , x(K) , z. It is clear that I (from above) is a maximal set of algebraically independent
pure invariants. It is now easy to show using the Jacobian criterion (Proposition 4.18) that if any R(m(x))
is added to I, it will no longer be algebraically independent. The result now follows using basic properties
of algebraic independence (Proposition 4.22 and Lemma 4.23).
Proof of Proposition 4.15.
′
Since R[x]G ⊆ R[x]G , it is clear (in light of the above) that trdeg(R[x]G ) ≤ r. Thus we need only to show
trdeg(R[x]G ) ≥ r by demonstrating r algebraically independent invariants. Let e1 , . . . , eK be the elementary
symmetric functions in K variables. With fi as above, we take the invariants
{ek (fi (x(1) ), . . . , fi (x(K) ))}1≤i≤r̃,1≤k≤K ∪ {e2 (z1 , . . . , zK ), . . . , eK (z1 , . . . , zK )}.
Note that e1 (z1 , . . . , zK ) is not included because it is equal to 0. The fact that ek (fi (x(1) ), . . . , fi (x(K) )) are
algebraically independent can be seen because {e1 , . . . , eK } is algebraically independent and {fi (x(k) )}i,k
is algebraically independent. We can see that {ek (z1 , . . . , zK )}k≥2 are algebraically independent as follows.
An algebraic dependence would be a polynomial P such that P (e2 (z2 , . . . , zK ), . . . , eK (z1 , . . . , zK )) (now
P
treating zK as a separate variable) has a root zK = − K−1
k=1 zk and thus has e1 (z1 , . . . , zK ) as factor.
But this contradicts the fact that any symmetric polynomial has a unique representation in terms of the
elementary symmetric polynomials.

8.6

Gröbner bases

In this section we show how to use Gröbner bases to test various algebraic conditions. In particular, we
prove Theorems 4.26 and 4.28. The ideas from this section are mostly standard in the theory of Gröbner
bases; see e.g. [CLO07] for a reference.
Definition 8.5. A monomial order on R[x] is a well-ordering on the set M of all (monic) monomials,
satisfying M ≤ N ⇔ M P ≤ N P for all M, N, P ∈ M. We will say that a monomial order favors a variable
xi if the monomial xi is larger (with respect to the monomial order) than any monomial not involving xi .
We write LM(f ) to denote the leading monomial of a polynomial f , i.e. the monomial occurring in f that is
largest (with respect to the monomial order); LM(f ) does not include the coefficient.

30

Definition 8.6. A Gröbner basis of an ideal I ⊆ R[x] is a finite subset B ⊆ I such that for every f ∈ I
there exists b ∈ B such that LM(f ) is a multiple of LM(b). We call B a reduced Gröbner basis if all its
elements are monic and it has the additional property that for every pair of distinct b, b′ ∈ B, no monomial
occurring in b is a multiple of LM(b′ ).
The following basic facts about Gröbner bases are proved in [CLO07]. A Gröbner basis is indeed a basis, in
that it generates the ideal. Every ideal I ⊆ R[x] has a Gröbner basis, and has a unique reduced Gröbner
basis. Buchberger’s algorithm computes the reduced Gröbner basis of an ideal I = hf1 , . . . , fm i, given a list
of generators fi . (It is not a polynomial-time algorithm, however.)
Suppose we are interested in the relations between polynomials f1 , . . . , fm ∈ R[x]. Introduce additional
variables t = (t1 , . . . , tm ) and consider the ideal I := hf1 (x) − t1 , . . . , fm (x) − tm i ⊆ R[x, t]. Given f1 , . . . , fm
there is an algorithm to compute a Gröbner basis for the elimination ideal
J := hf1 (x) − t1 , . . . , fm (x) − tm i ∩ R[t].
In fact, the algorithm is simply to compute a Gröbner basis for I using a particular monomial order and then
keep only the elements that depend only on t (see Chapter 3 of [CLO07]). The elimination ideal consists
precisely of the polynomial relations among f1 , . . . , fm :
Lemma 8.7. For any polynomial P ∈ R[t] we have: P ∈ J if and only if P (f1 (x), . . . , fm (x)) ≡ 0.

Proof. The direction ‘⇒’ is clear because if we let ti = fi (x) for all i then the generators of I vanish and
so every element of I vanishes. To show the converse, it suffices to show that for any polynomial P ∈ R[t],
P (f1 (x), . . . , fm (x)) − P (t1 , . . . , tm ) ∈ I. This can be shown inductively using the following key idea:
x1 x2 − t1 t2 =

1
1
(x1 − t1 )(x2 + t2 ) + (x2 − t2 )(x1 + t1 )
2
2

and so x1 x2 − t1 t2 ∈ hx1 − t1 , x2 − t2 i.
Generation as an R-algebra. Suppose we want to know whether fm ∈ R[f1 , . . . , fm−1 ]. This is equivalent
to asking whether there exists P ∈ J of the form
P (t) = tm − Q(t1 , . . . , tm−1 )

(9)

for some Q ∈ R[t1 , . . . , tm−1 ]. Suppose that J contains an element P of the form (9). Compute a Gröbner
basis B for J with respect to a monomial order that favors tm . The leading monomial of P is tm so by the
definition of a Gröbner basis there must be an element b ∈ B whose leading monomial divides tm . Since
1 ∈
/ J (by Lemma 8.7), the leading monomial of b is exactly tm and so b takes the form (9). Therefore,
fm ∈ R[f1 , . . . , fm−1 ] if and only if B contains an element of the form (9).
We can now prove Theorem 4.28: to test whether R[f1 , . . . , fm ] = R[x]G , compute generators g1 , . . . , gs
for R[x]G (see Section 8.1) and use the above to test whether each gi is in R[f1 , . . . , fm ].
Generation as a field. Suppose we want to know whether fm ∈ R(f1 , . . . , fm−1 ). This is equivalent to
asking whether fm can be expressed as a rational function of f1 , . . . , fm−1 (with coefficients in R), which is
equivalent (by multiplying through by the denominator) to asking whether there exists P ∈ J of the form
P (t) = tm Q1 (t1 , . . . , tm−1 ) − Q2 (t1 , . . . , tm−1 ) with Q1 ∈
/ J.

(10)

Suppose that J contains an element P of the form (10). Compute a reduced Gröbner basis B for J with
respect to a monomial order that favors tm . It is a basic property of Gröbner bases that P can be written as
X
pi (t)bi (t)
P (t) =
i

where pi ∈ R[t] and bi ∈ B with LM(pi ) ≤ LM(P ) and LM(bi ) ≤ LM(P ). If no bi involves the variable
tm then Q1 ∈ J, a contradiction. Therefore some bj must have degree 1 in tm . Since B is a reduced
Gröbner basis it cannot contain any element of the form (10) with Q1 ∈ J. This completes the proof that
fm ∈ R(f1 , . . . , fm−1 ) if and only if B contains an element of the form (10).
31

Degree of field extension. Consider the setup from Theorem 4.24: given a finite set U = {f1 , . . . , fm } ⊆
R[x]G , we want to compute [FG : FU ] where FU = R(U ) and FG is the field of fractions of R[x]G . We can
assume [FG : FU ] is finite (since we can efficiently test whether this is the case using Proposition 8.2 and
the methods of Section 4.2). Let d be such that R[x]G
≤d generates FG as a field (over R). (It is sufficient
G
for R[x]G
to
generate
R[x]
as
an
R-algebra;
such
a
d
can be computed via Section 8.1. If G is finite then
≤d
d = |G| is sufficient; see Section 4.4.) A generic element of R[x]G
≤d will generate the field extension:
Lemma 8.8. For all but a measure-zero set of α ∈ R[x]G
≤d , FG = FU (α).
This fact is related to the primitive element theorem. We include a proof for completeness.
Proof. The field extension FG /FU is finite and separable (since we’re in characteristic zero), so by the
fundamental theorem of Galois theory, there are only finitely many intermediate fields. (Take the normal
closure of FG /FU ; then the intermediate fields are in bijection with a finite group, and only some of them
lie inside FG .) Let L be the collection of intermediate fields of FG /FU that are proper subfields of FG . We
know R[x]G
≤d is a subspace of FG that generates FG and therefore is not contained by any field in L. This
G
means each field L ∈ L intersects R[x]G
≤d at a proper subspace VL of R[x]≤d . The finite union ∪L∈L VL is a
measure-zero subset of R[x]G
≤d , and any α outside of it satisfies FG = FU (α).
Let α be a generic element of R[x]G
≤d . In light of the above, [FG : FU ] is equal to the smallest positive
integer D for which there exists a relation
QD (f1 , . . . , fm )αD + · · · + Q1 (f1 , . . . , fm )α + Q0 (f1 , . . . , fm ) ≡ 0
for polynomials Qi with QD (f1 , . . . , fm ) 6≡ 0. This can be tested similarly to field generation. Compute
a reduced Gröbner basis B for the elimination ideal J ⊆ R[t1 , . . . , tm , τ ] consisting of the relations among
f1 , . . . , fm , α; use a monomial order that favors τ . Then [FG : FU ] is equal to the smallest positive integer
D for which B contains an element of degree D in τ (or ∞ if B contains no element that involves τ ). This
proves Theorem 4.26.
Remark 8.9. An alternative to using Gröbner bases for the above tasks is to solve a (very large) linear
system in order to find the minimal relation among a set of polynomials. There are bounds on the maximum
possible degree of such a relation (if one exists) [Kay09].

9

Proofs for S 2 registration

9.1

Formula for Hilbert series of R[x]G

We can derive the Hilbert series of R[x]G for S 2 registration using the methods in Section 4.6 of [DK15].
Proposition 9.1. Consider S 2 registration with frequencies F . For |t| < 1, the Hilbert series of R[x]G is
given by
X
H(t) =
Res(f, z)
z∈P

where

f (z) =

z

1 − 21 (z + 1/z)
−z N −2(1 − z)2
hQ
i
= Q
Qℓ
Qℓ
ℓ
m
m
m
2 ℓ∈F
ℓ∈F
m=−ℓ (1 − tz )
m=0 (1 − tz )
m=1 (z − t)

Q

P
with N = 12 ℓ∈F ℓ(ℓ + 1). Here Res(f, z) denotes the residue (from complex analysis) of the function f at
the point z, and P is the set of poles of f (z) inside the unit circle (in C). Namely, P contains t1/m e2πik/m
for all m ∈ {1, 2, . . . , maxℓ∈F ℓ} and for all k ∈ {0, 1, . . . , m − 1}. If N ≤ 1, P also contains 0.

32

Proof. Recall Molien’s formula (Proposition 4.13):
H(t) =

E

g∼Haar(G)

det(I − t ρ(g))−1 .

Note that det(I − t ρ(g)) depends only on the conjugacy class of g. In SO(3), two elements are conjugate
if and only if they rotate by the same angle φ. When g ∼ Haar(SO(3)), the angle φ = φ(g) is distributed
with density function π1 (1 − cos φ) on [0, π] (see e.g. [Sal79]). If g has angle φ, the matrix ρℓ (g) by which
it acts on the irreducible representation Vℓ has eigenvalues e−iℓφ , e−i(ℓ−1)φ , . . . , eiℓφ (see e.g. [Vve01]). The
matrix ρ(g) by which g acts on V = ⊕ℓ∈F Vℓ is block diagonal with blocks ρℓ (g). Using the above we write
an expression for the Hilbert series:
H(t) =

1
π

Z

π

0

1
1 − cos φ
dφ =
Qℓ
imφ )
2π
ℓ∈F
m=−ℓ (1 − te

Q

Z

0

2π

1 − 21 (eiφ + e−iφ )
dφ.
Qℓ
imφ )
ℓ∈F
m=−ℓ (1 − te

Q

Now write this as a complex contour integral around the unit circle in C and apply the residue theorem from
complex analysis to arrive at the result.

9.2

Formula for dimension of R[x]G
d

The dimension of R[x]G can be extracted as the coefficient of td in the Hilbert series from the previous
section, but here we give a different formula based on character theory from representation theory. The
character of a representation ρ : G → GL(V ) (where V is a finite-dimensional real vector space) is the
function χV : G → R defined by χV (g) = tr(ρ(g)).
In our case, using the eigenvalues of ρℓ (g) from the previous section, we have
χVℓ (g) = 1 + 2

ℓ
X

cos(m φ(g))

m=1

P
where φ(g) is the angle of rotation of g. For V = ⊕ℓ∈F Vℓ we then have χV (g) = ℓ∈F χVℓ (g).
As a representation of G = SO(3), R[x]d is (isomorphic to) the dth symmetric power of V , denoted
S d (V ). (This is using the fact that a real representation is isomorphic to its dual.) There is a recursive
formula for the character of S d (V ):
d

χS d (V ) (g) =

1X
χV (g i )χS d−i (V ) (g).
d i=1

This comes from the Newton–Girard formula for expressing complete homogeneous symmetric polynomials
in terms of power sum polynomials.
The representation R[x]d = S d (V ) decomposes as the direct sum of irreducible representations Vℓ . The
subspace of R[x]d consisting of all copies of the trivial representation V0 (the 1-dimensional representation
G
on which every group element acts as the identity) is precisely R[x]G
d . Thus, dim(R[x]d ) is the number of
copies of the trivial representation in the decomposition of R[x]d . This can be computed using characters:
dim(R[x]G
d ) = hχS d (V ) , χV0 i = hχS d (V ) , 1i where hf1 , f2 i := Eg∼Haar(G) [f1 (g)f2 (g)]. Since characters are class
functions (i.e. they are constant on conjugacy classes), we can compute this inner product by integrating
over the angle φ (as in the previous section). This yields the formula stated in Proposition 5.7.

Acknowledgements
ASW is grateful for feedback given by several members of the audience when he presented a preliminary
version of these results at a workshop dedicated to multi-reference alignment, organized as part of the Simons
Collaboration on Algorithms & Geometry.
33

References
[ABL+ 17]

Emmanuel Abbe, Tamir Bendory, William Leeb, João Pereira, Nir Sharon, and Amit Singer.
Multireference alignment is easier with an aperiodic translation distribution. arXiv preprint
arXiv:1710.02793, 2017.

[ADBS16]

Cecilia Aguerrebere, Mauricio Delbracio, Alberto Bartesaghi, and Guillermo Sapiro. Fundamental limits in multi-image alignment. IEEE Trans. Signal Process., 64(21):5707–5722, 2016.

[ADLM84]

Marc Adrian, Jacques Dubochet, Jean Lepault, and Alasdair W McDowall. Cryo-electron
microscopy of viruses. Nature, 308(5954):32–36, 1984.

[APS17]

Emmanuel Abbe, Joao Pereira, and Amit Singer. Sample complexity of the boolean multireference alignment problem. arXiv preprint arXiv:1701.07540, 2017.

[Ban15]

Afonso S. Bandeira. Convex Relaxations for Certain Inverse Problems on Graphs. PhD thesis,
Princeton University, June 2015.

[BBLS17]

Nicolas Boumal, Tamir Bendory, Roy R. Lederman, and Amit Singer. Heterogeneous multireference alignment: a single pass approach. arXiv preprint arXiv:1710.02590, 2017.

[BBM+ 17]

Tamir Bendory, Nicolas Boumal, Chao Ma, Zhizhen Zhao, and Amit Singer. Bispectrum
inversion with application to multireference alignment. arXiv preprint arXiv:1705.00641, 2017.

[BCS15]

Afonso S. Bandeira, Yutong Chen, and Amit Singer. Non-unique games over compact groups
and orientation estimation in cryo-EM. arXiv preprint arXiv:1505.03840, 2015.

[BCSZ14]

Afonso S. Bandeira, Moses Charikar, Amit Singer, and Andy Zhu. Multireference alignment
using semidefinite programming. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 459–470. ACM, 2014.

[BFB97]

Miguel A Blanco, M Flórez, and M Bermejo. Evaluation of the rotation matrices in the basis
of real spherical harmonics. Journal of Molecular Structure: Theochem, 419(1):19–27, 1997.

[BMS13]

Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic independence and blackbox
identity testing. Information and Computation, 222:2–19, 2013.

[Böh13]

Arno Böhm. Quantum mechanics: foundations and applications. Springer Science & Business
Media, 2013.

[BRW17]

Afonso Bandeira, Philippe Rigollet, and Jonathan Weed. Optimal rates of estimation for
multi-reference alignment. arXiv preprint arXiv:1702.08546, 2017.

[BZS15]

Tejal Bhamre, Teng Zhang, and Amit Singer. Orthogonal matrix retrieval in cryo-electron
microscopy. In Biomedical Imaging (ISBI), 2015 IEEE 12th International Symposium on,
pages 1048–1052. IEEE, 2015.

[CL11]

T. Tony Cai and Mark G. Low. Testing composite hypotheses, Hermite polynomials and
optimal estimation of a nonsmooth functional. Ann. Statist., 39(2):1012–1041, 2011.

[CLO07]

David Cox, John Little, and Don O’Shea. Ideals, varieties, and algorithms: an introduction to
computational algebraic geometry and commutative algebra. Springer New York, 2007.

[Coh13]

J. Cohen. Is high-tech view of hiv too good to be true? Science, 6145(341):443–444, 2013.

[Dia92]

R. Diamond. On the multiple simultaneous superposition of molecular structures by rigid body
transformations. Protein Science, 1(10):1279–1287, October 1992.

34

[DK15]

Harm Derksen and Gregor Kemper. Computational invariant theory. Springer, 2015.

[Dol03]

Igor Dolgachev. Lectures on invariant theory, volume 296. Cambridge University Press, 2003.

[Dom16]

M. Domokos. Degree bounds for separating invariants of abelian groups. arXiv preprint
arXiv:1602.06597, 2016.

[Eli57]

Peter Elias. List decoding for noisy channels. Technical Report 335, Research Laboratory of
Electronics, Massachusetts Institute of Technology, 1957.

[ER93]

Richard Ehrenborg and Gian-Carlo Rota. Apolarity and canonical forms for homogeneous
polynomials. European Journal of Combinatorics, 14(3):157–181, 1993.

[Ete96]

Gábor Etesi. Spontaneous symmetry breaking in the SO(3) gauge theory to discrete subgroups.
Journal of Mathematical Physics, 37(4):1596–1601, 1996.

[Fel68]

W. Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, 1968.

[Hil90]

David Hilbert. Über die Theorie der algebraischen Formen. Mathematische Annalen, 36:473–
531, 1890.

[Hil93]

David Hilbert. Über die vollen Invariantensysteme. Mathematische Annalen, 42:313–370, 1893.

[Huỳ86]

Dũng T. Huỳnh. A superexponential lower bound for Gröbner bases and Church-Rosser commutative Thue systems. Inform. and Control, 68(1-3):196–206, 1986.

[Jon16]

Slavica Jonić. Cryo-electron microscopy analysis of structurally heterogeneous macromolecular
complexes. Computational and structural biotechnology journal, 14:385–390, 2016.

[Kač94]

Victor Kač. Invariant theory [lecture notes]. https://people.kth.se/~laksov/notes/invariant.pdf,
1994.

[Kak09]

Ramakrishna Kakarala. Completeness of bispectrum on compact groups. arXiv preprint
arXiv:0902.0196, 1, 2009.

[Kam80]

Zvi Kam. The reconstruction of structure from electron micrographs of randomly oriented
particles. Journal of Theoretical Biology, 82(1):15–39, 1980.

[Kay09]

Neeraj Kayal. The complexity of the annihilating polynomial. In 24th Annual IEEE Conference
on Computational Complexity (CCC’09), pages 184–193. IEEE, 2009.

[KK10]

Martin Kohls and Hanspeter Kraft. Degree bounds for separating invariants. arXiv preprint
arXiv:1001.5216, 2010.

[LBB+ 17]

Eitan Levin, Tamir Bendory, Nicolas Boumal, Joe Kileel, and Amit Singer. 3D ab initio
modeling in cryo-EM by autocorrelation analysis. arXiv preprint arXiv:1710.08076, 2017.

[LeC73]

L. LeCam. Convergence of estimates under dimensionality restrictions. Ann. Statist., 1:38–53,
1973.

[LNS99]

O. Lepski, A. Nemirovski, and V. Spokoiny. On estimation of the Lr norm of a regression
function. Probab. Theory Related Fields, 113(2):221–253, 1999.

[LS16]

Roy R. Lederman and Amit Singer. A representation theory perspective on simultaneous
alignment and classification. arXiv preprint arXiv:1607.03464, 2016.

[LS17]

Roy R Lederman and Amit Singer. Continuously heterogeneous hyper-objects in cryo-EM and
3-D movies of many temporal dimensions. arXiv preprint arXiv:1704.02899, 2017.

35

[MSS16]

Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with
sum-of-squares. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 438–446. IEEE, 2016.

[Nog16]

Eva Nogales. The development of cryo-EM into a mainstream structural biology technique.
Nature methods, 13(1):24–27, 2016.

[NY83]

A. S. Nemirovsky and D. B. and Yudin. Problem complexity and method efficiency in optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1983. Translated
from the Russian and with a preface by E. R. Dawson, Wiley-Interscience Series in Discrete
Mathematics.

[Osg07]

Brad Osgood.
Chapter 8:
n-dimensional Fourier Transform.
Lecture Notes for EE 261:
The Fourier Transform and its Applications.
https://see.stanford.edu/materials/lsoftaee261/book-fall-07.pdf, 2007.

[PWB+ 17]

Amelia Perry, Jonathan Weed, Afonso Bandeira, Philippe Rigollet, and Amit Singer. The
sample complexity of multi-reference alignment. arXiv preprint arXiv:1707.00943, 2017.

[PWBM16a] Amelia Perry, Alexander S Wein, Afonso S. Bandeira, and Ankur Moitra. Message-passing algorithms for synchronization problems over compact groups. arXiv preprint arXiv:1610.04583,
2016.
[PWBM16b] Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, and Ankur Moitra. Optimality and
sub-optimality of PCA for spiked random matrices and synchronization. arXiv:1609.05573,
2016.
[PZAF05]

R. G. Pita, M. R. Zurera, P. J. Amores, and F. L. Ferreras. Using multilayer perceptrons to
align high range resolution radar signals. In Artificial Neural Networks: Formal Models and
Their Applications - ICANN 2005, pages 911–916. Springer Berlin Heidelberg, 2005.

[Ros57]

Morris E Rose. Elementary theory of angular momentum. Physics Today, 10:30, 1957.

[Sad89]

B. M. Sadler. Shift and rotation invariant object reconstruction using the bispectrum. In
Workshop on Higher-Order Spectral Analysis, pages 106–111, Jun 1989.

[Sal79]

Eugene Salamin. Application of quaternions to computation with rotations. Technical report,
Working Paper, 1979.

[Sch03]

Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. Springer Science
& Business Media, 2003.

[Sch12]

S. H. W. Scheres. RELION: implementation of a bayesian approach to cryo-EM structure
determination. J. Struct. Biol., 180(3):519–530, 2012.

[SG92]

Brian M Sadler and Georgios B Giannakis. Shift-and rotation-invariant object reconstruction
using the bispectrum. JOSA A, 9(1):57–69, 1992.

[Sha94]

Igor R. Shafarevich. Basic algebraic geometry. Springer, 1994.

[Sig16]

Fred J. Sigworth. Principles of cryo-EM single-particle image processing. Microscopy, 65(1):57–
67, 2016.

[Sin11]

Amit Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied
and computational harmonic analysis, 30(1):20–36, 2011.

36

[SS11]

Amit Singer and Yoel Shkolnisky. Three-dimensional structure determination from common
lines in cryo-EM by eigenvectors and semidefinite programming. SIAM Journal on Imaging
Sciences, 4(2):543–572, 2011.

[Stu08]

Bernd Sturmfels. Algorithms in invariant theory. Springer Science & Business Media, 2008.

[TS12]

D. L. Theobald and P. A. Steindel. Optimal simultaneous superpositioning of multiple structures with missing data. Bioinformatics, 28(15):1972–1979, 2012.

[Tsy09]

Alexandre B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics.
Springer, New York, 2009. Revised and extended from the 2004 French original, Translated
by Vladimir Zaiats.

[vdV98]

A. W. van der Vaart. Asymptotic statistics, volume 3 of Cambridge Series in Statistical and
Probabilistic Mathematics. Cambridge University Press, Cambridge, 1998.

[VG86]

BK Vainshtein and AB Goncharov. Determination of the spatial orientation of arbitrarily
arranged identical particles of unknown structure from their projections. In Soviet Physics
Doklady, volume 31, page 278, 1986.

[VH87]

Marin Van Heel. Angular reconstitution: a posteriori assignment of projection directions for
3D reconstruction. Ultramicroscopy, 21(2):111–123, 1987.

[Vve01]

Dimitri
Vvedensky.
Chapter
8:
Irreducible
Representations
of
SO(2)
and
SO(3).
Group
theory
course
[lecture
notes].
http://www.cmth.ph.ic.ac.uk/people/d.vvedensky/groups/Chapter8.pdf, 2001.

[ZvdHGG03] J. P. Zwart, R. van der Heiden, S. Gelsema, and F. Groen. Fast translation invariant classification of HRR range profiles in a zero phase representation. Radar, Sonar and Navigation,
IEE Proceedings, 150(6):411–418, 2003.

A
A.1

Spherical harmonics and SO(3) invariants
Spherical harmonics

We follow the conventions of [BFB97]. Parametrize the unit sphere by angular spherical coordinates (θ, φ)
with θ ∈ [0, π] and φ ∈ [0, 2π). (Here θ = 0 is the north pole and θ = π is the south pole.) For integers ℓ ≥ 0
and −ℓ ≤ m ≤ ℓ, define the complex spherical harmonic
Yℓm (θ, φ) = (−1)m Nℓm Pℓm (cos θ)eimφ
with normalization factor
Nℓm =

s

(2ℓ + 1)(ℓ − m)!
4π(ℓ + m)!

where Pℓm (x) are the associated Legendre polynomials
Pℓm (x) =

1
2ℓ ℓ!

(1 − x2 )m/2

dℓ+m 2
(x − 1)ℓ .
dxℓ+m

In the S 2 registration problem we are interested in representing a real-valued function on the sphere, in
which case we use an expansion (with real coefficients) in terms of the real spherical harmonics:
 (−1)m
√
m

m > 0,
 √2 (Yℓm (θ, φ) + Yℓm (θ, φ)) = 2Nℓm Pℓ (cos θ) cos(mφ)
Yℓ0 (θ, φ) = Nℓ0 Pℓ0 (cos θ)
m = 0,
Sℓm (θ, φ) =
√
m

|m|
 (−1)
√ (Yℓ|m| (θ, φ) − Yℓ|m| (θ, φ)) =
2Nℓ|m| Pℓ (cos θ) sin(|m|φ) m < 0.
i 2
37

Here Yℓm is the complex conjugate of Yℓm , which satisfies the identity
Yℓm (θ, φ) = (−1)m Yℓ(−m) (θ, φ).

(11)

−m
m
= (−1)m Nℓm Pℓm .
Above we have also used the identity Pℓ−m = (−1)m (ℓ−m)!
(ℓ+m)! Pℓ , which implies Nℓ(−m) Pℓ
In the cryo-EM problem we are instead interested in representing the Fourier transform of a real-valued
function. Such a function f has the property that if ~r and −~r are antipodal points on the sphere, f (−~r) =
f (~r). For this type of function we use an expansion (with real coefficients) in terms of a new basis of spherical
harmonics:

1
ℓ+m

Yℓ(−m) (θ, φ))
m > 0,
 √2 (Yℓm (θ, φ) + (−1)
ℓ
i Yℓ0 (θ, φ)
m = 0,
Hℓm (θ, φ) =

 √i (Yℓ|m| (θ, φ) − (−1)ℓ+m Yℓ(−|m|) (θ, φ)) m < 0.
2

One can check that Hℓm (−~r) = Hℓm (~r) using (11) along with the fact Yℓm (−~r) = (−1)ℓ Yℓm (~r) which comes
from Pℓm (−x) = (−1)ℓ+m Pℓm (x).

A.2

Wigner D-matrices

We will mostly work in the basis of complex spherical harmonics Yℓm since the formulas are simpler. The
analogous results for the other bases can be worked out by applying the appropriate change of basis.
Let Vℓ ≃ C2ℓ+1 be the vector space consisting of degree-ℓ complex spherical
harmonics represented
P
in the basis {Yℓm }−ℓ≤m≤ℓ , i.e. v ∈ C2ℓ+1 encodes the spherical harmonic ℓm=−ℓ vm Yℓm . These Vℓ (for
ℓ = 0, 1, 2, . . .) are the irreducible representations of SO(3). Each can also be defined over the real numbers
by changing basis to the real spherical harmonics Sℓm .
A group element g ∈ SO(3) acts on a (spherical harmonic) function f : S 2 → R via (g · f )(x) = f (g −1 x).
The action of g on Vℓ is given by the Wigner D-matrix Dℓ (g) ∈ C(2ℓ+1)×(2ℓ+1) defined as in [BFB97].
We will need the following orthogonality properties of the Wigner D-matrices. First, the standard Schur
orthogonality relations from representation theory yield
′

ℓ (g)D ℓ
Dmk
m′ k′ (g) =

E

g∼Haar(SO(3))

1
1ℓ=ℓ′ 1m=m′ 1k=k′ .
2ℓ + 1

We also have [Ros57]
ℓ
ℓ′
Dmk
(g)Dm
′ k′ (g)

=

′
ℓ+ℓ
X

L
hℓ m ℓ′ m′ |L (m + m′ )ihℓ k ℓ′ k ′ |L (k + k ′ )iD(m+m
′ )(k+k′ ) (g)

L=|ℓ−ℓ′ |

where hℓ1 m1 ℓ2 m2 |ℓ mi is a Clebsch-Gordan coefficient. There is a closed-form expression for these coefficients [Böh13]:
s
(2ℓ + 1)(ℓ + ℓ1 − ℓ2 )!(ℓ − ℓ1 + ℓ2 )!(ℓ1 + ℓ2 − ℓ)!
hℓ1 m1 ℓ2 m2 |ℓ mi =1m=m1 +m2
×
(ℓ1 + ℓ2 + ℓ + 1)!
p
(ℓ + m)!(ℓ − m)!(ℓ1 − m1 )!(ℓ1 + m1 )!(ℓ2 − m2 )!(ℓ2 + m2 )! ×
X
(−1)k
k

k!(ℓ1 + ℓ2 − ℓ − k)!(ℓ1 − m1 − k)!(ℓ2 + m2 − k)!(ℓ − ℓ2 + m1 + k)!(ℓ − ℓ1 − m2 + k)!

where the sum is over all k for which the argument of every factorial is nonnegative.

38

A.3

Moment tensor

Let F be a multi-set of frequencies from {1, 2, . . .} and consider the action of G = SO(3) on V = ⊕ℓ∈F Vℓ .
Recall that we want an explicit formula for Td (x) = Eg [(Π(g · x))⊗d ] with g ∼ Haar(G) (where Π can be the
identity in the case of no projection). We have
Eg [(Π(g · x))⊗d ] = Π⊗d Eg [ρ(g)⊗d ]x⊗d
(where x⊗d is a column vector of length dim(V )d ) and so we need an explicit formula for the matrix
Eg [ρ(g)⊗d ]. Here ρ(g) is block diagonal with blocks Dℓ (g) for ℓ ∈ F . There are no degree-1 invariants
since we have excluded the trivial representation ℓ = 0. For the degree-2 invariants Eg [ρ(g)⊗2 ], consider a
particular block Eg [Dℓ1 (g) ⊗ Dℓ2 (g)] for some pair (ℓ1 , ℓ2 ). The entries in this block can be computed using
0
the above orthogonality relations (and using D00
(g) = 1):
Eg [(Dℓ1 (g))m1 k1 (Dℓ2 (g))m2 k2 ] = 1ℓ1 =ℓ2 1m1 =−m2 1k1 =−k2 hℓ1 m1 ℓ2 m2 |0 0ihℓ1 k1 ℓ2 k2 |0 0i
= 1ℓ1 =ℓ2 1m1 =−m2 1k1 =−k2

(−1)m1 +k1
2ℓ1 + 1

ℓ1 +m1

√
using the special case hℓ1 m1 ℓ2 m2 |0 0i = 1ℓ1 =ℓ2 1m1 =−m2 (−1)
.
2ℓ1 +1
Similarly, for degree 3 we have

Eg [(Dℓ1 (g))m1 k1 (Dℓ2 (g))m2 k2 (Dℓ3 (g))m3 k3 ] =

1|ℓ2 −ℓ3 |≤ℓ1 ≤ℓ2 +ℓ3 1m1 +m2 +m3 =0 1k1 +k2 +k3 =0
A.4

(−1)m1 +k1
hℓ2 m2 ℓ3 m3 |ℓ1 (m2 + m3 )ihℓ2 k2 ℓ3 k3 |ℓ1 (k2 + k3 )i.
2ℓ1 + 1

Projection

Let V = ⊕ℓ∈F Vℓ with F a subset of {1, 2, . . .}. Let Π : V → W be the projection that takes a complex
spherical harmonic function and reveals only its values on the equator θ = π/2. In cryo-EM this projection
is applied separately to each shell (see Section 5.5). Letting L = maxℓ∈F ℓ, the functions b−L , b−L+1 , . . . , bL
(from the circle S 1 to R) form a basis for W , where bm (φ) = eimφ . The projection Π takes the form
Π(Yℓm ) = (−1)m Nℓm Pℓm (0)bm
extended by linearity. By taking a binomial expansion of (x2 − 1)ℓ it can be shown that
(
0
(ℓ + m) odd,
m

Pℓ (0) =
(−1)(ℓ−m)/2
ℓ
(ℓ+m)/2 (ℓ + m)! (ℓ + m) even.
2ℓ ℓ!

(12)

For cryo-EM, if we use the basis Hℓm so that the expansion coefficients are real, the output of the
projection can be expressed (with real coefficients) in the basis

1
imφ

+ (−1)m e−imφ )
m > 0,
 √2 (e
1
m = 0,
hm (φ) =

 √i (ei|m|φ − (−1)m e−i|m|φ ) m < 0,
2

where the projection Π takes the form

|m|

Π(Hℓm ) = (−1)m Nℓ|m| Pℓ
extended by linearity.

39

(0)hm

A.5

Explicit construction of invariants

Consider the cryo-EM setup (see Section 5.5) with S shells and F frequencies. We will cover S 2 registration as
the special case S = 1 (without projection). Use the basis of complex spherical harmonics, with corresponding
variables xsℓm with 1 ≤ s ≤ S, 1 ≤ ℓ ≤ F , and −ℓ ≤ m ≤ ℓ. One can change variables to Sℓm or Hℓm but
for our purposes of testing the rank of the Jacobian it is sufficient to just work with Yℓm (since the change
of variables has no effect on the rank of the Jacobian).
Recall that in Section A.3 we computed expressions for the matrices Eg [Dℓ1 (g)⊗ Dℓ2 (g)] and Eg [Dℓ1 (g)⊗
ℓ2
D (g) ⊗ Dℓ3 (g)], and in particular they are rank-1. Using this we can explicitly compute the entries of Td (x)
and thus extract a basis for U2T and U3T . We present the results below.
A.5.1

Degree-2 invariants

Without projection, the degree-2 invariants are
I2 (s1 , s2 , ℓ) =

X
1
(−1)k xs1 ℓk xs2 ℓ(−k)
2ℓ + 1
|k|≤ℓ

for s1 , s2 ∈ {1, . . . , S} and ℓ ∈ {1, . . . , F }. Swapping s1 with s2 results in the same invariant, so take s1 ≤ s2
to remove redundancies.
With projection, the degree-2 invariants are
X
Nℓm Nℓ(−m) Pℓm (0)Pℓ−m (0)I2 (s1 , s2 , ℓ)
P2 (s1 , s2 , m) = (−1)m
ℓ≥|m|

with s1 , s2 ∈ {1, . . . , S} and m ∈ {−F, . . . , F }. Negating m or swapping s1 with s2 results in the same
invariant (up to sign) so take s1 ≤ s2 and m ≥ 0 to remove redundancies. Recall the expression (12) for
Pℓm (0).
A.5.2

Degree-3 invariants

Let ∆(ℓ1 , ℓ2 , ℓ3 ) denote the predicate |ℓ2 − ℓ3 | ≤ ℓ1 ≤ ℓ2 + ℓ3 (which captures whether ℓ1 , ℓ2 , ℓ3 can be the
side-lengths of a triangle). Without projection, the degree-3 invariants are
I3 (s1 , ℓ1 , s2 , ℓ2 , s3 , ℓ3 ) =

1
2ℓ1 + 1

X

(−1)k1 hℓ2 k2 ℓ3 k3 |ℓ1 (−k1 )ixs1 ℓ1 k1 xs2 ℓ2 k2 xs3 ℓ3 k3

k1 +k2 +k3 =0
|ki |≤ℓi

for si ∈ {1, . . . , S} and ℓi ∈ {1, . . . , F } satisfying ∆(ℓ1 , ℓ2 , ℓ3 ). There are some redundancies here. First,
permuting the three (si , ℓi ) pairs (while keeping each pair in tact) results in the same invariant (up to scalar
multiple). Also, some of the above invariants are actually zero; specifically, this occurs when (s1 , ℓ1 ) =
(s2 , ℓ2 ) = (s3 , ℓ3 ) with ℓ1 odd, or when (s1 , ℓ1 ) = (s2 , ℓ2 ) 6= (s3 , ℓ3 ) with ℓ3 odd (or some permutation of this
case).
With projection, the degree-3 invariants are
P3 (s1 , m1 , s2 , m2 , s3 , m3 ) =
X
1
2
3
(0)Pℓm
(0)Pℓm
(0)hℓ2 m2 ℓ3 m3 |ℓ1 (−m1 )iI3 (s1 , ℓ1 , s2 , ℓ2 , s3 , ℓ3 )
Nℓ1 m1 Nℓ2 m2 Nℓ3 m3 Pℓm
(−1)m1
1
2
3
ℓ1 ,ℓ2 ,ℓ3 : ∆(ℓ1 ,ℓ2 ,ℓ3 )

for si ∈ {1, . . . , S} and mi ∈ {−F, . . . , F } such that m1 + m2 + m3 = 0. There are again redundancies under
permutation: permuting the three (si , mi ) pairs results in the same invariant. Negating all three m’s also
results in the same invariant. There are additional non-trivial linear relations (see Section A.6 below).

40

A.6
A.6.1

Counting the number of invariants
S 2 registration

For the case of S 2 registration (S = 1) the above degree-2 and degree-3 invariants without projection (with
G
redundancies removed as discussed above) form a basis for R[x]G
2 ⊕ R[x]3 (although we have not made this
rigorous). Thus, counting these invariants gives a combinatorial analogue of Proposition 5.7.
A.6.2

Cryo-EM

T
In this section we give a formula for trdeg(U≤3
) for (heterogeneous) cryo-EM (with projection), valid for all
K ≥ 1, S ≥ 1 and F ≥ 2. The formula is conjectural but has been tested (via the Jacobian criterion) for
various small values of K, S, F .
The number of algebraically independent degree-2 invariants turns out to be the number of distinct I2
invariants (i.e. without projection), since the projected invariants P2 are linear combinations of these. The
number of such invariants is 21 S(S + 1)F .
For degree 3, things are more complicated because the projected invariants P3 have smaller dimension
than the I3 . We start by counting the number of distinct (up to scalar multiple) P3 invariants. To this
end, let X (S, F ) be the set of equivalence classes of tuples (s1 , m1 , s2 , m2 , s3 , m3 ) with si ∈ {1, . . . , S} and
mi ∈ {−F, . . . , F }, modulo the relations

(s1 , m1 , s2 , m2 , s3 , m3 ) ∼ (s2 , m2 , s1 , m1 , s3 , m3 ) ∼ (s1 , m1 , s3 , m3 , s2 , m2 )
(s1 , m1 , s2 , m2 , s3 , m3 ) ∼ (s1 , −m1 , s2 , −m2 , s3 , −m3 )

(permutation)

(negation).

There are some non-trivial linear relations among the distinct P3 invariants, which we must now account
for. The number of such relations is
E(S) := 2S + 4S(S − 1) + S(S − 1)(S − 2).
This can be broken down as follows. For each k ∈ {1, 2, 3} there are 2k relations for each size-3 multisubset {s1 , s2 , s3 } of {1, . . . , S} with exactly k distinct elements. (We do not currently have a thorough
understanding of what exactly the linear relations are, but we have observed that the above pattern holds.)
We can now put it all together and state our conjecture. We will also use the formula (3) for trdeg(R[x]G ),
extended to the heterogeneous case via Proposition 4.15.
Conjecture A.1. Consider cryo-EM with F ≥ 2 frequencies.
• trdeg(R[x]G ) = K[S(F 2 + 2F ) − 3] + K − 1,
• dim(U2T ) = 12 S(S + 1)F ,
• dim(U3T ) = |X (S, F )| − E(S),
• generic list recovery is possible at degree 3 if and only if dim(U2T ) + dim(U3T ) ≥ trdeg(R[x]G ).
When S and F are large, the dominant term in dim(U2T ) + dim(U3T ) is |X (S, F )| ≈ S 3 F 2 /4 and so generic
list recovery is possible when (roughly) K ≤ S 2 /4.

B

Unique recovery for the regular representation

Let G be a finite abelian group. Let V be the regular representation of G over R, i.e. V = R|G| with
basis indexed by the elements of G, and the action of G permutes the basis elements vg according to group
multiplication: h · vg = vhg . Note that for the cyclic group G = Z/p, this is precisely the MRA problem. We
will show that with this setup, generic unique recovery is possible at degree 3:

41

Theorem B.1. Let G be a finite abelian group and let V be the regular representation of G over R. Then
T
R(U≤3
) is equal to the field of fractions of R[x]G .
Recall that the equality of the two fields above implies generic unique recovery at degree 3 by Corollary 4.25.
Generic unique recovery at degree 3 is actually true in the more general setting where V is the regular
representation over R of any finite group [Kak09].
T
Proof. It is sufficient to show C(U≤3
) = C(R[x]G ). Let p = |G| = dim(V ). The polynomial algebra on V
gets an action of G in the usual way and the degree-1 component is isomorphic to the regular representation.
Over C, the regular representation decomposes as a direct sum of all the characters χ(1) , . . . , χ(p) of G
(each of which is a group homomorphism G → C× = C r {0}). (Here we have used the fact that G is finite
and abelian, and so its irreducible representations are 1-dimensional.)
b = {χ(1) , . . . , χ(p) } be the set of characters. For each χ ∈ G
b let yχ ∈ C[V ] be the associated
Let G
eigenvector (in the degree-1 component of the polynomial algebra) so that g · yχ = χ(g)yχ for all g ∈ G.
b forms an abelian group (the character group or Pontryagin dual of G) under pointwise multiplication:
G
(χ1 χ2 )(g) = χ1 (g)χ2 (g).
b yχ yχ−1 is a degree-2 invariant, and for any χ1 , χ2 ∈ G,
b yχ1 yχ2 y(χ χ )−1 is a
Observe that for any χ ∈ G,
1 2
b we have
degree-3 invariant. For each χ ∈ G
Y
Y
yχ′ yχ′−1 =
yχp
yχ yχ′ y(χχ′ )−1
b
χ′ ∈G

b
χ′ ∈G

and so yχp lies in the field generated by the invariants of degree ≤ 3.
The field extension C(yχ(1) , . . . , yχ(p) )/C(yχp (1) , . . . , yχp (p) ) is Galois with Galois group H = (Z/p)p ; the
generator of the ith copy of Z/p acts by multiplying yχ(i) by a fixed primitive pth root of unity. (Recall that
the Galois group is the automorphisms of the larger field that fix the smaller field pointwise.)
By the fundamental theorem of Galois theory, intermediate extensions of the above Galois extension are
in bijection with subgroups of H. The correspondence maps a field to the group that fixes it (pointwise) and
maps a group to the field that it fixes. The field C(R[x]G ) is an intermediate extension with corresponding
T
group G. The field C(U≤3
) is also an intermediate extension, and we will show that its corresponding group
T
is also G, thus proving C(U≤3
) = C(R[x]G ) as desired.
T
T
Clearly G fixes C(U≤3 ) (since U≤3
are invariants), so it remains to show that there are no other automorT
phisms of C(yχ(1) , . . . , yχ(p) ) that fix U≤3
. Let φ ∈ H. As an element of (Z/p)p , we can write φ = (φ1 , . . . , φp ).
If χ = χ(i) we will also write φχ for φi . If φ fixes the degree-2 invariant yχ yχ−1 , we must have φχ−1 = φ−1
χ . If
.
In
particular,
=
φ
φ also fixes the degree-3 invariant yχ1 yχ2 y(χ1 χ2 )−1 , we must have φχ1 φχ2 = φ−1
χ
χ
−1
1 2
(χ1 χ2 )
b → C× given by χ 7→ φχ is a group homomorphism. Thus, any φ fixing U T can be identified
the map G
≤3
b
b , which is isomorphic to G; in particular there are only p
with an element of the Pontryagin double dual G
such elements φ, which completes the proof.

42

