Phase Retrieval for Sparse Signals: Uniqueness Conditions

In a variety of fields, in particular those involving imaging and optics, we often measure signals whose phase is missing or has been irremediably distorted. Phase retrieval attempts the recovery of the phase information of a signal from the magnitude of its Fourier transform to enable the reconstruction of the original signal. A fundamental question then is: "Under which conditions can we uniquely recover the signal of interest from its measured magnitudes?" In this paper, we assume the measured signal to be sparse. This is a natural assumption in many applications, such as X-ray crystallography, speckle imaging and blind channel estimation. In this work, we derive a sufficient condition for the uniqueness of the solution of the phase retrieval (PR) problem for both discrete and continuous domains, and for one and multi-dimensional domains. More precisely, we show that there is a strong connection between PR and the turnpike problem, a classic combinatorial problem. We also prove that the existence of collisions in the autocorrelation function of the signal may preclude the uniqueness of the solution of PR. Then, assuming the absence of collisions, we prove that the solution is almost surely unique on 1-dimensional domains. Finally, we extend this result to multi-dimensional signals by solving a set of 1-dimensional problems. We show that the solution of the multi-dimensional problem is unique when the autocorrelation function has no collisions, significantly improving upon a previously known result.

Super Resolution Phase Retrieval for Sparse Signals

Gilles Baechler, Amina Chebira, Miranda Krekovic, Juri Ranieri, Martin Vetterli

In a variety of fields, in particular those involving imaging and optics, we often measure signals whose phase is missing or has been irremediably distorted. Phase retrieval attempts to recover the phase information of a signal from the magnitude of its Fourier transform to enable the reconstruction of the original signal. Solving the phase retrieval problem is equivalent to recovering a signal from its auto-correlation function. In this paper, we assume the original signal to be sparse; this is a natural assumption in many applications, such as X-ray crystallography, speckle imaging and blind channel estimation. We propose an algorithm that resolves the phase retrieval problem in three stages: i) we leverage the finite rate of innovation sampling theory to super-resolve the auto-correlation function from a limited number of samples, ii) we design a greedy algorithm that identifies the locations of a sparse solution given the super-resolved auto-correlation function, iii) we recover the amplitudes of the atoms given their locations and the measured auto-correlation function. Unlike traditional approaches that recover a discrete approximation of the underlying signal, our algorithm estimates the signal on a continuous domain, which makes it the first of its kind. Along with the algorithm, we derive its performance bound with a theoretical analysis and propose a set of enhancements to improve its computational complexity and noise resilience. Finally, we demonstrate the benefits of the proposed method via a comparison against Charge Flipping, a notable algorithm in crystallography.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2018

Sampling the Multiple Facets of Light

Gilles Baechler

The theme of this thesis revolves around three important manifestations of light, namely its corpuscular, wave and electromagnetic nature. Our goal is to exploit these principles to analyze, design and build imaging modalities by developing new signal processing and algorithmic tools, based in particular on sampling and sparsity concepts. First, we introduce a new sampling scheme called variable pulse width, which is based on the finite rate of innovation (FRI) sampling paradigm. This new framework enables to sample and perfectly reconstruct weighted sums of Lorentzians; perfect reconstruction from sampled signals is guaranteed by a set of theorems. Second, we turn to the context of light and study its reflection, which is based on the corpuscular model of light. More precisely, we propose to use our FRI-based model to represent bidirectional reflectance distribution functions. We develop dedicated light domes to acquire reflectance functions and use the measurements obtained to demonstrate the usefulness and versatility of our model. In particular, we concentrate on the representation of specularities, which are sharp and bright components generated by the direct reflection of light on surfaces. Third, we explore the wave nature of light through Lippmann photography, a century-old photography technique that acquires the entire spectrum of visible light. This fascinating process captures interferences patterns created by the exposed scene inside the depth of a photosensitive plate. By illuminating the developed plate with a neutral light source, the reflected spectrum corresponds to that of the exposed scene. We propose a mathematical model which precisely explains the technique and demonstrate that the spectrum reproduction suffers from a number of distortions due to the finite depth of the plate and the choice of reflector. In addition to describing these artifacts, we describe an algorithm to invert them, essentially recovering the original spectrum of the exposed scene. Next, the wave nature of light is further generalized to the electromagnetic theory, which we invoke to leverage the concept of polarization of light. We also return to the topic of the representation of reflectance functions and focus this time on the separation of the specular component from the other reflections. We exploit the fact that the polarization of light is preserved in specular reflections and investigate camera designs with polarizing micro-filters with different orientations placed just in front of the camera sensor; the different polarizations of the filters create a mosaic image, from which we propose to extract the specular component. We apply our demosaicing method to several scenes and additionally demonstrate that our approach improves photometric stereo. Finally, we delve into the problem of retrieving the phase information of a sparse signal from the magnitude of its Fourier transform. We propose an algorithm that resolves the phase retrieval problem for sparse signals in three stages. Unlike traditional approaches that recover a discrete approximation of the underlying signal, our algorithm estimates the signal on a continuous domain, which makes it the first of its kind. The concluding chapter outlines several avenues for future research, like new optical devices such as displays and digital cameras, inspired by the topic of Lippmann photography.

