Publications (106)
Toward single particle reconstruction without particle picking: Breaking the detection limit
Tamir Bendory, Nicolas Boumal, William Leeb +2
Single-particle cryo-electron microscopy (cryo-EM) has recently joined X-ray crystallography and NMR spectroscopy as a high-resolution structural method to resolve biological macro…
Non-Local Patch Regression: Robust Image Denoising in Patch Space
Kunal N. Chaudhury, Amit Singer
It was recently demonstrated in [Chaudhury et al.,Non-Local Euclidean Medians,2012] that the denoising performance of Non-Local Means (NLM) can be improved at large noise levels by…
Non-unique games over compact groups and orientation estimation in cryo-EM
Afonso S. Bandeira, Yutong Chen, Amit Singer
Let be a compact group and let . We define the Non-Unique Games (NUG) problem as finding to minimize $\su…
Centering noisy images with application to cryo-EM
Ayelet Heimowitz, Nir Sharon, Amit Singer
We target the problem of estimating the center of mass of noisy 2-D images. We assume that the noise dominates the image, and thus many standard approaches are vulnerable to estima…
Steerable PCA: Rotationally Invariant Exponential Family PCA
Zhizhen Zhao, Lydia T. Liu, Amit Singer
In photon-limited imaging, the pixel intensities are affected by photon count noise. Many applications, such as 3-D reconstruction using correlation analysis in X-ray free electron…
Two Datasets Are Better Than One: Method of Double Moments for 3-D Reconstruction in Cryo-EM
Joe Kileel, Oscar Mickelin, Amit Singer +1
Cryo-electron microscopy (cryo-EM) is a powerful imaging technique for reconstructing three-dimensional molecular structures from noisy tomographic projection images of randomly or…
Multi-target Detection with an Arbitrary Spacing Distribution
Ti-Yen Lan, Tamir Bendory, Nicolas Boumal +1
Motivated by the structure reconstruction problem in single-particle cryo-electron microscopy, we consider the multi-target detection model, where multiple copies of a target signa…
SO(3)-invariant PCA with application to molecular data
Michael Fraiman, Paulina Hoyos, Tamir Bendory +4
Principal component analysis (PCA) is a fundamental technique for dimensionality reduction and denoising; however, its application to three-dimensional data with arbitrary orientat…
Image recovery from rotational and translational invariants
Nicholas F. Marshall, Ti-Yen Lan, Tamir Bendory +1
We introduce a framework for recovering an image from its rotationally and translationally invariant features based on autocorrelation analysis. This work is an instance of the mul…
Product Manifold Learning
Sharon Zhang, Amit Moscovich, Amit Singer
We consider problems of dimensionality reduction and learning data representations for continuous spaces with two or more independent degrees of freedom. Such problems occur, for e…
Alignment of Density Maps in Wasserstein Distance
Amit Singer, Ruiyi Yang
In this paper we propose an algorithm for aligning three-dimensional objects when represented as density maps, motivated by applications in cryogenic electron microscopy. The algor…
Factor Analysis for Spectral Estimation
Joakim Andén, Amit Singer
Power spectrum estimation is an important tool in many applications, such as the whitening of noise. The popular multitaper method enjoys significant success, but fails for short s…
Bayesian Perspective for Orientation Determination in Cryo-EM with Application to Structural Heterogeneity Analysis
Sheng Xu, Amnon Balanov, Amit Singer +1
Accurate orientation estimation is a crucial component of 3D molecular structure reconstruction, both in single-particle cryo-electron microscopy (cryo-EM) and in the increasingly…
The sample complexity of multi-reference alignment
Amelia Perry, Jonathan Weed, Afonso S. Bandeira +2
The growing role of data-driven approaches to scientific discovery has unveiled a large class of models that involve latent transformations with a rigid algebraic constraint. Three…
Continuously heterogeneous hyper-objects in cryo-EM and 3-D movies of many temporal dimensions
Roy R. Lederman, Amit Singer
Single particle cryo-electron microscopy (EM) is an increasingly popular method for determining the 3-D structure of macromolecules from noisy 2-D images of single macromolecules w…
Cryo-EM reconstruction of continuous heterogeneity by Laplacian spectral volumes
Amit Moscovich, Amit Halevi, Joakim Andén +1
Single-particle electron cryomicroscopy is an essential tool for high-resolution 3D reconstruction of proteins and other biological macromolecules. An important challenge in cryo-E…
Eigenvector Synchronization, Graph Rigidity and the Molecule Problem
Mihai Cucuringu, Amit Singer, David Cowburn
The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology.…
Rotationally Invariant Image Representation for Viewing Direction Classification in Cryo-EM
Zhizhen Zhao, Amit Singer
We introduce a new rotationally invariant viewing angle classification method for identifying, among a large number of Cryo-EM projection images, similar views without prior knowle…
Mathematics of Data Science
Afonso S. Bandeira, Amit Singer, Thomas Strohmer
This book is about the mathematical foundations of data science. 1. Introduction 2. Curses, Blessings, and Surprises in High Dimensions 3. Singular Value Decomposition and Principa…
Fast rigid alignment of heterogeneous images in sliced Wasserstein distance
Yunpeng Shi, Amit Singer, Eric J. Verbeke
Many applications of computer vision rely on the alignment of similar but non-identical images. We present a fast algorithm for aligning heterogeneous images based on optimal trans…
Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery
Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher +1
We consider the problem of clustering a graph into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed…
Ab-initio Contrast Estimation and Denoising of Cryo-EM Images
Yunpeng Shi, Amit Singer
Background and Objective: The contrast of cryo-EM images varies from one to another, primarily due to the uneven thickness of the ice layer. This contrast variation can affect the…
Super-resolution multi-reference alignment
Tamir Bendory, Ariel Jaffe, William Leeb +2
We study super-resolution multi-reference alignment, the problem of estimating a signal from many circularly shifted, down-sampled, and noisy observations. We focus on the low SNR…
Mahalanobis Distance for Class Averaging of Cryo-EM Images
Tejal Bhamre, Zhizhen Zhao, Amit Singer
Single particle reconstruction (SPR) from cryo-electron microscopy (EM) is a technique in which the 3D structure of a molecule needs to be determined from its contrast transfer fun…
Multireference Alignment using Semidefinite Programming
Afonso S. Bandeira, Moses Charikar, Amit Singer +1
The multireference alignment problem consists of estimating a signal from multiple noisy shifted observations. Inspired by existing Unique-Games approximation algorithms, we provid…
Sparse multi-reference alignment: sample complexity and computational hardness
Tamir Bendory, Oscar Mickelin, Amit Singer
Motivated by the problem of determining the atomic structure of macromolecules using single-particle cryo-electron microscopy (cryo-EM), we study the sample and computational compl…
The Spectrum of Random Inner-product Kernel Matrices
Xiuyuan Cheng, Amit Singer
We consider n-by-n matrices whose (i, j)-th entry is f(X_i^T X_j), where X_1, ...,X_n are i.i.d. standard Gaussian random vectors in R^p, and f is a real-valued function. The eigen…
Quantitatively visualizing bipartite datasets
Tal Einav, Yuehaw Khoo, Amit Singer
As experiments continue to increase in size and scope, a fundamental challenge of subsequent analyses is to recast the wealth of information into an intuitive and readily-interpret…
Optimal prediction in the linearly transformed spiked model
Edgar Dobriban, William Leeb, Amit Singer
We consider the linearly transformed spiked model, where observations are noisy linear transforms of unobserved signals of interest : \begin{align*} Y_i = A_i X_i + \var…
Orientation Determination from Cryo-EM images Using Least Unsquared Deviation
Lanhui Wang, Amit Singer, Zaiwen Wen
A major challenge in single particle reconstruction from cryo-electron microscopy is to establish a reliable ab-initio three-dimensional model using two-dimensional projection imag…
APPLE Picker: Automatic Particle Picking, a Low-Effort Cryo-EM Framework
Ayelet Heimowitz, Joakim Andén, Amit Singer
Particle picking is a crucial first step in the computational pipeline of single-particle cryo-electron microscopy (cryo-EM). Selecting particles from the micrographs is difficult…
3D ab initio modeling in cryo-EM by autocorrelation analysis
Eitan Levin, Tamir Bendory, Nicolas Boumal +2
Single-Particle Reconstruction (SPR) in Cryo-Electron Microscopy (cryo-EM) is the task of estimating the 3D structure of a molecule from a set of noisy 2D projections, taken from u…
Subspace method of moments for ab initio 3-D single-particle cryo-EM reconstruction
Jeremy Hoskins, Yuehaw Khoo, Oscar Mickelin +2
Cryo-electron microscopy (cryo-EM) is a widely used technique for recovering the 3-D structure of biological molecules from a large number of experimentally generated noisy 2-D tom…
Covariance Matrix Estimation for the Cryo-EM Heterogeneity Problem
Gene Katsevich, Alexander Katsevich, Amit Singer
In cryo-electron microscopy (cryo-EM), a microscope generates a top view of a sample of randomly-oriented copies of a molecule. The problem of single particle reconstruction (SPR)…
Robust Moment-Based Estimation via Spectral Gradient Reweighting
Liu Zhang, Amit Singer
Moment-based estimation is a theoretically attractive approach to parametric inference, especially when likelihood-based estimation is unavailable, misspecified, or computationally…
A Molecular Prior Distribution for Bayesian Inference Based on Wilson Statistics
Marc Aurèle Gilles, Amit Singer
Background and Objective: Wilson statistics describe well the power spectrum of proteins at high frequencies. Therefore, it has found several applications in structural biology, e.…
A New Rank Constraint on Multi-view Fundamental Matrices, and its Application to Camera Location Recovery
Soumyadip Sengupta, Tal Amir, Meirav Galun +4
Accurate estimation of camera matrices is an important step in structure from motion algorithms. In this paper we introduce a novel rank constraint on collections of fundamental ma…
Representation theoretic patterns in three dimensional cryo-electron microscopy II - The class averaging problem
Ronny Hadani, Amit Singer
In this paper we study the formal algebraic structure underlying the intrinsic classification algorithm, recently introduced by Hadani, Shkolnisky, Singer and Zhao, for classifying…
Manifold learning techniques and model reduction applied to dissipative PDEs
Benjamin E. Sonday, Amit Singer, C. William Gear +1
We link nonlinear manifold learning techniques for data analysis/compression with model reduction techniques for evolution equations with time scale separation. In particular, we d…
Marchenko-Pastur Law for Tyler's M-estimator
Teng Zhang, Xiuyuan Cheng, Amit Singer
This paper studies the limiting behavior of Tyler's M-estimator for the scatter matrix, in the regime that the number of samples and their dimension both go to infinity, an…
Computational Methods for Single-Particle Cryo-EM
Amit Singer, Fred J. Sigworth
Single-particle electron cryomicroscopy (cryo-EM) is an increasingly popular technique for elucidating the three-dimensional structure of proteins and other biologically significan…
Fast expansion into harmonics on the disk: a steerable basis with fast radial convolutions
Nicholas F. Marshall, Oscar Mickelin, Amit Singer
We present a fast and numerically accurate method for expanding digitized images representing functions on supported on the disk $\{x \in \mathbb{R}^2 : |x|…
A Representation Theory Perspective on Simultaneous Alignment and Classification
Roy R. Lederman, Amit Singer
One of the difficulties in 3D reconstruction of molecules from images in single particle Cryo-Electron Microscopy (Cryo-EM), in addition to high levels of noise and unknown image o…
A Cheeger Inequality for the Graph Connection Laplacian
Afonso S. Bandeira, Amit Singer, Daniel A. Spielman
The O(d) Synchronization problem consists of estimating a set of unknown orthogonal transformations O_i from noisy measurements of a subset of the pairwise ratios O_iO_j^{-1}. We f…
Multi-target detection with rotations
Tamir Bendory, Ti-Yen Lan, Nicholas F. Marshall +2
We consider the multi-target detection problem of estimating a two-dimensional target image from a large noisy measurement image that contains many randomly rotated and translated…
PCA from noisy, linearly reduced data: the diagonal case
Edgar Dobriban, William Leeb, Amit Singer
Suppose we observe data of the form or , , where $D_i \in \mathbb{R…
Hyper-Molecules: on the Representation and Recovery of Dynamical Structures, with Application to Flexible Macro-Molecular Structures in Cryo-EM
Roy R. Lederman, Joakim Andén, Amit Singer
Cryo-electron microscopy (cryo-EM), the subject of the 2017 Nobel Prize in Chemistry, is a technology for determining the 3-D structure of macromolecules from many noisy 2-D projec…
Random Conical Tilt Reconstruction without Particle Picking in Cryo-electron Microscopy
Ti-Yen Lan, Nicolas Boumal, Amit Singer
We propose a method to reconstruct the 3-D molecular structure from micrographs collected at just one sample tilt angle in the random conical tilt scheme in cryo-electron microscop…
A Fourier-based Approach for Iterative 3D Reconstruction from Cryo-EM Images
Lanhui Wang, Yoel Shkolnisky, Amit Singer
A major challenge in single particle reconstruction methods using cryo-electron microscopy is to attain a resolution sufficient to interpret fine details in three-dimensional (3D)…
Large-Scale Sensor Network Localization via Rigid Subnetwork Registration
Kunal N. Chaudhury, Yuehaw Khoo, Amit Singer
In this paper, we describe an algorithm for sensor network localization (SNL) that proceeds by dividing the whole network into smaller subnetworks, then localizes them in parallel…
Heterogeneous multireference alignment: a single pass approach
Nicolas Boumal, Tamir Bendory, Roy R. Lederman +1
Multireference alignment (MRA) is the problem of estimating a signal from many noisy and cyclically shifted copies of itself. In this paper, we consider an extension called heterog…
Synchronization over Cartan motion groups via contraction
Onur Ozyesil, Nir Sharon, Amit Singer
Group contraction is an algebraic map that relates two classes of Lie groups by a limiting process. We utilize this notion for the compactification of the class of Cartan motion gr…
Cramér-Rao bounds for synchronization of rotations
Nicolas Boumal, Amit Singer, P. -A. Absil +1
Synchronization of rotations is the problem of estimating a set of rotations R_i in SO(n), i = 1, ..., N, based on noisy measurements of relative rotations R_i R_j^T. This fundamen…
Fast expansion into harmonics on the ball
Joe Kileel, Nicholas F. Marshall, Oscar Mickelin +1
We devise fast and provably accurate algorithms to transform between an Cartesian voxel representation of a three-dimensional function and its expansion into t…
PCA: High Dimensional Exponential Family PCA
Lydia T. Liu, Edgar Dobriban, Amit Singer
Many applications, such as photon-limited imaging and genomics, involve large datasets with noisy entries from exponential family distributions. It is of interest to estimate the c…
Fast Principal Component Analysis for Cryo-EM Images
Nicholas F. Marshall, Oscar Mickelin, Yunpeng Shi +1
Principal component analysis (PCA) plays an important role in the analysis of cryo-EM images for various tasks such as classification, denoising, compression, and ab-initio modelin…
Disentangling Orthogonal Matrices
Teng Zhang, Amit Singer
Motivated by a certain molecular reconstruction methodology in cryo-electron microscopy, we consider the problem of solving a linear system with two unknown orthogonal matrices, wh…
Noisy dynamic simulations in the presence of symmetry: data alignment and model reduction
Benjamin E. Sonday, Amit Singer, Ioannis G. Kevrekidis
We process snapshots of trajectories of evolution equations with intrinsic symmetries, and demonstrate the use of recently developed eigenvector-based techniques to successfully qu…
Giant Components in Biased Graph Processes
Gideon Amir, Ori Gurel-Gurevich, Eyal Lubetzky +1
A random graph process, $\Gorg[1](n)$, is a sequence of graphs on vertices which begins with the edgeless graph, and where at each step a single edge is added according to a un…
Covariance estimation using conjugate gradient for 3D classification in Cryo-EM
Joakim Andén, Eugene Katsevich, Amit Singer
Classifying structural variability in noisy projections of biological macromolecules is a central problem in Cryo-EM. In this work, we build on a previous method for estimating the…
Mathematics for cryo-electron microscopy
Amit Singer
Single-particle cryo-electron microscopy (cryo-EM) has recently joined X-ray crystallography and NMR spectroscopy as a high-resolution structural method for biological macromolecul…
Structural Variability from Noisy Tomographic Projections
Joakim Andén, Amit Singer
In cryo-electron microscopy, the 3D electric potentials of an ensemble of molecules are projected along arbitrary viewing directions to yield noisy 2D images. The volume maps repre…
An approximate expectation-maximization for two-dimensional multi-target detection
Shay Kreymer, Amit Singer, Tamir Bendory
We consider the two-dimensional multi-target detection (MTD) problem of estimating a target image from a noisy measurement that contains multiple copies of the image, each randomly…
Uniqueness of Low-Rank Matrix Completion by Rigidity Theory
Amit Singer, Mihai Cucuringu
The problem of completing a low-rank matrix from a subset of its entries is often encountered in the analysis of incomplete data sets exhibiting an underlying factor model with app…
Multi-target detection with application to cryo-electron microscopy
Tamir Bendory, Nicolas Boumal, William Leeb +2
We consider the multi-target detection problem of recovering a set of signals that appear multiple times at unknown locations in a noisy measurement. In the low noise regime, one c…
Robust Camera Location Estimation by Convex Programming
Onur Ozyesil, Amit Singer
D structure recovery from a collection of D images requires the estimation of the camera locations and orientations, i.e. the camera motion. For large, irregular collections…
Manifold learning in metric spaces
Liane Xu, Amit Singer
Laplacian-based methods are popular for the dimensionality reduction of data lying in . Several theoretical results for these algorithms depend on the fact that the E…
Vector Diffusion Maps and the Connection Laplacian
Amit Singer, Hau-tieng Wu
We introduce {\em vector diffusion maps} (VDM), a new mathematical framework for organizing and analyzing massive high dimensional data sets, images and shapes. VDM is a mathematic…
Anisotropic twicing for single particle reconstruction using autocorrelation analysis
Tejal Bhamre, Teng Zhang, Amit Singer
The missing phase problem in X-ray crystallography is commonly solved using the technique of molecular replacement, which borrows phases from a previously solved homologous structu…
Method of moments for 3-D single particle ab initio modeling with non-uniform distribution of viewing angles
Nir Sharon, Joe Kileel, Yuehaw Khoo +2
Single-particle reconstruction in cryo-electron microscopy (cryo-EM) is an increasingly popular technique for determining the 3-D structure of a molecule from several noisy 2-D pro…
Open problem: Tightness of maximum likelihood semidefinite relaxations
Afonso S. Bandeira, Yuehaw Khoo, Amit Singer
We have observed an interesting, yet unexplained, phenomenon: Semidefinite programming (SDP) based relaxations of maximum likelihood estimators (MLE) tend to be tight in recovery p…
Bispectrum Inversion with Application to Multireference Alignment
Tamir Bendory, Nicolas Boumal, Chao Ma +2
We consider the problem of estimating a signal from noisy circularly-translated versions of itself, called multireference alignment (MRA). One natural approach to MRA could be to e…
Spectral Convergence of the connection Laplacian from random samples
Amit Singer, Hau-tieng Wu
Spectral methods that are based on eigenvectors and eigenvalues of discrete graph Laplacians, such as Diffusion Maps and Laplacian Eigenmaps are often used for manifold learning an…
Moment-based metrics for molecules computable from cryo-EM images
Andy Zhang, Oscar Mickelin, Joe Kileel +4
Single particle cryogenic electron microscopy (cryo-EM) is an imaging technique capable of recovering the high-resolution 3-D structure of biological macromolecules from many noisy…
Expectation-maximization for structure determination directly from cryo-EM micrographs
Shay Kreymer, Amit Singer, Tamir Bendory
A single-particle cryo-electron microscopy (cryo-EM) measurement, called a micrograph, consists of multiple two-dimensional tomographic projections of a three-dimensional (3-D) mol…
NMR Assignment through Linear Programming
Jose F. S. Bravo-Ferreira, David Cowburn, Yuehaw Khoo +1
Nuclear Magnetic Resonance (NMR) Spectroscopy is the second most used technique (after X-ray crystallography) for structural determination of proteins. A computational challenge in…
Sample Complexity of the Boolean Multireference Alignment Problem
Emmanuel Abbe, Joao Pereira, Amit Singer
The Boolean multireference alignment problem consists in recovering a Boolean signal from multiple shifted and noisy observations. In this paper we obtain an expression for the err…
Estimation in the group action channel
Emmanuel Abbe, João M. Pereira, Amit Singer
We analyze the problem of estimating a signal from multiple measurements on a $\mbox{group action channel}$ that linearly transforms a signal by a random group action followed by a…
Autocorrelation analysis for cryo-EM with sparsity constraints: Improved sample complexity and projection-based algorithms
Tamir Bendory, Yuehaw Khoo, Joe Kileel +2
The number of noisy images required for molecular reconstruction in single-particle cryo-electron microscopy (cryo-EM) is governed by the autocorrelations of the observed, randomly…
Representation theoretic patterns in three dimensional Cryo-Electron Microscopy I - The intrinsic reconstitution algorithm
Ronny Hadani, Amit Singer
In this paper, we describe and study a mathematical framework for cryo-elecron microscopy. The main result, is a a proof of the admissability (correctness) and the numerical stabil…
Bias and variance reduction and denoising for CTF Estimation
Ayelet Heimowitz, Joakim Andén, Amit Singer
When using an electron microscope for imaging of particles embedded in vitreous ice, the objective lens will inevitably corrupt the projection images. This corruption manifests as…
Bias Correction in Saupe Tensor Estimation
Yuehaw Khoo, Amit Singer, David Cowburn
Estimation of the Saupe tensor is central to the determination of molecular structures from residual dipolar couplings (RDC) or chemical shift anisotropies. Assuming a given templa…
Integrating NOE and RDC using sum-of-squares relaxation for protein structure determination
Yuehaw Khoo, Amit Singer, David Cowburn
We revisit the problem of protein structure determination from geometrical restraints from NMR, using convex optimization. It is well-known that the NP-hard distance geometry probl…
Denoising and Covariance Estimation of Single Particle Cryo-EM Images
Tejal Bhamre, Teng Zhang, Amit Singer
The problem of image restoration in cryo-EM entails correcting for the effects of the Contrast Transfer Function (CTF) and noise. Popular methods for image restoration include `pha…
Fourier-Bessel rotational invariant eigenimages
Zhizhen Zhao, Amit Singer
We present an efficient and accurate algorithm for principal component analysis (PCA) of a large set of two dimensional images, and, for each image, the set of its uniform rotation…
Angular Synchronization by Eigenvectors and Semidefinite Programming
Amit Singer
The angular synchronization problem is to obtain an accurate estimation (up to a constant additive phase) for a set of unknown angles from noisy measurements of…
Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities
Tamir Bendory, Alberto Bartesaghi, Amit Singer
In recent years, an abundance of new molecular structures have been elucidated using cryo-electron microscopy (cryo-EM), largely due to advances in hardware technology and data pro…
Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
Afonso S. Bandeira, Nicolas Boumal, Amit Singer
Maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using con…
Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups
Afonso S. Bandeira, Christopher Kennedy, Amit Singer
The little Grothendieck problem consists of maximizing over binary variables , where C is a positive semidefinite matrix. In this paper we f…
Heterogeneous multireference alignment for images with application to 2-D classification in single particle reconstruction
Chao Ma, Tamir Bendory, Nicolas Boumal +2
Motivated by the task of 2-D classification in single particle reconstruction by cryo-electron microscopy (cryo-EM), we consider the problem of heterogeneous multireference alignme…
Diagonally-Weighted Generalized Method of Moments Estimation for Gaussian Mixture Modeling
Liu Zhang, Oscar Mickelin, Sheng Xu +1
Since Pearson [Philosophical Transactions of the Royal Society of London. A, 185 (1894), pp. 71-110] first applied the method of moments (MM) for modeling data as a mixture of one-…
Orthogonal Matrix Retrieval in Cryo-Electron Microscopy
Tejal Bhamre, Teng Zhang, Amit Singer
In single particle reconstruction (SPR) from cryo-electron microscopy (cryo-EM), the 3D structure of a molecule needs to be determined from its 2D projection images taken at unknow…
Misspecified Maximum Likelihood Estimation for Non-Uniform Group Orbit Recovery
Sheng Xu, Anderson Ye Zhang, Amit Singer
We study maximum likelihood estimation (MLE) in the generalized group orbit recovery model, where each observation is generated by applying a random group action and a known, fixed…
On a linearization of quadratic Wasserstein distance
Philip Greengard, Jeremy G. Hoskins, Nicholas F. Marshall +1
This paper studies the problem of computing a linear approximation of quadratic Wasserstein distance . In particular, we compute an approximation of the negative homogeneous w…
Wasserstein K-Means for Clustering Tomographic Projections
Rohan Rao, Amit Moscovich, Amit Singer
Motivated by the 2D class averaging problem in single-particle cryo-electron microscopy (cryo-EM), we present a k-means algorithm based on a rotationally-invariant Wasserstein metr…
Stable Camera Motion Estimation Using Convex Programming
Onur Ozyesil, Amit Singer, Ronen Basri
We study the inverse problem of estimating n locations (up to global scale, translation and negation) in from noisy measurements of a subset of the (unsigned)…
Multireference Alignment is Easier with an Aperiodic Translation Distribution
Emmanuel Abbe, Tamir Bendory, William Leeb +3
In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal's o…
Semidefinite Programming Approach for the Quadratic Assignment Problem with a Sparse Graph
Jose F. S. Bravo Ferreira, Yuehaw Khoo, Amit Singer
The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations…
Fast Steerable Principal Component Analysis
Zhizhen Zhao, Yoel Shkolnisky, Amit Singer
Cryo-electron microscopy nowadays often requires the analysis of hundreds of thousands of 2D images as large as a few hundred pixels in each direction. Here we introduce an algorit…
A Survey of Structure from Motion
Onur Ozyesil, Vladislav Voroninski, Ronen Basri +1
The structure from motion (SfM) problem in computer vision is the problem of recovering the three-dimensional (D) structure of a stationary scene from a set of projective measur…