A new robust and efficient estimator for ill-conditioned linear inverse problems with outliers

Solving a linear inverse problem may include difficulties such as the presence of outliers and a mixing matrix with a large condition number. In such cases a regularized robust estimator is needed. We propose a new tau-type regularized robust estimator that is simultaneously highly robust against outliers, highly efficient in the presence of purely Gaussian noise, and also stable when the mixing matrix has a large condition number. We also propose an algorithm to compute the estimates, based on a regularized iterative reweighted least squares algorithm. A basic and a fast version of the algorithm are given. Finally, we test the performance of the proposed approach using numerical experiments and compare it with other estimators. Our estimator provides superior robustness, even up to 40% of outliers, while at the same time performing quite close to the optimal maximum likelihood estimator in the outlier-free case.

Blowing in the Wind

Marta Martinez-Camara

Every day tons of pollutants are emitted into the atmosphere all around the world. These pollutants are altering the equilibrium of our planet, causing profound changes in its climate, increasing global temperatures, and raising the sea level. The need to curb these emissions is clear and urgent. To do so, it is first necessary to estimate the quantity of pollutants that is being emitted. Hence, the central challenge of this thesis: how can we estimate the spatio-temporal emissions of a pollutant from many later observations of the concentration of that pollutant at different times and locations? Mathematically speaking, given such observations and an atmospheric dispersion model, this is a linear inverse problem. Using real datasets, we show that the main difficulties in solving this problem are ill-conditioning and outliers. Ill-conditioning amplifies the effect of additive noise, and each outlier strongly deflects our estimate from the ground truth. We proceed in two different ways to design new estimation methods that can handle these challenges. In the first approach, we enhance traditional estimators, which are already equipped to deal with ill-conditioning, with a preprocessing step to make them robust against outliers. This preprocessing step blindly localizes outliers in the dataset to remove them completely or to downgrade their influence. We propose two ways of localizing outliers: the first one uses several transport models, while the second one uses random sampling techniques. We show that our preprocessing step significantly improves the performance of traditional estimators, both in synthetic datasets as well as in real-world measurements. The second approach is based on enhancing existing robust estimators, which are already equipped to deal with outliers, with suitable regularizations, so that they are stable when the problem is ill-conditioned. We analyze the properties of our new estimators and compare them with the properties of existing estimators, showing the advantages of introducing the regularization. Our new estimators perform well both in the presence and in the absence of outliers, making them generally applicable. They have good performance with up to 50 % of outliers in the dataset. They are also stable when the problem is ill-conditioned. We demonstrate their performance using real-world measurements. Two different algorithms to compute the new estimators are given: one is based on an iterative re-weighted least squares algorithm and the other on a proximal gradient algorithm. Software implementations of all our proposed estimators, along with sample datasets, are provided as part of our commitment to reproducible results. In addition, we provide LinvPy, an open-source python package that contains tested, documented, and user-friendly implementations of our regularized robust algorithms.

EPFL2017

Impulse Radio Ultra-Wideband Ranging Based on Maximum Likelihood Estimation

John Farserotu, Jean-Yves Le Boudec, Hai Zhan

We propose a high-resolution ranging algorithm for impulse radio (IR) ultra-WideBand (UWB) communication systems in additive white Gaussian noise. We formulate the ranging problem as a maximum- likelihood (ML) estimation problem for the channel delays and amplitudes at the receiver. Then we translate the obtained delay estimates into an estimate of the distance. The ML estimation problem is a non-linear problem and is hard to solve. Some previous works focus on finding alternative estimation procedures, for example by denoising. In contrast, we tackle the ML estimation problem directly. First, we use the same transformation as the first step of Iterative quadratic maximum likelihood (IQML) and we transform the ML problem into another optimization problem that avoids the estimation of the amplitude coefficients. Second, we solve the remaining optimization problem with a gradient descent approach (pseudo-quadratic maximum likelihood (PQML) algorithm). To demonstrate the good performance of the proposed estimator, we present the numerical evaluations under the IEEE 802.15.4a channel model. We show that our algorithm performs significantly better than previously published heuristics. We also derive a reduced complexity version of the algorithm algorithm, which will be implemented on the Xinlix field-programmable gate array (FPGA) board in the future. We test the approach in a real weak line of sight (LOS) propagation environment and obtained good accuracy for the ranging.

Institute of Electrical and Electronics Engineers2009

Blowing in the Wind

Marta Martinez-Camara

EPFL2017