---
abstract: 'In this paper, we establish optimal rates of adaptive estimation of a vector in the multi-reference alignment model, a problem with important applications in fields such as signal processing, image processing, and computer vision, among others.  We describe how this model can be viewed as a multivariate Gaussian mixture model under the constraint that the centers belong to the orbit of a group.  This enables us to derive matching upper and lower bounds that feature an interesting dependence on the signal-to-noise ratio of the model.  Both upper and lower bounds are articulated around a tight local control of Kullback-Leibler divergences that showcases the central role of moment tensors in this problem.' 
address:
- |
    [Afonso S. Bandeira]{}\
    [Department of Mathematics]{}\
    [Courant Institute of Mathematical Sciences]{}\
    [Center for Data Science]{}\
    [New York Univeristy,]{}\
    [New York, NY 10012, USA]{}\
- |
    [Philippe Rigollet]{}\
    [Department of Mathematics]{}\
    [Massachusetts Institute of Technology]{}\
    [77 Massachusetts Avenue,]{}\
    [Cambridge, MA 02139-4307, USA]{}\
- |
    [Jonathan Weed]{}\
    [Department of Mathematics]{}\
    [Massachusetts Institute of Technology]{}\
    [77 Massachusetts Avenue,]{}\
    [Cambridge, MA 02139-4307, USA]{}\
author:
-  
-  
-  
bibliography:
- 'mra\_moment\_matching.bib'
title: 'Optimal rates of estimation for multi-reference alignment'
---

,

,

Multi-reference alignment, Orbit retrieval, Mixtures of Gaussians

Introduction
============

A fundamental problem arising in various scientific and engineering domains is the presence of heterogenous data.  In many applications, each observation of an object of interest is corrupted not only by noise but also by a latent transformation, which can often be modeled as the action of an unknown element of a known group.  The presence of these latent transformations raises serious challenges, both in theory and in practice. 

Our goal in this work is to inaugurate the statistical study of such models and establish optimal rates of estimation for a particular version known in the computer science literature as *multi-reference alignment*, a simple problem arising in fields such as structural biology [@SchValNun05; @TheSte12; @Sad89], image recognition [@Bro92], and signal processing [@ZwaHeiGel03].  The tools we develop to prove these bounds provide a unified theoretical framework for statistical estimation in the presence of algebraic structure. 

Algebraically structured models and cryo-EM
-------------------------------------------

A primary motivation to study models with algebraic structure is cryo-electron microscopy (cryo-EM), an important technique to determine three-dimensional structures of biological macromolecules.  The citation for the 2017 Nobel prize in Chemistry, awarded to its inventors, reads:

> The Nobel Prize in Chemistry 2017 was awarded to Jacques Dubochet, Joachim Frank and Richard Henderson “for developing cryo-electron microscopy for the high-resolution structure determination of biomolecules in solution". 

In this imaging technique, each measurement consists of a noisy tomographic projection of a rotated—by an unknown rotation in $\mathrm{SO}(3)$—copy of an unknown molecule.  The task is then to reconstruct the molecule density from many such measurements.  This reconstruction problem has received significant attention, primarily from computational perspectives, but its statistical properties remain largely unexplored.  This problem features three singular characteristics: (i) The latent group action in each observation—here a rotation—(ii) the tomographic projection and (iii) the presence of high noise as illustrated by Figure \[FIG:noisy\_image\]. 

[r]{}[0.4]{}

As a first step toward the statistical analysis of this class of algebraically structured models, we focus on a simpler model that features two of the aforementioned characteristics, namely (i) the presence of a group action and (iii) the presence of high noise.  This model is simpler to analyze and already presents fundamentally novel statistical features that manifest themselves in nonclassical rates of estimation. 

Denote by ${\mathcal{G}}$ a known compact subgroup of the group $\mathrm{O}(L)$ of orthogonal transformations of ${{\rm I}\kern-0.18em{\rm R}}^L$. Throughout this paper, we identify the action of a group element $G \in {\mathcal{G}}\subset \mathrm{O}(L)$ on ${{\rm I}\kern-0.18em{\rm R}}^L$ by left-multiplication with an orthogonal matrix $G$. We slightly abuse terminology by referring to $G$ as a group element.  Our goal is to recover a parameter $\theta \in {{\rm I}\kern-0.18em{\rm R}}^L$, which we often refer to as a *signal*, on the basis of very noisy observations corrupted by unknown elements of ${\mathcal{G}}$. Concretely, we observe $$\label{eqn:basic_model}
Y_i = G_i \theta + \sigma \xi_i\,,$$ where $G_i \in {\mathcal{G}}$ is unknown and $\xi_i$ is standard Gaussian noise independent of $G_i$. The parameter $\theta$ is only identifiable up to the action of ${\mathcal{G}}$, so we focus on obtaining an estimator $\tilde \theta$ whose distance to the orbit of $\theta$ as defined by $$\rho(\tilde \theta, \theta) := \min_{G \in {\mathcal{G}}} \|\tilde \theta - G \theta\|$$ is small in expectation.  We call  an *algebraically structured model*.  For normalization purposes, we assume that $c^{-1} \leq \|\theta\| \leq c$ for some universal positive constant $c$. Fixing the scaling of $\theta$ in such a way allows us to control the signal-to-noise ratio of the problem only via the parameter $\sigma$, which plays a central role in the sequel. 

