Search

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., Comment: 34 pages, 9 figures, for code see https://github.com/idohadi/CompactificationImageProcessing

Rank-one update of the spectrum of a matrix is a fundamental problem in classical perturbation theory. In this paper, we consider its variant where only part of the spectrum is known. We address this variant using an efficient scheme for updating the known eigenpairs with guaranteed error bounds. Then, we apply our scheme to the extension of the top eigenvectors of the graph Laplacian to a new data sample. In particular, we model this extension as a perturbation problem and show how to solve it using our rank-one updating scheme. We provide a theoretical analysis of this extension method, and back it up with numerical results that illustrate its advantages.

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.

Multiscale transforms have become a key ingredient in many data processing tasks. With technological development we observe a growing demand for methods to cope with nonlinear data structures such as manifold values. In this paper we propose a multiscale approach for analyzing manifold-valued data using a pyramid transform. The transform uses a unique class of downsampling operators that enable a noninterpolating subdivision schemes as upsampling operators. We describe this construction in detail and present its analytical properties, including stability and coefficient decay. Next, we numerically demonstrate the results and show the application of our method to denoising and anomaly detection.

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.

We target the problem of estimating the center of mass of objects in noisy two-dimensional images. We assume that the noise dominates the image, and thus many standard approaches are vulnerable to estimation errors, e.g., the direct computation of the center of mass and the geometric median which is a robust alternative to the center of mass. In this paper, we define a novel surrogate function to the center of mass. We present a mathematical and numerical analysis of our method and show that it outperforms existing methods for estimating the center of mass of an object in various realistic scenarios. As a case study, we apply our centering method to data from single-particle cryo-electron microscopy (cryo-EM), where the goal is to reconstruct the three-dimensional structure of macromolecules. We show how to apply our approach for a better translational alignment of molecule images picked from experimental data. In this way, we facilitate the succeeding steps of reconstruction and streamline the entire cryo-EM pipeline, saving computational time and supporting resolution enhancement.

We study super-resolution multi-reference alignment, the problem of estimating a signal from many circularly shifted, down-sampled and noisy observations. We focus on the low SNR regime, and show that a signal in ${\mathbb{R}}^M$ is uniquely determined when the number $L$ of samples per observation is of the order of the square root of the signal’s length ($L=O(\sqrt{M})$). Phrased more informally, one can square the resolution. This result holds if the number of observations is proportional to $1/\textrm{SNR}^3$. In contrast, with fewer observations recovery is impossible even when the observations are not down-sampled ($L=M$). The analysis combines tools from statistical signal processing and invariant theory. We design an expectation-maximization algorithm and demonstrate that it can super-resolve the signal in challenging SNR regimes.

Subdivision schemes have become an important tool for approximation of manifold-valued functions. In this paper, we describe a construction of manifold-valued subdivision schemes for geodesically complete manifolds. Our construction is based upon the adaptation of linear subdivision schemes using the notion of repeated binary averaging, where as a repeated binary average we propose to use the geodesic inductive mean. We derive conditions on the adapted schemes which guarantee convergence from any initial manifold-valued sequence. The definition and analysis of convergence are intrinsic to the manifold. The adaptation technique and the convergence analysis are demonstrated by several important examples of subdivision schemes. Two numerical examples visualizing manifold-valued curves generated by such schemes are given together with a link to the code that generated them.

A rational approximation (that is, approximation by a ratio of two polynomials) is a flexible alternative to polynomial approximation. In particular, rational functions exhibit accurate estimations to nonsmooth and non-Lipschitz functions, where polynomial approximations are not efficient. We prove that the optimisation problems appearing in the best uniform rational approximation and its generalisation to a ratio of linear combinations of basis functions are quasiconvex even when the basis functions are not restricted to monomials. Then we show how this fact can be used in the development of computational methods. This paper presents a theoretical study of the arising optimisation problems and provides results of several numerical experiments. We apply our approximation as a preprocessing step to deep learning classifiers and demonstrate that the classification accuracy is significantly improved compared to the classification of the raw signals.

