Local sampling set conditions in weighted shift-invariant signal spaces

How to represent a continuous signal in terms of a discrete sequence is a fundamental problem in sampling theory. Most of the known results concern global sampling in shift-invariant signal spaces. But in fact, the local reconstruction from local samples is one of the most desirable properties for many applications in signal processing, e.g. for implementing real-time reconstruction numerically. However, the local reconstruction problem has not been given much attention. In this article, we find conditions on a finite sampling set X such that at least in principle a continuous signal on a finite interval is uniquely and stably determined by their sampling value on the finite sampling set X in shift-invariant signal spaces.     

Phaseless inverse discrete Hilbert transform and determination of signals in shift‐invariant space

In this paper, we first address the uniqueness of phaseless inverse discrete Hilbert transform (phaseless IDHT for short) from the magnitude of discrete Hilbert transform (DHT for short). The measurement vectors of phaseless IDHT do not satisfy the complement property, a traditional requirement for ensuring the uniqueness of phase retrieval. Consequently, the uniqueness problem of phaseless IDHT is essentially different from that of the traditional phase retrieval. For the phaseless IDHT related to compactly supported functions, conditions are given in our first main theorem to ensure the uniqueness. A condition on the step size of DHT is crucial for the insurance. The second main theorem concerns the uniqueness related to noncompactly supported functions. It is not the trivial generalization of the first main theorem. Our third main result is on the determination of signals in shift‐invariant spaces by phaseless IDHT. Note that the measurements used for the determination are the DHT magnitudes. They are the approximations to the Hilbert transform magnitudes. Recall that for the existing methods of phaseless sampling (a special phase‐retrieval problem), to determine a signal depends on the exact measurements but not the approximative ones. Therefore, our determination method is essentially different from the traditional phaseless sampling. Numerical simulations are conducted to examine the efficiency of phaseless IDHT and its application in determining signals in spline Hilbert shift‐invariant space.     

Local Sampling and Reconstruction in Shift-Invariant Spaces and Their Applications in Spline Subspaces

The local reconstruction from samples is one of the most desirable properties for many applications in signal processing. Local sampling is practically useful since we need only to consider a signal on a bounded interval and computer can only process finite samples. However, the local sampling and reconstruction problem has not been given as much attention. Most of known results concern global sampling and reconstruction. There are only a few results about local sampling and reconstruction in spline subspaces. In this article, we study local sampling and reconstruction in general shift-invariant spaces and multiple generated shift-invariant spaces with compactly supported generators. Then we give several applications in spline subspaces and multiple generated spline subspaces.     

Local reconstruction for sampling in shift-invariant spaces

The local reconstruction from samples is one of most desirable properties for many applications in signal processing, but it has not been given as much attention. In this paper, we will consider the local reconstruction problem for signals in a shift-invariant space. In particular, we consider finding sampling sets X such that signals in a shift-invariant space can be locally reconstructed from their samples on X. For a locally finite-dimensional shift-invariant space V we show that signals in V can be locally reconstructed from its samples on any sampling set with sufficiently large density. For a shift-invariant space V(? ₁, ..., ? _N ) generated by finitely many compactly supported functions ? ₁, ..., ? _N , we characterize all periodic nonuniform sampling sets X such that signals in that shift-invariant space V(? ₁, ..., ? _N ) can be locally reconstructed from the samples taken from X. For a refinable shift-invariant space V(?) generated by a compactly supported refinable function ?, we prove that for almost all \((x_0, x_1)\in [0,1]^2\), any signal in V(?) can be locally reconstructed from its samples from \(\{x_0, x_1\}+{\mathbb Z}\) with oversampling rate 2. The proofs of our results on the local sampling and reconstruction in the refinable shift-invariant space V(?) depend heavily on the linear independent shifts of a refinable function on measurable sets with positive Lebesgue measure and the almost ripplet property for a refinable function, which are new and interesting by themselves.     

Weighted sampling and reconstruction in weighted reproducing kernel spaces

In this paper, we discuss sampling and reconstruction of signals in the weighted reproducing kernel space associated with an idempotent integral operator. We show that any signal in that space can be stably reconstructed from its weighted samples taken on a relatively-separated set with sufficiently small gap. We also develop an iterative reconstruction algorithm for the reconstruction of a signal from its weighted samples taken on a relatively-separated set with sufficiently small gap.     

混合范数条件下平移不变信号的非均匀平均采样

L~p平移不变子空间中的采样研究通常要求生成函数属于一个不依赖于p的Wiener amalgam空间,此条件因不能控制p而显得太强.本文主要讨论生成函数属于混合范数空间时,非衰减平移不变空间中的非均匀平均采样与重构.生成函数属于混合范数空间的条件弱于Wiener amalgam空间且依赖于参数p.基于混合范数空间中的一些引理,针对两种平均采样泛函建立了采样稳定性,并给出了对应的具有指数收敛的迭代重构算法.     

