Search

We consider the finite alphabet phase retrieval problem: recovering a signal whose entries lie in a small alphabet of possible values from its Fourier magnitudes. This problem arises in the celebrated technology of X-ray crystallography to determine the atomic structure of biological molecules. Our main result states that for generic values of the alphabet, two signals have the same Fourier magnitudes if and only if several partitions have the same difference sets. Thus, the finite alphabet phase retrieval problem reduces to the combinatorial problem of determining a signal from those difference sets. Notably, this result holds true when one of the letters of the alphabet is zero, namely, for sparse signals with finite alphabet, which is the situation in X-ray crystallography. [ABSTRACT FROM AUTHOR]

The q -th order spectrum is a polynomial of degree q in the entries of a signal x ∈ C N , which is invariant under circular shifts of the signal. For q ≥ 3 , this polynomial determines the signal uniquely, up to a circular shift, and is called a high-order spectrum. The high-order spectra, and in particular the bispectrum (q = 3) and the trispectrum (q = 4), play a prominent role in various statistical signal processing and imaging applications, such as phase retrieval and single-particle reconstruction. However, the dimension of the q -th order spectrum is N q − 1 , far exceeding the dimension of x , leading to increased computational load and storage requirements. In this work, we show that it is unnecessary to store and process the full high-order spectra: a signal can be uniquely characterized up to symmetries, from only N + 1 linear measurements of its high-order spectra. The proof relies on tools from algebraic geometry and is corroborated by numerical experiments. [ABSTRACT FROM AUTHOR]

Phase retrieval refers to recovering a signal from its Fourier magnitude. This problem arises naturally in many scientific applications, such as ultra-short laser pulse characterization and diffraction imaging. Unfortunately, phase retrieval is ill-posed for almost all one-dimensional signals. In order to characterize a laser pulse and overcome the ill-posedness, it is common to use a technique called Frequency-Resolved Optical Gating (FROG). In FROG, the measured data, referred to as FROG trace, is the Fourier magnitude of the product of the underlying signal with several translated versions of itself. The FROG trace results in a system of phaseless quartic Fourier measurements. In this paper, we prove that it suffices to consider only three translations of the signal to determine almost all bandlimited signals, up to trivial ambiguities. In practice, one usually also has access to the signal's Fourier magnitude. We show that in this case only two translations suffice. Our results significantly improve upon earlier work. [ABSTRACT FROM AUTHOR]

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

Abstract: 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 Candès and Fernandez-Granda (2014), where the theory was developed for trigonometric polynomials. We also show results for the multivariate case. [Copyright &y& Elsevier]