ITC/USA 2014 Conference Proceedings / The Fiftieth Annual International Telemetering Conference and Technical Exhibition / October 20-23, 2014 / Town and Country Resort & Convention Center, San Diego, CA / Massive amounts of data are typically acquired in third generation full-waveform (FW) LIDAR systems to generate image-like depthmaps of a scene of acceptable quality. The sampling systems acquiring this data, however, seldom take into account the low information rate generally present in the FW signals and, consequently, they sample very inefficiently. Our main goal here is to compare two efficient sampling models and processes for the individual time-resolved FW signals collected by a LIDAR system. Specifically, we compare two approaches of sub-Nyquist sampling of the continuous-time LIDAR FW return pulses: (i) modeling FW signals as short-duration pulses with multiple bandlimited echoes, and (ii) modeling them as signals with finite rates of innovation (FRI).

Sampling and interpolation are two important topics in signal processing. Signal processing is a vast field of study that deals with analysis and operations of signals such as sounds, images, sensor data, telecommunications and so on. It also utilizes many mathematical theories such as approximation theory, analysis and wavelets. This dissertation is divided into two chapters: Modified Pal´ Interpolation and Sampling Bilevel Signals with Finite Rate of Innovation. In the first chapter, we introduce a new interpolation process, the modified Pal interpolation, based on papers by P ´ al, J ´ oo´ and Szabo, and we establish the existence and uniqueness of interpolation polynomials of modified ´ Pal type. ´ The paradigm to recover signals with finite rate of innovation from their samples is a fairly recent field of study. In the second chapter, we show that causal bilevel signals with finite rate of innovation can be stably recovered from their samples provided that the sampling period is at or above the maximal local rate of innovation, and that the sampling kernel is causal and positive on the first sampling period. Numerical simulations are presented to discuss the recovery of bilevel causal signals in the presence of noise.