Cone Fields and Topological Sampling in Manifolds with Bounded Curvature

A standard reconstruction problem is how to discover a compact set from a noisy point cloud that approximates it. A finite point cloud is a compact set. This paper proves a reconstruction theorem which gives a sufficient condition, as a bound on the Hausdorff distance between two compact sets, for when certain offsets of these two sets are homotopic in terms of the absence of μ-critical points in an annular region. We reduce the problem of reconstructing a subset from a point cloud to the existence of a deformation retraction from the offset of the subset to the subset itself. The ambient space can be any Riemannian manifold but we focus on ambient manifolds which have nowhere negative curvature (this includes Euclidean space). We get an improvement on previous bounds for the case where the ambient space is Euclidean whenever μ≤0.945 (μ∈(0,1) by definition). In the process, we prove stability theorems for μ-critical points when the ambient space is a manifold.     

Attractor information for discrete dynamical systems by means of optimal discrete Galerkin bases

We introduce local adaptive discrete Galerkin bases as a basis set in order to obtain geometrical and topological information about attractors of discrete dynamical systems. The asymptotic behavior of these systems is described by the reconstruction of their attractors in a finite dimensional Euclidean space and by the attractor topological characteristics including the minimal embedding dimension and its local dimension. We evaluate numerically the applicability of our geometrical and topological results by examining two examples: a dissipative discrete system and a nonlinear discrete predator–prey model that includes several types of self-limitation on the prey.     

Multivariate generalized sampling in shift-invariant spaces and its approximation properties

Nowadays the topic of sampling in a shift-invariant space is having a significant impact: it avoids most of the problems associated with classical Shannon's theory. Under appropriate hypotheses, any multivariate function in a shift-invariant space can be recovered from its samples at Zd. However, in many common situations the available data are samples of some convolution operators acting on the function itself: this leads to the problem of multivariate generalized sampling in shift-invariant spaces. This extra information on the functions in the shift-invariant space will allow to sample in an appropriate sub-lattice of Zd. In this paper an L²(Rd) theory involving the frame theory is exhibited. Sampling formulas which are frame expansions for the shift-invariant space are obtained. In the case of overcomplete frame formulas, the search of reconstruction functions with prescribed good properties is allowed. Finally, approximation schemes using these generalized sampling formulas are included.     

Improved sampling and reconstruction in spline subspaces

As a special shift-invariant spaces, spline subspaces yield many advantages so that there are many practical applications for signal or image processing. In this paper, we pay attention to the sampling and reconstruction problem in spline subspaces. We improve lower bound of sampling set conditions in spline subspaces. Based on the improved explicit lower bound, a improved explicit convergence ratio of reconstruction algorithm is obtained. The improved convergence ratio occupies faster convergence rate than old one. At the end, some numerical examples are shown to validate our results.     

Localization from Incomplete Noisy Distance Measurements

We consider the problem of positioning a cloud of points in the Euclidean space ? ^d , using noisy measurements of a subset of pairwise distances. This task has applications in various areas, such as sensor network localization and reconstruction of protein conformations from NMR measurements. It is also closely related to dimensionality reduction problems and manifold learning, where the goal is to learn the underlying global geometry of a data set using local (or partial) metric information. Here we propose a reconstruction algorithm based on semidefinite programming. For a random geometric graph model and uniformly bounded noise, we provide a precise characterization of the algorithm’s performance: in the noiseless case, we find a radius r ₀ beyond which the algorithm reconstructs the exact positions (up to rigid transformations). In the presence of noise, we obtain upper and lower bounds on the reconstruction error that match up to a factor that depends only on the dimension d, and the average degree of the nodes in the graph.     

Robustness of sampling and reconstruction and Beurling–Landau-type theorems for shift-invariant spaces

Beurling–Landau-type results are known for a rather small class of functions limited to the Paley–Wiener space and certain spline spaces. Here, we show that the sampling and reconstruction problem in shift-invariant spaces is robust with respect to two classes of probing measures as well as to the underlying shift-invariant space. As an application we enlarge the class of functions for which Beurling–Landau-type results hold.     

Generalized sampling reconstruction from Fourier measurements using compactly supported shearlets

In this paper we study the general reconstruction of a compactly supported function from its Fourier coefficients using compactly supported shearlet systems. We assume that only finitely many Fourier samples of the function are accessible and based on this finite collection of measurements an approximation is sought in a finite dimensional shearlet reconstruction space. We analyze this sampling and reconstruction process by a recently introduced method called generalized sampling. In particular by studying the stable sampling rate of generalized sampling we then show stable recovery of the signal is possible using an almost linear rate. Furthermore, we compare the result to the previously obtained rates for wavelets.     