Prior work: The synchronization approach {#sec:synchro}
----------------------------------------

The difficulty of algebraically structured models resides in the fact that both the signal $\theta$ and the transformations $G_1,\ldots,G_n \in {\mathcal{G}}$ are unknown and the latter are therefore latent variables.  If the group elements were known, one could easily estimate the vector $\theta$ by taking the average of $G_i^{-1} Y_i, i =1, \ldots, n$. In fact, this simple observation is the basis of the leading current approach to this problem, called the “synchronization approach" [@BanChaSin14; @BanCheSin15].  Specifically, synchronization aims at recovering the latent variables $G_{i}$ by solving a problem of the form $$\label{eqn:latent_rotations}
\min_{H_{1}, \dots, H_{n} \in {\mathcal{G}}} \sum_{1 \leq i, j \leq n} \big\|{H}_{i}^{-1} Y_i - {H}_{j}^{-1} Y_j\big\|^2\,.$$ Denoting by $\tilde H_{i}$ the solutions of , one can then estimate $\theta$ by the average of ${\tilde H}^{-1}_i Y_i, i =1, \ldots, n$.

Despite synchronization problems being computationally hard in general [@BanChaSin14], certain theoretical guarantees have been derived under specific noise models that are unfortunately not realistic for the problems of interest in this paper.  For example, it is often assumed that each *pair* of observations is corrupted by independent noise, so that the terms in the sum in  are independent.  Instead, our model adopts the more relevant assumption of independent noise on each observation.  Among the most prominent methods to date are spectral methods [@Sin11; @BanSinSpi11], semidefinite relaxations [@BanChaSin14; @BanCheSin15; @AbbBanBra14b; @BanBouSin16; @JavMonRic16; @BanBouVor16], methods based on Approximate Message Passing [@PerWeiBan16a] and other modified power methods [@Boumal_ProjPowerMethod; @Chen_Candes_ProjPowerMethod].  Synchronization also enjoys many interesting connections with geometry (see, e.g., [@Gao_GeometrySynchronization]). 

Another fundamental drawback of the synchronization approach is its intolerance to large noise levels $\sigma$. When $\sigma$ is significantly smaller than $\|\theta\|$, the prior work referenced above has demonstrated empirically and theoretically that the synchronization approach yields excellent results.  Intuitively, the success of this approach relies on the fact that when the noise is small, macroscopic features of the underlying signal are still visible.  However, as noted in our discussion of cryo-EM, the noise level in applications is often significantly larger than the signal [@Sig16], which renders the synchronization approach unusable.  An illustration of the difference between these regimes appears in Figure \[fig:noise\_low\_high\]. 

![ Instances of the multi-reference alignment problem, defined in Section \[sec:mra\], at low (left column) and high (right column) noise levels.  The true underlying signal appears in gray, and the noised version appears in red.  When the noise level is low, large features of the signal are still visible despite the noise; in the presence of large noise, however, the signals cannot reliably be synchronized.[]{data-label="fig:noise_low_high"}](noise_low_high.pdf){width="\textwidth"}

From a theoretical standpoint, this fact implies that the low- and high-noise regimes are very different: when the noise is sufficiently large, prior work has shown that the transformations are impossible to reliably estimate, regardless of the number of samples [@Weinstein_limitssignalalignment; @Sapiro_limitsimagealignment].  Thus, for the high-noise regime, new techniques are required.  We therefore focus in this work on the case where the variance of the noise is bounded below by a constant. 

The Gaussian mixture approach {#SEC:setup}
-----------------------------

We propose an alternative to the synchronization approach that completely bypasses the estimation of the transformations $G_1,\dots,G_n$ in favor of estimating $\theta$ directly.  To do so, we first show how to recast our model as a continuous mixture of Gaussians whose centers are algebraically constrained. 

To reinterpret  as a Gaussian mixture model, we replace the latent group elements $G_1, \dots, G_n$ by group elements drawn independently and uniformly at random (according to the Haar measure) from ${\mathcal{G}}$. This is a worst-case assumption, which is appropriate since we prove minimax rates.[^1] Indeed, we can always reduce to this case: since the Gaussian distribution is invariant under the action of the orthogonal group, we can transform each observation $Y_i$ into $H_i Y_i$, where $H_i$ is uniformly distributed over ${\mathcal{G}}$ and independent of all other random variables.  Since $H_i G_i$ is also uniformly distributed over ${\mathcal{G}}$, these new observations are drawn from a mixture of Gaussians whose centers are given by $G\theta$, $G \in {\mathcal{G}}$, with uniform mixing weights.  In particular, these centers are linked together by a rigid algebraic structure: they are the orbit of $\theta \in {{\rm I}\kern-0.18em{\rm R}}^L$ under the action of ${\mathcal{G}}$.

We therefore specify the following Gaussian mixture model.  Given a noise level $\sigma$, group ${\mathcal{G}}\subseteq \mathrm{O}(L)$, and parameter of interest $\theta \in {{\rm I}\kern-0.18em{\rm R}}^L$, denote by ${\mathrm}{P}_\theta$ the distribution of a random variable $Y$ satisfying $$\label{eq:MRA:model}
Y = G\theta + \sigma \xi\,,$$ where $G$ is drawn uniformly from ${\mathcal{G}}$ and $\xi \sim {\mathcal{N}}(0, I_L)$ is independent Gaussian noise. 

We assume throughout that the noise variance $\sigma^2$ is known.  This assumption is realistic in many applications such as imaging or signal processing, where it is inexpensive to collect pure-noise samples from ${\mathrm}{P}_0$ and thereby estimate $\sigma^2$ to arbitrary accuracy. 

In this work, we analyze the maximum likelihood estimator (MLE) $\tilde \theta_n$ for : $$\label{eq:ML:mixtureGaussian}
\tilde \theta_n=\operatorname*{argmax}_{\phi \in {{\rm I}\kern-0.18em{\rm R}}^L} \sum_{i=1}^n \log {{\rm I}\kern-0.18em{\rm E}}\big[ \exp\big(- \frac{1}{2\sigma^2} \|Y_i - G \phi\|^2\big)\big|Y_i\big]\,.$$ We focus on obtaining the optimal scaling of the quantity $\rho(\tilde \theta_n, \theta)$ with the signal-to-noise ratio of the problem.[^2] This question is central to signal processing problems where $\sigma$ is quite large, since it determines the order of magnitude of the sample size $n$ required to achieve a certain accuracy.  Moreover, in many applications, technological improvements to the measurement apparatus can directly improve the effective value of $\sigma$—in cryo-EM, for instance, this is a focus of active research [@Sig16].  For these reasons, understanding the scaling of $\rho(\tilde \theta_n, \theta)$ with $\sigma$ is a core question both in theory and in practice.  Our main upper bound result gives a *uniform* analysis of this maximum likelihood estimator, valid for any algebraically constrained model.  We complement this analysis with lower bounds which are equally universal.  In both cases, we proceed by controlling the Fisher information of the model. 

Gaussian mixture models have been extensively studied in the statistical literature since their introduction by [@Pea94] in the nineteenth century (see, e.g., [@McLPee00] for an overview).  As illustrated by the extant literature, mixture models are quite rich and broadly applicable to a variety of statistical problems ranging from clustering to density estimation.  It is known that the rate of estimation of the parameters of a Gaussian mixture with $k$ components can scale like $n^{-O(1/k)}$ (see for example [@Che95; @MoiVal10] and more recently [@HeiKah15] for an interesting explanation from the point of view of model misspecification).  In this work, our analysis of the multi-reference alignment problem focuses on a setting where the convergence of $\tilde \theta_n$ to $\theta$ occurs at the parametric $n^{-1/2}$ rate; nevertheless, our results show that even in this benign setting, the optimal dependence of this rate on $\sigma$ can still be extremely poor. 

Multi-reference alignment {#sec:mra}
-------------------------

As an application of our techniques, we analyze and establish optimal rates for a model known as multi-reference alignment, a simple algebraically structured model.  Multi-reference alignment is a special case of cryo-EM, where instead of three-dimensional rotations we consider phase shifts of a periodic signal.  This represents a special case of cryo-EM because it corresponds to the situation when the axis of rotation of the molecule is known, but not its angle. 

In addition to being a toy model for cryo-EM, this simpler model is also of independent interest in several applications including in structural biology [@TheSte12] and radar classification [@ZwaHeiGel03].  A discrete version of this problem where the group is the cyclic group ${\mathbb{Z}}/L$ acting on the coordinates of $\theta$ was introduced in [@BanChaSin14] to permit approaches based on semi-definite programming; however, our results indicate that this simplification is not actually benign, in the sense that the discretized model admits significantly worse rates of estimation than the model we describe below.  We compare our more general model with theirs in Appendix \[supp\]. 

Let $f: [0, 1] \to {{\rm I}\kern-0.18em{\rm R}}$ be an unknown function, and let $g_{s}$ be the shift operator which acts on $f$ by $g_{s}\hspace{-.5ex}\circ\hspace{-.5ex} f(x) = f(x + s)$, where $s \in [0, 1)$ and the addition is performed modulo $1$. These operators clearly form a group, denoted ${\mathcal{S}}$, which is isomorphic to ${{\rm I}\kern-0.18em{\rm R}}/{\mathbb{Z}}$. We observe independent copies of $$\label{eq:continuous_model}
Y = g_{s} \hspace{-.5ex}\circ\hspace{-.5ex} f(x) + \sigma \xi\,,$$ where where $g_{s} \hspace{-.5ex}\circ\hspace{-.5ex} f(x) \in {{\rm I}\kern-0.18em{\rm R}}^L$ denotes the vector $(g_s\hspace{-.5ex}\circ\hspace{-.5ex} f(x_j))_{j=1}^L$ for the fixed design $x_j = j/L$, $s$ is drawn uniformly at random from $[0, 1]$, and $\xi \sim {\mathcal{N}}(0, I_L)$ is independent of $s$. To put  into the same form as , assume that the function $f$ is *band limited*—i.e.,  the Fourier transform of $f$ vanishes outside the interval $[-B, B]$ for some positive integer $B$—and that the measurements are performed above the *Nyquist frequency*—i.e.,  $L > 2B$. This assumption ensures that the function $f$ is identifiable, in that the discrete measurements $f(x_1), \dots, f(x_L)$ suffice to recover $f$.

The action of ${\mathcal{S}}$ on $f(x)$ can be identified with a subgroup of the orthogonal group $\mathrm{O}(L)$ by passing to the Fourier domain.  Indeed, since $f$ is band limited, it can be identified with the vector of its $2B + 1$ Fourier coefficients $(\hat f(-B), \dots, \hat f(B))$, which we denote by $\hat f$. Writing $$f(x) = \sum_{k=-B}^{B} \hat f(k) e^{-2\pi \mathrm{i} k x}\,,$$ yields the relation $$\widehat{g_{s} \hspace{-.5ex}\circ\hspace{-.5ex} f}(k) = \hat f(k) e^{-2 \pi \mathrm{i} s k} =: \hat f(k) z^k\,,$$ where $z = e^{-2 \pi \mathrm{i} s}$ is a complex number of unit norm.  This identifies ${\mathcal{S}}$ with the circle group $U(1)$. Writing $\theta$ for the vector $f(x)$, we obtain an example of : we observe independent copies of $$\label{eq:phase_shift}
Y = G_{z} \theta + \sigma \xi\,,$$ where $\theta \in {{\rm I}\kern-0.18em{\rm R}}^L$ is the parameter to be estimated, $z$ is drawn uniformly at random from $U(1)$, $\xi$ is a standard Gaussian random variable independent of $z$, and $G_{z} \theta$ is defined by its Fourier coefficients: $$\label{eq:discrete_action}
\widehat{G_z \theta}_k = z^k \hat \theta_k \text{ for $k = -\lfloor L/2 \rfloor, \dots, \lfloor L/2 \rfloor$,}$$ where we use the notation $\hat \theta$ to represent the discrete Fourier transform of $\theta$. If we restrict $z$ to be of the form $\omega^L$, where $\omega$ is a primitive $L$th root of unity, then we recover the discrete model of [@BanChaSin14].  We call model , the *phase shift* model. 

Organization of the paper
-------------------------

In Section \[section\_mainresults\] we present our main results, Theorems \[thm:main\_lower\] and \[thm:main\_upper\], providing minimax rates for the multi-reference alignment problem under the phase shift model .  The proofs of these theorems rely on developing general tools for analyzing algebraically structured models and controlling the Kullback-Leibler divergence between distributions corresponding to two different signals. 

In Section \[sec:uniform\_upper\], we give guarantees on the maximum likelihood estimator (MLE) under a condition on the curvature of the KL divergence.  We then specialize to the phase shift model in Section \[SEC:modMLE\] and develop a modified MLE for the phase shift model which achieves the optimal rates in Theorem \[thm:main\_upper\].  Section \[sec:multi\] concludes by establishing the lower bound in Theorem \[thm:main\_lower\]; the proof involves finding pairs of different signals with several matching invariant moment tensors.  Both lower and upper bounds depend on an analysis of the KL divergence for algebraically structure models, which appears in Appendix \[sec:tight\_bounds\]. 

Notation
--------

We define the Fourier transform $\hat \theta$ of $\theta \in {{\rm I}\kern-0.18em{\rm R}}^L$ by $$\hat \theta_j = \frac{1}{\sqrt L} \sum_{k=1}^L e^{2 \pi \mathrm{i} j k /L} \theta_k\,, \quad \quad - \lfloor L/2 \rfloor \leq j \leq \lfloor L/2 \rfloor\,.$$ We assume for convenience throughout that $L$ is odd. 

The symbol $\|\cdot \|$ denotes the $\ell_2$ norm on ${{\rm I}\kern-0.18em{\rm R}}^L$. For any positive integer $k$, we write $[k]=\{1, \ldots, k\}$. We use $z^*$ to denote the complex conjugate of $z \in \mathbb{C}$

Given a vector $t$, let $t^{\otimes k}$ denote the order-$k$ tensor formed by taking the $k$-fold tensor product of $t$ with itself.  Denote by $\|A\|$ the Hilbert-Schmidt norm of a tensor $A$, defined by $\|A\|^2 = \langle A, A\rangle$, where $\langle \cdot, \cdot \rangle$ denotes the entrywise inner product.  It is easy to check that, for any two column vectors $t, u$ of the same size, the identity $\langle t^{\otimes k}, u^{\otimes k}\rangle=(t^\top u)^k$ holds. 

A tensor $A$ is *symmetric* if $A_{i_1\dots i_k} = A_{i_{\pi(1)} \dots i_{\pi(k)}}$ for any permutation $\pi$ of $[k]$. For such tensors, the value $A_{i_1\dots i_k}$ depends only on the multiset $\{i_1,\dots,i_k\}$, or equivalently on the multi-index $\alpha$ defined by $\alpha_\ell = |\{j \in [k]: i_j = \ell\}|$.

The Kullback-Leibler (KL) divergence between two distributions $P$ and $Q$ such that $P \ll Q$ is given by $$D(P {\,\|\,}Q) = \int\log \big(\frac{dP}{dQ}\big) \,dP\,.$$ It is well known that $D(P {\,\|\,}Q) \geq 0$, with equality holding iff $P = Q$.

Main results {#section_mainresults}
============

As mentioned above, the rescaled loss $\sqrt{n}\rho(\tilde \theta_n, \theta)$ of the maximum depends asymptotically on the Fisher information of the model, which can be related to the curvature of the Kullback-Leibler divergence around its minimum.  Conversely, (lack of) curvature of the Kullback-Leibler divergence around its minimum is what controls minimax lower bounds that are valid for *any* esitmator.  We provide a unified framework for proving upper and lower bounds based on the curvature of the divergence function, following an idea originally introduced in [@LepNemSpo99] in the context of functional estimation and further developed by [@JudNem02; @CaiLow11; @WuYan16; @CarVer17; @BlaCarGut17].  In the multi-reference alignment model, this approach allows us to relate Kullback-Leibler divergence to moment tensors, which can in turn be controlled using Fourier-theoretic arguments. 

Our analysis establishes that the difficulty of estimating a particular signal $\theta$ depends on the support of the Fourier transform $\hat \theta$ of $\theta$. Define the *positive support* $\operatorname{psupp}(\hat \theta)$ of $\hat \theta$ by $$\operatorname{psupp}(\hat \theta) = \{j \mid j \in \{1, \dots,  L/2 \}, \hat \theta_j \neq 0\}\,.$$ We focus only on the positive indices because the signal $\theta$ is real, so the Fourier transform is conjugate symmetric: $\hat \theta_j^* = \hat \theta_{-j}$. We make the following assumptions. 

\[assumption:norm\] There exists an absolute constant $c > 1$ such that $c^{-1} \leq \|\theta\| \leq c$.

\[assumption\] Moreover, there exists an absolute constant $c_0$, not depending on $n$, such that $c_0 \leq |\hat \theta_j|$ for all $j \in \operatorname{psupp}(\hat \theta)$.

We denote by ${\mathcal{T}}$ the set of vectors satisfying Assumptions \[assumption:norm\] and \[assumption\].  Assumption \[assumption:norm\] is benign and is adopted for normalization purposes, so that $\sigma$ captures entirely the signal-to-noise ratio of the problem.  Regarding Assumption \[assumption\], we emphasize that this is the situation of most interest to practitioners: the existence of very small, but non-zero, coordinates whose values approach $0$ with $n$ should rightly be considered pathological.  Assumption \[assumption\] rules out certain artificial situations analogous to classical difficulties arising in estimating mixtures of Gaussians, such as distinguishing the mixture $.5{\mathcal{N}}(+{\varepsilon}, 1) + .5{\mathcal{N}}(-{\varepsilon}, 1)$ from the single Gaussian ${\mathcal{N}}(0, 1)$ for very small ${\varepsilon}$. Determining minimax rates of estimation without Assumption \[assumption\] is certainly of theoretical interest, and we leave this question for future work. 

As noted above, our results focus on understanding how minimax rates of estimation for the multi-reference alignment problem scale with $\sigma$. This is the question of primary interest in algebraically structured problems like cryo-EM, since in these applications $\sigma$ is the only part of the model that can be improved by the development of new imaging technologies and techniques.  We note that our results do not address the dependence on the dimension $L$, and obtaining sharp dependence on $L$ is an attractive open problem. 

The following theorem reveals a surprising phenomenon: even under Assumption \[assumption\], the multi-reference alignment problem suffers from the curse of dimensionality.  We prove the following lower bound for the phase shift model. 

\[thm:main\_lower\] Let $0 \leq s \leq \lfloor L/2 \rfloor$. Let ${\mathcal{T}}_s$ be the set of vectors $\theta \in {\mathcal{T}}$ satisfying $\operatorname{psupp}(\hat \theta) \subset [s]$. For any $\sigma \geq \max_{\theta \in {\mathcal{T}}_s} \|\theta\|$, the phase shift model satisfies $$\label{eqn:minimax_lower}
\inf_{T_n} \sup_{\theta \in {\mathcal{T}}_s} {{\rm I}\kern-0.18em{\rm E}}_\theta[{\rho}(T_n, \theta)] \geq C\Big( \frac{\sigma^{(2s-1) \vee (s+1)}}{\sqrt n} \wedge 1\Big)\,,$$ where the infimum is taken over all estimators $T_n$ of $\theta$ and where $C$ is a universal constant. 

The $\sigma^{s+1}/\sqrt n$ rate in Theorem \[thm:main\_upper\] holds only in the edge case when $s \in \{0, 1\}$; for $2 \leq s \leq \lfloor L/2 \rfloor$ the rate scales as $\sigma^{2s-1}/\sqrt n$.

In Section \[sec:upper\_proof\], we show that a modified version of the MLE achieves the optimal rate asymptotically for $2 \leq s \leq \lfloor L/2 \rfloor$. This estimator is also adaptive to the class ${\mathcal{T}}_s$.

\[thm:main\_upper\] For any $\sigma \geq 1$ and $2 \leq s \leq \lfloor L/2 \rfloor$, the modified MLE $\check \theta_n$ for the phase shift model satisfies $$\label{eqn:minimax_upper}
\sup_{\theta \in {\mathcal{T}}_s} {{\rm I}\kern-0.18em{\rm E}}_\theta[{\rho}(\check \theta_n, \theta)] \leq C' \frac{\sigma^{2s -1}}{\sqrt n} + C_\sigma \frac{\log n}{n}\,,$$ where $C_\sigma \leq C'' \sigma^{12 s - 11}$ and $C'$ and $C''$ are constants depending on $L$ and $c_0$ but on no other parameter. 

Theorem \[thm:main\_upper\] excludes the cases where $s = 0$ or $s = 1$. The behavior of these cases is different, and is significantly easier to analyze. 

\[thm:small\_s\] If $s \in 
\{0,1\}$ and $\sigma \geq 1$, then the phase shift model satisfies $$\inf_{T_n} \sup_{\theta \in {\mathcal{T}}_s} {{\rm I}\kern-0.18em{\rm E}}_\theta[{\rho}(T_n, \theta)] \leq C''' \frac{\sigma^{s+1}}{\sqrt n}\,,$$ where $C'''$ is a constant depending on $c_0$ but on no other parameter. 

Theorem \[thm:small\_s\] is proved in Appendix \[supp\], where we exhibit a computationally efficient estimator achieving the upper bounds for $s \in \{0, 1\}$.

A few remarks are in order.  We have given rates over the classes ${\mathcal{T}}_s$ because, in the context of cryo-EM, it is generally assumed that band-limited signals, that is, signals lying in ${\mathcal{T}}_s$ for $s$ small, are easier to estimate.  Our work offers partial validation for this view.  However, we stress that the dependence on $s$ present in Theorems \[thm:main\_lower\] and \[thm:main\_upper\] is a consequence of the minimax paradigm.  Indeed, our proof of the lower bound involves a class of signals with very specific support in the Fourier domain.  Such signals drive the worst case bound of order $\sigma^{2s-1}/\sqrt{n}$. This is in striking contrast to the behavior for signals which are likely to arise in practice—in a companion paper [@PerWeeBan17], we show that signals whose Fourier transform has full support can be estimated at the rate $\sigma^3/\sqrt n$.

Second, our proof techniques do not allow us to remove the $\sigma$ dependence of the term $C_\sigma \log n/n$ in the upper bound.  In particular, for small values of $n$, this term may actually dominate.  We conjecture that this issue is an artifact of our proof technique and note that preliminary numerical results in [@PerWeeBan17] support this claim. 

Third, though we focus on the “high-noise regime,” we note that Theorems \[thm:main\_lower\] and \[thm:main\_upper\] do not require that $\sigma \to \infty$; we merely require that $\sigma$ be bounded below by a (small) constant. 

The rest of this paper is devoted to the proof of the main results in Theorems \[thm:main\_lower\] and \[thm:main\_upper\]. 

Maximum likelihood estimation {#sec:uniform_upper}
=============================

Let $Y_1, \dots, Y_n$ be i.i.d observations from the phase shift model  and consider the MLE $\tilde \theta_n$ that was defined in .  In this section, we prove our main statistical result, that is a *uniform* upper bound on the rate of convergence of the MLE in terms of the curvature of the divergence $D(\theta {\,\|\,}\phi)$ near its minimum.  Note that this analysis departs from the classical *pointwise* rate of convergence for MLE that guarantees a rate of convergence $n^{-1/2}$ *for each fixed choice of parameter* as $n \to \infty$. Our tools strengthen this result considerably.  Indeed, we show that for reasonable choices of $\theta$, the MLE achieves a rate of $n^{1/2}$ *uniformly* over all choices of $\theta$. We refer the reader to [@HeiKah15] for examples of Gaussian mixture problems where the pointwise and uniform rates of estimation differ. 

The following theorem establishes an upper bound for the MLE under a general lower bound for the KL divergence for any algebraically structured model.  Our proof technique applies to any subgroup ${\mathcal{G}}$ of $\mathrm{O}(L)$ and can be broadly applied to derive uniform rates of convergence for the MLE from the tight bounds on the KL divergence given in Theorem \[thm:tight\_KL\_bound\].  In the following section, we specialize this result to obtain the minimax upper bounds for the phase shift model over ${\mathcal{T}}_s$ that are presented in Theorem \[thm:main\_upper\].  From here on, positive constants may depend on $L$ unless noted otherwise. 

\[thm:non\_asymptotic\] Let ${\mathcal{T}}$ be any subspace of ${{\rm I}\kern-0.18em{\rm R}}^L$. Assume that there exist $k \geq 1$ and positive constants $c$ and $C$ such that for all $\theta, \phi \in {\mathcal{T}}$ satisfying $c^{-1} \leq \|\theta\| \leq c$ and $\sigma \in {{\rm I}\kern-0.18em{\rm R}}$ satisfying $\sigma \geq \|\theta\|$, $$D(\theta {\,\|\,}\phi)\geq C \sigma^{-2k}\rho^2(\theta, \phi)\,.\label{EQ:universal_curvature}$$ Then there exists positive constants $C'$ and $C''$ such that the MLE $\tilde \theta_n$ constrained to lie in ${\mathcal{T}}$ satisfies $$\label{eq:theorem:non_asymptotic}
{{\rm I}\kern-0.18em{\rm E}}_\theta[{\rho}(\tilde \theta_n, \theta)] \leq C'\frac{\sigma^{k}}{\sqrt{n}} + C_\sigma\frac{\log n}{n}\,,$$ uniformly over $\theta \in {\mathcal{T}}$ satisfying $c^{-1} \leq \|\theta\| \leq c$ and $\sigma \in {{\rm I}\kern-0.18em{\rm R}}$ satisfying $\sigma \geq \|\theta\|$, where $C_\sigma\le C''\sigma^{6k-5}$.

The symbols $c$ and $C$ denote constants whose value may change from line to line.  In the rest of this proof, we write $\tilde \theta=\tilde \theta_n$ to denote the constrained MLE.  Since $\theta$ and $\tilde \theta$ are both constrained to lie in ${\mathcal{T}}$, we restrict all functions of this proof to this subspace without loss of generality.  By rescaling by a constant, we can assume $\|\theta\| = 1$ and $\sigma \geq 1$.

The proof strategy is to combine control of the curvature of the function $D$ with control of the deviations of the log-likelihood function. 

Define the event ${\mathcal{E}}=\{{\rho}(\tilde \theta, \theta) \le {\varepsilon}\}$ where ${\varepsilon}$ is to be specified.  Since $D$ is invariant under the action of ${\mathcal{G}}$, we can assume without loss of generality that ${\rho}(\tilde \theta, \theta) = \|\tilde \theta - \theta\|$. We first establish that on this event, $\|\tilde \theta - \theta\|$ can be controlled in terms of the metric induced by the Hessian of $D$ at $\theta$. Fix $\theta \in {\mathcal{T}}$ and denote by $H$ the Hessian of the function $\phi \mapsto D(\theta {\,\|\,}\phi)$ evaluated at $\phi = \theta$. For any $u \in {{\rm I}\kern-0.18em{\rm R}}^L$, define $\|u\|_H = \sqrt{u^\top H u}$.

It follows from a Taylor expansion (Lemma \[lem:d\_taylor\] in Appendix \[supp\]) that on ${\mathcal{E}}$, $$\Big|D(\theta {\,\|\,}\tilde \theta) - \frac 1 2 \|\tilde \theta -\theta\|_H^2\Big| \leq C\frac{\|\tilde \theta -\theta\|^3}{\sigma^3}<\frac12D(\theta {\,\|\,}\tilde \theta)\,.$$ as long as ${\varepsilon}\leq c \sigma^{3 - 2k}$ for some sufficiently small constant $c$. This yields $$\frac 1 3 \|\tilde \theta - \theta\|_H^2 \leq D(\theta \, \| \, \tilde \theta) \leq \|\tilde \theta - \theta\|_H^2\,, \label{eqn:d_to_h_bound}$$ and, by , $$\|\tilde \theta - \theta\|_H^2 \geq c \sigma^{-2k} \|\tilde \theta - \theta\|^2\,.  \label{eqn:rho_to_h_bound}$$ for some constant $c$.

We now control the geometry of the log-likelihood function near $\theta$. Define $$D_n(\theta {\,\|\,}\phi) = \frac 1 n \sum_{i=1}^n \log \frac{f_\theta}{f_\phi}(Y_i)\,,$$ where $Y_i$ are i.i.d from ${\mathrm}{P}_\theta$ and $f_\zeta$ is the density of ${\mathrm}{P}_\zeta, \zeta \in {{\rm I}\kern-0.18em{\rm R}}^L$. Note that $D_n(\theta {\,\|\,}\theta) = 0$ and recall that $\tilde \theta$ minimizes $\phi \mapsto D_n(\theta {\,\|\,}\phi)
$ so that $D_n(\theta {\,\|\,}\tilde \theta) \leq 0$.

Since $\theta$ is held fixed throughout the proof, we abbreviate $D(\theta {\,\|\,}\phi)$ and $D_n(\theta {\,\|\,}\phi)$ as $D(\phi)$ and $D_n(\phi)$, respectively. 

Using Taylor expansion and $D(\theta)=D_n(\theta)=\nabla D(\theta)=0$, we get $$D(\tilde \theta) - D_n(\tilde \theta) = -\nabla D_n(\theta)^\top h + \frac 1 2 h^\top \nabla^2 (D - D_n)(\bar \theta)h\,,$$ where $h=\tilde \theta -\theta$ and $\bar \theta$ lies on a segment between $\tilde \theta$ and $\theta$. For all $\zeta \in {\mathcal{T}}$, write $H_n(\zeta)$ for the Hessian of $D_n(\phi)$ evaluated at $\phi = \zeta$, and similarly let $H(\zeta)$ be the Hessian of $D(\phi)$ evaluated at $\phi = \zeta$.

Combining the above equation with  and the fact that $D_n(\tilde \theta) \leq 0$ yields $$\label{eqn:second_order_expansion}
\frac 1 3 \|h\|_H^2 \leq D(\tilde \theta) - D_n(\tilde \theta) \leq - \nabla D_n(\theta)^\top h + \frac 1 2 h^\top (H(\bar \theta) - H_n(\bar \theta)) h\,.$$

For the first term, we employ the bound $|\nabla D_n(\theta)^\top h| \leq \|\nabla D_n(\theta)\|_H^* \|h\|_H$, where $\|\cdot\|_H^*$ denotes the dual norm to $\|\cdot\|_H$.

To control the second, note first that by , it holds $\|h\| \le C\sigma^k \|h\|_H$. Therefore, $$h^\top (H(\bar \theta) - H_n(\bar \theta)) h \leq C\sigma^k\|h\|_H\|h\|  \sup_{\phi \in {\mathcal{B}}_{\varepsilon}} \|H(\phi) - H_n(\phi)\|_\text{op} \,,$$ where ${\mathcal{B}}_{\varepsilon}:=\{\phi \in {{\rm I}\kern-0.18em{\rm R}}^L\,:\, \rho(\phi, \theta) \le {\varepsilon}\}$.

Combining the above bounds and dividing by $\|h\|_H$, we get that on ${{\mathcal{E}}}$, $$\begin{aligned}
\sigma^{-k}\|h\| \leq C \|h\|_H & \leq C\|\nabla D_n(\theta)\|_{H}^* + C\sigma^k\|h\|  \sup_{\phi \in {\mathcal{B}}_{\varepsilon}} \|H(\phi) - H_n(\phi)\|_\text{op}\\
& \leq C\|\nabla D_n(\theta)\|_{H}^* + C\sigma^{k+3} \sup_{\phi \in {\mathcal{B}}_{\varepsilon}} \|H(\phi) - H_n(\phi)\|_\text{op}^2+ \sigma^{k-3}\|h\|^2\,,\end{aligned}$$ where we applied Young’s inequality. 

Since ${\varepsilon}^{-1}{\rho}(\tilde \theta, \theta) \geq 1$ on ${\mathcal{E}}^c$, we get $$\begin{aligned}
{{\rm I}\kern-0.18em{\rm E}}[{\rho}(\tilde \theta, \theta)] &= {{\rm I}\kern-0.18em{\rm E}}[{\rho}(\tilde \theta, \theta){{\rm 1}\kern-0.24em{\rm I}}_{{\mathcal{E}}}] + {{\rm I}\kern-0.18em{\rm E}}[{\rho}(\tilde \theta, \theta){{\rm 1}\kern-0.24em{\rm I}}_{{{\mathcal{E}}}^c}]\\
&\le  C\sigma^{k}{{\rm I}\kern-0.18em{\rm E}}[\|h\|_H{{\rm 1}\kern-0.24em{\rm I}}_{{\mathcal{E}}}] +{\varepsilon}^{-1}{{{\rm I}\kern-0.18em{\rm E}}[{\rho}^2(\tilde \theta, \theta)]}\,.\end{aligned}$$

Choose ${\varepsilon}= c \sigma^{3-2k}$ for some small constant $c$. We obtain $$\label{EQ:pr_mainbd}
{{\rm I}\kern-0.18em{\rm E}}[{\rho}(\tilde \theta, \theta)]  \le C\Big(\sigma^k{{\rm I}\kern-0.18em{\rm E}}\|\nabla D_n(\theta)\|_{H}^* + \sigma^{2k+3} {{\rm I}\kern-0.18em{\rm E}}\sup_{\phi \in {\mathcal{B}}_{\varepsilon}} \|H(\phi) - H_n(\phi)\|_\text{op}^2+ \sigma^{2k-3}{{\rm I}\kern-0.18em{\rm E}}[{\rho}^2(\tilde \theta, \theta)]\Big)$$

It suffices to control the right side of the above inequality.  The main term is the first one.  We note that if $H$ were invertible, and hence $\|\cdot\|_H$ a genuine metric, then it is well known (see, e.g., [@HirLem01short]) that $
\|\nabla D_n(\theta)\|_H^*=\|\nabla D_n(\theta)\|_{H^{-1}}\,. 
$ In general, $H$ is not invertible, but we still have $$\|u\|_H^* = \left\{\begin{array}{ll}
\sqrt{u^\top H^\dagger u} & \text{ if $u$ lies in the row space of $H$,} \\
\infty & \text{ otherwise,}
\end{array}\right.$$ where $H^\dagger$ denotes the Moore-Penrose pseudo-inverse of the matrix $H$. The Bartlett identities state that $$\begin{aligned}
{{\rm I}\kern-0.18em{\rm E}}[\nabla_\phi \log f_\phi(Y_i)|_{\phi = \theta}] & = 0\,,\\
{{\rm I}\kern-0.18em{\rm E}}[(\nabla_\phi \log f_\phi(Y_i)|_{\phi = \theta}) (\nabla_\phi \log f_\phi(Y_i)|_{\phi = \theta})^\top] & = H\,,\end{aligned}$$ and since $\nabla D_n(\theta) = \frac 1 n \sum_{i=1}^n \nabla_\phi \log f_\phi(Y_i)|_{\phi = \theta}$ and $Y_1, \dots, Y_n$ are independent, we obtain $${{\rm I}\kern-0.18em{\rm E}}[\nabla D_n(\theta) \nabla D_n(\theta)^\top] = \frac 1 n H\,.$$ In particular, $\nabla D_n(\theta)$ lies in the row space of $H$ almost surely.  Jensen’s inequality implies $$\label{EQ:bdGradient}
{{\rm I}\kern-0.18em{\rm E}}\|\nabla D_n(\theta)\|_{H}^* \le \Big(\operatorname{tr}( H^{\dagger} {{\rm I}\kern-0.18em{\rm E}}[\nabla D_n(\theta) \nabla D_n(\theta)^\top])\Big)^{1/2}  = \Big(\frac 1 n \operatorname{tr}(H^{\dagger} H)\Big)^{1/2}  \leq \sqrt{\frac L n}\,.$$ For the second term, standard matrix concentration bounds can be applied to show $$\label{EQ:bdHessian}
{{\rm I}\kern-0.18em{\rm E}}\sup_{\phi \in {\mathcal{B}}_{\varepsilon}} \|H(\phi) - H_n(\phi)\|_\text{op}^2 \leq C \frac{\log n}{n\sigma^4}\,.$$ A proof of  appears as Lemma \[lem:bdHessian\] in Appendix \[supp\]. 

Likewise, a standard slicing argument, Lemma \[eventA\] in Appenddix \[supp\], implies $$\label{EQ:slicing_ub}{{\rm I}\kern-0.18em{\rm E}}[{\rho}^2(\tilde \theta, \theta)] \le C\frac{\sigma^{4k-2}}{n}\,.$$

Plugging , , and  into , we get $${{\rm I}\kern-0.18em{\rm E}}[{\rho}(\tilde \theta, \theta)]  \le C\Big(\frac{\sigma^k}{\sqrt{n}} + \frac{\sigma^{2k-1}\log n}{n}+ \frac{\sigma^{6k-5}}{n}\Big)\,,$$ as desired. 

Minimax upper bounds {#SEC:modMLE}
====================

In this section, we apply the results of Section \[sec:uniform\_upper\] to the phase shift model .  Note that rather than the MLE, we study a constrained MLE because the lower bound  may only hold for a proper subset ${\mathcal{T}}\subset {{\rm I}\kern-0.18em{\rm R}}^L$ in Theorem \[thm:non\_asymptotic\].  This phenomenon does occur in the specific case of phase shifts: the divergence $D(\phi)$ is not curved enough in directions that perturb a null Fourier coefficient of $\theta$. To overcome this limitation, we split the sample $Y_1, \ldots, Y_n$ into two parts: with the first part we estimate the support of $\hat \theta$ under Assumption \[assumption\] and with the second part, we compute a maximum likelihood estimator constrained to have the estimated support. 

Specifically, assume for simplicity that we have a sample $Y_1, \ldots, Y_{2n}$ of size $2n$ and split it into two samples ${\mathcal{Y}}_1=\{Y_1, \ldots, Y_n\}$ and ${\mathcal{Y}}_2=\{Y_{n+1}, \ldots, Y_{2n}\}$ of equal size. 

Fourier support estimation
--------------------------

We use the first subsample ${\mathcal{Y}}_1$ to construct a set $\tilde S$ that coincides with $\operatorname{psupp}(\hat \theta)$ with high probability.  For any $j =1, \ldots, \lfloor L/2\rfloor $, define, $$M_j = \frac 1 n \sum_{i=1}^n |\widehat{(Y_i)}_j|^2 - \sigma^2\,.$$ Recall that, by Assumption \[assumption\], there exists a positive constant $c_0$ such that $|\hat \theta_j| \geq c_0$ for all $j \in \operatorname{psupp}(\hat \theta)$. Define the set $\tilde S$ by $$\tilde S=\Big\{ j \in \{1, \ldots, \lfloor L/2\rfloor\}\,:\,  M_j \geq \frac 12 c_0^2|  \Big\}$$

The following proposition shows that $\tilde S=\operatorname{psupp}(\hat \theta)$ with high probability. 

\[prop:projection\_construction\] There exists a positive constant $c$ depending on $c_0$ such that $${{\rm I}\kern-0.18em{\rm P}}[\tilde S \neq \operatorname{psupp}(\hat \theta)] \le   2L \exp(-c n \sigma^{-4})\,.$$

This follows from standard concentration arguments.  A full proof appears in Appendix \[supp\]. 

Constrained MLE
---------------

We use the second sample to construct a constrained MLE.  To that end, for any $S \subset  \{1, \ldots, \lfloor L/2\rfloor\}$, define the projection $P_S$ by $$\widehat{P_S(\phi)}_j = \left\{\begin{array}{ll}
\hat \phi_j & \text{ if $j \in S \cup -S$} \\
\hat \phi_0 & \text{ if $j = 0$} \\
0 & \text{ otherwise.} 
\end{array}
\right.$$ The image $\operatorname{Im}(P_{\tilde S})$ of $P_S$ is a $(2|S|+1)$-dimensional real vector space.  For convenience, write $\phi_S = P_S \phi$ for any vector $\phi \in {{\rm I}\kern-0.18em{\rm R}}^L$.

Having constructed the set $\tilde S$, we use the samples in ${\mathcal{Y}}_2$ to calculate a modified MLE $\check \theta_n$ constrained to lie in the subspace $\operatorname{Im}(P_{\tilde S})$. To analyze the performance of this constrained MLE, we check that  holds on this subspace. 

\[prop:lambda\_P\_bound\] Fix $2 \leq s \leq \lfloor L/2 \rfloor$ and $\theta \in {\mathcal{T}}_s$. Let $S = \operatorname{psupp}(\hat \theta)$. If ${\mathcal{T}}= \operatorname{Im}(P_S)$, then there exists $C>0$ such that for all $\sigma\ge \|\theta\|, \phi \in {\mathcal{T}}$, it holds $$D(\theta {\,\|\,}\phi)\geq C \sigma^{-4s+2}\rho^2(\theta, \phi) \,.\label{EQ:shift_universal_curvature}$$

For the sake of exposition, we only prove  for $\phi$ such that ${\rho}(\theta, \phi) \leq {\varepsilon}_0$ for some small ${\varepsilon}_0$ to be specified.  The complete proof is deferred to Appendix \[supp\].  In what follows, the symbols $c$ and $C$ will refer to unspecified positive constants whose value may change from line to line.  By rescaling by a constant, we can assume $\|\theta\| = 1$ and $\sigma \geq 1$.

By Lemma \[lem:first\_moment\], $$\label{eqn:k1_boundmt}
D(\phi) = \frac{1}{2\sigma^2}\| {{\rm I}\kern-0.18em{\rm E}}[G \theta - G \phi]\|^2 + D(\vartheta {\,\|\,}\varphi)\,,$$ where $\vartheta = \theta - {{\rm I}\kern-0.18em{\rm E}}G\theta$ and $\varphi = \phi - {{\rm I}\kern-0.18em{\rm E}}G \phi$. If $|\hat \theta_0 - \hat \phi_0| \geq \frac 1 2 {\rho}(\theta, \phi)$, then  implies $$D(\phi) \geq \frac{1}{2\sigma^2}\| {{\rm I}\kern-0.18em{\rm E}}[G \theta - G \phi]\|^2 = \frac{1}{2\sigma^2}(\hat \theta_0 - \hat \phi_0)^2 \ge \frac{{\rho}^2(\theta, \phi)}{8\sigma^2} \geq \frac 1 8 \sigma^{-4s+2} {\rho}^2(\theta, \phi)\,.$$ On the other hand, if $|\hat \theta_0 - \hat \phi_0| < \frac 1 2 {\rho}(\theta, \phi)$, then $${\rho}(\vartheta, \varphi)^2 = {\rho}(\theta_S, \phi)^2  - |\hat \theta_0 - \hat \phi_0|^2 \ge 3{\rho}^2(\theta, \phi)/4\,.$$ Thus, by , it suffices to show that $$D(\vartheta {\,\|\,}\varphi) \ge C \sigma^{-4s+2} {\rho}(\vartheta, \varphi)^2\,,$$ for vectors $\vartheta$ and $\varphi$ satisfying ${{\rm I}\kern-0.18em{\rm E}}G \vartheta  = {{\rm I}\kern-0.18em{\rm E}}G \varphi = 0$. In what follows, write ${\rho}(\vartheta, \varphi) = {\varepsilon}$. Since $D(\varphi)=D(G\varphi)$ for all $G \in {\mathcal{S}}$, we may assume that $\|\vartheta - \varphi\| = {\varepsilon}$. We will show that there exists a small positive constant $c$ such that for some $m \leq 2 s - 1$, $$\|\Delta_m\| := \|{{\rm I}\kern-0.18em{\rm E}}[(G\vartheta)^{\otimes m} - (G\varphi)^{\otimes m}]\| \geq c {\varepsilon}\,,$$ and the claim will follow from Theorem \[thm:tight\_KL\_bound\].  We denote by $\kappa$ a small constant whose value will be specified.  There are two cases: either $\vartheta$ and $\varphi$ have essentially the same power spectrum (i.e., $|\hat \vartheta_k| \approx |\hat \varphi_k|$ for all $k$) or their power spectra are very different.  We will treat these two cases separately. 

Recall that for each $j \in S$, by Assumptions \[assumption:norm\] and \[assumption\], the bounds $c_0^{-1}\le| \hat \vartheta_j| \le c$ hold.  Consider the polar form $\hat \varphi_j/\hat \vartheta_j = r_j e^{\mathrm{i} \delta_j}$, where $r_j\ge 0$.

#### Case a: There exists $j \in S$ such that $|1 - r_j| \ge \kappa {\varepsilon}$

The fact that $|\hat \vartheta_j| \geq c_0^{-1}$ implies $$\begin{aligned}
\|\Delta_2\|^2 & = \|{{\rm I}\kern-0.18em{\rm E}}[(G \vartheta)^{\otimes 2} - (G \varphi)^{\otimes 2}]\|^2 \\
& = \sum_{k = -\lfloor L/2 \rfloor}^{\lfloor L/2 \rfloor} (|\hat \vartheta_k|^2 - |\hat \varphi_k|^2)^2 \\
& \geq (|\hat \vartheta_j|^2 - |\varphi_j|^2)^2 \\
& = |\hat \vartheta_j|^4 (1 - r_j^2)^2 \\
& \geq c_0^{-4} (1+r_j)^2(1-r_j)^2 \\
& \geq c_0^{-4} \kappa^2 {\varepsilon}^2\,,\end{aligned}$$ so that $\|\Delta_2\| \geq c {\varepsilon}$.

#### Case b: $|1 - r_j| < \kappa {\varepsilon}$ for all $j \in S$

Denote by $p$ the smallest integer in $S$ and observe that $${\varepsilon}^2= {\rho}(\vartheta, \varphi)^2 = \min_{z: |z| = 1} 2 \sum_{j \in S} |1-r_jz^je^{\mathrm{i}\delta_j}|^2|\hat \vartheta_j|^2 \le C \sum_{j \in S} |1 - r_j e^{\mathrm{i}(p\delta_j-j \delta_p)/p}|^2\,,$$ where the inequality follows from choosing $z = e^{-\mathrm{i} \delta_p/p}$. Therefore, there exists a coordinate $\ell \in S$ such that $$\label{EQ:deltaphases}
|1 - e^{\mathrm{i} (p \delta_\ell - \ell \delta_p)/p}| \geq |1 - r_\ell e^{\mathrm{i}(p \delta_\ell - \ell \delta_p)/p}| - \kappa {\varepsilon}\geq c {\varepsilon}\,,$$ as long as $\kappa $ is chosen sufficiently small.  In particular, $|1 - e^{\mathrm{i} (p \delta_\ell - \ell \delta_p)/p}| > 0$, so $\ell \neq p$. Note that this fact implies that, if $|1 - r_j| < \kappa {\varepsilon}$ for all $j \in S$, then $|S| \geq 2$.

Choose $m = \ell + p$. Since $\ell, p \in S \subseteq [s]$ and $\ell \neq p$, the bound $m \leq 2s - 1$ holds.  As in the proof of Proposition \[prop:generalized\_matching\], we have that $$\begin{aligned}
\|\Delta_m\|^2 & = \sum_{j_1 + \dots + j_{m} = 0} \left|\prod_{n = 1}^{m} \hat \vartheta_{j_n}- \prod_{n = 1}^{m} \hat \varphi_{j_n}\right|^2 \\
& = \sum_{j_1 + \dots + j_{m} = 0} \left|1 - \prod_{n = 1}^{m} r_{j_n} e^{\mathrm{i} \delta_{j_n}}\right|^2 \prod_{n = 1}^{m} |\hat \vartheta_{j_n}|^2\,.\end{aligned}$$ Each term in the above sum is positive.  One valid solution to the equation $j_1 + \dots + j_m = 0$ is $j_1 = \dots = j_\ell = -p$ and $j_{\ell + 1} = \dots = j_m = \ell$. We obtain $$\begin{aligned}
\|\Delta_m\|^2 &\ge C \left|1 - e^{i (p\delta_\ell - \ell \delta_p)} \prod_{n = 1}^{m} r_{j_n} \right|^2 \\
& \geq C |1 - e^{i (p\delta_\ell - \ell \delta_p)}|^2 - C\left|1 - \prod_{n = 1}^{m} r_{j_n}\right|^2\,.\end{aligned}$$ As long as $\kappa {\varepsilon}$ is small enough, $\left|1 - \prod_{n = 1}^{m} r_{j_n}\right| \leq 2 m \kappa {\varepsilon}$. Moreover, as long as ${\varepsilon}_0 $ is chosen sufficiently small, $\delta_\ell$ and $\delta_p$ can both be chosen small enough that $|p \delta_\ell - \ell \delta_p| \leq 1$, in which case it holds $$|1 - e^{i (p\delta_\ell - \ell \delta_p)}|^2 \ge |1 - e^{i (p \delta_\ell - \ell \delta_p)/p}|^2 \ge c^2{\varepsilon}^2\,,$$ where the last inequality follows from .  So for ${\varepsilon}_0$ and $\kappa$ chosen sufficiently small, this proves the existence of an $m \leq 2s -1$ for which $\|\Delta_m\| \geq c {\varepsilon}$.

Proof of Theorem \[thm:main\_upper\] {#sec:upper_proof}
------------------------------------

Define ${\mathcal{R}}=\{\tilde S=\operatorname{psupp}(\hat \theta)\}$ and observe that $${{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta)] = {{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta){{\rm 1}\kern-0.24em{\rm I}}_{{\mathcal{R}}}] + {{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta){{\rm 1}\kern-0.24em{\rm I}}_{{\mathcal{R}}^c}]\,.$$ The first term is controlled by combining Proposition \[prop:lambda\_P\_bound\] and Theorem \[thm:non\_asymptotic\] to get $${{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta){{\rm 1}\kern-0.24em{\rm I}}_{{\mathcal{R}}}]\le C\frac{\sigma^{2s-1}}{\sqrt{n}} + C_\sigma\frac{\log n}{n}\,,$$ where $C_\sigma \le C\sigma^{12s-11}$.

To bound the second term, we use the Cauchy-Schwarz inequality and Proposition \[prop:projection\_construction\] to get $${{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta){{\rm 1}\kern-0.24em{\rm I}}_{{\mathcal{R}}^c}]\le 2L \exp(-c n \sigma^{-4}) \sqrt{{{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta)^2]} \leq C \frac{\sigma^4}{n} \sqrt{{{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta)^2]}\,.$$ We now show that ${{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta)^2]$ is bounded uniformly over all choices of $\tilde S$ by a constant multiple of $\sigma^2$ using a similar slicing argument as the one employed in the proof of Lemma \[eventA\] in Appendix \[supp\]. 

By the triangle inequality, $${\rho}(\check \theta_{n}, \theta) \leq {\rho}(\check \theta_{n}, \theta_{\tilde S}) + {\rho}(\theta_{\tilde S}, \theta) \leq {\rho}(\check \theta_{n}, \theta_{\tilde S}) + 1\,.$$ By Lemma \[lem:far\_quadratic\] in Appendix \[supp\], when ${\rho}(\check \theta_{n}, \theta_{\tilde S}) \geq 3 \sqrt 2 \sigma$, the divergence satisfies $D(\theta_{\tilde S} {\,\|\,}\check \theta_{n}) \geq c \sigma^{-2} {\rho}(\check \theta_{n}, \theta_{\tilde S})$. We therefore have $${\rho}(\check \theta_{n}, \theta_{\tilde S})^2\le 18 \sigma^2 + c^{-1} \sigma^2 D(\theta_{\tilde S} {\,\|\,}\check \theta_{n}) \le (C^\circ \sigma)^2(1+ \mathfrak{G}_n(\theta_{\tilde S} {\,\|\,}\check \theta_{n}))\,,$$ for some constant $C^\circ$, where $$\mathfrak{G}_n(\theta_{\tilde S} {\,\|\,}\check \theta_{n}) = D(\theta_{\tilde S} {\,\|\,}\check \theta_{n}) - D_n(\theta_{\tilde S} {\,\|\,}\check \theta_{n})$$ and where we have used the fact that $D_n(\theta_{\tilde S} {\,\|\,}\check \theta_{n}) \leq D_n(\theta_{\tilde S} {\,\|\,}\theta_{\tilde S}) = 0$.

For $j \ge 0$, define $T_j=\{\phi \in {{\rm I}\kern-0.18em{\rm R}}^d\,:\, 2^j\sigma \le \rho(\phi, \theta_{\tilde S})\le 2^{j+1}\sigma\}$ and let $J$ be such that $C^\circ \le 2^J \le 2C^\circ$. Observe that $$\begin{aligned}
{{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta_{\tilde S})^2]&\le 4 (C^\circ \sigma)^2 + \sum_{j\ge J} {{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta_{\tilde S})^2{{\rm 1}\kern-0.24em{\rm I}}(\check \theta_{n} \in T_j)]\\
&\le  4 (C^\circ \sigma)^2 + \sigma^2\sum_{j>J} 2^{2j+2}{{\rm I}\kern-0.18em{\rm P}}[\sup_{\phi \in T_j}\mathfrak{G}_n(\theta_{\tilde S} {\,\|\,}\phi)>2^{2j}]\\
&\le 4 (C^\circ \sigma)^2 + C \sigma^2 \sum_{j\ge 0} 2^{2j}\exp(-C2^{2j})\le C \sigma^2\,,\end{aligned}$$ where we used  from Appendix \[supp\] in the third inequality.  We obtain $${{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta)^2] \leq 2 {{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta_{\tilde S})^2] + 2 \leq C\sigma^2\,.$$

We have established that $${{\rm I}\kern-0.18em{\rm E}}[{\rho}(\check \theta_{n}, \theta)] \le C\Big(\frac{\sigma^{2s-1}}{\sqrt{n}}+\sigma^{12s - 11}\frac{\log n}{n}+\frac{\sigma^5}{n} \Big)\,,$$ which, since $s \geq 2$, completes the proof of Theorem \[thm:main\_upper\]. 

Minimax lower bounds {#sec:multi}
====================

Our minimax lower bounds rely ultimately on Le Cam’s classical two-point testing method [@LeC73].  For this reason, our lower bounds do not capture the optimal dependence in $L$ but only in $\sigma$ and $n$. In particular, the version that we use requires an upper bound on the KL divergence, which can be obtained using Theorem \[thm:tight\_KL\_bound\] and a moment matching argument. 

Moment matching
---------------

Theorem \[thm:tight\_KL\_bound\] implies that ${\mathrm}{P}_\theta$ and ${\mathrm}{P}_\phi$ are hard to distinguish when the quantities $$\|\Delta_m\| = \|{{\rm I}\kern-0.18em{\rm E}}[(G\theta)^{\otimes m}] - {{\rm I}\kern-0.18em{\rm E}}[(G\phi)^{\otimes m}]\|$$ vanish for $m \in [k]$. In this section, we show that, in the phase shift model, $\Delta_m, m \in [k]$ can be made to vanish for large $k$ by appropriately choosing the support of the Fourier transforms $\hat \theta$ and $\hat \phi$.

Before stating our main results, we first give a brief sketch of the technique.  As we show in the proof of Proposition \[prop:generalized\_matching\] below, the tensor ${{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes m}]$ has a simple form in the Fourier basis: $${{\rm I}\kern-0.18em{\rm E}}[(\widehat{G \theta})^{\otimes m}]_{j_1 \dots j_m} = \left\{\begin{array}{ll}
\hat \theta_{j_1} \cdots \hat \theta_{j_m} & \text{ if $j_1 + \dots + j_m = 0$,} \\
0 & \text{ otherwise.} 
\end{array}\right.$$

For example, the first moment tensor ${{\rm I}\kern-0.18em{\rm E}}[G \theta]$ contains only the term $\hat \theta_0$, and the second moment tensor ${{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes 2}]$ contains the term $\hat \theta_j \hat \theta_{-j}$ for each index $j$. Since $\theta$ has real entries, $\hat \theta_j \hat \theta_{-j} = |\hat \theta_j|^2$, so that ${{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes 2}]$ contains enough information to reconstruct the magnitudes of the Fourier coefficients, but not their phases.  This implies that if $\theta$ and $\phi$ satisfy $|\hat \theta_j| = |\hat \phi_j|$ for all $j$, then $\|{{\rm I}\kern-0.18em{\rm E}}[(G\theta)^{\otimes 2}] - {{\rm I}\kern-0.18em{\rm E}}[(G\phi)^{\otimes 2}]\| = 0$.

To exhibit two signals whose higher moments also match, we employ the following idea: if a tuple $(j_1, \dots, j_m)$ is of the form $(j_1, -j_1, j_2, -j_2, \dots)$, then ${{\rm I}\kern-0.18em{\rm E}}[(\widehat{G \theta})^{\otimes m}]_{j_1 \dots j_m} = |\hat \theta_{j_1}|^2  \cdots |\hat \theta_{j_m}|^2$. In other words, this entry of the $m$th moment tensor also only depends on the magnitudes of the Fourier coefficients of $\theta$ and not on their phases.  Therefore, if the only nonzero entries of ${{\rm I}\kern-0.18em{\rm E}}[(\widehat{G \theta})^{\otimes m}]$ and ${{\rm I}\kern-0.18em{\rm E}}[(\widehat{G \phi})^{\otimes m}]$ correspond to tuples of this form and if the magnitudes of the Fourier coefficients of $\theta$ and $\phi$ agree, then $\|{{\rm I}\kern-0.18em{\rm E}}[(G\theta)^{\otimes m}] - {{\rm I}\kern-0.18em{\rm E}}[(G\phi)^{\otimes m}]\| = 0$.

This argument is formalized in Proposition \[prop:generalized\_matching\]. 

\[prop:generalized\_matching\] Fix $2 \leq s \leq \lfloor L/2 \rfloor$ and let $\theta, \phi \in {{\rm I}\kern-0.18em{\rm R}}^L$ satisfy $$\hat \theta_j = \hat \phi_j = 0 \quad \text{for $j \notin \{\pm(s-1), \pm s \}$}$$ and $$|\hat \theta_{j}| = |\hat \phi_{j}| \quad \text{for $j \in \{\pm(s-1), \pm s\}$.}$$ If $G$ is drawn uniformly from ${\mathcal{S}}$, then for any $m =1, \dots, 2s-2$, $${{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes m}] = {{\rm I}\kern-0.18em{\rm E}}[(G \phi)^{\otimes m}]$$

Fix $m \leq 2s-2$. Since ${{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes m}]$ and ${{\rm I}\kern-0.18em{\rm E}}[(G \phi)^{\otimes m}]$ are symmetric tensors, to show that they are equal it suffices to show that $$\langle {{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes m}], u^{\otimes m}\rangle = \langle {{\rm I}\kern-0.18em{\rm E}}[(G \phi)^{\otimes m}], u^{\otimes m}\rangle \qquad \forall\, u \in {{\rm I}\kern-0.18em{\rm R}}^L$$ or equivalently, that $$\label{EQ:equaltensors}
{{\rm I}\kern-0.18em{\rm E}}[(u^\top G \theta)^m] = {{\rm I}\kern-0.18em{\rm E}}[(u^\top G \phi)^m]\qquad \forall\, u \in {{\rm I}\kern-0.18em{\rm R}}^L\,.$$

Consider the set ${\mathcal{P}}= \{\zeta \,:\, |\hat \zeta_j| = |\hat \theta_j| \,, \ \forall\, j\}$ and note that $\theta, \phi \in {\mathcal{P}}$. We show that the function $\zeta \mapsto {{\rm I}\kern-0.18em{\rm E}}[(u^\top G \zeta)^m]$ is constant on ${\mathcal{P}}$, which readily yields .  For a fixed shift $G_z \in {\mathcal{F}}$, we obtain $$u^\top G_z \zeta = \langle \hat u, \widehat{G_z \zeta}\rangle = \sum_{j = -\lfloor L/2 \rfloor}^{\lfloor L/2 \rfloor} \hat u_{-j} \hat \zeta_j z^{j}\,,$$ so $$(u^\top G_z \zeta)^m = \sum_{j_1, \dots, j_m = -\lfloor L/2 \rfloor}^{\lfloor L/2 \rfloor} z^{j_1 + \dots + j_m} \prod_{n = 1}^m \hat u_{-j_n} \hat \zeta_{j_n}\,.$$

Taking expectations with respect to a uniform choice of $z$ yields $$\label{EQ:sumofji}
{{\rm I}\kern-0.18em{\rm E}}[(u^\top G_z \zeta)^m]  = \sum_{j_1 + \dots + j_m = 0} \prod_{n = 1}^m \hat u_{-j_n} \hat \zeta_{j_n}\,,$$ where the sums are over all choices of coordinates $j_1, \dots, j_m \in \{-\lfloor L/2 \rfloor, \dots, \lfloor L/2 \rfloor\}$ whose sum is $0$.

The Fourier transform of $\zeta$ is supported only on coordinates $\pm (s-1)$ and $\pm s$, so we may restrict our attention to sums involving only those coordinates.  Suppose $j_1 + \dots + j_m = 0$. Define $$\begin{aligned}
\alpha & = |\{i : j_i = s-1\}| &
\beta & = |\{i : j_i = -(s-1)\}| \\
\gamma & = |\{i : j_i = s\}| &
\delta & = |\{i : j_i = -s\}| \end{aligned}$$

By assumption $j_1 + \dots + j_m = 0$, so the tuple $(\alpha, \beta, \gamma, \delta)$ is a solution to $$\alpha (s-1) + \beta (-(s-1)) + \gamma (s) + \delta (-s)  = 0$$ or, equivalently, $$\begin{aligned}
(\alpha-\beta) (s-1) + (\gamma-\delta) s & = 0 \nonumber\end{aligned}$$

Since $s-1$ and $s$ are coprime, $(\alpha - \beta)$ and $(\gamma - \delta)$ must be multiples of $s$ and $s-1$, respectively.  Since $|\alpha - \beta| + |\gamma - \delta| \leq m < 2s - 1$, in fact $\alpha - \beta = \gamma - \delta = 0$.

Therefore the only $m$-tuples $(j_1, \ldots, j_m)$ that appear in the sum on the right-hand side of  are those in which $+(s-1)$ and $-(s-1)$ occur an equal number of times and $+s$ and $-s$ occur an equal number of times.  For such $m$-tuples, the product $\prod_{n = 1}^m \hat u_{-j_n} \hat \zeta_{j_n}$ can be reduced to a product of terms of the form $\hat u_{-(s-1)}\hat u_{s-1}\hat \zeta_{s-1} \hat \zeta_{-(s-1)}$ and $\hat u_{-s}\hat u_{s}\hat \zeta_s \hat \zeta_{-s}$. Since $u$ and $\zeta$ are real vectors, $\hat u_j \hat u_{-j} = |u_j|^2$ and $\hat \zeta_j \hat \zeta_{-j} = |\hat \zeta_{j}|^2$ for all $j =  -\lfloor L/2 \rfloor, \dots, \lfloor L/2 \rfloor$, so $$\prod_{n = 1}^m \hat u_{-j_n} \hat \zeta_{j_n} = (|\hat u_{s-1}|^2 |\hat \zeta_{s-1}|^2)^{\alpha+\beta} (|\hat u_s|^2 |\hat \zeta_s|^2)^{\gamma+\delta}\,.$$ This quantity depends only on the moduli $|\hat \zeta_s|$ and $|\hat \zeta_{s-1}|$, hence it is the same for all $\zeta \in {\mathcal{P}}$. This completes the proof of  and therefore the proof of the proposition. 

Proof of Theorem \[thm:main\_lower\]
------------------------------------

Fix $n \geq 1$. We will select $\phi, \theta_n \in {\mathcal{T}}_s$ such that $\rho(\phi, \theta_n) \geq c \big(\frac{\sigma^{(2s-1) \vee (s+1)}}{\sqrt n} \wedge 1\big)$ for some small universal constant $c > 0$ but $D({\mathrm}{P}_{\theta_n}^n {\,\|\,}{\mathrm}{P}_{\phi}^n) \leq \frac 12$. The bound will then follow from standard techniques. 

If $s = 0$, then let $\phi = 0$ and $\theta_n = \frac{\sigma}{\sqrt{nL
}} {\mathbf{1}}$, where ${\mathbf{1}}$ denotes the all-ones vector of ${{\rm I}\kern-0.18em{\rm R}}^L$. Note that ${\rho}(\theta_n, \phi) = \sigma/\sqrt n$. Moving to the Fourier domain, we have $(\widehat{\theta_n})_0 = \sigma/\sqrt{n}$ and $(\widehat{\theta_n})_j = 0$ for $j \neq 0$, so that $\theta_n, \phi \in {\mathcal{T}}_0$. By Lemma \[lem:first\_moment\], $$D({\mathrm}{P}_{\theta_n}^n {\,\|\,}{\mathrm}{P}_{\phi}^n) = \frac{n\sigma^2}{2 n\sigma^2} = \frac{1}{2}\,.$$

If $s = 1$, let $\phi$ be given by $$\hat \phi_j = 
\left\{ \begin{array}{ll}
1/\sqrt{2} & \text{if $j  \in \{\pm 1\}$,} \\
0 & \text{otherwise.}\end{array}\right.$$ and let $\theta_n$ satisfy $$(\widehat{\theta_n})_j =
\left\{ \begin{array}{ll}
1/\sqrt{2} +  c_1 \frac{\sigma^2}{\sqrt{2n}} & \text{if $j \in \{\pm 1\}$,} \\
0 & \text{otherwise,}\end{array}\right.$$ for some constant $c_1 > 0$ to be specified.  Clearly $\theta_n, \phi \in {\mathcal{T}}_1$, and ${\rho}(\theta_n, \phi) = c_1 \frac{\sigma^2}{\sqrt n}$.

Theorem \[thm:tight\_KL\_bound\] implies that $$D({\mathrm}{P}_{\theta_n}^n {\,\|\,}{\mathrm}{P}_{\phi}^n) \leq \overline C \frac{n{\rho}(\theta_n, \phi)^2}{\sigma^4} \leq \frac{1}{2}\,,$$ by choosing $c_1$ small enough. 

Finally, suppose $s \geq 2$. Fix $z = e^{\mathrm{i} \delta}$ for $\delta = c_1 (\sigma^{2s-1}/\sqrt{n} \wedge 1)$ for some positive constant $c_1 \leq 1$ to be specified.  Let $\phi$ be given by $$\hat \phi_j  =
\left\{ \begin{array}{ll}
1/2 & \text{if $j  \in \{\pm(s-1), \pm s \}$,} \\
0 & \text{otherwise.} 
\end{array}\right.$$ Let $\theta_n$ be given by $$\begin{aligned}
(\widehat{\theta_n})_j  =
\left\{ \begin{array}{ll}
1/2 & \text{if $j \in \{\pm(s-1)\}$,} \\
z/2 & \text{ if $j = s$,} \\
z^*/2 & \text{ if $j = -s$,} \\
0 & \text{otherwise.} 
\end{array}\right.\end{aligned}$$ Note that $\theta_n$ and $\phi$ both lie in ${\mathcal{T}}_s$.

For any unit complex number $w \in U(1)$, we have $$\|\theta_n - G_w \phi\|^2 = \frac 12 (\|1 - w\|^2 + \|z - w\|^2) \ge \frac14 \|1 - z\|^2\,.$$ So $$\frac 1 4 \|1-z\|^2 \leq \rho^2(\theta_n, \phi) \leq \|\theta_n - \phi\|^2 = \frac 12 \|1 - z\|^2\,,$$ and under the assumption that $\delta \leq 1$, we have $\frac 12 \delta^2 \leq \|1 - z\|^2 \leq \delta^2$.

Therefore $$c \delta \leq \rho(\theta_n, \phi) \leq C \delta$$ for absolute positive constants $c$ and $C$.  Theorem \[thm:tight\_KL\_bound\] and Proposition \[prop:generalized\_matching\] imply that$$D({\mathrm}{P}_{\theta_n}^n {\,\|\,}{\mathrm}{P}_{\phi}^n) \le \overline{C} n \sigma^{-4s+2}{\rho}^2(\phi_n, \tau)\le \frac12\,,$$ by taking $c_1$ small enough. 

In all three cases, we have a bound $D({\mathrm}{P}_{\theta_n}^n {\,\|\,}{\mathrm}{P}_{\phi}^n) \le 1/2$ for $\theta_n, \phi \in {\mathcal{T}}_s$ satisfying ${\rho}(\theta_n, \phi) \geq c (\sigma^{(2s -1) \wedge (s+1)}/\sqrt n \wedge 1)$ for some constant $c > 0$. Using standard minimax lower bound techniques [@Tsy09], we get the desired result. 

Information geometry for algebraically structured models {#sec:tight_bounds}
========================================================

Our proof techniques rely on understanding the curvature of the Kullback-Leibler divergence around its minimum, which is known to control the information geometry of the problem.  In this section, we obtain precise bounds on the divergence $D({\mathrm}{P}_\theta {\,\|\,}{\mathrm}{P}_\phi)$ for pairs of signals $\theta$ and $\phi$ for any choice of a subgroup ${\mathcal{G}}$ of the orthogonal group $\mathrm{O}(L)$.

We extend the approach of [@CaiLow11] to bound the divergence between $D({\mathrm}{P}_\theta {\,\|\,}{\mathrm}{P}_\phi)$ in terms of the Hilbert-Schmidt distance between the moment tensors ${{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes m}]$ and ${{\rm I}\kern-0.18em{\rm E}}[(G \phi)^{\otimes m}]$. Recall that $G$ is uniformly distributed over ${\mathcal{G}}$. In what follows, we write $$\Delta_m := {{\rm I}\kern-0.18em{\rm E}}[(G\theta)^{\otimes m}] - {{\rm I}\kern-0.18em{\rm E}}[(G \phi)^{\otimes m}]\,.$$ Our results imply that when $\sigma$ is bounded below by a constant, the divergence can be bounded above and below by an infinite series of the form $\sum_m \frac{c^m\|\Delta_m\|^2}{\sigma^{2m} m!}$. We note that the assumption that $\sigma$ be bounded below is essential: when $\sigma \to 0$, it is not hard to show that $D(\theta {\,\|\,}\phi) = \frac{{\rho}^2(\phi, \theta)}{2 \sigma^2} + o(\sigma^{-2})$.

For convenience, we write $D(\theta {\,\|\,}\phi)$ for $D({\mathrm}{P}_\theta {\,\|\,}{\mathrm}{P}_\phi)$. We begin by establishing the effect of the first moments ${{\rm I}\kern-0.18em{\rm E}}G \theta$ and ${{\rm I}\kern-0.18em{\rm E}}G \phi$ on $D(\theta {\,\|\,}\phi)$.

\[lem:first\_moment\] If $\vartheta = \theta - {{\rm I}\kern-0.18em{\rm E}}G \theta$ and $\varphi = \phi - {{\rm I}\kern-0.18em{\rm E}}G \phi$, then $$D(\theta {\,\|\,}\phi) =D(\vartheta {\,\|\,}\varphi)+ \frac{1}{2\sigma^2} \|\Delta_1\|^2 \,.$$

Lemma \[lem:first\_moment\] implies that it suffices to bound $D(\theta {\,\|\,}\phi)$ for vectors $\theta$ and $\phi$ satisfying ${{\rm I}\kern-0.18em{\rm E}}G \theta = {{\rm I}\kern-0.18em{\rm E}}G \phi = 0$, which we accomplish in the following theorem. 

\[thm:tight\_KL\_bound\] Let $\theta, \phi$ in ${{\rm I}\kern-0.18em{\rm R}}^L$ satisfy $3 {\rho}(\theta, \phi) \leq \|\theta\| \le \sigma$ and ${{\rm I}\kern-0.18em{\rm E}}G \theta = {{\rm I}\kern-0.18em{\rm E}}G \phi = 0$. For any $k \geq 1$, there exist universal constants $\underline C$ and $\overline C$ such that $$\underline C \sum_{m=1}^{\infty} \frac{\|\Delta_m\|^2}{(\sqrt 3\sigma)^{2m} m!}  \leq D(\theta {\,\|\,}\phi) \leq 2 \sum_{m=1}^{k-1} \frac{\|\Delta_m\|^2}{\sigma^{2m} m!}  + \overline C\frac{\|\theta\|^{2k-2}{\rho}(\theta, \phi)^2}{\sigma^{2k}} \,.$$

In particular, Theorem \[thm:tight\_KL\_bound\] implies that if $\|\Delta_m\| = 0$ for $m = 1, \dots, k-1$ and $\|\Delta_k\| \geq c {\rho}(\theta, \phi)$ for some constant $c$, then $D(\theta \,\|\, \phi)$ is of order $\sigma^{-2k} {\rho}^2(\theta, \phi)$.

We first prove the following simple expression: $$D({\mathrm}{P}_\theta {\,\|\,}{\mathrm}{P}_\phi) = D(\theta {\,\|\,}\phi) = \frac{1}{2 \sigma^2}(\|\phi\|^2 - \|\theta\|^2) + {{\rm I}\kern-0.18em{\rm E}}\log \frac{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} (\theta + \sigma \xi)^\top G \theta} \mid \xi ]}{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} (\theta + \sigma \xi)^\top G \phi} \mid \xi ]}\,,$$ where $\xi\sim {\mathcal{N}}(0,I_L)$ and $G \in {\mathcal{G}}$ is uniform and independent of $\xi$.

This claim follows directly from the definition of divergence.  Let ${\mathsf{g}}$ the density of a standard Gaussian random variable with respect to the Lebesgue measure on ${{\rm I}\kern-0.18em{\rm R}}^L$. It holds $$\begin{aligned}
\frac{d{\mathrm}{P}_\theta}{d{\mathrm}{P}_\phi}(y) & = \frac{{{\rm I}\kern-0.18em{\rm E}}[{\mathsf{g}}((y - G\theta)/\sigma)]}{{{\rm I}\kern-0.18em{\rm E}}[{\mathsf{g}}((y - G\phi)/\sigma)]} \\
& = \frac{{{\rm I}\kern-0.18em{\rm E}}\left[\exp\left(-\frac{1}{2\sigma^2}(\|y\|^2 - 2 y^\top G \theta + \|G \theta\|^2)\right)\right]}{{{\rm I}\kern-0.18em{\rm E}}\left[\exp\left(-\frac{1}{2\sigma^2}(\|y\|^2 - 2 y^\top G \phi + \|G \phi\|^2)\right)\right]} \\
& = \exp\left(\frac{1}{2\sigma^2}(\|\phi\|^2 - \|\theta\|^2)\right)\frac{{{\rm I}\kern-0.18em{\rm E}}\left[\exp\left(\frac{1}{\sigma^2}y^\top G \theta\right)\right]}{{{\rm I}\kern-0.18em{\rm E}}\left[\exp\left(\frac{1}{\sigma^2} y^\top G \phi\right)\right]}\,,\end{aligned}$$ since $G$ is orthogonal.  Hence, if $Y \sim {\mathrm}{P}_\theta$, we have $$\begin{aligned}
D(\theta {\,\|\,}\phi) & = {{\rm I}\kern-0.18em{\rm E}}\log \frac{d{\mathrm}{P}_\theta}{d{\mathrm}{P}_\phi}(Y) = \frac{1}{2\sigma^2}(\|\phi\|^2 - \|\theta\|^2) + {{\rm I}\kern-0.18em{\rm E}}\log \frac{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} Y^\top G \theta} \mid Y ]}{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} Y^\top G \phi} \mid Y]}\,.\end{aligned}$$ Note that we can write $Y = G' \theta + \sigma \xi$ for a standard Gaussian vector $\xi$ and $G' \in {\mathcal{G}}$ an independent copy of $G$. Since $G'\in O(L)$, $Y$ has the same distribution as $G'(\theta + \sigma \xi)$. If $G$ and $G'$ are independent and uniform, then $(G')^\top G$ has the same distribution as $G$, so $$Y^\top G \theta \stackrel{d}{=} (\theta + \sigma \xi)^\top G \theta\,,$$ where the above equality holds in distribution.  It yields $$\label{EQ:KLexp}
D(\theta {\,\|\,}\phi) = \frac{1}{2\sigma^2}(\|\phi\|^2 - \|\theta\|^2) + {{\rm I}\kern-0.18em{\rm E}}\log \frac{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} (\theta + \sigma \xi)^\top G \theta} \mid \xi ]}{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} (\theta + \sigma \xi)^\top G \phi} \mid \xi]}\,.$$

