Search

In event-based sensing, many sensors independently and asynchronously emit events when there is a change in their input. Event-based sensing can present significant improvements in power efficiency when compared to traditional sampling, because (1) the output is a stream of events where the important information lies in the timing of the events, and (2) the sensor can easily be controlled to output information only when interesting activity occurs at the input. Moreover, event-based sampling can often provide better resolution than standard uniform sampling. Not only does this occur because individual event-based sensors have higher temporal resolution (Rebecq et al., 2021) it also occurs because the asynchrony of events within a sensor and therefore across sensors allows for less redundant and more informative encoding. We would like to explain how such curious results come about. To do so, we use ideal time encoding machines as a proxy for event-based sensors. We explore time encoding of signals with low rank structure, and apply the resulting theory to video. We then see how the asynchronous firing across time encoding machines can couple spatial sampling density with temporal resolution, leading to better reconstruction, whereas, in frame-based video, temporal resolution depends solely on the frame-rate and spatial resolution solely on the pixel grid used. [ABSTRACT FROM AUTHOR]

Finite rate of innovation (FRI) is a powerful reconstruction framework enabling the recovery of sparse Dirac streams from uniform low-pass filtered samples. An extension of this framework, called generalised FRI (genFRI), has been recently proposed for handling cases with arbitrary linear measurement models. In this context, signal reconstruction amounts to solving a joint constrained optimisation problem, yielding estimates of both the Fourier series coefficients of the Dirac stream and its so-called annihilating filter, involved in the regularisation term. This optimisation problem is however highly non convex and non linear in the data. Moreover, the proposed numerical solver is computationally intensive and without convergence guarantee. In this work, we propose an implicit formulation of the genFRI problem. To this end, we leverage a novel regularisation term which does not depend explicitly on the unknown annihilating filter yet enforces sufficient structure in the solution for stable recovery. The resulting optimisation problem is still non convex, but simpler since linear in the data and with less unknowns. We solve it by means of a provably convergent proximal gradient descent (PGD) method. Since the proximal step does not admit a simple closed-form expression, we propose an inexact PGD method, coined Cadzow plug-and-play gradient descent (CPGD). The latter approximates the proximal steps by means of Cadzow denoising, a well-known denoising algorithm in FRI. We provide local fixed-point convergence guarantees for CPGD. Through extensive numerical simulations, we demonstrate the superiority of CPGD against the state-of-the-art in the case of non uniform time samples. [ABSTRACT FROM AUTHOR]

We study the accuracy of triangulation in multi-camera systems with respect to the number of cameras. We show that, under certain conditions, the optimal achievable reconstruction error decays quadratically as more cameras are added to the system. Furthermore, we analyze the error decay-rate of major state-of-the-art algorithms with respect to the number of cameras. To this end, we introduce the notion of consistency for triangulation, and show that consistent reconstruction algorithms achieve the optimal quadratic decay, which is asymptotically faster than some other methods. Finally, we present simulations results supporting our findings. Our simulations have been implemented in MATLAB and the resulting code is available in the supplementary material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TPAMI.2019.2939530. [ABSTRACT FROM AUTHOR]

Euclidean distance matrices (EDMs) are a major tool for localization from distances, with applications ranging from protein structure determination to global positioning and manifold learning. They are, however, static objects which serve to localize points from a snapshot of distances. If the objects move, one expects to do better by modeling the motion. In this paper, we introduce Kinetic Euclidean Distance Matrices (KEDMs)—a new kind of time-dependent distance matrices that incorporate motion. The entries of KEDMs become functions of time, the squared time-varying distances. We study two smooth trajectory models—polynomial and bandlimited trajectories—and show that these trajectories can be reconstructed from incomplete, noisy distance observations, scattered over multiple time instants. Our main contribution is a semidefinite relaxation, inspired by similar strategies for static EDMs. Similarly to the static case, the relaxation is followed by a spectral factorization step; however, because spectral factorization of polynomial matrices is more challenging than for constant matrices, we propose a new factorization method that uses anchor measurements. Extensive numerical experiments show that KEDMs and the new semidefinite relaxation accurately reconstruct trajectories from noisy, incomplete distance data and that, in fact, motion improves rather than degrades localization if properly modeled. This makes KEDMs a promising tool for problems in geometry of dynamic points sets. [ABSTRACT FROM AUTHOR]

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, first, we leverage the finite rate of innovation sampling theory to super-resolve the auto-correlation function from a limited number of samples, second, we design a greedy algorithm that identifies the locations of a sparse solution given the super-resolved auto-correlation function, finally, 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Estimating Diracs in continuous two or higher dimensions is a fundamental problem in imaging. Previous approaches extended one-dimensional (1-D) methods, like the ones based on finite rate of innovation (FRI) sampling, in a separable manner, e.g., along the horizontal and vertical dimensions separately in 2-D. The separate estimation leads to a sample complexity of $\mathcal {O}\left(K^D\right)$ for $K$ Diracs in $D$ dimensions, despite that the total degrees of freedom only increase linearly with respect to $D$. We propose a new method that enforces the continuous-domain sparsity constraints simultaneously along all dimensions, leading to a reconstruction algorithm with linear sample complexity $\mathcal {O}(K)$ , or a gain of $\mathcal {O}\left(K^{D-1}\right)$ over previous FRI-based methods. The multi-dimensional Dirac locations are subsequently determined by the intersections of hypersurfaces (e.g., curves in 2-D), which can be computed algebraically from the common roots of polynomials. We first demonstrate the performance of the new multidimensional algorithm on simulated data: multidimensional Dirac location retrieval under noisy measurements. Then, we show results on real data: radio astronomy point source reconstruction (from LOFAR telescope measurements) and the direction of arrival estimation of acoustic signals (using Pyramic microphone arrays). [ABSTRACT FROM AUTHOR]

