Average sampling in spline subspaces

We show that every function in a spline subspace is uniquely determined and can be reconstructed by its local averages near certain points. Regular and irregular average sampling theorems for spline subspaces are obtained.     

Characterization of local sampling sequences for spline subspaces

The sampling theorem is one of the most powerful tools in signal analysis. It says that to recover a function in certain function spaces, it suffices to know the values of the function on a sequence of points. Most of known results, e.g., regular and irregular sampling theorems for band-limited functions, concern global sampling. That is, to recover a function at a point or on an interval, we have to know all the samples which are usually infinitely many. On the other hand, local sampling, which invokes only finite samples to reconstruct a function on a bounded interval, is practically useful since we need only to consider a function on a bounded interval in many cases and computers can process only finite samples. In this paper, we give a characterization of local sampling sequences for spline subspaces, which is equivalent to the celebrated Schönberg-Whitney Theorem and is easy to verify. As applications, we give several local sampling theorems on spline subspaces, which generalize and improve some known results.     

Chebyshev approximations in subspaces of spline functions

The main purpose of this paper is to consider strict approximations from subspaces of spline functions of degree m-1 with k fixed knots. Rice defines the strict approximation which is a particular unique best Chebyshev approximation for problems defined on a finite set. In order to determine best approximations on an interval I we define a sequence of strict approximations on finite subsets of I where the subsets fill up the interval. It is shown that the sequences always converge if k≤m. In the case k>m the sequences are convergent if we restrict ourselves to problems defined on certain subsets of I. It seems to be natural to denote these limits as strict approximations. To be able to compute these functions we also develop a Remez type algorithm.     

Uniqueness and strong uniqueness of best approximations by spline subspaces and other subspaces

A complete characterization is given of those functions in $\text{C¦a, b¦}$ which have a unique best approximation from the subspace of spline functions of degree n with k fixed knots. Also, the relationship between unique and strongly unique best approximations from arbitrary finitedimensional subspaces of C₀(T) is investigated.     

Reconstruction of functions in spline subspaces from local averages

In this paper, we study the reconstruction of functions in spline subspaces from local averages. We present an average sampling theorem for shift invariant subspaces generated by cardinal B-splines and give the optimal upper bound for the support length of averaging functions. Our result generalizes an earlier result by Aldroubi and Gröchenig.

     

Characterization of strict approximations in subspaces of spline functions

The problem of approximating a given function by spline functions with fixed knots is discussed. Strict approximations which are particular unique best Chebyshev approximations are considered. The chief purpose is to develop a characterization theorem for these strict approximations.     

Vector sampling expansions in shift invariant subspaces

Multi-input multi-output (MIMO) sampling scheme which is motivated by applications in multi-channel deconvolution and multi-source separation has been investigated in many aspects. Common for most of results on MIMO systems is that the input signals are supposed to be band-limited. In this paper, we study vector sampling expansions on general finitely generated shift-invariant subspaces. Necessary and sufficient conditions for a vector sampling theorem to hold are given. We also give several examples to illustrate the main result.     

On the sampling theorem for wavelet subspaces

In [13], Walter extended the classical Shannon sampling theorem to some wavelet subspaces. For any closed subspace V₀/L² (R), we present a necessary and sufficient condition under which there is a sampling expansion for everyf V₀-Several examples are given.     

New spline basis functions for sampling approximations

We describe a method of constructing a new kind of splines with compact support on . These basis functions consisting of a linear combination of the cardinal B-splines of mixed orders enable us to achieve simultaneously a good sampling approximation and an interpolation of any smooth function.     

An algorithm for the computation of strict approximations in subspaces of spline functions

The problem of approximating a given function by spline functions with fixed knots is discussed. Strict approximations which are particular unique best Chebyshev approximations are considered. The chief purpose is to develop a characterization theorem for these strict approximations.     

Isogeometric spline reconstruction of plane curves

We establish conditions for the isogeometric reconstruction of plane curves by using parabolic and cubic parametric splines of minimal defect.     

Beurling-Landau-type theorems for non-uniform sampling in shift invariant spline spaces

Under the appropriate definition of sampling density D_ϕ, a function f that belongs to a shift invariant space can be reconstructed in a stable way from its non-uniform samples only if D_ϕ≥1. This result is similar to Landau's result for the Paley-Wiener space B _1/2 . If the shift invariant space consists of polynomial splines, then we show that D_ϕ<1 is sufficient for the stable reconstruction of a function f from its samples, a result similar to Beurling's special case B _1/2 .     

Local reconstruction of low‐rank matrices and subspaces

We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix that is low‐rank and close to M under some distance function Δ. Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where Δ is the normalized Hamming distance (between matrices). Given M that is ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When Δ is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when Δ is the truncated Euclidean distance and , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017     

Interior-compact subspaces and differentiation in model subspaces

We discuss relations between Koosis’ theorem on interior-compact subspaces of the space L²(0, ∞) and recent Dyakonov’s results on differentiation in model subspaces of the Hardy class H² in the upper half-plane. Bibliography: 10 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 327, 2005, pp. 17–24.     

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.     

Perturbed sampling formulas and local reconstruction in shift invariant spaces

Let V? be a closed subspace of L₂(R) generated from the integer shifts of a continuous function ? with a certain decay at infinity and a non-vanishing property for the function Φ^†(γ)=_∑n∈Z?(n)e−inγ on [−π,π]. In this paper we determine a positive number δ? so that the set {n+δn}_n∈Z is a set of stable sampling for the space V? for any selection of the elements δn within the ranges ±δ?. We demonstrate the resulting sampling formula (called perturbation formula) for functions f∈V? and also we establish a finite reconstruction formula approximating f on bounded intervals. We compute the corresponding error and we provide estimates for the jitter error as well.     

Improved bounds for sampling contingency tables

We study the problem of sampling contingency tables (nonnegative integer matrices with specified row and column sums) uniformly at random. We give an algorithm which runs in polynomial time provided that the row sums r_i and the column sums c_j satisfy r_i = Ω(n^3/2m log m), and c_j = Ω(m^3/2n log n). This algorithm is based on a reduction to continuous sampling from a convex set. The same approach was taken by Dyer, Kannan, and Mount in previous work. However, the algorithm we present is simpler and has weaker requirements on the row and column sums. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 135–146, 2002