We now turn to the proof of Lemma \[lem:first\_moment\].  For convenience write $\bar \theta = {{\rm I}\kern-0.18em{\rm E}}G \theta$ and $\bar \phi = {{\rm I}\kern-0.18em{\rm E}}G \phi$. These vectors satisfy $G \bar \theta = \bar \theta$ and $G \bar \phi = \bar \phi$ almost surely and $\vartheta^\top\bar \theta=0$. Hence, almost surely, $$\begin{aligned}
(\theta + \sigma \xi)^\top G \theta & = (\bar \theta + \vartheta + \sigma \xi)^\top G (\bar \theta + \vartheta) \\
& = (\vartheta + \sigma \xi)^\top G \vartheta + (\bar \theta + \sigma \xi)^\top \bar \theta\,,\end{aligned}$$ and similarly $$(\theta + \sigma \xi)^\top G \phi = (\vartheta + \sigma \xi)^\top G \varphi + (\bar \theta + \sigma \xi)^\top \bar \phi\,.$$

Plugging these quantities into  yields $$\begin{aligned}
D(\theta &{\,\|\,}\phi)  = \frac{1}{2\sigma^2}(\|\phi\|^2 - \|\theta\|^2) + {{\rm I}\kern-0.18em{\rm E}}\log \frac{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} (\vartheta + \sigma \xi)^\top G \vartheta + (\bar \theta + \sigma \xi)^\top \bar \theta} \mid \xi ]}{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} (\vartheta + \sigma \xi)^\top G \varphi + (\bar \theta + \sigma \xi)^\top \bar \phi} \mid \xi]} \\
& = \frac{1}{2\sigma^2}(\|\phi\|^2 - \|\theta\|^2) + \frac{1}{\sigma^2}{{\rm I}\kern-0.18em{\rm E}}(\bar \theta + \sigma \xi)^\top (\bar \theta - \bar \phi) + {{\rm I}\kern-0.18em{\rm E}}\log \frac{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} (\vartheta + \sigma \xi)^\top G \vartheta} \mid \xi ]}{{{\rm I}\kern-0.18em{\rm E}}[e^{\frac{1}{\sigma^2} (\vartheta + \sigma \xi)^\top G \varphi} \mid \xi]} \\
& = \frac{1}{2\sigma^2}(\|\bar \phi\|^2 - \|\bar \theta\|^2) + \frac{1}{\sigma^2} (\|\bar \theta\|^2 - \bar \theta^\top \bar \phi) + D(\vartheta {\,\|\,}\varphi) \\
& = \frac{1}{2 \sigma^2}\|{{\rm I}\kern-0.18em{\rm E}}[G \theta - G \phi]\|^2 + D(\vartheta {\,\|\,}\varphi)\,.\end{aligned}$$

