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

Tamir Bendory

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

ResearcherUnclaimed source record
Information Theorymath.ITeess.SPComputer Visioneess.IVmath.AGComputationMachine Learningmath-phmath.MPmath.NA

Catalog footprint

What is connected

29works
11topics
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

29 published item(s)

preprint2026arXiv

An Ultra-Fast MLE for Low SNR Multi-Reference Alignment

Motivated by single-particle cryo-electron microscopy, multi-reference alignment (MRA) models the task of recovering an unknown signal from multiple noisy observations corrupted by random rotations. The standard approach, expectation-maximization (EM), often becomes computationally prohibitive, particularly in low signal-to-noise ratio (SNR) settings. We introduce an alternative, ultra-fast algorithm for MRA over the special orthogonal group $\mathrm{SO}(2)$. By performing a Taylor expansion of the log-likelihood in the low-SNR regime, we estimate the signal by sequentially computing data-driven averages of observations. Our method requires only one pass over the data, dramatically reducing computational cost compared to EM. Numerical experiments show that the proposed approach achieves high accuracy in low-SNR environments and provides an excellent initialization for subsequent EM refinement.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

An accelerated expectation-maximization algorithm for multi-reference alignment

The multi-reference alignment (MRA) problem entails estimating an image from multiple noisy and rotated copies of itself. If the noise level is low, one can reconstruct the image by estimating the missing rotations, aligning the images, and averaging out the noise. While accurate rotation estimation is impossible if the noise level is high, the rotations can still be approximated, and thus can provide indispensable information. In particular, learning the approximation error can be harnessed for efficient image estimation. In this paper, we propose a new computational framework, called Synch-EM, that consists of angular synchronization followed by expectation-maximization (EM). The synchronization step results in a concentrated distribution of rotations; this distribution is learned and then incorporated into the EM as a Bayesian prior. The learned distribution also dramatically reduces the search space, and thus the computational load, of the EM iterations. We show by extensive numerical experiments that the proposed framework can significantly accelerate EM for MRA in high noise levels, occasionally by a few orders of magnitude, without degrading the reconstruction quality.

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

Compactification of the Rigid Motions Group in Image Processing

Image processing problems in general, and in particular in the field of single-particle cryo-electron microscopy, often require considering images up to their rotations and translations. Such problems were tackled successfully when considering images up to rotations only, using quantities which are invariant to the action of rotations on images. Extending these methods to cases where translations are involved is more complicated. Here we present a computationally feasible and theoretically sound approximate invariant to the action of rotations and translations on images. It allows one to approximately reduce image processing problems to similar problems over the sphere, a compact domain acted on by the group of 3D rotations, a compact group. We show that this invariant is induced by a family of mappings deforming, and thereby compactifying, the group structure of rotations and translations of the plane, i.e., the group of rigid motions, into the group of 3D rotations. Furthermore, we demonstrate its viability in two image processing tasks: multi-reference alignment and classification. To our knowledge, this is the first instance of a quantity that is either exactly or approximately invariant to rotations and translations of images that both rests on a sound theoretical foundation and also applicable in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Dihedral multi-reference alignment

We study the dihedral multi-reference alignment problem of estimating the orbit of a signal from multiple noisy observations of the signal, acted on by random elements of the dihedral group. We show that if the group elements are drawn from a generic distribution, the orbit of a generic signal is uniquely determined from the second moment of the observations. This implies that the optimal estimation rate in the high noise regime is proportional to the square of the variance of the noise. This is the first result of this type for multi-reference alignment over a non-abelian group with a non-uniform distribution of group elements. Based on tools from invariant theory and algebraic geometry, we also delineate conditions for unique orbit recovery for multi-reference alignment models over finite groups (namely, when the dihedral group is replaced by a general finite group) when the group elements are drawn from a generic distribution. Finally, we design and study numerically three computational frameworks for estimating the signal based on group synchronization, expectation-maximization, and the method of moments.

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

Two-dimensional multi-target detection: an autocorrelation analysis approach

