In this paper, we generalize finite depth wavelet scattering transforms, which we formulate as norms of a cascade of continuous wavelet transforms (or dyadic wavelet transforms) and contractive nonlinearities. We then provide norms for these operators, prove that these operators are well-defined, and are Lipschitz continuous to the action of diffeomorphisms in specific cases. Lastly, we extend our results to formulate an operator invariant to the action of rotations and an operator that is equivariant to the action of rotations of .

Single particle cryo-electron microscopy (EM) is a method for determining the 3-D structure of macromolecules from many noisy 2-D projection images of individual macromolecules whose orientations and positions are random and unknown. The problem of orientation assignment for the images motivated work on general multireference alignment. The recently introduced non-unique games framework provides a representation theoretic approach to alignment over compact groups, and offers a convex relaxation which is formulated as semidefinite programs with certificates of global optimality under certain circumstances. One of the great opportunities in cryo-EM is studying heterogeneous samples, containing two or more distinct classes or conformations of molecules. Taking advantage of this opportunity presents an algorithmic challenge: determining both the class and orientation of each particle. We generalize multireference alignment to a problem of alignment and classification, and 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.

The Fourier-domain Douglas-Rachford (FDR) algorithm is analyzed for phase retrieval with a single random mask. Since the uniqueness of phase retrieval solution requires more than a single oversampled coded diffraction pattern, the extra information is imposed in either of the following forms: 1) the sector condition on the object; 2) another oversampled diffraction pattern, coded or uncoded. For both settings, the uniqueness of projected fixed point is proved and for setting 2) the local, geometric convergence is derived with a rate given by a spectral gap condition. Numerical experiments demonstrate global, power-law convergence of FDR from arbitrary initialization for both settings as well as for 3 or more coded diffraction patterns oversampling. In practice, the geometric convergence can be recovered from the power-law regime by a simple projection trick, resulting in highly accurate reconstruction from generic initialization.

This paper explores robust recovery of a superposition of distinct complex exponential functions with or without damping factors from a few random Gaussian projections. We assume that the signal of interest is of 2 - 1 dimensions and < 2 - 1. This framework covers a large class of signals arising from real applications in biology, automation, imaging science, etc. To reconstruct such a signal, our algorithm is to seek a low-rank Hankel matrix of the signal by minimizing its nuclear norm subject to the consistency on the sampled data. Our theoretical results show that a robust recovery is possible as long as the number of projections exceeds (ln). No incoherence or separation condition is required in our proof. Our method can be applied to spectral compressed sensing where the signal of interest is a superposition of complex sinusoids. Compared to existing results, our result here does not need any separation condition on the frequencies, while achieving better or comparable bounds on the number of measurements. Furthermore, our method provides theoretical guidance on how many samples are required in the state-of-the-art non-uniform sampling in NMR spectroscopy. The performance of our algorithm is further demonstrated by numerical experiments.

Gabor frames can advantageously be redefined using the Heisenberg-Weyl operators familiar from harmonic analysis and quantum mechanics. Not only does this redefinition allow us to recover in a very simple way known results of symplectic covariance, but it immediately leads to the consideration of a general deformation scheme by Hamiltonian isotopies ( arbitrary paths of non-linear symplectic mappings passing through the identity). We will study in some detail an associated weak notion of Hamiltonian deformation of Gabor frames, using ideas from semiclassical physics involving coherent states and Gaussian approximations. We will thereafter discuss possible applications and extensions of our method, which can be viewed - as the title suggests - as the very first steps towards a general deformation theory for Gabor frames.

The local histogram transform of an image is a data cube that consists of the histograms of the pixel values that lie within a fixed neighborhood of any given pixel location. Such transforms are useful in image processing applications such as classification and segmentation, especially when dealing with textures that can be distinguished by the distributions of their pixel intensities and colors. We, in particular, use them to identify and delineate biological tissues found in histology images obtained via digital microscopy. In this paper, we introduce a mathematical formalism that rigorously justifies the use of local histograms for such purposes. We begin by discussing how local histograms can be computed as systems of convolutions. We then introduce probabilistic image models that can emulate textures one routinely encounters in histology images. These models are rooted in the concept of image occlusion. A simple model may, for example, generate textures by randomly speckling opaque blobs of one color on top of blobs of another. Under certain conditions, we show that, on average, the local histograms of such model-generated-textures are convex combinations of more basic distributions. We further provide several methods for creating models that meet these conditions; the textures generated by some of these models resemble those found in histology images. Taken together, these results suggest that histology textures can be analyzed by decomposing their local histograms into more basic components. We conclude with a proof-of-concept segmentation-and-classification algorithm based on these ideas, supported by numerical experimentation.

