BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Amit Singer

Amit Singer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Visionmath.OCmath.NAInformation Theorymath.ITBiomoleculesData Structures and Algorithmseess.IVMachine LearningNumerical Analysismath.STStatistics Theoryphysics.comp-phApplicationseess.SPmath.PRmath.SPphysics.data-anQuantitative MethodsBiological PhysicsComputationComputational Engineering, Finance, and Sciencemath.CAmath.COmath.DSmath.FAmath.RTMethodologyNetworking and Internet Architecturephysics.soc-phSystems and Control

Catalog footprint

What is connected

50works
31topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

50 published item(s)

preprint2022arXiv

A Molecular Prior Distribution for Bayesian Inference Based on Wilson Statistics

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.g., it is the basis for sharpening steps used in cryogenic electron microscopy (cryo-EM). A recent paper gave the first rigorous proof of Wilson statistics based on a formalism of Wilson's original argument. This new analysis also leads to statistical estimates of the scattering potential of proteins that reveal a correlation between neighboring Fourier coefficients. Here we exploit these estimates to craft a novel prior that can be used for Bayesian inference of molecular structures. Methods: We describe the properties of the prior and the computation of its hyperparameters. We then evaluate the prior on two synthetic linear inverse problems, and compare against a popular prior in cryo-EM reconstruction at a range of SNRs. Results: We show that the new prior effectively suppresses noise and fills-in low SNR regions in the spectral domain. Furthermore, it improves the resolution of estimates on the problems considered for a wide range of SNR and produces Fourier Shell Correlation curves that are insensitive to masking effects. Conclusions: We analyze the assumptions in the model, discuss relations to other regularization strategies, and postulate on potential implications for structure determination in cryo-EM.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Ab-initio Contrast Estimation and Denoising of Cryo-EM Images

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 quality of 2-D class averaging, 3-D ab-initio modeling, and 3-D heterogeneity analysis. Contrast estimation is currently performed during 3-D iterative refinement. As a result, the estimates are not available at the earlier computational stages of class averaging and ab-initio modeling. This paper aims to solve the contrast estimation problem directly from the picked particle images in the ab-initio stage, without estimating the 3-D volume, image rotations, or class averages. Methods: The key observation underlying our analysis is that the 2-D covariance matrix of the raw images is related to the covariance of the underlying clean images, the noise variance, and the contrast variability between images. We show that the contrast variability can be derived from the 2-D covariance matrix and we apply the existing Covariance Wiener Filtering (CWF) framework to estimate it. We also demonstrate a modification of CWF to estimate the contrast of individual images. Results: Our method improves the contrast estimation by a large margin, compared to the previous CWF method. Its estimation accuracy is often comparable to that of an oracle that knows the ground truth covariance of the clean images. The more accurate contrast estimation also improves the quality of image restoration as demonstrated in both synthetic and experimental datasets. Conclusions: This paper proposes an effective method for contrast estimation directly from noisy images without using any 3-D volume information. It enables contrast correction in the earlier stage of single particle analysis, and may improve the accuracy of downstream processing.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

An approximate expectation-maximization for two-dimensional multi-target detection

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 rotated and translated. The MTD model serves as a mathematical abstraction of the structure reconstruction problem in single-particle cryo-electron microscopy, the chief motivation of this study. We focus on high noise regimes, where accurate detection of image occurrences within a measurement is impossible. To estimate the image, we develop an expectation-maximization framework that aims to maximize an approximation of the likelihood function. We demonstrate image recovery in highly noisy environments, and show that our framework outperforms the previously studied autocorrelation analysis in a wide range of parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-target detection with rotations

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 copies of the target image. Motivated by single-particle cryo-electron microscopy, we focus on the low signal-to-noise regime, where it is difficult to estimate the locations and orientations of the target images in the measurement. Our approach uses autocorrelation analysis to estimate rotationally and translationally invariant features of the target image. We demonstrate that, regardless of the level of noise, our technique can be used to recover the target image when the measurement is sufficiently large.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On a linearization of quadratic Wasserstein distance