We study the problem of solving a linear sensing system when the observations are unlabeled. Specifically we seek a solution to a linear system of equations \mathbfy= \mathbfA \mathbfx when the order of the observations in the vector \mathbfy is unknown. Focusing on the setting in which \mathbfA is a random matrix with i.i.d. entries, we show that if the sensing matrix \mathbfA admits an oversampling ratio of 2 or higher, then, with probability 1, it is possible to recover \mathbfx exactly without the knowledge of the order of the observations in \mathbfy . Furthermore, if \mathbfx is of dimension $K$ , then any $2K$ entries of \mathbfy are sufficient to recover \mathbfx . This result implies the existence of deterministic unlabeled sensing matrices with an oversampling factor of 2 that admit perfect reconstruction. The result is universal in that conditioned on the realization of matrix \mathbfA , recovery is guaranteed for all possible choices of \mathbfx . While the proof is constructive, it uses a combinatorial algorithm which is not practical, leaving the question of complexity open. We also analyze a noisy version of the problem and show that local stability is guaranteed by the solution. In particular, for every \mathbfx , the recovery error tends to zero as the signal-to-noise ratio tends to infinity. The question of universal stability is unclear. In addition, we obtain a converse of the result in the noiseless case: If the number of observations in \mathbfy is less than $2K$ , then with probability 1, universal recovery fails, i.e., with probability 1, there exist distinct choices of \mathbfx which lead to the same unordered list of observations in \mathbfy . We also present extensions of the result of the noiseless case to special cases with non-i.i.d. entries in \mathbfA , and to a different setting in which the labels of a portion of the observations \mathbfy are known. In terms of applications, the unlabeled sensing problem is related to data association problems encountered in different domains including robotics where it is appears in a method called “simultaneous localization and mapping”, multi-target tracking applications, and in sampling signals in the presence of jitter. [ABSTRACT FROM PUBLISHER]

We address the problem of sampling and reconstruction of sparse signals with finite rate of innovation.We derive general conditions under which perfect reconstruction is possible for sampling kernels satisfying Strang-Fix conditions. Previous results on the subject consider two particular cases;when the kernel is able to reproduce (complex) exponentials, or when it has the polynomial reproduction property. In this paper, we extend such analysis to the case where both properties could be found in the sampling kernel and show that the former two situations can be regarded as special cases. As a result of our analysis, we provide general conditions under which perfect recovery in the noiseless case is possible. In practice, a given sampling kernel might not satisfy Strang-Fix conditions. When dealing with arbitrary sampling kernels, we propose a unified view for sampling and reconstruction in the frequency domain. Our formulation generalizes previous approaches and provides new insights for devising optimal reconstruction schemes.We also propose a novel algorithm for denoising treating the problem as a particular instance of structured low-rank approximation. Finally, we provide some numerical experiments and a comparison between different state-of-the-art methods showing the improved estimation performance of the proposed approach. [ABSTRACT FROM AUTHOR]

Recent sampling results enable the reconstruction of signals composed of streams of fixed-shaped pulses. These results have found applications in topics as varied as channel estimation, biomedical imaging and radio astronomy. However, in many real signals, the pulse shapes vary throughout the signal. In this paper, we show how to sample and perfectly reconstruct Lorentzian pulses with variable width. In the noiseless case, perfect recovery is guaranteed by a set of theorems. In addition, we verify that our algorithm is robust to model mismatch and noise. This allows us to apply the technique to two practical applications: electrocardiogram (ECG) compression and bidirectional reflectance distribution function (BRDF) sampling. ECG signals are one dimensional, but the BRDF is a higher dimensional signal, which is more naturally expressed in a spherical coordinate system; this motivated us to extend the theory to the 2D and spherical cases. Experiments on real data demonstrate the viability of the proposed model for ECG acquisition and compression, as well as the efficient representation and low-rate sampling of specular BRDFs. [ABSTRACT FROM PUBLISHER]