EPFL2018

Sensing the real world

Juri Ranieri

A sensor is a device that detects or measures a physical property and records, indicates, or otherwise responds to it. In other words, a sensor allows us to interact with the surrounding environment, by measuring qualitatively or quantitatively a given phenomena. Biological evolution provided every living entity with a set of sensors to ease the survival to daily challenges. In addition to the biological sensors, humans developed and designed “artificial” sensors with the aim of improving our capacity of sensing the real world. Today, thanks to technological developments, sensors are ubiquitous and thus, we measure an exponentially growing amount of data. Here is the challenge—how do we process and use this data? Nowadays, it is common to design real-world sensing architectures that use the measured data to estimate certain parameters of the measured physical field. This type of problems are known in mathematics as inverse problems and finding their solution is challenging. In fact, we estimate a set of parameters of a physical field with possibly infinite degrees of freedom with only a few measurements, that are most likely corrupted by noise. Therefore, we would like to design algorithms to solve the given inverse problem, while ensuring the existence of the solution, its uniqueness and its robustness to the measurement noise. In this thesis, we tackle different inverse problems, all inspired by real-world applications. First, we propose a new regularization technique for linear inverse problems based on the sensor placement optimization of the sensor network collecting the data. We propose Frame- Sense, a greedy algorithm inspired by frame theory that finds a near-optimal sensor placement with respect to the reconstruction error of the inverse problem solution in polynomial time. We substantiate our theoretical findings with numerical simulations showing that our method improves the state of the art. In particular, we show significant improvements on two realworld applications: the thermal monitoring of many-core processors and the adaptive sampling scheduling of environmental sensor networks. Second, we introduce the dual of the sensor placement problem, namely the source placement problem. In this case, instead of regularizing the inverse problem, we enable a precise control of the physical field by means of a forward problem. For this problem, we propose a near-optimal algorithm for the noiseless case, that is when we know exactly the current state of the physical field. Third, we consider a family of physical phenomena that can be modeled by means of graphs, where the nodes represent a set of entities and the edges model the transmission delay of an information between the entities. Examples of this phenomena are the spreading of a virus within the population of a given region or the spreading of a rumor on a social network. In this scenario, we identify two new key problems: the source placement and vaccination. For the former, we would like to find a set of sources such that the spreading of the information over the network is as fast as possible. For the latter, we look for an optimal set of nodes to be “vaccinated” such that the spreading of the virus is the slowest. For both problems, we propose greedy algorithms directly optimizing the average time of infection of the network. Such algorithms out-perform the current state of the art and we evaluate their performance with a set of experiments on synthetic datasets. Then, we discuss three distinct inverse problems for physical fields characterized by a diffusive phenomena, such as temperature of solid bodies or the dispersion of pollution in the atmosphere. We first study the uniform sampling and reconstruction of diffusion fields and we show that we can exploit the kernel of the field to control and bound the aliasing error. Second, we study the source estimation of a diffusive field given a set of spatio-temporal measurements of the field and under the assumption that the sources can be modeled as a set of Dirac’s deltas. For this estimation problem, we propose an algorithm that exploits the eigenfunctions representation of the diffusion field and we show that this algorithm recovers the sources precisely. Third, we propose an algorithm for the estimation of time-varying emissions of smokestacks from the data collected in the surrounding environment by a sensor network, under the assumption that the emission rates can be modeled as signals lying on low-dimensional subspaces or with a finite rate of innovation. Last, we analyze a classic non-linear inverse problem, namely the sparse phase retrieval. In such a problem, we would like to estimate a signal from just the magnitude of its Fourier transform. Phase retrieval is of interest for many scientific applications, such as X-ray crystallography and astronomy. We assume that the signal of interest is spatially sparse, as it happens for many applications, and we model it as a linear combination of Dirac’s delta. We derive sufficient conditions for the uniqueness of the solution based on the support of the autocorrelation function of the measured sparse signal. Finally, we propose a reconstruction algorithm for the sparse phase retrieval taking advantage of the sparsity of the signal of interest.