This paper studies the problem of computing a linear approximation of quadratic Wasserstein distance $W_2$. In particular, we compute an approximation of the negative homogeneous weighted Sobolev norm whose connection to Wasserstein distance follows from a classic linearization of a general Monge-Ampére equation. Our contribution is threefold. First, we provide expository material on this classic linearization of Wasserstein distance including a quantitative error estimate. Second, we reduce the computational problem to solving an elliptic boundary value problem involving the Witten Laplacian, which is a Schrödinger operator of the form $H = -Δ+ V$, and describe an associated embedding. Third, for the case of probability distributions on the unit square $[0,1]^2$ represented by $n \times n$ arrays we present a fast code demonstrating our approach. Several numerical examples are presented.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantitatively visualizing bipartite datasets

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-interpretable form. Often, each measurement only conveys the relationship between a pair of entries, and it is difficult to integrate these local interactions across a dataset to form a cohesive global picture. The classic localization problem tackles this question, transforming local measurements into a global map that reveals the underlying structure of a system. Here, we examine the more challenging bipartite localization problem, where pairwise distances are only available for bipartite data comprising two classes of entries (such as antibody-virus interactions, drug-cell potency, or user-rating profiles). We modify previous algorithms to solve bipartite localization and examine how each method behaves in the presence of noise, outliers, and partially-observed data. As a proof of concept, we apply these algorithms to antibody-virus neutralization measurements to create a basis set of antibody behaviors, formalize how potently inhibiting some viruses necessitates weakly inhibiting other viruses, and quantify how often combinations of antibodies exhibit degenerate behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Centering noisy images with application to cryo-EM

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 estimation errors. Our approach uses a surrogate function to the geometric median, which is a robust estimator of the center of mass. We mathematically analyze cases in which the geometric median fails to provide a reasonable estimate of the center of mass, and prove that our surrogate function leads to a successful estimate. One particular application for our method is to improve 3-D reconstruction in single-particle cryo-electron microscopy (cryo-EM). We show how to apply our approach for a better translational alignment of macromolecules picked from experimental data. In this way, we facilitate the succeeding steps of reconstruction and streamline the entire cryo-EM pipeline, saving valuable computational time and supporting resolution enhancement.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Random Conical Tilt Reconstruction without Particle Picking in Cryo-electron Microscopy

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 microscopy. Our method uses autocorrelation analysis on the micrographs to estimate features of the molecule which are invariant under certain nuisance parameters such as the positions of molecular projections in the micrographs. This enables us to reconstruct the molecular structure directly from micrographs, completely circumventing the need for particle picking. We demonstrate reconstructions with simulated data and investigate the effect of the missing-cone region. These results show promise to reduce the size limit for single particle reconstruction in cryo-electron microscopy.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Bias and variance reduction and denoising for CTF Estimation

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 a band-pass filter on the micrograph. In addition, it causes the phase of several frequency bands to be flipped and distorts frequency bands. As a precursor to compensating for this distortion, the corrupting point spread function, which is termed the contrast transfer function (CTF) in reciprocal space, must be estimated. In this paper, we will present a novel method for CTF estimation. Our method is based on the multi-taper method for power spectral density estimation, which aims to reduce the bias and variance of the estimator. Furthermore, we use known properties of the CTF and of the background of the power spectrum to increase the accuracy of our estimation. We will show that the resulting estimates capture the zero-crossings of the CTF in the low-mid frequency range.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Computational Methods for Single-Particle Cryo-EM

Single-particle electron cryomicroscopy (cryo-EM) is an increasingly popular technique for elucidating the three-dimensional structure of proteins and other biologically significant complexes at near-atomic resolution. It is an imaging method that does not require crystallization and can capture molecules in their native states. In single-particle cryo-EM, the three-dimensional molecular structure needs to be determined from many noisy two-dimensional tomographic projections of individual molecules, whose orientations and positions are unknown. The high level of noise and the unknown pose parameters are two key elements that make reconstruction a challenging computational problem. Even more challenging is the inference of structural variability and flexible motions when the individual molecules being imaged are in different conformational states. This review discusses computational methods for structure determination by single-particle cryo-EM and their guiding principles from statistical inference, machine learning, and signal processing that also play a significant role in many other data science applications.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multi-target Detection with an Arbitrary Spacing Distribution

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 signal occur at unknown locations in a long measurement, further corrupted by additive Gaussian noise. At low noise levels, one can easily detect the signal occurrences and estimate the signal by averaging. However, in the presence of high noise, which is the focus of this paper, detection is impossible. Here, we propose two approaches---autocorrelation analysis and an approximate expectation maximization algorithm---to reconstruct the signal without the need to detect signal occurrences in the measurement. In particular, our methods apply to an arbitrary spacing distribution of signal occurrences. We demonstrate reconstructions with synthetic data and empirically show that the sample complexity of both methods scales as 1/SNR^3 in the low SNR regime.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Earthmover-based manifold learning for analyzing molecular conformation spaces