If $\theta = 0$, then the conditions of the theorem imply that $\phi = 0$, so the statement is vacuous.  We therefore assume $\theta \neq 0$. The divergence $D(\theta {\,\|\,}\phi)$ and the moment tensors ${{\rm I}\kern-0.18em{\rm E}}[(G \phi)^{\otimes m}]$ are unaffected if we replace $\phi$ by $G_0 \phi$ for any $G_0 \in {\mathcal{G}}$. Hence without loss of generality, we can assume that $\|\theta - \phi\| = {\rho}(\theta, \phi) =: {\varepsilon}$. Moreover, the quantity $D(\theta {\,\|\,}\phi)$ and the bounds in question are all unaffected upon replacing $\theta$, $\phi$, and $\sigma$ by $\theta/\|\theta\|$, $\phi/\|\theta\|$, and $\sigma/\|\theta\|$, respectively, so we assume in what follows that $\|\theta\| = 1$ and $\sigma \geq 1$.

We first prove the upper bound.  Denote by ${\mathsf{g}}$ the density of a standard $L$-dimensional Gaussian random variable.  For all $\zeta \in {{\rm I}\kern-0.18em{\rm R}}^L$, let $f_\zeta$ denote the density of ${\mathrm}{P}_\zeta$ defined in .  Recall that in this model, $G$ is drawn uniformly from the Haar measure on ${\mathcal{G}}$. Then, for any $y \in {{\rm I}\kern-0.18em{\rm R}}^L$ we have $$f_\zeta(y) = {{\rm I}\kern-0.18em{\rm E}}\frac{1}{\sigma^d} {\mathsf{g}}(\sigma^{-1}(y - G \zeta)) = \frac{1}{\sigma^d} {\mathsf{g}}(\sigma^{-1} y) e^{-\frac{\|\zeta\|^2}{2 \sigma^2}}{{\rm I}\kern-0.18em{\rm E}}e^{\frac{y^\top G \zeta}{\sigma^2}}\,.$$ Let $\chi^2(\theta, \phi)$ denote the $\chi^2$-divergence between ${\mathrm}{P}_\theta$ and ${\mathrm}{P}_\phi$, defined by $$\chi^2(\theta, \phi) = \int \frac{(f_\theta(y) - f_\phi(y))^2}{f_\theta(y)} \mathrm dy\,.$$

