English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work we study orbit recovery over $SO(3)$, where the goal is torecover a function on the sphere from noisy, randomly rotated copies of it. Weassume that the function is a linear combination of low-degree sphericalharmonics. This is a natural abstraction for the problem of recovering thethree-dimensional structure of a molecule through cryo-electron tomography. Forprovably learning the parameters of a generative model, the method of momentsis the standard workhorse of theoretical machine learning. It turns out thatthere is a natural incarnation of the method of moments for orbit recoverybased on invariant theory. Bandeira et al. [BBSK+18] used invariant theory togive tight bounds on the sample complexity in terms of the noise level. Howevermany of the key challenges remain: Can we prove bounds on the sample complexitythat are polynomial in $n$, the dimension of the signal? The bounds in[BBSK+18] hide constants that have an unspecified dependence on $n$ and onlyhold in the limit as $\sigma^2 \rightarrow \infty$ where $\sigma^2$ is thevariance of the noise. Moreover can we give efficient algorithms? We revisitthese challenges from the perspective of smoothed analysis, where we assumethat the coefficients of the signal, in the basis of spherical harmonics, aresubject to small random perturbations. Our main result is a quasi-polynomialtime algorithm for orbit recovery over $SO(3)$ in this model. Our approach isbased on frequency marching, which sequentially solves linear systems to findhigher degree coefficients. Our main technical contribution is to show thatthese linear systems have unique solutions, are well-conditioned, and that theerror can be made to compound over at most a logarithmic number of rounds. Webelieve that our work takes an important first step towards uncovering thealgorithmic implications of invariant theory.

Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over $SO(3)$