A refinement of manifold data is a computational process, which produces a denser set of discrete data from a given one. Such refinements are closely related to multiresolution representations of manifold data by pyramid transforms, and approximation of manifold-valued functions by repeated refinements schemes. Most refinement methods compute each refined element separately, independently of the computations of the other elements. Here we propose a global method which computes all the refined elements simultaneously, using geodesic averages. We analyse repeated refinements schemes based on this global approach, and derive conditions guaranteeing strong convergence., Comment: arXiv admin note: text overlap with arXiv:1407.8361

We present a method for improving a Non Local Means operator by computing its low-rank approximation. The low-rank operator is constructed by applying a filter to the spectrum of the original Non Local Means operator. This results in an operator which is less sensitive to noise while preserving important properties of the original operator. The method is efficiently implemented based on Chebyshev polynomials and is demonstrated on the application of natural images denoising. For this application, we provide a comprehensive comparison of our method with leading denoising methods.

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., 41 pages. v2: additional numerical experiments, appendices edited, other updates

We construct univariate subdivision schemes for noisy data.The constructed schemes are based on fitting local least squares polynomials.We study the convergence, smoothness, and basic limit functions of these schemes.A statistical model is analyzed and validated by several numerical examples.We present applications of the schemes for data sampled from curves and surfaces. We introduce and analyze univariate, linear, and stationary subdivision schemes for refining noisy data by fitting local least squares polynomials. This is the first attempt to design subdivision schemes for noisy data. We present primal schemes, with refinement rules based on locally fitting linear polynomials to the data, and study their convergence, smoothness, and basic limit functions. Then, we provide several numerical experiments that demonstrate the limit functions generated by these schemes from initial noisy data. The application of an advanced local linear regression method to the same data shows that the methods are comparable. In addition, several extensions and variants are discussed and their performance is illustrated by examples. We conclude by applying the schemes to noisy geometric data.

We introduce a framework for representing functions dened on high-dimensional data. In this framework, we propose to use the eigenvectors of the graph Laplacian to construct a multiresolution analysis on the data. We assume the dataset to have an associated hierarchical tree partition, together with a function that measures the similarity between pairs of points in the dataset. The construction results in a one parameter family of orthonormal bases, which includes both the Haar basis as well as the eigenvectors of the graph Laplacian, as its two extremes. We describe a fast discrete transform for the expansion in any of the bases in this family, and estimate the decay rate of the expansion coecients. We also

In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal’s orbit by accessing multiple independent observations. Of particular interest is the sample complexity, i.e., the number of observations/samples needed in terms of the signal-to-noise ratio (SNR) (the signal energy divided by the noise variance) in order to drive the mean-square error to zero. Previous work showed that if the translations are drawn from the uniform distribution, then, in the low SNR regime, the sample complexity of the problem scales as $\omega (1/ \mathrm {SNR}^{3})$ . In this paper, using a generalization of the Chapman–Robbins bound for orbits and expansions of the $\chi ^{2}$ divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as $\omega (1/ \mathrm {SNR}^{2})$ . This rate is achieved by a simple spectral algorithm. We propose two additional algorithms based on non-convex optimization and expectation–maximization. We also draw a connection between the multireference alignment problem and the spiked covariance model.

The article derives the optimal allocation of projects when two firms are engaged in a strategic alliance with an asymmetric liquidation option. Our model solves for the optimal allocation when a manager can liquidate the internally managed project and reallocate the funds to the alliance but has no control over the alliance's assets. We find the somewhat surprising result, which in some cases the probabilities of success of the two projects are irrelevant to the initial allocation of the projects. Finally, we parametrize our model and demonstrate graphically how the choice of projects vary across the various scenarios.

Group contraction is an algebraic map that relates two classes of Lie groups by a limiting process. We utilize this notion for the compactification of the class of Cartan motion groups. The compactification process is then applied to reduce a non-compact synchronization problem to a problem where the solution can be obtained by means of a unitary, faithful representation. We describe this method of synchronization via contraction in detail and analyze several important aspects of this application. One important special case of Cartan motion groups is the group of rigid motions, also called the special Euclidean group. We thoroughly discuss the synchronization over this group and show numerically the advantages of our approach compared to some current state-of-the-art synchronization methods on both synthetic and real data.