Since ${{\rm I}\kern-0.18em{\rm E}}G \theta = 0$ by assumption, Jensen’s inequality implies $$f_\theta(y) \geq \frac{1}{\sigma^d} {\mathsf{g}}(\sigma^{-1} y) e^{-\frac{\|\theta\|^2}{2\sigma^2}}e^{{{\rm I}\kern-0.18em{\rm E}}\frac{y^\top G \theta}{\sigma^2}} = \frac{1}{\sigma^d} {\mathsf{g}}(\sigma^{-1} y) e^{-\frac{\|\theta\|^2}{2\sigma^2}} \,.$$

Hence $$\frac{(f_\theta(y) - f_\phi(y))^2}{f_\theta(y)} \leq e^{\frac{\|\theta\|^2}{2 \sigma^2}} \big(e^{-\frac{\|\theta\|^2}{2 \sigma^2}}{{\rm I}\kern-0.18em{\rm E}}e^{\frac{y^\top G \theta}{\sigma^2}} - e^{-\frac{\|\phi\|^2}{2 \sigma^2}}{{\rm I}\kern-0.18em{\rm E}}e^{\frac{y^\top G \phi}{\sigma^2}}\big)^2 \big(\frac{1}{\sigma^d} {\mathsf{g}}(\sigma^{-1} y)\big)\,.$$ Integrating this quantity with respect to $y$ yields a bound on the $\chi^2$ divergence.  Let $\xi \sim {\mathcal{N}}(0, I_d)$ and observe that $$\begin{aligned}
\chi^2(\theta, \phi) & \leq {{\rm I}\kern-0.18em{\rm E}}\Big[e^{\frac{\|\theta\|^2}{2 \sigma^2}} \big(e^{-\frac{\|\theta\|^2}{2 \sigma^2}}{{\rm I}\kern-0.18em{\rm E}}\big[ e^{\frac{\sigma \xi^\top G \theta}{\sigma^2}}\big|\xi\big] - e^{-\frac{\|\phi\|^2}{2 \sigma^2}}{{\rm I}\kern-0.18em{\rm E}}\big[ e^{\frac{\sigma \xi^\top G \phi}{\sigma^2}}\big|\xi\big]\big)^2 \Big]\\
& =  {{\rm I}\kern-0.18em{\rm E}}\Big[ e^{\frac{\|\theta\|^2}{2 \sigma^2}} \big(e^{-\frac{\|\theta\|^2}{ \sigma^2}}e^{\frac{\xi^\top (G + G')\theta}{\sigma}} - 2 e^{-\frac{\|\theta\|^2 + \|\phi\|^2 }{2 \sigma^2}} e^{\frac{\xi^\top (G \theta + G' \phi)}{\sigma}}\\
&\le 2{{\rm I}\kern-0.18em{\rm E}}\big[  e^{\frac{(G'\theta)^\top G \theta}{\sigma^2}} - 2 e^{\frac{(G'\phi)^\top G \theta}{\sigma^2}} +e^{\frac{(G'\phi)^\top G\phi}{\sigma^2}}\big]\end{aligned}$$ where $G' \in {\mathcal{G}}$ is an independent copy of $G$ and we used the bound $e^{\|\theta\|^2/(2\sigma^2)} \le 2$ that holds for $\sigma \geq 1$ and $\|\theta\|^2 \leq 1$.

The random variables $G \theta$ and $G \phi$ have moment generating functions that converge in a neighborhood of the origin, hence $$\begin{aligned}
\chi^2(\theta, \phi) & \le \sum_{m \geq 0} \frac{2}{\sigma^{2m} m!} {{ \rm I}\kern-0.18em{\rm E}}\left[((G'\theta)^\top G \theta)^m - 2 ((G'\phi)^\top G \theta)^m + ((G'\phi)^\top G\phi)^m\right] \\
& = \sum_{m \geq 0} \frac{2}{\sigma^{2m} m!}  \|{{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes m}]\|^2 - 2 \langle {{\rm I}\kern-0.18em{\rm E}}[(G \theta)^{\otimes m}], {{\rm I}\kern-0.18em{\rm E}}[(G \phi)^{\otimes m}]\rangle + \|{{\rm I}\kern-0.18em{\rm E}}[(G \phi)^{\otimes m}]\|^2 \\
& = \sum_{m \geq 0} \frac{2}{\sigma^{2m} m!}  \left\| \Delta_m\right\|^2 \\
 &\leq 2\sum_{m =1}^{k-1} \frac{\|\Delta_m\|^2}{\sigma^{2m}m!}  + 24 \sum_{m \geq k} \frac{2^{m}}{\sigma^{2m}m!} { \varepsilon}^2
  \leq 2\sum_{m =1}^{k-1} \frac{\|\Delta_m\|^2}{\sigma^{2m}m!}  + 24 e^{2} \frac{{\varepsilon}^2}{\sigma^{2k}}\,,
$$ where the penultimate inequality follows from Lemma \[lem:tensor\_bound\] in Appendix \[supp\].  The bound follows upon applying the inequality $D(\theta {\,\|\,}\phi) \leq \chi^2(\theta, \phi)$ [@Tsy09]. 

We now turn to the lower bound.  Recall that the Hermite polynomials $\{h_k(x)\}_{k \geq 0}$ satisfy the following three properties [@Sze75]:

1.   The function $h_k(x)$ is a degree-$k$ polynomial. 

2.   The functions $\{h_k\}_{k \geq 0}$ form an orthogonal basis of of $L_2(\gamma)$, where $\gamma$ denotes the standard Gaussian measure on ${{\rm I}\kern-0.18em{\rm R}}$, with $\|h_k\|_\mu^2 = k!$.

3.   If $Y \sim {\mathcal{N}}(\mu, 1)$, then ${{\rm I}\kern-0.18em{\rm E}}[h_k(Y)] = \mu^k$.

Given a multi-index $\alpha \in {{\rm I}\kern-0.18em{\rm N}}^L$, define the multivariate Hermite polynomial $h_\alpha$ by $$h_\alpha(x_1, \dots, x_L) = \prod_{i=1}^L h_{\alpha_i}(x_i)\,.$$ The multivariate Hermite polynomials form an orthonormal basis for the space ${{\rm I}\kern-0.18em{\rm R}}[x_1, \dots, x_L]$ of $L$-variate polynomial functions with respect to the inner product over $L_2(\gamma^{\otimes L})$.

Given $y \in {{\rm I}\kern-0.18em{\rm R}}^L$ and $m \geq 1$, denote by $H_m(y)$ the order-$m$ symmetric tensor defined as follows.  The $(i_1, \ldots, i_m)$th entry of $H_m(y)$ is given by $\sigma^m h_\alpha(\sigma^{-1}y_1, \dots, \sigma^{-1}y_L)$, where $\alpha \in \{0, \ldots, m\}^L$ denotes the multi-index associated to $(i_1, \ldots, i_m)$: $\alpha_l=|\{j\in [m]\,: i_j=\ell\}|, l \in \{0,\ldots, m\}$. Property 3 of the Hermite polynomials implies that if $Y \sim {\mathcal{N}}(\mu, \sigma^2 I)$, then ${{\rm I}\kern-0.18em{\rm E}}[H_m(Y)] = \mu^{\otimes m}$.

Fix $k \geq 1$, and consider the degree-$k$ polynomial $$t(y) = \sum_{m=1}^{k} \frac{\langle \Delta_m, H_m(y)\rangle}{(\sqrt 3 \sigma)^{2m} m!}\,.$$ Note that, if $Y \sim {\mathrm}{P}_\zeta$, then $${{\rm I}\kern-0.18em{\rm E}}[t(Y)] = {{\rm I}\kern-0.18em{\rm E}}\left[\sum_{m=1}^{k} \frac{\langle \Delta_m, {{\rm I}\kern-0.18em{\rm E}}[H_m(Y) | G]\rangle}{(\sqrt 3 \sigma)^{2m} m!}\right] = \sum_{m=1}^{k} \frac{\langle \Delta_m, {{\rm I}\kern-0.18em{\rm E}}[(G\zeta)^{\otimes m}]\rangle}{(\sqrt 3 \sigma)^{2m} m!}\,.$$ Thus if $Y \sim {\mathrm}{P}_\theta$ and $Y'\sim {\mathrm}{P}_\phi$, we get $${{\rm I}\kern-0.18em{\rm E}}[t(Y)] - {{\rm I}\kern-0.18em{\rm E}}[t(Y')] = \sum_{m=1}^{k} \frac{\|\Delta_m\|^2}{(\sqrt 3 \sigma)^{2m} m!}  =: \delta\,.$$ Lemma \[lem:tensor\_bound\] in Appendix \[supp\] implies that $\delta \leq 4$. Moreover, by Lemma \[lem:hermite\_variance\_bound\] in Appendix \[supp\], the variances of both $t(Y)$ and $t(Y')$ are bounded above by $e\delta$. Applying Lemma \[lem:testing\_bound\] in Appendix \[supp\] therefore yields $$D(\theta \, \| \, \phi) \geq \frac{\delta^2}{4 e \delta + \delta^2} \geq \frac{\delta^2}{(4e+4)\delta} > \frac{1}{15} \sum_{m=1}^{k} \frac{\|\Delta_m\|^2}{(\sqrt 3 \sigma)^{2m} m!}\,.$$ Since $k \geq 1$ was arbitrary and the summands are nonnegative, letting $k \to \infty$ yields the claim. 

[^1]: Following an earlier version of this paper, [@AbbBenLee17] considered a version of multi-reference alignment when the distribution of $G$ is not uniform and showed that strictly better rates can be obtained in some cases. 

[^2]: Our focus in this work is on statistical properties rather than on computation.  In a companion paper [@PerWeeBan17], we propose and analyze a computationally efficient estimator for multi-reference alignment.