Search

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. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating a cloud of points from numerous noisy observations of that cloud after unknown rotations and possibly reflections. This is an instance of the general problem of estimation under group action, originally inspired by applications in three-dimensional imaging and computer vision. We focus on a regime where the noise level is larger than the magnitude of the signal, so much so that the rotations cannot be estimated reliably. We propose a simple and efficient procedure based on invariant polynomials (effectively: the Gram matrices) to recover the signal, and we assess it against fundamental limits of the problem that we derive. We show our approach adapts to the noise level and is statistically optimal (up to constants) for both the low and high noise regimes. In studying the variance of our estimator, we encounter the question of the sensivity of a type of thin Cholesky factorization, for which we provide an improved bound which may be of independent interest. [ABSTRACT FROM AUTHOR]

Spectral methods that are based on eigenvectors and eigenvalues of discrete graph Laplacians, such as DiffusionMaps and Laplacian Eigenmaps, are often used for manifold learning and nonlinear dimensionality reduction. Itwas previously shown by Belkin&Niyogi (2007, Convergence of Laplacian eigenmaps, vol. 19. Proceedings of the 2006 Conference on Advances in Neural Information Processing Systems. The MIT Press, p. 129.) that the eigenvectors and eigenvalues of the graph Laplacian converge to the eigen-functions 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 article, 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. [ABSTRACT FROM AUTHOR]

Synchronization of rotations is the problem of estimating a set of rotations Ri ∈ SO(n), i=1⋯ N, based on noisy measurements of relative rotations Ri Rj⊤. 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 visualization tools for these bounds and interpretation in terms of random walks in both the anchored and anchor-free scenarios. Similar bounds previously established were limited to rotations in the plane and Gaussian-like noise. [ABSTRACT FROM AUTHOR]

The synchronization problem over the special orthogonal group SO(d) consists of estimating a set of unknown rotations from noisy measurements of a subset of their pairwise ratios . 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 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; secondly, 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 with existing methods. [ABSTRACT FROM PUBLISHER]

The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. In this paper, we extend the previous work and propose the 3D-As-Synchronized-As-Possible (3D-ASAP) algorithm, for the graph realization problem in ℝ3, given a sparse and noisy set of distance measurements. 3D-ASAP is a divide and conquer, non-incremental and non-iterative algorithm, which integrates local distance information into a global structure determination. Our approach starts with identifying, for every node, a subgraph of its 1-hop neighborhood graph, which can be accurately embedded in its own coordinate system. In the noise-free case, the computed coordinates of the sensors in each patch must agree with their global positioning up to some unknown rigid motion, that is, up to translation, rotation and possibly reflection. In other words, to every patch, there corresponds an element of the Euclidean group, Euc(3), of rigid transformations in ℝ3, and the goal was to estimate the group elements that will properly align all the patches in a globally consistent way. Furthermore, 3D-ASAP successfully incorporates information specific to the molecule problem in structural biology, in particular information on known substructures and their orientation. In addition, we also propose 3D-spectral-partitioning (SP)-ASAP, a faster version of 3D-ASAP, which uses a spectral partitioning algorithm as a pre-processing step for dividing the initial graph into smaller subgraphs. Our extensive numerical simulations show that 3D-ASAP and 3D-SP-ASAP are very robust to high levels of noise in the measured distances and to sparse connectivity in the measurement graph, and compare favorably with similar state-of-the-art localization algorithms. [ABSTRACT FROM PUBLISHER]