The Shannon sampling framework is widely used for discrete representation of analog bandlimited signals, starting from samples taken at the Nyquist rate. In many practical applications, signals are not bandlimited. In order to accommodate such signals within the Shannon-Nyquist framework, one typically passes the signal through an anti-aliasing filter, which essentially performs bandlimiting. In applications such as RADAR, SONAR, ultrasound imaging, optical coherence to-mography, multiband signal communication, wideband spectrum sensing, etc., the signals to be sampled have a certain structure, which could manifest in one of the following forms: (i) sparsity or parsimony in a certain bases; (ii) shift-invariant representation; (iii) multi-band spectrum; (iv) finite rate of innovation property, etc.. By using such structure as a prior, one could devise efficient sampling strategies that operate at sub-Nyquist rates. In this Ph.D. thesis, we consider the problem of sampling and reconstruction of finite-rate-of-innovation (FRI) signals, which fall in one of the two classes: (i) Sum-of-weighted and time-shifted (SWTS) pulses; and (ii) Sum-of-weighted exponential (SWE). Finite-rate-of-innovation signals are not necessarily bandlimited, but they are specified by a finite number of free parameters per unit time interval. Hence, the FRI reconstruction problem could be solved by estimating the parameters starting from measurements on the signal. Typically, parameter estimation is done using high-resolution spectral estimation (HRSE) techniques such as the annihilating filter, matrix pencil method, estimation of signal parameter via rotational invariance technique (ESPRIT), etc.. The sampling issues include design of the sampling kernel and choice of the sampling grid structure. Following a frequency-domain reconstruction approach, we propose a novel technique to design compactly supported sampling kernels. The key idea is to cancel aliasing at certain set of uniformly spaced frequencies and make sure that the rest of the frequency response is specified such that the kernel follows the Paley-Wiener criterion for compactly supported functions. To assess the robustness in the presence of noise, we consider a particular class of the proposed kernel whose impulse response has the form of sum of modulated splines (SMS). In the presence of continuous-time and digital noise cases, we show that the reconstruction accuracy is improved by 5 to 25 dB by using the SMS kernel compared with the state-of-the-art compactly supported kernels. Apart from noise robustness, the SMS kernel also has polynomial-exponential reproducing property where the exponents are harmonically related. An interesting feature of the SMS kernel, in contrast with E-splines, is that its support is independent of the number of exponentials. In a typical SWTS signal reconstruction mechanism, first, the SWTS signal is trans formed to a SWE signal followed by uniform sampling, and then discrete-domain annihilation is applied for parameter estimation. In this thesis, we develop a continuous-time annihilation approach using the shift operator for estimating the parameters of SWE signals. Instead of using uniform sampling-based HRSE techniques, operator-based annihilation allows us to estimate parameters from structured non-uniform samples (SNS), and gives more accurate parameters estimates. On the application front, we first consider the problem of curve fitting and curve completion, specifically, ellipse fitting to uniform or non-uniform samples. In general, the ellipse fitting problem is solved by minimizing distance metrics such as the algebraic distance, geometric distance, etc.. It is known that when the samples are measured from an incomplete ellipse, such fitting techniques tend to estimate biased ellipse parameters and the estimated ellipses are relatively smaller than the ground truth. By taking into account the FRI property of an ellipse, we show how accurate ellipse fitting can be performed even to data measured from a partial ellipse. Our fitting technique first estimates the underlying sampling rate using annihilating filter and then carries out least-squares regression to estimate the ellipse parameters. The estimated ellipses have lesser bias compared with the state-of-the-art methods and the mean-squared error is lesser by about 2 to 10 dB. We show applications of ellipse fitting in iris images starting from partial edge contours. We found that the proposed method is able to localize iris/pupil more accurately compared with conventional methods. In a related application, we demonstrate curve completion to partial ellipses drawn on a touch-screen tablet. We also applied the FRI principle to imaging applications such as frequency-domain optical-coherence tomography (FDOCT) and nuclear magnetic resonance (NMR) spectroscopy. In these applications, the resolution is limited by the uncertainty principle, which, in turn, is limited by the number of measurements. By establishing the FRI property of the measurements, we show that one could attain super-resolved tomograms and NMR spectra by using the same or lesser number of samples compared with the classical Fourier-based techniques. In the case of FDOCT, by assuming a piecewise-constant refractive index of the specimen, we show that the measurements have SWE form. We show how super-resolved tomograms could be achieved using SNS-based reconstruction technique. To demonstrate clinical relevance, we consider FDOCT measurements obtained from the retinal pigment epithelium (RPE) and photoreceptor inner/outer segments (IS/OS) of the retina. We show that the proposed method is able to resolve the RPE and IS/OS layers by using only 40% of the available samples. In the context of NMR spectroscopy, the measured signal or free induction decay (FID) can be modelled as a SWE signal. Due to the exponential decay, the FIDs are non-stationary. Hence, one cannot directly apply autocorrelation-based methods such as ESPRIT. We develop DEESPRIT, a counterpart of ESPRIT for decaying exponentials. We consider FID measurements taken from amino acid mixture and show that the proposed method is able to resolve two closely spaced frequencies by using only 40% of the measurements. In summary, this thesis focuses on various aspects of sub-Nyquist sampling and demonstrates concrete applications to super-resolution imaging.

In many practical imaging scenarios, including computed tomography and magnetic resonance imaging (MRI), the goal is to reconstruct an image from few of its Fourier domain samples. Many state-of-the-art reconstruction techniques, such as total variation minimization, focus on discrete ‘on-the-grid” modelling of the problem both in spatial domain and Fourier domain. While such discrete-to-discrete models allow for fast algorithms, they can also result in sub-optimal sampling rates and reconstruction artifacts due to model mismatch. Instead, this thesis presents a framework for “off-the-grid”, i.e. continuous domain, recovery of piecewise smooth signals from an optimal number of Fourier samples. The main idea is to model the edge set of the image as the level-set curve of a continuous domain band-limited function. Sampling guarantees can be derived for this framework by investigating the algebraic geometry of these curves. This model is put into a robust and efficient optimization framework by posing signal recovery entirely in Fourier domain as a structured low-rank (SLR) matrix completion problem. An efficient algorithm for this problem is derived, which is an order of magnitude faster than previous approaches for SLR matrix completion. This SLR approach based on off-the-grid modeling shows significant improvement over standard discrete methods in the context of undersampled MRI reconstruction.