In this paper, we propose a novel approach for manifold learning that combines the Earthmover's distance (EMD) with the diffusion maps method for dimensionality reduction. We demonstrate the potential benefits of this approach for learning shape spaces of proteins and other flexible macromolecules using a simulated dataset of 3-D density maps that mimic the non-uniform rotary motion of ATP synthase. Our results show that EMD-based diffusion maps require far fewer samples to recover the intrinsic geometry than the standard diffusion maps algorithm that is based on the Euclidean distance. To reduce the computational burden of calculating the EMD for all volume pairs, we employ a wavelet-based approximation to the EMD which reduces the computation of the pairwise EMDs to a computation of pairwise weighted-$\ell_1$ distances between wavelet coefficient vectors.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Hyper-Molecules: on the Representation and Recovery of Dynamical Structures, with Application to Flexible Macro-Molecular Structures in Cryo-EM

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 projections of instances of these macromolecules, whose orientations and positions are unknown. The molecular structures are not rigid objects, but flexible objects involved in dynamical processes. The different conformations are exhibited by different instances of the macromolecule observed in a cryo-EM experiment, each of which is recorded as a particle image. The range of conformations and the conformation of each particle are not known a priori; one of the great promises of cryo-EM is to map this conformation space. Remarkable progress has been made in determining rigid structures from homogeneous samples of molecules in spite of the unknown orientation of each particle image and significant progress has been made in recovering a few distinct states from mixtures of rather distinct conformations, but more complex heterogeneous samples remain a major challenge. We introduce the ``hyper-molecule'' framework for modeling structures across different states of heterogeneous molecules, including continuums of states. The key idea behind this framework is representing heterogeneous macromolecules as high-dimensional objects, with the additional dimensions representing the conformation space. This idea is then refined to model properties such as localized heterogeneity. In addition, we introduce an algorithmic framework for recovering such maps of heterogeneous objects from experimental data using a Bayesian formulation of the problem and Markov chain Monte Carlo (MCMC) algorithms to address the computational challenges in recovering these high dimensional hyper-molecules. We demonstrate these ideas in a prototype applied to synthetic data.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Image recovery from rotational and translational invariants

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 multi-target detection statistical model, which is mainly used to study the mathematical and computational properties of single-particle reconstruction using cryo-electron microscopy (cryo-EM) at low signal-to-noise ratios. We demonstrate with synthetic numerical experiments that an image can be reconstructed from rotationally and translationally invariant features and show that the reconstruction is robust to noise. These results constitute an important step towards the goal of structure determination of small biomolecules using cryo-EM.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Method of moments for 3-D single particle ab initio modeling with non-uniform distribution of viewing angles

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 projections images taken at unknown viewing angles. Most reconstruction algorithms require a low-resolution initialization for the 3-D structure, which is the goal of ab initio modeling. Suggested by Zvi Kam in 1980, the method of moments (MoM) offers one approach, wherein low-order statistics of the 2-D images are computed and a 3-D structure is estimated by solving a system of polynomial equations. Unfortunately, Kam's method suffers from restrictive assumptions, most notably that viewing angles should be distributed uniformly. Often unrealistic, uniformity entails the computation of higher-order correlations, as in this case first and second moments fail to determine the 3-D structure. In the present paper, we remove this hypothesis, by permitting an unknown, non-uniform distribution of viewing angles in MoM. Perhaps surprisingly, we show that this case is statistically easier than the uniform case, as now first and second moments generically suffice to determine low-resolution expansions of the molecule. In the idealized setting of a known, non-uniform distribution, we find an efficient provable algorithm inverting first and second moments. For unknown, non-uniform distributions, we use non-convex optimization methods to solve for both the molecule and distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Multi-target detection with application to cryo-electron microscopy

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 can estimate the signals by first detecting occurrences, then clustering and averaging them. In the high noise regime however, neither detection nor clustering can be performed reliably, so that strategies along these lines are destined to fail. Notwithstanding, using autocorrelation analysis, we show that the impossibility to detect and cluster signal occurrences in the presence of high noise does not necessarily preclude signal estimation. Specifically, to estimate the signals, we derive simple relations between the autocorrelations of the observation and those of the signals. These autocorrelations can be estimated accurately at any noise level given a sufficiently long measurement. To recover the signals from the observed autocorrelations, we solve a set of polynomial equations through nonlinear least-squares. We provide analysis regarding well-posedness of the task, and demonstrate numerically the effectiveness of the method in a variety of settings. The main goal of this work is to provide theoretical and numerical support for a recently proposed framework to image 3-D structures of biological macromolecules using cryo-electron microscopy in extreme noise levels.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities

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 processing techniques. Owing to these new exciting developments, cryo-EM was selected by Nature Methods as Method of the Year 2015, and the Nobel Prize in Chemistry 2017 was awarded to three pioneers in the field. The main goal of this article is to introduce the challenging and exciting computational tasks involved in reconstructing 3-D molecular structures by cryo-EM. Determining molecular structures requires a wide range of computational tools in a variety of fields, including signal processing, estimation and detection theory, high-dimensional statistics, convex and non-convex optimization, spectral algorithms, dimensionality reduction, and machine learning. The tools from these fields must be adapted to work under exceptionally challenging conditions, including extreme noise levels, the presence of missing data, and massively large datasets as large as several Terabytes. In addition, we present two statistical models: multi-reference alignment and multi-target detection, that abstract away much of the intricacies of cryo-EM, while retaining some of its essential features. Based on these abstractions, we discuss some recent intriguing results in the mathematical theory of cryo-EM, and delineate relations with group theory, invariant theory, and information theory.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Representation Theory Perspective on Simultaneous Alignment and Classification

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 orientations, is heterogeneity in samples: in many cases, the samples contain a mixture of molecules, or multiple conformations of one molecule. Many algorithms for the reconstruction of molecules from images in heterogeneous Cryo-EM experiments are based on iterative approximations of the molecules in a non-convex optimization that is prone to reaching suboptimal local minima. Other algorithms require an alignment in order to perform classification, or vice versa. The recently introduced Non-Unique Games framework provides a representation theoretic approach to studying problems of alignment over compact groups, and offers convex relaxations for alignment problems which are formulated as semidefinite programs (SDPs) with certificates of global optimality under certain circumstances. In this manuscript, we propose to extend Non-Unique Games to the problem of simultaneous alignment and classification with the goal of simultaneously classifying Cryo-EM images and aligning them within their respective classes. Our proposed approach can also be extended to the case of continuous heterogeneity.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Bias Correction in Saupe Tensor Estimation

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 template structure, the singular value decomposition (SVD) method proposed in Losonczi et al. 1999 has been used traditionally to estimate the Saupe tensor. Despite its simplicity, whenever the template structure has large structural noise, the eigenvalues of the estimated tensor have a magnitude systematically smaller than their actual values. This leads to systematic error when calculating the eigenvalue dependent parameters, magnitude and rhombicity. We propose here a Monte Carlo simulation method to remove such bias. We further demonstrate the effectiveness of our method in the setting when the eigenvalue estimates from multiple template protein fragments are available and their average is used as an improved eigenvalue estimator. For both synthetic and experimental RDC datasets of ubiquitin, when using template fragments corrupted by large noise, the magnitude of our proposed bias-reduced estimator generally reaches at least 90% of the actual value, whereas the magnitude of SVD estimator can be shrunk below 80% of the true value.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Denoising and Covariance Estimation of Single Particle Cryo-EM Images

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 `phase flipping', which corrects only for the Fourier phases but not amplitudes, and Wiener filtering, which requires the spectral signal to noise ratio. We propose a new image restoration method which we call `Covariance Wiener Filtering' (CWF). In CWF, the covariance matrix of the projection images is used within the classical Wiener filtering framework for solving the image restoration deconvolution problem. Our estimation procedure for the covariance matrix is new and successfully corrects for the CTF. We demonstrate the efficacy of CWF by applying it to restore both simulated and experimental cryo-EM images. Results with experimental datasets demonstrate that CWF provides a good way to evaluate the particle images and to see what the dataset contains even without 2D classification and averaging.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Marchenko-Pastur Law for Tyler's M-estimator