We consider the two-dimensional multi-target detection problem of recovering a target image from a noisy measurement that contains multiple copies of the image, each randomly rotated and translated. Motivated by the structure reconstruction problem in single-particle cryo-electron microscopy, we focus on the high noise regime, where the noise hampers accurate detection of the image occurrences. We develop an autocorrelation analysis framework to estimate the image directly from a measurement with an arbitrary spacing distribution of image occurrences, bypassing the estimation of individual locations and rotations. We conduct extensive numerical experiments, and demonstrate image recovery in highly noisy environments. The code to reproduce all numerical experiments is publicly available at https://github.com/krshay/MTD-2D.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Generalized autocorrelation analysis for multi-target detection

We study the multi-target detection problem of recovering a target signal from a noisy measurement that contains multiple copies of the signal at unknown locations. Motivated by the structure reconstruction problem in cryo-electron microscopy, we focus on the high noise regime, where noise hampers accurate detection of signal occurrences. Previous works proposed an autocorrelation analysis framework to estimate the signal directly from the measurement, without detecting signal occurrences. Specifically, autocorrelation analysis entails finding a signal that best matches the observable autocorrelations by minimizing a least squares objective. This paper extends this line of research by developing a generalized autocorrelation analysis framework that replaces the least squares by a weighted least squares. The optimal weights can be computed directly from the data and guarantee favorable statistical properties. We demonstrate signal recovery from highly noisy measurements, and show that the proposed framework outperforms autocorrelation analysis in a wide range of parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

The generalized method of moments for multi-reference alignment

This paper studies the application of the generalized method of moments (GMM) to multi-reference alignment (MRA): the problem of estimating a signal from its circularly-translated and noisy copies. We begin by proving that the GMM estimator maintains its asymptotic optimality for statistical models with group symmetry, including MRA. Then, we conduct a comprehensive numerical study and show that the GMM substantially outperforms the classical method of moments, whose application to MRA has been studied thoroughly in the literature. We also formulate the GMM to estimate a three-dimensional molecular structure using cryo-electron microscopy and present numerical results on simulated data.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A note on Douglas-Rachford, gradients, and phase retrieval

The properties of gradient techniques for the phase retrieval problem have received a considerable attention in recent years. In almost all applications, however, the phase retrieval problem is solved using a family of algorithms that can be interpreted as variants of Douglas-Rachford splitting. In this work, we establish a connection between Douglas-Rachford and gradient algorithms. Specifically, we show that in some cases a generalization of Douglas-Rachford, called relaxed-reflect-reflect (RRR), can be viewed as gradient descent on a certain objective function. The solutions coincide with the critical points of that objective, which---in contrast to standard gradient techniques---are not its minimizers. Using the objective function, we give simple proofs of some basic properties of the RRR algorithm. Specifically, we describe its set of solutions, show a local convexity around any solution, and derive stability guarantees. Nevertheless, in its present state, the analysis does not elucidate the remarkable empirical performance of RRR and its global properties.

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
preprint2020arXiv

Stable Super-Resolution of Images: A Theoretical Study

We study the ubiquitous super-resolution problem, in which one aims at localizing positive point sources in an image, blurred by the point spread function of the imaging device. To recover the point sources, we propose to solve a convex feasibility program, which simply finds a nonnegative Borel measure that agrees with the observations collected by the imaging device. In the absence of imaging noise, we show that solving this convex program uniquely retrieves the point sources, provided that the imaging device collects enough observations. This result holds true if the point spread function of the imaging device can be decomposed into horizontal and vertical components, and if the translations of these components form a Chebyshev system, i.e., a system of continuous functions that loosely behave like algebraic polynomials. Building upon recent results for one-dimensional signals [1], we prove that this super-resolution algorithm is stable, in the generalized Wasserstein metric, to model mismatch (i.e., when the image is not sparse) and to additive imaging noise. In particular, the recovery error depends on the noise level and how well the image can be approximated with well-separated point sources. As an example, we verify these claims for the important case of a Gaussian point spread function. The proofs rely on the construction of novel interpolating polynomials---which are the main technical contribution of this paper---and partially resolve the question raised in [2] about the extension of the standard machinery to higher dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Toward a mathematical theory of the crystallographic phase retrieval problem

