Nonideal sampling and regularized interpolation of noisy data

Conventional sampling (Shannon's sampling formulation and its approximation-theoretic counterparts) and interpolation theories provide effective solutions to the problem of reconstructing a signal from its samples, but they are primarily restricted to the noise-free scenario. The purpose of this thesis is to extend the standard techniques so as to be able to handle noisy data. First, we consider a realistic setting where a multidimensional signal is prefiltered prior to sampling, and the samples are corrupted by additive noise. In order to counterbalance the effect of noise, the reconstruction problem is formulated in a variational framework where the solution is obtained by minimizing a continuous-domain Tikhonov-like L2-regularization subject to a ℓp-based data fidelity constraint. We present theoretical justification for the minimization of this cost functional and show that the global-minimum solution belongs to a shift-invariant space generated by a function that is generally not bandlimited. The optimal reconstruction space is characterized by a condition that links the generating function to the regularization operator and implies the existence of a B-spline-like basis. We also consider stochastic formulations – min-max and minimum mean-squared error (MMSE/Wiener) formulations – of the nonideal sampling problem and show that they yield the same type of estimators and point towards the existence of optimal shift-invariant spaces for certain classes of stochastic processes. In the stochastic context, we also derive an exact formula for the error of approximating a stationary stochastic signal in the presence of discrete additive noise and justify the noise-reducing effect of regularization through illustrations. Next, we focus on the use of a much wider class of non-quadratic regularization functionals for the problem of interpolation in the presence of noise. Starting from the afine-invariance of the solution, we show that the Lp-norm (p ≠ 2) is the most suitable type of non-quadratic regularization for our purpose. We give monotonically convergent numerical algorithms to carry out the minimization of the non-quadratic cost criterion. We also demonstrate experimentally that the proposed regularized interpolation scheme provides superior interpolation performance compared to standard methods in the presence of noise. Finally, we address the problem of selecting an appropriate value for the regularization parameter which is most crucial for the working of variational methods in general including those discussed in this thesis. We propose a practical scheme that is based on the concept of risk estimation to achieve minimum MSE performance. In this context, we first review a well known result due to Stein (Stein's unbiased risk estimate — SURE) that is applicable for data corrupted by additive Gaussian noise and also derive a new risk estimate for a Poisson-Gaussian mixture model that is appropriate for certain biomedical imaging applications. Next, we introduce a novel and efficient Monte-Carlo technique to compute SURE for arbitrary nonlinear algorithms. We demonstrate experimentally that the proposed Monte-Carlo SURE yields regularization parameter values that are close to the oracle-optimum (minimum MSE) for all methods considered in this work. We also present results that illustrate the applicability of our technique to a wide variety of algorithms in denoising and deconvolution.

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.

EPFL2014

Graph-based regularization for spherical signal interpolation

Pascal Frossard, Tamara Tosic

This paper addresses the problem of the interpolation of 2-d spherical signals from non-uniformly sampled and noisy data. We propose a graph-based regularization algorithm to improve the signal reconstructed by local interpolation methods such as nearest neighbour or kernel-based interpolation algorithms. We represent the signal as a function on a graph where weights are adapted to the particular geometry of the sphere. We then solve a total variation (TV) minimization problem with a modified version of Chambolle's algorithm. Experimental results with noisy and uncomplete datasets show that the regularization algorithm is able to improve the result of local interpolation schemes in terms of reconstruction quality.

2010

Reconstruction of Large, Irregularly Sampled Multidimensional Images. A Tensor-Based Approach

Michaël Unser

Many practical applications require the reconstruction of images from irregularly sampled data. The spline formalism offers an attractive framework for solving this problem; the currently available methods, however, are hard to deploy for large-scale interpolation problems in dimensions greater than two (3-D, 3-D+time) because of an exponential increase of their computational cost (curse of dimensionality). Here, we revisit the standard regularized least-squares formulation of the interpolation problem, and propose to perform the reconstruction in a uniform tensor-product B-spline basis as an alternative to the classical solution involving radial basis functions. Our analysis reveals that the underlying multilinear system of equations admits a tensor decomposition with an extreme sparsity of its one dimensional components. We exploit this property for implementing a parallel, memory-efficient system solver. We show that the computational complexity of the proposed algorithm is essentially linear in the number of measurements and that its dependency on the number of dimensions is significantly less than that of the original sparse matrix-based implementation. The net benefit is a substantial reduction in memory requirement and operation count when compared to standard matrix-based algorithms, so that even 4-D problems with millions of samples become computationally feasible on desktop PCs in reasonable time. After validating the proposed algorithm in 3-D and 4-D, we apply it to a concrete imaging problem: the reconstruction of medical ultrasound images (3-D+time) from a large set of irregularly sampled measurements, acquired by a fast rotating ultrasound transducer.

IEEE2011

Sensing the real world

Juri Ranieri

EPFL2014