UC Davis

Methods for structure determination in single particle cryogenic electron microscopy upended imaging sciences by demonstrating that crystallization is not necessary to resolve biological molecules at the atomic level. As imaging techniques have matured, so has the mathematical theory used to analyze these data. In particular, the method of moments and algebraic techniques show promise for the challenges posed by a low signal-to-noise ratio, the unknown orientation of particles in the imaging plane, and different classes of particles in a mixture. Cryo-EM remains a challenging problem approached from this direction and has motivated the study of simpler models capturing its core challenges. In particular, multireference alignment (MRA) is a well-studied model in which one observes copies of a signal corrupted by unknown cyclic shifts and isotropic Gaussian noise. In this work, I study two variants of multireference alignment, one introducing a step modeling tomographic projection (projected MRA) and another allowing reflections of the signal as well as cyclic shifts to appear (dihedral MRA). For signals of length a power of two, I develop an efficient recursive method for recovering signals from the third moment tensor of the samples. Beyond these specific orbit recovery problems, a subroutine using in my algorithm solves a linear system with a solution constrained to be a symmetric rank-1 matrix. Such problems arise in algebraic compressive sensing. Even when a given linear system is under-determined, the rank-1 constraint provides a ``sparsity'' assumption which may ensure a unique solution. To prove that my algorithm succeeds, I develop a construction which can be used to certify that specific linear systems with a rank-1 constraint have unique solutions. We show the algorithm succeeds in recovering a generic signal on the condition that a particular symbolic matrix has full column-rank. This condition can be easily checked on the computer in polynomial time, and we give strong evidence the matrices have full column-rank for a couple of dimensions. The foray into algebraic compressive sensing also reveals a close connection to the problem of finding a set of rank-1 matrices ``planted'' in a subspace of matrices. An algorithm of Johnston, Lovitz and Vijayaraghavan for finding the intersection of a linear subspace with a conic variety can recover such rank-1 matrices as a particular application. However, the upper bound on generic subspace dimension for which these authors prove their algorithm will succeed proves pessimistic in this specific case. We conjecture that a simple dimension counting bound gives the sharp threshold for the maximum dimension of generic subspace from which the JLV intersection algorithm can successfully recover a set of planted rank-1 matrices. To give evidence for this conjecture, I implemented a method of computer-proof which certifies the sharp boundary in several thousand specific cases. We give an analogous conjecture for the variety of symmetric rank-1 matrices and similar computer-proof of a similar sharp boundary in this case. Moreover, I give a floating point implementation of the JLV intersection algorithm in Python which can compute the intersection of any linear subspace with any Segre-Veronese variety (the varieties of rank-1 tensor with any set of partial symmetries and of any shape). Using this implementation, I give further evidence for our conjecture, showing that the algorithm does indeed recover planted matrices beyond the bound proven in the original paper up to our newly conjectured threshold. As an immediate consequence, we more than double the maximum rank of generic third- and fourth-order tensors (with or without partial symmetry) for which the JLV intersection algorithm will give a provably correct decomposition.