Motivated by the X-ray crystallography technology to determine the atomic structure of biological molecules, we study the crystallographic phase retrieval problem, arguably the leading and hardest phase retrieval setup. This problem entails recovering a K-sparse signal of length N from its Fourier magnitude or, equivalently, from its periodic auto-correlation. Specifically, this work focuses on the fundamental question of uniqueness: what is the maximal sparsity level K/N that allows unique mapping between a signal and its Fourier magnitude, up to intrinsic symmetries. We design a systemic computational technique to affirm uniqueness for any specific pair (K,N), and establish the following conjecture: the Fourier magnitude determines a generic signal uniquely, up to intrinsic symmetries, as long as K<=N/2. Based on group-theoretic considerations and an additional computational technique, we formulate a second conjecture: if K<N/2, then for any signal the set of solutions to the crystallographic phase retrieval problem has measure zero in the set of all signals with a given Fourier magnitude. Together, these conjectures constitute the first attempt to establish a mathematical theory for the crystallographic phase retrieval problem.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Frequency-Resolved Optical Gating Recovery via Smoothing Gradient

Frequency-resolved optical gating (FROG) is a popular technique for complete characterization of ultrashort laser pulses. The acquired data in FROG, called FROG trace, is the Fourier magnitude of the product of the unknown pulse with a time-shifted version of itself, for several different shifts. To estimate the pulse from the FROG trace, we propose an algorithm that minimizes a smoothed non-convex least-squares objective function. The method consists of two steps. First, we approximate the pulse by an iterative spectral algorithm. Then, the attained initialization is refined based upon a sequence of block stochastic gradient iterations. The algorithm is theoretically simple, numerically scalable, and easy-to-implement. Empirically, our approach outperforms the state-of-the-art when the FROG trace is incomplete, that is, when only few shifts are recorded. Simulations also suggest that the proposed algorithm exhibits similar computational cost compared to a state-of-the-art technique for both complete and incomplete data. In addition, we prove that in the vicinity of the true solution, the algorithm converges to a critical point. A Matlab implementation is publicly available at https://github.com/samuelpinilla/FROG.

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

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

Robust Recovery of Stream of Pulses using Convex Optimization

This paper considers the problem of recovering the delays and amplitudes of a weighted superposition of pulses. This problem is motivated by a variety of applications such as ultrasound and radar. We show that for univariate and bivariate stream of pulses, one can recover the delays and weights to any desired accuracy by solving a tractable convex optimization problem, provided that a pulse-dependent separation condition is satisfied. The main result of this paper states that the recovery is robust to additive noise or model mismatch.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Sparse Sampling in Helical Cone-Beam CT Perfect Reconstruction Algorithms

In the current paper we consider the Helical Cone Beam CT. This scanning method exposes the patient to large quantities of radiation and results in very large amounts of data being collected and stored. Both these facts are prime motivators for the development of an efficient, reduced rate, sampling pattern. We calculate bounds on the support in the frequency domain of the collected data and use these to suggest an efficient sampling pattern. A reduction of up to a factor of 2 in sampling rate is suggested. Indeed, we show that reconstruction quality is not affected by this reduction of sampling rates.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Least Squares Approach for Stable Phase Retrieval from Short-Time Fourier Transform Magnitude

We address the problem of recovering a signal (up to global phase) from its short-time Fourier transform (STFT) magnitude measurements. This problem arises in several applications, including optical imaging and speech processing. In this paper we suggest three interrelated algorithms. The first algorithm estimates the signal efficiently from noisy measurements by solving a simple least-squares (LS) problem. In contrast to previously proposed algorithms, the LS approach has stability guarantees and does not require any prior knowledge on the sought signal. However, the recovery is guaranteed under relatively strong restrictions on the STFT window. The second approach is guaranteed to recover a non-vanishing signal efficiently from noise-free measurements, under very moderate conditions on the STFT window. Finally, the third method estimates the signal robustly from noisy measurements by solving a semi-definite program (SDP). The proposed SDP algorithm contains an inherent trade-off between its robustness and the restrictions on the STFT windows that can be used.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Convex Optimization Approach for Stable Decomposition of Stream of Pulses