The class of symmetric positive definite matrices is an important class both in theory and application. Although this class is well studied, little is known about how to efficiently interpolate such data within the class. We extend the 4-point interpolatory subdivision scheme, as a method of interpolation, to data consisting of symmetric positive definite matrices. This extension is based on an explicit formula for calculating a binary “geodetic average”. Our method generates a smooth curve of matrices, which retain many important properties of the interpolated matrices. Furthermore, the scheme is robust and easy to implement.

The paper presents a bivariate subdivision scheme interpolating data consisting of univariate functions along equidistant parallel lines by repeated refinements. This method can be applied to the construction of a surface passing through a given set of parametric curves. Following the methodology of polysplines and tension surfaces, we define a local interpolator of four consecutive univariate functions, from which we sample a univariate function at the mid-point. This refinement step is the basis to an extension of the 4-point subdivision scheme to our setting. The bivariate subdivision scheme can be reduced to a countable number of univariate, interpolatory, non-stationary subdivision schemes. Properties of the generated interpolant are derived, such as continuity, smoothness and approximation order.

Over 75% of obese subjects fail to maintain their weight following weight loss interventions. We aimed to identify phenotypic and genetic markers associated with weight maintenance/regain following a dietary intervention.In the 2-year Dietary Intervention Randomized Controlled Trial, we assessed potential predictors for weight changes during the 'weight loss phase' (0-6 months) and the 'weight maintenance/regain phase' (7-24 months). Genetic variation between study participants was studied using single-nucleotide polymorphisms in the leptin gene (LEP).Mean weight reduction was -5.5% after 6 months, with a mean weight regain of 1.2% of baseline weight during the subsequent 7-24 months. In a multivariate regression model, higher baseline high-molecular-weight adiponectin was the only biomarker predictor of greater success in 0- to 6-month weight loss (β = -0.222, P-value = 0.044). In a multivariate regression model adjusted for 6-month changes in weight and various biomarkers, 6-month plasma leptin reduction exhibited the strongest positive association with 6-month weight loss (β = 0.505, P-value0.001). Conversely, 6-month plasma leptin reduction independently predicted weight regain during the following 18 months (β = -0.131, P-value0.013). Weight regain was higher among participants who had a greater (top tertiles) 6-month decrease in both weight and leptin (+3.4% (95% confidence interval 2.1-4.8)) as compared with those in the lowest combined tertiles (+0.2% (95% confidence interval -1.1 to 1.4)); P-value0.001. Weight regain was further significantly and independently associated with genetic variations in LEP (P = 0.006 for both rs4731426 and rs2071045). Adding genetic data to the phenotypic multivariate model increased its predictive value for weight regain by 34%.Although greater reduction in leptin concentrations during the initial phase of a dietary intervention is associated with greater weight loss in the short term, plasma leptin reduction, combined with the degree of initial weight loss and with genetic variations in the LEP gene, constitutes a significant predictor of subsequent long-term weight regain.

Macrophage scavenger receptor 1 (MSR1) mediates the uptake of modified low density lipoprotein (LDL)-cholesterol. The significance of MSR1 in atherosclerosis development in animal models is uncertain. In this study we sought to determine the significance of MSR1 polymorphisms in its encoding gene in susceptibility to atherosclerosis.We genotyped three polymorphic sites in the MSR1 gene including a 3-bp "TTA" insertion-deletion in intron 7 (rs3036811, Indel 7), an intron 5 SNP (rs33959637, IVS5-59), and a missense coding single nucleotide polymorphism (SNP) in exon 6 (rs3747531, P275A) in 136 nondiabetic Ashkenazi men under age 55 years (mean = 47.3 +/- 4.8 years) undergoing coronary angiography. Assessment of coronary disease was done by the number of segments with stenosis greater than 20% (coronary artery narrowing greater than 20% [CAGE20%]), greater than 50% (CAGE50%), and total number of diseased vessels. Linear regression modeling was used to define associations between atherosclerotic burden and MSR1 SNPs and haplotypes.Significant associations were noted between IVS5-59 and number of diseased vessels (p = 0.009) and CAGE20% (p = 0.017), which remained significant upon controlling for age, cholesterol level, hypertension, and smoking.This study demonstrates an association between MSR1 polymorphisms and atherosclerosis, suggesting that atherosclerotic risk associated with classic risk factors may be modified by MSR1 polymorphisms. These findings point to a significant role of MSR1 in atherosclerosis.