This paper studies the limiting behavior of Tyler's M-estimator for the scatter matrix, in the regime that the number of samples $n$ and their dimension $p$ both go to infinity, and $p/n$ converges to a constant $y$ with $0<y<1$. We prove that when the data samples $x_1, \ldots, x_n$ are identically and independently generated from the Gaussian distribution $\mathcal{N}(0, I)$, the operator norm of the difference between a properly scaled Tyler's M-estimator and $\sum_{i=1}^n x_i x_i^\top/n$ tends to zero. As a result, the spectral distribution of Tyler's M-estimator converges weakly to the Marčenko-Pastur distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using convex relaxations. In some cases, the relaxation is tight: it recovers the true MLE. Most tightness proofs only apply to situations where the MLE exactly recovers a planted solution (known to the analyst). It is then sufficient to establish that the optimality conditions hold at the planted signal. In this paper, we study an estimation problem (angular synchronization) for which the MLE is not a simple function of the planted solution, yet for which the convex relaxation is tight. To establish tightness in this context, the proof is less direct because the point at which to verify optimality conditions is not known explicitly. Angular synchronization consists in estimating a collection of $n$ phases, given noisy measurements of the pairwise relative phases. The MLE for angular synchronization is the solution of a (hard) non-bipartite Grothendieck problem over the complex numbers. We consider a stochastic model for the data: a planted signal (that is, a ground truth set of phases) is corrupted with non-adversarial random noise. Even though the MLE does not coincide with the planted signal, we show that the classical semidefinite relaxation for it is tight, with high probability. This holds even for high levels of noise.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups

The little Grothendieck problem consists of maximizing $\sum_{ij}C_{ij}x_ix_j$ over binary variables $x_i\in\{\pm1\}$, where C is a positive semidefinite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C a dn x dn positive semidefinite matrix, the objective is to maximize $\sum_{ij}Tr (C_{ij}^TO_iO_j^T)$ restricting $O_i$ to take values in the group of orthogonal matrices, where $C_{ij}$ denotes the (ij)-th d x d block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve this problem and show a constant approximation ratio. Our method is based on semidefinite programming. For a given $d\geq 1$, we show a constant approximation ratio of $α_{R}(d)^2$, where $α_{R}(d)$ is the expected average singular value of a d x d matrix with random Gaussian $N(0,1/d)$ i.i.d. entries. For d=1 we recover the known $α_{R}(1)^2=2/π$ approximation guarantee for the classical little Grothendieck problem. Our algorithm and analysis naturally extends to the complex valued case also providing a constant approximation ratio for the analogous problem over the Unitary Group. Orthogonal-Cut also serves as an approximation algorithm for several applications, including the Procrustes problem where it improves over the best previously known approximation ratio of~$\frac1{2\sqrt{2}}$. The little Grothendieck problem falls under the class of problems approximated by a recent algorithm proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and it provides a more efficient algorithm with better approximation ratios and matching integrality gaps. Finally, we also provide an improved approximation algorithm for the more general little Grothendieck problem over the orthogonal (or unitary) group with rank constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Covariance estimation using conjugate gradient for 3D classification in Cryo-EM

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 covariance matrix of the three-dimensional structure present in the molecules being imaged. Our proposed method allows for incorporation of contrast transfer function and non-uniform distribution of viewing angles, making it more suitable for real-world data. We evaluate its performance on a synthetic dataset and an experimental dataset obtained by imaging a 70S ribosome complex.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fast Steerable Principal Component Analysis

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 algorithm that efficiently and accurately performs principal component analysis (PCA) for a large set of two-dimensional images, and, for each image, the set of its uniform rotations in the plane and their reflections. For a dataset consisting of $n$ images of size $L \times L$ pixels, the computational complexity of our algorithm is $O(nL^3 + L^4)$, while existing algorithms take $O(nL^4)$. The new algorithm computes the expansion coefficients of the images in a Fourier-Bessel basis efficiently using the non-uniform fast Fourier transform. We compare the accuracy and efficiency of the new algorithm with traditional PCA and existing algorithms for steerable PCA.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Large-Scale Sensor Network Localization via Rigid Subnetwork Registration

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 using some fast and accurate algorithm, and finally registers the localized subnetworks in a global coordinate system. We demonstrate that this divide-and-conquer algorithm can be used to leverage existing high-precision SNL algorithms to large-scale networks, which could otherwise only be applied to small-to-medium sized networks. The main contribution of this paper concerns the final registration phase. In particular, we consider a least-squares formulation of the registration problem (both with and without anchor constraints) and demonstrate how this otherwise non-convex problem can be relaxed into a tractable convex program. We provide some preliminary simulation results for large-scale SNL demonstrating that the proposed registration algorithm (together with an accurate localization scheme) offers a good tradeoff between run time and accuracy.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Non-unique games over compact groups and orientation estimation in cryo-EM