In this paper we provide rigorous proof for the convergence of an iterative voting-based image segmentation algorithm called Active Masks. Active Masks (AM) was proposed to solve the challenging task of delineating punctate patterns of cells from fluorescence microscope images. Each iteration of AM consists of a linear convolution composed with a nonlinear thresholding; what makes this process special in our case is the presence of additive terms whose role is to "skew" the voting when prior information is available. In real-world implementation, the AM algorithm always converges to a fixed point. We study the behavior of AM rigorously and present a proof of this convergence. The key idea is to formulate AM as a generalized (parallel) majority cellular automaton, adapting proof techniques from discrete dynamical systems.

One of the main objectives in the analysis of a high dimensional large data set is to learn its geometric and topological structure. Even though the data itself is parameterized as a point cloud in a high dimensional ambient space ℝ(p), the correlation between parameters often suggests the "manifold assumption" that the data points are distributed on (or near) a low dimensional Riemannian manifold ℳ(d) embedded in ℝ(p), with d ≪ p. We introduce an algorithm that determines the orientability of the intrinsic manifold given a sufficiently large number of sampled data points. If the manifold is orientable, then our algorithm also provides an alternative procedure for computing the eigenfunctions of the Laplacian that are important in the diffusion map framework for reducing the dimensionality of the data. If the manifold is non-orientable, then we provide a modified diffusion mapping of its orientable double covering.

The angular synchronization problem is to obtain an accurate estimation (up to a constant additive phase) for a set of unknown angles θ(1), …, θ(n) from m noisy measurements of their offsets θ(i) - θ(j) mod 2π. Of particular interest is angle recovery in the presence of many outlier measurements that are uniformly distributed in [0, 2π) and carry no information on the true offsets. We introduce an efficient recovery algorithm for the unknown angles from the top eigenvector of a specially designed Hermitian matrix. The eigenvector method is extremely stable and succeeds even when the number of outliers is exceedingly large. For example, we successfully estimate n = 400 angles from a full set of m=(4002) offset measurements of which 90% are outliers in less than a second on a commercial laptop. The performance of the method is analyzed using random matrix theory and information theory. We discuss the relation of the synchronization problem to the combinatorial optimization problem Max-2-Lin mod L and present a semidefinite relaxation for angle recovery, drawing similarities with the Goemans-Williamson algorithm for finding the maximum cut in a weighted graph. We present extensions of the eigenvector method to other synchronization problems that involve different group structures and their applications, such as the time synchronization problem in distributed networks and the surface reconstruction problems in computer vision and optics.

Recovering the three-dimensional structure of molecules is important for understanding their functionality. We describe a spectral graph algorithm for reconstructing the three-dimensional structure of molecules from their cryo-electron microscopy images taken at random unknown orientations.We first identify a one-to-one correspondence between radial lines in three-dimensional Fourier space of the molecule and points on the unit sphere. The problem is then reduced to determining the coordinates of points on the sphere given a subset of their pairwise geodesic distances. To recover those coordinates, we exploit the special geometry of the problem, as rendered by the Fourier projection-slice theorem, to construct a weighted graph whose vertices are the radial Fourier lines and whose edges are linked using the common line property. The graph organizes the radial lines on the sphere in a global manner that reveals the acquisition direction of each image. This organization is derived from a global computation of a few eigenvectors of the graph's sparse adjacency matrix. Once the directions are obtained, the molecule can be reconstructed using classical tomography methods.The presented algorithm is direct (as opposed to iterative refinement schemes), does not require any prior model for the reconstructed object, and is shown to have favorable computational and numerical properties. Moreover, the algorithm does not impose any assumption on the distribution of the projection orientations. Physically, this means that the algorithm is applicable to molecules that have unknown spatial preference.

We present a fast method for evaluating expressions of the form where are real numbers, and are points in a compact interval of . This expression can be viewed as representing the electrostatic potential generated by charges on a line in . While fast algorithms for computing the electrostatic potential of general distributions of charges in exist, in a number of situations in computational physics it is useful to have a simple and extremely fast method for evaluating the potential of charges on a line; we present such a method in this paper, and report numerical results for several examples.