Dans cette thèse, nous nous intéressons à deux méthodes permettant de reconstruire un signal parcimonieux largement sous-échantillonné : l’échantillonnage de signaux à taux d’innovation fini et l’acquisition comprimée.Il a été montré récemment qu’en utilisant un noyau de pré-filtrage adapté, les signaux impulsionnels peuvent être parfaitement reconstruits bien qu’ils soient à bande non-limitée. En présence de bruit, la reconstruction est réalisée par une procédure d’estimation de tous les paramètres du signal d’intérêt. Dans cette thèse, nous considérons premièrement l’estimation des amplitudes et retards paramétrisant une somme finie d'impulsions de Dirac filtrée par un noyau quelconque et deuxièmement l’estimation d’une somme d’impulsions de forme quelconque filtrée par un noyau en somme de sinus cardinaux (SoS). Le noyau SoS est intéressant car il est paramétrable par un jeu de paramètres à valeurs complexes et vérifie les conditions nécessaires à la reconstruction. En se basant sur l’information de Fisher Bayésienne relative aux paramètres d’amplitudes et de retards et sur des outils d’optimisation convexe, nous proposons un nouveau noyau d’échantillonnage.L’acquisition comprimée permet d’échantillonner un signal en-dessous de la fréquence d’échantillonnage de Shannon, si le vecteur à échantillonner peut être approximé comme une combinaison linéaire d’un nombre réduit de vecteurs extraits d’un dictionnaire sur-complet. Malheureusement, dans des conditions réalistes, le dictionnaire (ou base) n’est souvent pas parfaitement connu, et est donc entaché d’une erreur (DB). L’estimation par dictionnaire, se basant sur les mêmes principes, permet d’estimer des paramètres à valeurs continues en les associant selon une grille partitionnant l’espace des paramètres. Généralement, les paramètres ne se trouvent pas sur la grille, ce qui induit un erreur d’estimation même à haut rapport signal sur bruit (RSB). C’est le problème de l’erreur de grille (EG). Dans cette thèse nous étudions les conséquences des modèles d’erreur DB et EG en terme de performances bayésiennes et montrons qu’un biais est introduit même avec une estimation parfaite du support et à haut RSB. La BCRB est dérivée pour les modèles DB et EG non structurés, qui bien qu’ils soient très proches, ne sont pas équivalents en terme de performances. Nous donnons également la borne de Cramér-Rao moyennée (BCRM) dans le cas d’une petite erreur de grille et étudions l’expression analytique de l’erreur quadratique moyenne bayésienne (BEQM) sur l’estimation de l’erreur de grille à haut RSB. Cette dernière est confirmée en pratique dans le contexte de l’estimation de fréquence pour différents algorithmes de reconstruction parcimonieuse.Nous proposons deux nouveaux estimateurs : le Bias-Correction Estimator (BiCE) et l’Off-Grid Error Correction (OGEC) permettant de corriger l'erreur de modèle induite par les erreurs DB et EG, respectivement. Ces deux estimateurs principalement basés sur une projection oblique des mesures sont conçus comme des post-traitements, destinés à réduire le biais d’estimation suite à une pré-estimation effectuée par n’importe quel algorithme de reconstruction parcimonieuse. Les biais et variances théoriques du BiCE et du OGEC sont dérivés afin de caractériser leurs efficacités statistiques.Nous montrons, dans le contexte difficile de l’échantillonnage des signaux impulsionnels à bande non-limitée que ces deux estimateurs permettent de réduire considérablement l’effet de l'erreur de modèle sur les performances d’estimation. Les estimateurs BiCE et OGEC sont tout deux des schémas (i) génériques, car ils peuvent être associés à tout estimateur parcimonieux de la littérature, (ii) rapides, car leur coût de calcul reste faible comparativement au coût des estimateurs parcimonieux, et (iii) ont de bonnes propriétés statistiques. / In this thesis, we are interested in two different low rate sampling schemes that challenge Shannon’s theory: the sampling of finite rate of innovation signals and compressed sensing.Recently it has been shown that using appropriate sampling kernel, finite rate of innovation signals can be perfectly sampled even though they are non-bandlimited. In the presence of noise, reconstruction is achieved by a model-based estimation procedure. In this thesis, we consider the estimation of the amplitudes and delays of a finite stream of Dirac pulses using an arbitrary kernel and the estimation of a finite stream of arbitrary pulses using the Sum of Sincs (SoS) kernel. In both scenarios, we derive the Bayesian Cramér-Rao Bound (BCRB) for the parameters of interest. The SoS kernel is an interesting kernel since it is totally configurable by a vector of weights. In the first scenario, based on convex optimization tools, we propose a new kernel minimizing the BCRB on the delays, while in the second scenario we propose a family of kernels which maximizes the Bayesian Fisher Information, i.e., the total amount of information about each of the parameter in the measures. The advantage of the proposed family is that it can be user-adjusted to favor either of the estimated parameters.Compressed sensing is a promising emerging domain which outperforms the classical limit of the Shannon sampling theory if the measurement vector can be approximated as the linear combination of few basis vectors extracted from a redundant dictionary matrix. Unfortunately, in realistic scenario, the knowledge of this basis or equivalently of the entire dictionary is often uncertain, i.e. corrupted by a Basis Mismatch (BM) error. The related estimation problem is based on the matching of continuous parameters of interest to a discretized parameter set over a regular grid. Generally, the parameters of interest do not lie in this grid and there exists an estimation error even at high Signal to Noise Ratio (SNR). This is the off-grid (OG) problem. The consequence of the BM and the OG mismatch problems is that the estimation accuracy in terms of Bayesian Mean Square Error (BMSE) of popular sparse-based estimators collapses even if the support is perfectly estimated and in the high Signal to Noise Ratio (SNR) regime. This saturation effect considerably limits the effective viability of these estimation schemes.In this thesis, the BCRB is derived for CS model with unstructured BM and OG. We show that even though both problems share a very close formalism, they lead to different performances. In the biased dictionary based estimation context, we propose and study analytical expressions of the Bayesian Mean Square Error (BMSE) on the estimation of the grid error at high SNR. We also show that this class of estimators is efficient and thus reaches the Bayesian Cramér-Rao Bound (BCRB) at high SNR. The proposed results are illustrated in the context of line spectra analysis for several popular sparse estimator. We also study the Expected Cramér-Rao Bound (ECRB) on the estimation of the amplitude for a small OG error and show that it follows well the behavior of practical estimators in a wide SNR range.In the context of BM and OG errors, we propose two new estimation schemes called Bias-Correction Estimator (BiCE) and Off-Grid Error Correction (OGEC) respectively and study their statistical properties in terms of theoretical bias and variances. Both estimators are essentially based on an oblique projection of the measurement vector and act as a post-processing estimation layer for any sparse-based estimator and mitigate considerably the BM (OG respectively) degradation. The proposed estimators are generic since they can be associated to any sparse-based estimator, fast, and have good statistical properties. To illustrate our results and propositions, they are applied in the challenging context of the compressive sampling of finite rate of innovation signals.