Let $\mathcal{G}$ be a compact group and let $f_{ij} \in L^2(\mathcal{G})$. We define the Non-Unique Games (NUG) problem as finding $g_1,\dots,g_n \in \mathcal{G}$ to minimize $\sum_{i,j=1}^n f_{ij} \left( g_i g_j^{-1}\right)$. We devise a relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of $f_{ij}$ over $\mathcal{G}$, which can then be solved efficiently. The NUG framework can be seen as a generalization of the little Grothendieck problem over the orthogonal group and the Unique Games problem and includes many practically relevant problems, such as the maximum likelihood estimator} to registering bandlimited functions over the unit sphere in $d$-dimensions and orientation estimation in cryo-Electron Microscopy.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Orthogonal Matrix Retrieval in Cryo-Electron Microscopy

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 unknown viewing directions. Zvi Kam showed already in 1980 that the autocorrelation function of the 3D molecule over the rotation group SO(3) can be estimated from 2D projection images whose viewing directions are uniformly distributed over the sphere. The autocorrelation function determines the expansion coefficients of the 3D molecule in spherical harmonics up to an orthogonal matrix of size $(2l+1)\times (2l+1)$ for each $l=0,1,2,...$. In this paper we show how techniques for solving the phase retrieval problem in X-ray crystallography can be modified for the cryo-EM setup for retrieving the missing orthogonal matrices. Specifically, we present two new approaches that we term Orthogonal Extension and Orthogonal Replacement, in which the main algorithmic components are the singular value decomposition and semidefinite programming. We demonstrate the utility of these approaches through numerical experiments on simulated data.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Robust Camera Location Estimation by Convex Programming

$3$D structure recovery from a collection of $2$D images requires the estimation of the camera locations and orientations, i.e. the camera motion. For large, irregular collections of images, existing methods for the location estimation part, which can be formulated as the inverse problem of estimating $n$ locations $\mathbf{t}_1, \mathbf{t}_2, \ldots, \mathbf{t}_n$ in $\mathbb{R}^3$ from noisy measurements of a subset of the pairwise directions $\frac{\mathbf{t}_i - \mathbf{t}_j}{\|\mathbf{t}_i - \mathbf{t}_j\|}$, are sensitive to outliers in direction measurements. In this paper, we firstly provide a complete characterization of well-posed instances of the location estimation problem, by presenting its relation to the existing theory of parallel rigidity. For robust estimation of camera locations, we introduce a two-step approach, comprised of a pairwise direction estimation method robust to outliers in point correspondences between image pairs, and a convex program to maintain robustness to outlier directions. In the presence of partially corrupted measurements, we empirically demonstrate that our convex formulation can even recover the locations exactly. Lastly, we demonstrate the utility of our formulations through experiments on Internet photo collections.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Spectral Convergence of the connection Laplacian from random samples

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 and non-linear dimensionality reduction. It was previously shown by Belkin and Niyogi \cite{belkin_niyogi:2007} that the eigenvectors and eigenvalues of the graph Laplacian converge to the eigenfunctions and eigenvalues of the Laplace-Beltrami operator of the manifold in the limit of infinitely many data points sampled independently from the uniform distribution over the manifold. Recently, we introduced Vector Diffusion Maps and showed that the connection Laplacian of the tangent bundle of the manifold can be approximated from random samples. In this paper, we present a unified framework for approximating other connection Laplacians over the manifold by considering its principle bundle structure. We prove that the eigenvectors and eigenvalues of these Laplacians converge in the limit of infinitely many independent random samples. We generalize the spectral convergence results to the case where the data points are sampled from a non-uniform distribution, and for manifolds with and without boundary.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stable Camera Motion Estimation Using Convex Programming

