Sampling at unknown locations: Uniqueness and reconstruction under constraints

Benjamin Bejar Haro, Golnooshsadat Elhami, Michalina Wanda Pacholska, Adam James Scholefield, Martin Vetterli
2018
Journal paper

Abstract

Traditional sampling results assume that the sample locations are known. Motivated by simultaneous localization and mapping (SLAM) and structure from motion (SfM), we investigate sampling at unknown locations. Without further constraints, the problem is often hopeless. For example, we recently showed that, for polynomial and bandlimited signals, it is possible to find two signals, arbitrarily far from each other, that fit the measurements. However, we also showed that this can be overcome by adding constraints to the sample positions. In this paper, we show that these constraints lead to a uniform sampling of a composite of functions. Furthermore, the formulation retains the key aspects of the SLAM and SfM problems, whilst providing uniqueness, in many cases. We demonstrate this by studying two simple examples of constrained sampling at unknown locations. In the first, we consider sampling a periodic bandlimited signal composite with an unknown linear function. We derive the sampling requirements for uniqueness and present an algorithm that recovers both the bandlimited signal and the linear warping. Furthermore, we prove that, when the requirements for uniqueness are not met, the cases of multiple solutions have measure zero. For our second example, we consider polynomials sampled such that the sampling positions are constrained by a rational function. We previously proved that, if a specific sampling requirement is met, uniqueness is achieved. In addition, we present an alternate minimization scheme for solving the resulting non-convex optimization problem. Finally, fully reproducible simulation results are provided to support our theoretical analysis.

Official source

https://infoscience.epfl.ch/record/253299?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Benjamin Bejar Haro, Golnooshsadat Elhami, Michalina Wanda Pacholska, Adam James Scholefield, Martin Vetterli
2018
Journal paper

Abstract

Official source

https://infoscience.epfl.ch/record/253299?ln=en

About this result

Related concepts (17)

Related concepts

Related publications (16)

Related publications

Uncertain Sampling with Certain Priors

Golnooshsadat Elhami

Sampling has always been at the heart of signal processing providing a bridge between the analogue world and discrete representations of it, as our ability to process data in continuous space is quite limited. Furthermore, sampling plays a key part in understanding how to efficiently capture, store and process signals. Shannon's sampling theorem states that if the original signal is known to have a limited bandwidth, we can retrieve the signal from uniformly-spaced samples, provided that the sampling rate is greater than twice the highest frequency in the signal. Here, we see two key attributes: prior knowledge on the original signal (limited bandwidth) and a constrained sampling setup (uniform samples at a particular rate). In this thesis, we make weaker assumptions on the sampling setup by assuming that some information, such as the sample positions, is lost. We show that under proper prior knowledge, we can reconstruct the signal from its samples uniquely or up to some equivalence class. We start by the problem of linear sampling of discrete signals, where the sample values are known, but their order is lost. In general, the original signal is impossible to retrieve from the samples, but we show that by taking out symmetry from the sampling vectors, we can reconstruct the signal uniquely. We provide an efficient algorithm to find the sample orders and thus reconstruct the original signal. We also study the problem of reconstructing a continuous signal from samples taken at unknown locations. The lost sample locations take away any hope of uniquely retrieving the signal without prior knowledge. We show that this problem is equivalent to reconstructing a composite of functions from uniformly spaced samples. Then we provide an efficient algorithm that can recover bandlimited signals warped by a linear function uniquely given enough sampling frequency. We then investigate a problem, dubbed shape from bandwidth, where we have uniform samples from a picture (projection) of an unknown surface that is painted with an unknown texture. The goal is to reconstruct the shape of the surface from these samples. We show that having prior knowledge of the texture bandwidth provides us with enough information to reconstruct the surface from its picture. We provide reconstruction algorithms for both orthogonal and central projections and provide equivalence classes of solutions in each case. Next, in two consecutive chapters, using techniques from geometrical signal processing, we offer new designs for 3-D barcodes, whose information can be retrieved from a single projection using penetrating waves from an unknown direction. Because of the unknown scan direction, the correct correspondence of the samples to the information bits in the barcodes is lost. In this case, we use the known shape of the barcode as prior knowledge to estimate the unknown scan direction from the samples, and then transform the reconstruction as a linear problem that can be solved efficiently. Finally, we cover the theory of coordinate difference matrices (CDMs): matrices that store mutual differences between coordinates of points (sensors, microphones, molecules, etc.) in space. We show how we can leverage specific properties of these matrices, such as their low rank, as prior knowledge in order to reconstruct the position of the points in space using CDMs. We use our reconstruction algorithm to solve many real-life signal processing problems.

EPFL2021