Oversampling and reconstruction functions with compact support

Assume that a sequence of samples of a filtered version of a function in a shift-invariant space is given. This paper deals with the existence of a sampling formula involving these samples and having reconstruction functions with compact support. This is done in the light of the generalized sampling theory by using the oversampling technique. A necessary and sufficient condition is given in terms of the Smith canonical form of a polynomial matrix. Finally, we prove that the aforesaid oversampled formulas provide nice approximation schemes with respect to the uniform norm.     

Reconstructing Signals with Finite Rate of Innovation from Noisy Samples

A signal is said to have finite rate of innovation if it has a finite number of degrees of freedom per unit of time. Reconstructing signals with finite rate of innovation from their exact average samples has been studied in Sun (SIAM J. Math. Anal. 38, 1389–1422, 2006). In this paper, we consider the problem of reconstructing signals with finite rate of innovation from their average samples in the presence of deterministic and random noise. We develop an adaptive Tikhonov regularization approach to this reconstruction problem. Our simulation results demonstrate that our adaptive approach is robust against noise, is almost consistent in various sampling processes, and is also locally implementable.     

Approximation of Non-decaying Signals from Shift-Invariant Subspaces

In our recent work, the sampling and reconstruction of non-decaying signals, modeled as members of weighted-\(L_p\) spaces, were shown to be stable with an appropriate choice of the generating kernel for the shift-invariant reconstruction space. In this paper, we extend the Strang–Fix theory to show that, for d-dimensional signals whose derivatives up to order L are all in some weighted-\(L_p\) space, the weighted norm of the approximation error can be made to go down as \(O(h^L)\) when the sampling step h tends to 0. The sufficient condition for this decay rate is that the generating kernel belongs to a particular hybrid-norm space and satisfies the Strang–Fix conditions of order L. We show that the \(O(h^L)\) behavior of the error is attainable for both approximation schemes using projection (when the signal is prefiltered with the dual kernel) and interpolation (when a prefilter is unavailable). The requirement on the signal for the interpolation method, however, is slightly more stringent than that of the projection because we need to increase the smoothness of the signal by a margin of \(d/p+\varepsilon \), for arbitrary \(\varepsilon >0\). This extra amount of derivatives is used to make sure that the direct sampling is stable.

     

A parameter choice strategy for the inversion of multiple observations

In many geoscientific applications, multiple noisy observations of different origin need to be combined to improve the reconstruction of a common underlying quantity. This naturally leads to multi-parameter models for which adequate strategies are required to choose a set of ‘good’ parameters. In this study, we present a fairly general method for choosing such a set of parameters, provided that discrete direct, but maybe noisy, measurements of the underlying quantity are included in the observation data, and the inner product of the reconstruction space can be accurately estimated by the inner product of the discretization space. Then the proposed parameter choice method gives an accuracy that only by an absolute constant multiplier differs from the noise level and the accuracy of the best approximant in the reconstruction and in the discretization spaces.     

Band limited functions on quantum graphs

The notion of band limited functions is introduced on a quantum graph. The main results of the paper are a uniqueness theorem and a reconstruction algorithm of such functions from discrete sets of values. It turns out that some of our band limited functions can have compact supports and their frequencies can be localized on the ``time" side. It opens an opportunity to consider signals of a variable band width and to develop a sampling theory with variable rate of sampling.

     

Optimal Non-Linear Models for Sparsity and Sampling

Given a set of vectors (the data) in a Hilbert space ?, we prove the existence of an optimal collection of subspaces minimizing the sum of the square of the distances between each vector and its closest subspace in the collection. This collection of subspaces gives the best sparse representation for the given data, in a sense defined in the paper, and provides an optimal model for sampling in union of subspaces. The results are proved in a general setting and then applied to the case of low dimensional subspaces of ? ^N and to infinite dimensional shift-invariant spaces in L ²(? ^d ). We also present an iterative search algorithm for finding the solution subspaces. These results are tightly connected to the new emergent theories of compressed sensing and dictionary design, signal models for signals with finite rate of innovation, and the subspace segmentation problem.     

Optimal sampling points in reproducing kernel Hilbert spaces

The recent development of compressed sensing seeks to extract information from as few samples as possible. In such applications, since the number of samples is restricted, one should deploy the sampling points wisely. We are motivated to study the optimal distribution of finite sampling points in reproducing kernel Hilbert spaces, the natural background function spaces for sampling. Formulation under the framework of optimal reconstruction yields a minimization problem. In the discrete measure case, we estimate the distance between the optimal subspace resulting from a general Karhunen–Loève transform and the kernel space to obtain another algorithm that is computationally favorable. Numerical experiments are then presented to illustrate the effectiveness of the algorithms for the searching of optimal sampling points.