We study the inverse problem of estimating n locations $t_1, ..., t_n$ (up to global scale, translation and negation) in $R^d$ from noisy measurements of a subset of the (unsigned) pairwise lines that connect them, that is, from noisy measurements of $\pm (t_i - t_j)/\|t_i - t_j\|$ for some pairs (i,j) (where the signs are unknown). This problem is at the core of the structure from motion (SfM) problem in computer vision, where the $t_i$'s represent camera locations in $R^3$. The noiseless version of the problem, with exact line measurements, has been considered previously under the general title of parallel rigidity theory, mainly in order to characterize the conditions for unique realization of locations. For noisy pairwise line measurements, current methods tend to produce spurious solutions that are clustered around a few locations. This sensitivity of the location estimates is a well-known problem in SfM, especially for large, irregular collections of images. In this paper we introduce a semidefinite programming (SDP) formulation, specially tailored to overcome the clustering phenomenon. We further identify the implications of parallel rigidity theory for the location estimation problem to be well-posed, and prove exact (in the noiseless case) and stable location recovery results. We also formulate an alternating direction method to solve the resulting semidefinite program, and provide a distributed version of our formulation for large numbers of locations. Specifically for the camera location estimation problem, we formulate a pairwise line estimation method based on robust camera orientation and subspace estimation. Lastly, we demonstrate the utility of our algorithm through experiments on real images.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Covariance Matrix Estimation for the Cryo-EM Heterogeneity Problem

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) from cryo-EM is to use the resulting set of noisy 2D projection images taken at unknown directions to reconstruct the 3D structure of the molecule. In some situations, the molecule under examination exhibits structural variability, which poses a fundamental challenge in SPR. The heterogeneity problem is the task of mapping the space of conformational states of a molecule. It has been previously suggested that the leading eigenvectors of the covariance matrix of the 3D molecules can be used to solve the heterogeneity problem. Estimating the covariance matrix is challenging, since only projections of the molecules are observed, but not the molecules themselves. In this paper, we formulate a general problem of covariance estimation from noisy projections of samples. This problem has intimate connections with matrix completion problems and high-dimensional principal component analysis. We propose an estimator and prove its consistency. When there are finitely many heterogeneity classes, the spectrum of the estimated covariance matrix reveals the number of classes. The estimator can be found as the solution to a certain linear system. In the cryo-EM case, the linear operator to be inverted, which we term the projection covariance transform, is an important object in covariance estimation for tomographic problems involving structural variation. Inverting it involves applying a filter akin to the ramp filter in tomography. We design a basis in which this linear operator is sparse and thus can be tractably inverted despite its large size. We demonstrate via numerical experiments on synthetic datasets the robustness of our algorithm to high levels of noise.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery

We consider the problem of clustering a graph $G$ into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables $Y=B_G x \oplus Z$, where $B_G$ is the incidence matrix of a graph $G$, $x$ is the vector of unknown vertex variables (with a uniform prior) and $Z$ is a noise vector with Bernoulli$(\varepsilon)$ i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of $x$ is possible if and only the graph $G$ is connected, with a sharp threshold at the edge probability $\log(n)/n$ for Erdős-Rényi random graphs. The first goal of this paper is to determine how the edge probability $p$ needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by $α=np/\log(n)$, it is shown that exact recovery is possible if and only if $α>2/(1-2\varepsilon)^2+ o(1/(1-2\varepsilon)^2)$. In other words, $2/(1-2\varepsilon)^2$ is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph $G$, defining the degree rate as $α=d/\log(n)$, where $d$ is the minimum degree of the graph, it is shown that the proposed method achieves the rate $α> 4((1+λ)/(1-λ)^2)/(1-2\varepsilon)^2+ o(1/(1-2\varepsilon)^2)$, where $1-λ$ is the spectral gap of the graph $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Global registration of multiple point clouds using semidefinite programming

Consider $N$ points in $\mathbb{R}^d$ and $M$ local coordinate systems that are related through unknown rigid transforms. For each point we are given (possibly noisy) measurements of its local coordinates in some of the coordinate systems. Alternatively, for each coordinate system, we observe the coordinates of a subset of the points. The problem of estimating the global coordinates of the $N$ points (up to a rigid transform) from such measurements comes up in distributed approaches to molecular conformation and sensor network localization, and also in computer vision and graphics. The least-squares formulation of this problem, though non-convex, has a well known closed-form solution when $M=2$ (based on the singular value decomposition). However, no closed form solution is known for $M\geq 3$. In this paper, we demonstrate how the least-squares formulation can be relaxed into a convex program, namely a semidefinite program (SDP). By setting up connections between the uniqueness of this SDP and results from rigidity theory, we prove conditions for exact and stable recovery for the SDP relaxation. In particular, we prove that the SDP relaxation can guarantee recovery under more adversarial conditions compared to earlier proposed spectral relaxations, and derive error bounds for the registration error incurred by the SDP relaxation. We also present results of numerical experiments on simulated data to confirm the theoretical findings. We empirically demonstrate that (a) unlike the spectral relaxation, the relaxation gap is mostly zero for the semidefinite program (i.e., we are able to solve the original non-convex least-squares problem) up to a certain noise threshold, and (b) the semidefinite program performs significantly better than spectral and manifold-optimization methods, particularly at large noise levels.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Open problem: Tightness of maximum likelihood semidefinite relaxations