Purpose To explore the association between birth weight in offspring, a marker of the intrauterine environment, and mortality in their mothers, taking into account maternal pre-pregnancy characteristics, including maternal body mass index (BMI), smoking, and socioeconomic status. Distinguishing the effects of offspring's birth weight and pre-pregnancy characteristics on maternal outcome may provide clues regarding mechanisms underlying the association between birth weight and maternal mortality. Methods We studied long-term total mortality (average follow-up period, 29.1 years) in a population-based cohort of 13,185 mothers, aged 15 to 48 years at their offspring's birth, who delivered in West Jerusalem during 1974 through 1976. Results Univariate and multivariate Cox-proportional hazard models used to estimate the hazard of overall mortality among mothers indicated a nonlinear relationship with birth weight of offspring when introduced into the models as a continuous variable, and a linear positive association with maternal pre-pregnancy BMI. Inclusion of maternal BMI and other pre-pregnancy characteristics in the model did not alter the association between offspring's birth weight and mothers’ all-cause mortality. When birth weight was introduced as a categorical variable, higher mortality was observed among mothers who gave birth to babies with birth weight less than 2500 g (hazard ratio [HR] = 1.90; 95% confidence interval [95%CI], 1.23–2.94) as compared to mothers whose offspring had birth weight between 3000 and 3499 g. The HR for mothers who gave birth to babies with birth weight 4000 g or more was 1.30 (95%CI, 0.88–1.91). Conclusions Independent of pre-pregnancy maternal BMI and other characteristics, birth weight of offspring was associated with mortality in their mothers, suggesting that intrauterine metabolic events reflected by birth weight and not explained by maternal obesity, smoking, and socioeconomic status have remote consequences for maternal health. These findings underline the need to explore specific genetic and/or environmental mechanisms that account for these associations.

Although the association between birth weight and childhood leukemia is well described, the relation between a child's birth weight and parental risk of leukemia is unknown. We linked data from the Jerusalem Perinatal Study to the Israel Cancer Registry to ascertain the incidence of leukemia in mothers and fathers in relation to their offspring's birth weight. Birth weight ≥4500 g in any of the offspring was associated with a >3-fold risk of leukemia in mothers, but not fathers. Potential mechanisms include shared exposures of high birth weight infants and their mothers, possibly to radiation or growth factors, or genetic pathways leading to both high birth weight and leukemia.

The long-term risks of in vitro fertilization (IVF) treatment remain unclear. This study was designed to determine breast cancer risk factors in women who underwent IVF, and to establish characteristics of these tumors. Records of 7,162 consecutive women who underwent IVF at a single center between 1984 and 2002 were linked with the Israel Cancer Registry to identify women who developed breast cancer. IVF-related parameters were compared between 28 breast cancer patients who had undergone IVF (IVF BC) and for whom complete IVF data were available with 140 women who underwent IVF and did not develop breast cancer (IVF non-BC). Tumor parameters were compared between 38 patients who developed breast cancer after IVF and 114 age-matched breast cancer patients who did not undergo IVF (non-IVF BC). Age over 30 at the time of first IVF treatment, even after controlling for age at first birth, was the only parameter significantly associated with increased breast cancer risk (RR = 1.24, p = 0.02, 95% CI = 1.03-1.48). There were no differences between IVF-BC and IVF non-BC patients in all other IVF-related parameters. The only statistically significant difference in tumors developing in IVF-BC patients compared with non-IVF BC patients was in grade distribution, particularly for grade II tumors. However, the significance of such a difference is unclear. Women who start IVF after the age of 30 appear to be at increased risk of developing breast cancer. The characteristics of breast tumors in women who underwent IVF are no different than in patients without previous exposure to IVF.