La radio impulsionnelle UWB (IR-UWB) est une technologie de communication relativement récente, qui apporte une solution intéressante au problème de l’encombrement du spectre RF, et qui répond aux exigences de haut débit et localisation précise d’un nombre croissant d’applications, telles que les communications indoor, les réseaux de capteurs personnels et corporels, l’IoT, etc. Ses caractéristiques uniques sont obtenues par la transmission d’impulsions de très courte durée (inférieure à 1 ns), occupant une largeur de bande allant jusqu’à 7,5 GHz, et ayant une densité spectrale de puissance extrêmement faible (inférieure à -43 dBm/MHz). Les meilleures performances d’un système IR-UWB sont obtenues avec des récepteurs cohérents de type Rake, au prix d’une complexité accrue, due notamment à l’étape d’estimation du canal UWB, caractérisé par de nombreux trajets multiples. Cette étape de traitement nécessite l’estimation d’un ensemble de composantes spectrales du signal reçu, sans pouvoir faire appel aux techniques d’échantillonnage usuelles, en raison d’une limite de Nyquist particulièrement élevée (plusieurs GHz).Dans le cadre de cette thèse, nous proposons de nouvelles approches, à faible complexité, pour l’estimation du canal UWB, basées sur la représentation parcimonieuse du signal reçu, la théorie de l’acquisition compressée, et les méthodes de reconstruction des signaux à taux d’innovation fini. La réduction de complexité ainsi obtenue permet de diminuer de manière significative le coût d’implémentation du récepteur IR-UWB et sa consommation. D’abord, deux schémas d’échantillonnage compressé, monovoie (filtre SoS) et multivoie (MCMW) identifiés dans la littérature sont étendus au cas des signaux UWB ayant un spectre de type passe-bande, en tenant compte de leur implémentation réelle dans le circuit. Ces schémas permettent l’acquisition des coefficients spectraux du signal reçu et l’échantillonnage à des fréquences très réduites ne dépendant pas de la bande passante des signaux, mais seulement du nombre des trajets multiples du canal UWB. L’efficacité des approches proposées est démontrée au travers de deux applications : l’estimation du canal UWB pour un récepteur Rake cohérent à faible complexité, et la localisation précise en environnement intérieur dans un contexte d’aide à la dépendance.En outre, afin de réduire la complexité de l’approche multivoie en termes de nombre de voies nécessaires pour l’estimation du canal UWB, nous proposons une architecture à nombre de voies réduit, en augmentant le nombre d’impulsions pilotes émises.Cette même approche permet aussi la réduction de la fréquence d’échantillonnage associée au schéma MCMW. Un autre objectif important de la thèse est constitué par l’optimisation des performances des approches proposées. Ainsi, bien que l’acquisition des coefficients spectraux consécutifs permette une mise en oeuvre simple des schémas multivoie, nous montrons que les coefficients ainsi choisis, ne donnent pas les performances optimales des algorithmes de reconstruction. Ainsi, nous proposons une méthode basée sur la cohérence des matrices de mesure qui permet de trouver l’ensemble optimal des coefficients spectraux, ainsi qu’un ensemble sous-optimal contraint où les positions des coefficients spectraux sont structurées de façon à faciliter la conception du schéma MCMW. Enfin, les approches proposées dans le cadre de cette thèse sont validées expérimentalement à l’aide d’une plateforme expérimentale UWB du laboratoire Lab-STICC CNRS UMR 6285. / Ultra-wideband impulse radio (IR-UWB) is a relatively new communication technology that provides an interesting solution to the problem of RF spectrum scarcity and meets the high data rate and precise localization requirements of an increasing number of applications, such as indoor communications, personal and body sensor networks, IoT, etc. Its unique characteristics are obtained by transmitting pulses of very short duration (less than 1 ns), occupying a bandwidth up to 7.5 GHz, and having an extremely low power spectral density (less than -43 dBm / MHz). The best performances of an IR-UWB system are obtained with Rake coherent receivers, at the expense of increased complexity, mainly due to the estimation of UWB channel, which is characterized by a large number of multipath components. This processing step requires the estimation of a set of spectral components for the received signal, without being able to adopt usual sampling techniques, because of the extremely high Nyquist limit (several GHz).In this thesis, we propose new low-complexity approaches for the UWB channel estimation, relying on the sparse representation of the received signal, the compressed sampling theory, and the reconstruction of the signals with finite rate of innovation. The complexity reduction thus obtained makes it possible to significantly reduce the IR-UWB receiver cost and consumption. First, two existent compressed sampling schemes, single-channel (SoS) and multi-channel (MCMW), are extended to the case of UWB signals having a bandpass spectrum, by taking into account realistic implementation constraints. These schemes allow the acquisition of the spectral coefficients of the received signal at very low sampling frequencies, which are not related anymore to the signal bandwidth, but only to the number of UWB channel multipath components. The efficiency of the proposed approaches is demonstrated through two applications: UWB channel estimation for low complexity coherent Rake receivers, and precise indoor localization for personal assistance and home care.Furthermore, in order to reduce the complexity of the MCMW approach in terms of the number of channels required for UWB channel estimation, we propose a reduced number of channel architecture by increasing the number of transmitted pilot pulses. The same approach is proven to be also useful for reducing the sampling frequency associated to the MCMW scheme.Another important objective of this thesis is the performance optimization for the proposed approaches. Although the acquisition of consecutive spectral coefficients allows a simple implementation of the MCMW scheme, we demonstrate that it not results in the best performance of the reconstruction algorithms. We then propose to rely on the coherence of the measurement matrix to find the optimal set of spectral coefficients maximizing the signal reconstruction performance, as well as a constrained suboptimal set, where the positions of the spectral coefficients are structured so as to facilitate the design of the MCMW scheme. Finally, the approaches proposed in this thesis are experimentally validated using the UWB equipment of Lab-STICC CNRS UMR 6285.