We have observed an interesting, yet unexplained, phenomenon: Semidefinite programming (SDP) based relaxations of maximum likelihood estimators (MLE) tend to be tight in recovery problems with noisy data, even when MLE cannot exactly recover the ground truth. Several results establish tightness of SDP based relaxations in the regime where exact recovery from MLE is possible. However, to the best of our knowledge, their tightness is not understood beyond this regime. As an illustrative example, we focus on the generalized Procrustes problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Rotationally Invariant Image Representation for Viewing Direction Classification in Cryo-EM

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 knowledge of the molecule. Our rotationally invariant features are based on the bispectrum. Each image is denoised and compressed using steerable principal component analysis (PCA) such that rotating an image is equivalent to phase shifting the expansion coefficients. Thus we are able to extend the theory of bispectrum of 1D periodic signals to 2D images. The randomized PCA algorithm is then used to efficiently reduce the dimensionality of the bispectrum coefficients, enabling fast computation of the similarity between any pair of images. The nearest neighbors provide an initial classification of similar viewing angles. In this way, rotational alignment is only performed for images with their nearest neighbors. The initial nearest neighbor classification and alignment are further improved by a new classification method called vector diffusion maps. Our pipeline for viewing angle classification and alignment is experimentally shown to be faster and more accurate than reference-free alignment with rotationally invariant K-means clustering, MSA/MRA 2D classification, and their modern approximations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Cheeger Inequality for the Graph Connection Laplacian

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 formulate and prove a Cheeger-type inequality that relates a measure of how well it is possible to solve the O(d) synchronization problem with the spectra of an operator, the graph Connection Laplacian. We also show how this inequality provides a worst case performance guarantee for a spectral method to solve this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Fourier-based Approach for Iterative 3D Reconstruction from Cryo-EM Images

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) macromolecular structures. Obtaining high resolution 3D reconstructions is difficult due to unknown orientations and positions of the imaged particles, possible incomplete coverage of the viewing directions, high level of noise in the projection images, and limiting effects of the contrast transfer function of the electron microscope. In this paper, we focus on the 3D reconstruction problem from projection images assuming an existing estimate for their orientations and positions. We propose a fast and accurate Fourier-based Iterative Reconstruction Method (FIRM) that exploits the Toeplitz structure of the operator ${\bf A}^{*}{\bf A}$, where $\bf A$ is the forward projector and ${\bf A}^{*}$ is the back projector. The operator ${\bf A}^{*}{\bf A}$ is equivalent to a convolution with a kernel. The kernel is pre-computed using the non-uniform Fast Fourier Transform and is efficiently applied in each iteration step. The iterations by FIRM are therefore considerably faster than those of traditional iterative algebraic approaches, while maintaining the same accuracy even when the viewing directions are unevenly distributed. The time complexity of FIRM is comparable to the direct Fourier inversion method. Moreover, FIRM combines images from different defocus groups simultaneously and can handle a wide range of regularization terms. We provide experimental results on simulated data that demonstrate the speed and accuracy of FIRM in comparison with current methods.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Cramér-Rao bounds for synchronization of rotations

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 fundamental problem has found many recent applications, most importantly in structural biology. We provide a framework to study synchronization as estimation on Riemannian manifolds for arbitrary n under a large family of noise models. The noise models we address encompass zero-mean isotropic noise, and we develop tools for Gaussian-like as well as heavy-tail types of noise in particular. As a main contribution, we derive the Cramér-Rao bounds of synchronization, that is, lower-bounds on the variance of unbiased estimators. We find that these bounds are structured by the pseudoinverse of the measurement graph Laplacian, where edge weights are proportional to measurement quality. We leverage this to provide interpretation in terms of random walks and visualization tools for these bounds in both the anchored and anchor-free scenarios. Similar bounds previously established were limited to rotations in the plane and Gaussian-like noise.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Exact and Stable Recovery of Rotations for Robust Synchronization

The synchronization problem over the special orthogonal group $SO(d)$ consists of estimating a set of unknown rotations $R_1,R_2,...,R_n$ from noisy measurements of a subset of their pairwise ratios $R_{i}^{-1}R_{j}$. The problem has found applications in computer vision, computer graphics, and sensor network localization, among others. Its least squares solution can be approximated by either spectral relaxation or semidefinite programming followed by a rounding procedure, analogous to the approximation algorithms of \textsc{Max-Cut}. The contribution of this paper is three-fold: First, we introduce a robust penalty function involving the sum of unsquared deviations and derive a relaxation that leads to a convex optimization problem; Second, we apply the alternating direction method to minimize the penalty function; Finally, under a specific model of the measurement noise and for both complete and random measurement graphs, we prove that the rotations are exactly and stably recovered, exhibiting a phase transition behavior in terms of the proportion of noisy measurements. Numerical simulations confirm the phase transition behavior for our method as well as its improved accuracy compared to existing methods.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fourier-Bessel rotational invariant eigenimages

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 rotations in the plane and its reflection. The algorithm starts by expanding each image, originally given on a Cartesian grid, in the Fourier-Bessel basis for the disk. Because the images are bandlimited in the Fourier domain, we use a sampling criterion to truncate the Fourier-Bessel expansion such that the maximum amount of information is preserved without the effect of aliasing. The constructed covariance matrix is invariant to rotation and reflection and has a special block diagonal structure. PCA is efficiently done for each block separately. This Fourier-Bessel based PCA detects more meaningful eigenimages and has improved denoising capability compared to traditional PCA for a finite number of noisy images.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Multireference Alignment using Semidefinite Programming

The multireference alignment problem consists of estimating a signal from multiple noisy shifted observations. Inspired by existing Unique-Games approximation algorithms, we provide a semidefinite program (SDP) based relaxation which approximates the maximum likelihood estimator (MLE) for the multireference alignment problem. Although we show that the MLE problem is Unique-Games hard to approximate within any constant, we observe that our poly-time approximation algorithm for the MLE appears to perform quite well in typical instances, outperforming existing methods. In an attempt to explain this behavior we provide stability guarantees for our SDP under a random noise model on the observations. This case is more challenging to analyze than traditional semi-random instances of Unique-Games: the noise model is on vertices of a graph and translates into dependent noise on the edges. Interestingly, we show that if certain positivity constraints in the SDP are dropped, its solution becomes equivalent to performing phase correlation, a popular method used for pairwise alignment in imaging applications. Finally, we show how symmetry reduction techniques from matrix representation theory can simplify the analysis and computation of the SDP, greatly decreasing its computational cost.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Orientation Determination from Cryo-EM images Using Least Unsquared Deviation

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 images with unknown orientations. Common-lines based methods estimate the orientations without additional geometric information. However, such methods fail when the detection rate of common-lines is too low due to the high level of noise in the images. An approximation to the least squares global self consistency error was obtained using convex relaxation by semidefinite programming. In this paper we introduce a more robust global self consistency error and show that the corresponding optimization problem can be solved via semidefinite relaxation. In order to prevent artificial clustering of the estimated viewing directions, we further introduce a spectral norm term that is added as a constraint or as a regularization term to the relaxed minimization problem. The resulted problems are solved by using either the alternating direction method of multipliers or an iteratively reweighted least squares procedure. Numerical experiments with both simulated and real images demonstrate that the proposed methods significantly reduce the orientation estimation error when the detection rate of common-lines is low.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Non-Local Euclidean Medians