Fabry disease, an X-linked inborn error of metabolism, is characterized by multi-organ involvement including cardiac signs of left ventricular hypertrophy and abnormal intima-medial (IMT) thickening of arteries, progressive renal failure, neurological involvement, and more. The vitamin D receptor (VDR) and an enzyme producing vitamin D3 result in an autocrine loop with direct effects on blood vessels. The purpose of this study is to assess VDR polymorphisms (BsmI, FokI, ApaI, and TaqI) relative to clinically important disease parameters using a disease-specific severity score (MSSI) and haplotype analysis. There were statistically significant differences between females (43% of 74 patients) and males in MSSI total scores, and in general and neurologic sub-scores. There appears to be a protective effect of the TaqI tt genotype so that there were significantly lower scores in clinical categories between those with the tt genotype versus those with the TT genotype. Multivariate models of haplotypes with MSSI scores reveal that T-A-f-B and t-a-F-b haplotypes of the VDR gene polymorphisms are significantly associated with variation in the Fabry phenotype. Despite the limitations of using the MSSI score as a clinical correlate, these results are provocative and further studies in larger cohorts with more males are recommended.

Fabry disease is a multisystem disorder with phenotypic heterogeneity only partially explained by genotype. Elevated interleukin-6 (IL-6) plasma levels and C-reactive protein (CRP) serum levels are associated with increased risk and worse outcome of ischaemic events, a serious prognostic sign in Fabry disease.56 patients (34 hemizygous males, 22 females; 5 children) were studied. A promoter polymorphism -174GC of the IL-6 gene associated with serum IL-6 levels was compared with the Mainz Severity Score Index (MSSI) in patients with Fabry disease. CRP levels and polymorphism 1059 GC were evaluated as markers of inflammation to ascertain the possibility of an inflammatory mechanism of IL-6. Nonparametric ANOVA, Fisher's exact, Bonferroni, and Hardy-Weinberg (HW) statistics were used.Mean age of adults = 42 (range 26-58) years; 29 patients received enzyme therapy (ERT). Mean total MSSI = 26.7 (range 14.2-39.2) points, i.e. moderate disease, but females were lower (total 23.4 +/- 12.6 vs 32.2 +/- 13.6). Controls but not patients were in HW equilibrium. Significant correlation existed between all sub-scores of the MSSI and IL-6 genotypes in females but only with three MSSI sub-scores for males. The IL-6 C/C genotype was significantly correlated with the neurological, general and total MSSI sub-scores, generally twofold higher. There were no statistically significant correlations with CRP levels/polymorphisms and MSSI sub-scores nor with IL-6 polymorphisms. CRP levels decreased after ERT in patients with IL-6 G/G or G/C genotypes but increased in patients with C/C (p = 0.003).The prevalence of the IL-6 C allele significantly influences MSSI, i.e. clinical severity, especially in females. This is unrelated to IL-6 as a pro-inflammatory marker as demonstrated by lack of correlations with CRP levels and genotypes. IL-6 -174 polymorphic C allele may be a prognostic marker in Fabry disease, especially in females.

The paper revisits the classical problem of evaluating f ( A ) for a real function f and a matrix A with real spectrum. The evaluation is based on expanding f in Chebyshev polynomials, and the focus of the paper is to study the convergence rates of these expansions. In particular, we derive bounds on the convergence rates which reveal the relation between the smoothness of f and the diagonalizability of the matrix A. We present several numerical examples to illustrate our analysis.

Background. Patients receiving chemotherapy for hematological malignancies are at high risk for febrile neutropenia (FN). Garlic extracts (GEs) are natural food substances showing antimicrobial effects in vivo. Objectives. We explored whether adding GE may be efficacious in reducing the risk or severity of infections. Design. This was a placebo-controlled double-blind randomized study. Results. Of 95 patients randomized to receive GE or placebo following chemotherapy, a febrile episode was documented in 50% of patients receiving GE and 63.3% receiving placebo ( P = .89). There was a higher risk of developing a third and fourth febrile episode in the GE group ( P = .01). However, among those at a lower risk for FN, those receiving GE developed fewer FN episodes ( P = .075), especially those with severe neutropenia ( P = .05). Major adverse events were distributed equally, but nonadherence was more common in the GE than in the placebo group: 19.5% versus 4%, respectively ( P = .05). Conclusions. GE was safe and did not reduce FN risk in the entire cohort, but yet appeared to exert a protective effect in the lower-risk subgroup. We do not recommend the use of GE for FN prevention in higher-risk patients. A larger-scale clinical trial for the lower-risk subgroup of patients is advocated. (This trial was registered at www.clinicaltrials.gov as NCT00247039.)