This paper deals with the problem of estimating the delays and amplitudes of a weighted superposition of pulses, called stream of pulses. This problem is motivated by a variety of applications, such as ultrasound and radar. This paper shows that the recovery error of a tractable convex optimization problem is proportional to the noise level. Additionally, the estimated delays are clustered around the true delays. This holds provided that the pulse meets a few mild localization properties and that a separation condition holds. If the amplitudes are known to be positive, the separation is unnecessary. In this case, the recovery error is proportional to the noise level and depends on the maximal number of delays within a resolution cell.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Recovery of Sparse Positive Signals on the Sphere from Low Resolution Measurements

This letter considers the problem of recovering a positive stream of Diracs on a sphere from its projection onto the space of low-degree spherical harmonics, namely, from its low-resolution version. We suggest recovering the Diracs via a tractable convex optimization problem. The resulting recovery error is proportional to the noise level and depends on the density of the Diracs. We validate the theory by numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stable Support Recovery of Stream of Pulses with Application to Ultrasound Imaging

This paper considers the problem of estimating the delays of a weighted superposition of pulses, called stream of pulses, in a noisy environment. We show that the delays can be estimated using a tractable convex optimization problem with a localization error proportional to the square root of the noise level. Furthermore, all false detections produced by the algorithm have small amplitudes. Numerical and in-vitro ultrasound experiments corroborate the theoretical results and demonstrate their applicability for the ultrasound imaging signal processing.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Super-resolution on the Sphere using Convex Optimization

This paper considers the problem of recovering an ensemble of Diracs on a sphere from its low resolution measurements. The Diracs can be located at any location on the sphere, not necessarily on a grid. We show that under a separation condition, one can recover the ensemble with high precision by a three-stage algorithm, which consists of solving a semi-definite program, root finding and least-square fitting. The algorithm's computation time depends solely on the number of measurements, and not on the required solution accuracy. We also show that in the special case of non-negative ensembles, a sparsity condition is sufficient for recovery. Furthermore, in the discrete setting, we estimate the recovery error in the presence of noise as a function of the noise level and the super-resolution factor.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Unified Convex Optimization Approach to Super-Resolution Based on Localized Kernels

The problem of resolving the fine details of a signal from its coarse scale measurements or, as it is commonly referred to in the literature, the super-resolution problem arises naturally in engineering and physics in a variety of settings. We suggest a unified convex optimization approach for super-resolution. The key is the construction of an interpolating polynomial based on localized kernels. We also show that the localized kernels act as the connecting thread to another wide-spread problem of stream of pulses.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Edge Preserving Multi-Modal Registration Based On Gradient Intensity Self-Similarity

Image registration is a challenging task in the world of medical imaging. Particularly, accurate edge registration plays a central role in a variety of clinical conditions. The Modality Independent Neighbourhood Descriptor (MIND) demonstrates state of the art alignment, based on the image self-similarity. However, this method appears to be less accurate regarding edge registration. In this work, we propose a new registration method, incorporating gradient intensity and MIND self-similarity metric. Experimental results show the superiority of this method in edge registration tasks, while preserving the original MIND performance for other image features and textures.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Exact recovery of Dirac ensembles from the projection onto spaces of spherical harmonics

In this work we consider the problem of recovering an ensemble of Diracs on the sphere from its projection onto spaces of spherical harmonics. We show that under an appropriate separation condition on the unknown locations of the Diracs, the ensemble can be recovered through Total Variation norm minimization. The proof of the uniqueness of the solution uses the method of `dual' interpolating polynomials and is based on [8], where the theory was developed for trigonometric polynomials. We also show that in the special case of non-negative ensembles, a sparsity condition is sufficient for exact recovery.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Exact recovery of non-uniform splines from the projection onto spaces of algebraic polynomials

In this work we consider the problem of recovering non-uniform splines from their projection onto spaces of algebraic polynomials. We show that under a certain Chebyshev-type separation condition on its knots, a spline whose inner-products with a polynomial basis and boundary conditions are known, can be recovered using Total Variation norm minimization. The proof of the uniqueness of the solution uses the method of `dual' interpolating polynomials and is based on \cite{SR}, where the theory was developed for trigonometric polynomials. We also show results for the multivariate case.

0 citations0 reviewsNo code linkedOpen access