Sampling theory has prospered extensively in the last century. The elegant mathematics and the vast number of applications are the reasons for its popularity. The applications involved in this thesis are in signal processing and communications and call out to mathematical notions in Fourier theory, spectral analysis, basic linear algebra, spline and wavelet theory. This thesis is divided in two parts. Chapters 2 and 3 consider uniform sampling of non-bandlimited signals and Chapters 4, 5, and 6 treat different irregular sampling problems. In the first part we address the problem of sampling signals that are not bandlimited but are characterized as having a finite number of degrees of freedom per unit of time. These signals will be called signals with a finite rate of innovation. We show that these signals can be uniquely represented given a sufficient number of samples obtained using an appropriate sampling kernel. The number of samples must be greater or equal to the degrees of freedom of the signal; in other words, the sampling rate must be greater or equal to the rate of innovation of the signal. In particular, we derive sampling schemes for periodic and finite length streams of Diracs and piecewise polynomial signals using the sinc, the differentiated sinc and the Gaussian kernels. Sampling and reconstruction of piecewise bandlimited signals and filtered piecewise polynomials is also considered. We also derive local reconstruction schemes for infinite length piecewise polynomials with a finite "local" rate of innovation using compact support kernels such as splines. Numerical experiments on all of the reconstruction schemes are shown. The first topic of the second part of this thesis is the irregular sampling problem of bandlimited signals with unknown sampling instances. The locations of the irregular set of samples are found by treating the problem as a combinatorial optimization problem. Search methods for the locations are described and numerical simulations on a random set and a jittery set of locations are made. The second topic is the periodic nonuniform sampling problem of bandlimited signals. The irregular set of samples involved has a structure which is irregular yet periodic. We develop a fast scheme that reduces the complexity of the problem by exploiting the special pattern of the locations. The motivation for developing a fast scheme originates from the fact that the periodic nonuniform set was also considered in the sampling with unknown locations problem and that a fast search method for the locations was sought. Finally, the last topic is the irregular sampling of signals that are linearly and nonlinearly approximated using Fourier and wavelet bases. We present variants of the Papoulis Gerchberg algorithm which take into account the information given in the approximation of the signal. Numerical experiments are presented in the context of erasure correction.

EPFL2002

Non-linear Recovery of Sparse Signal Representations with Applications to Temporal and Spatial Localization

Zafer Dogan

Foundations of signal processing are heavily based on Shannon's sampling theorem for acquisition, representation and reconstruction. This theorem states that signals should not contain frequency components higher than the Nyquist rate, which is half of the sampling rate. Then, the signal can be perfectly reconstructed from its samples. Increasing evidence shows that the requirements imposed by Shannon's sampling theorem are too conservative for many naturally-occurring signals, which can be accurately characterized by sparse representations that require lower sampling rates closer to the signal's intrinsic information rates. Finite rate of innovation (FRI) is a new theory that allows to extract underlying sparse signal representations while operating at a reduced sampling rate. The goal of this PhD work is to advance reconstruction techniques for sparse signal representations from both theoretical and practical points of view. Specifically, the FRI framework is extended to deal with applications that involve temporal and spatial localization of events, including inverse source problems from radiating fields. We propose a novel reconstruction method using a model-fitting approach that is based on minimizing the fitting error subject to an underlying annihilation system given by the Prony's method. First, we showed that this is related to the problem known as structured low-rank matrix approximation as in structured total least squares problem. Then, we proposed to solve our problem under three different constraints using the iterative quadratic maximum likelihood algorithm. Our analysis and simulation results indicate that the proposed algorithms improve the robustness of the results with respect to common FRI reconstruction schemes. We have further developed the model-fitting approach to analyze spontaneous brain activity as measured by functional magnetic resonance imaging (fMRI). For this, we considered the noisy fMRI time course for every voxel as a convolution between an underlying activity inducing signal (i.e., a stream of Diracs) and the hemodynamic response function (HRF). We then validated this method using experimental fMRI data acquired during an event-related study. The results showed for the first time evidence for the practical usage of FRI for fMRI data analysis. We also addressed the problem of retrieving a sparse source distribution from the boundary measurements of a radiating field. First, based on Green's theorem, we proposed a sensing principle that allows to relate the boundary measurements to the source distribution. We focused on characterizing these sensing functions with particular attention for those that can be derived from holomorphic functions as they allow to control spatial decay of the sensing functions. With this selection, we developed an FRI-inspired non-iterative reconstruction algorithm. Finally, we developed an extension to the sensing principle (termed eigensensing) where we choose the spatial eigenfunctions of the Laplace operator as the sensing functions. With this extension, we showed that eigensensing principle allows to extract partial Fourier measurements of the source functions from boundary measurements. We considered photoacoustic tomography as a potential application of these theoretical developments.

EPFL2015