In this letter, we note that the denoising performance of Non-Local Means (NLM) at large noise levels can be improved by replacing the mean by the Euclidean median. We call this new denoising algorithm the Non-Local Euclidean Medians (NLEM). At the heart of NLEM is the observation that the median is more robust to outliers than the mean. In particular, we provide a simple geometric insight that explains why NLEM performs better than NLM in the vicinity of edges, particularly at large noise levels. NLEM can be efficiently implemented using iteratively reweighted least squares, and its computational complexity is comparable to that of NLM. We provide some preliminary results to study the proposed algorithm and to compare it with NLM.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Non-Local Patch Regression: Robust Image Denoising in Patch Space

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 replacing the mean by the robust Euclidean median. Numerical experiments on synthetic and natural images showed that the latter consistently performed better than NLM beyond a certain noise level, and significantly so for images with sharp edges. The Euclidean mean and median can be put into a common regression (on the patch space) framework, in which the l_2 norm of the residuals is considered in the former, while the l_1 norm is considered in the latter. The natural question then is what happens if we consider l_p (0<p<1) regression? We investigate this possibility in this paper.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Spectrum of Random Inner-product Kernel Matrices

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 eigenvalue distribution of these random kernel matrices is studied at the "large p, large n" regime. It is shown that, when p and n go to infinity, p/n = γwhich is a constant, and f is properly scaled so that Var(f(X_i^T X_j)) is O(p^{-1}), the spectral density converges weakly to a limiting density on R. The limiting density is dictated by a cubic equation involving its Stieltjes transform. While for smooth kernel functions the limiting spectral density has been previously shown to be the Marcenko-Pastur distribution, our analysis is applicable to non-smooth kernel functions, resulting in a new family of limiting densities.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Noisy dynamic simulations in the presence of symmetry: data alignment and model reduction

We process snapshots of trajectories of evolution equations with intrinsic symmetries, and demonstrate the use of recently developed eigenvector-based techniques to successfully quotient out the degrees of freedom associated with the symmetries in the presence of noise. Our illustrative examples include a one-dimensional evolutionary partial differential (the Kuramoto-Sivashinsky) equation with periodic boundary conditions, as well as a stochastic simulation of nematic liquid crystals which can be effectively modeled through a nonlinear Smoluchowski equation on the surface of a sphere. This is a useful first step towards data mining the "symmetry-adjusted" ensemble of snapshots in search of an accurate low-dimensional parametrization (and the associated reduction of the original dynamical system). We also demonstrate a technique ("vector diffusion maps") that combines, in a single formulation, the symmetry removal step and the dimensionality reduction step.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Representation theoretic patterns in three dimensional cryo-electron microscopy II - The class averaging problem

In this paper we study the formal algebraic structure underlying the intrinsic classification algorithm, recently introduced by Hadani, Shkolnisky, Singer and Zhao, for classifying noisy projection images of similar viewing directions in three-dimensional cryo-electron microscopy (cryo-EM). This preliminary classification is of fundamental importance in determining the three-dimensional structure of macromolecules from cryo-EM images. Inspecting this algebraic structure we obtain a conceptual explanation for the admissibility (correctness) of the algorithm and a proof of its numerical stability, thus putting it on firm mathematical grounds. The proof relies on studying the spectral properties of an integral operator of geometric origin on the two dimensional sphere, called the localized parallel transport operator. Along the way, we develop further the representation theoretic set-up for three-dimensional cryo-EM.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Vector Diffusion Maps and the Connection Laplacian

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 mathematical and algorithmic generalization of diffusion maps and other non-linear dimensionality reduction methods, such as LLE, ISOMAP and Laplacian eigenmaps. While existing methods are either directly or indirectly related to the heat kernel for functions over the data, VDM is based on the heat kernel for vector fields. VDM provides tools for organizing complex data sets, embedding them in a low dimensional space, and interpolating and regressing vector fields over the data. In particular, it equips the data with a metric, which we refer to as the {\em vector diffusion distance}. In the manifold learning setup, where the data set is distributed on (or near) a low dimensional manifold $\MM^d$ embedded in $\RR^{p}$, we prove the relation between VDM and the connection-Laplacian operator for vector fields over the manifold.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Manifold learning techniques and model reduction applied to dissipative PDEs

We link nonlinear manifold learning techniques for data analysis/compression with model reduction techniques for evolution equations with time scale separation. In particular, we demonstrate a `"nonlinear extension" of the POD-Galerkin approach to obtaining reduced dynamic models of dissipative evolution equations. The approach is illustrated through a reaction-diffusion PDE, and the performance of different simulators on the full and the reduced models is compared. We also discuss the relation of this nonlinear extension with the so-called "nonlinear Galerkin" methods developed in the context of Approximate Inertial Manifolds.

0 citations0 reviewsNo code linkedOpen access