Bounded mean oscillation and bandlimited interpolation in the presence of noise

We study some problems related to the effect of bounded, additive sample noise in the bandlimited interpolation given by the Whittaker-Shannon-Kotelnikov (WSK) sampling formula. We establish a generalized form of the WSK series that allows us to consider the bandlimited interpolation of any bounded sequence at the zeros of a sine-type function. The main result of the paper is that if the samples in this series consist of independent, uniformly distributed random variables, then the resulting bandlimited interpolation almost surely has a bounded global average. In this context, we also explore the related notion of a bandlimited function with bounded mean oscillation. We prove some properties of such functions, and in particular, we show that they are either bounded or have unbounded samples at any positive sampling rate. We also discuss a few concrete examples of functions that demonstrate these properties.     

Geometry of interpolation sets in derivative free optimization

We consider derivative free methods based on sampling approaches for nonlinear optimization problems where derivatives of the objective function are not available and cannot be directly approximated. We show how the bounds on the error between an interpolating polynomial and the true function can be used in the convergence theory of derivative free sampling methods. These bounds involve a constant that reflects the quality of the interpolation set. The main task of such a derivative free algorithm is to maintain an interpolation sampling set so that this constant remains small, and at least uniformly bounded. This constant is often described through the basis of Lagrange polynomials associated with the interpolation set. We provide an alternative, more intuitive, definition for this concept and show how this constant is related to the condition number of a certain matrix. This relation enables us to provide a range of algorithms whilst maintaining the interpolation set so that this condition number or the geometry constant remain uniformly bounded. We also derive bounds on the error between the model and the function and between their derivatives, directly in terms of this condition number and of this geometry constant.     

Sampling theorem and multi-scale spectrum based on non-linear Fourier atoms

This study concerns some new developments of unit analytic signals with non-linear phase. It includes ladder-shaped filter, generalized Sinc function based on non-linear Fourier atoms, generalized sampling theorem for non-bandlimited signals and the notion of multi-scale spectrum for discrete sequences. We first introduce the ladder-shaped filter and show that the impulse response of its corresponding linear time-shift invariant system is the generalized Sinc function as a product of periodic Poisson kernel and Sinc function. Secondly, we establish a Shannon-type sampling theorem based on generalized Sinc function for this type of non-bandlimited signal. We further prove that this type of signal may be holomorphically extended to strips in the complex plane containing the real axis. Finally, we introduce the notion of multi-scale spectrums for discrete sequences and develop the related fast algorithm.     

On determinants and the volume of random polytopes in isotropic convex bodies

In this paper we consider random polytopes generated by sampling points in multiple convex bodies. We prove related estimates for random determinants and give applications to several geometric inequalities.     

A novel quasicontinuum method for the seamless transition from atomistic to continumm length scales and its application to nanoindentation of single-crystalline materials

We propose a novel fully nonlocal quasicontinuum (QC) approach which is based on two approximation steps, (i) the coarsegraining via kinematic constraints and (ii) the sampling of the energy in clusters along with summation rules. The present approach is closely related to the framework in [1] where forces instead of the energy is subject to sampling. Here, we show that only energy sampling strictly preserves the symmetry of atomic interactions whereas force sampling generally does not. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Local uniformity properties for glauber dynamics on graph colorings

We investigate some local properties which hold with high probability for randomly selected colorings of a fixed graph with no short cycles. In a number of related works, establishing these particular properties has been a crucial step towards proving rapid convergence for the single‐site Glauber dynamics, a Markov chain for sampling colorings uniformly at random. For a large class of graphs, this approach yields the most efficient known algorithms for sampling random colorings. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Sampling and multilevel coarsening algorithms for fast matrix approximations

This paper addresses matrix approximation problems for matrices that are large, sparse, and/or representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed, which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. We consider a number of standard applications of this technique as well as a few new ones. Among standard applications, we first consider the problem of computing partial singular value decomposition, for which a combination of sampling and coarsening yields significantly improved singular value decomposition results relative to sampling alone. We also consider the column subset selection problem, a popular low‐rank approximation method used in data‐related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. We also establish theoretical results that characterize the approximation error obtained and the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. Numerical experiments illustrate the performances of the methods in a few applications.     

Sampling subproblems of heterogeneous Max‐Cut problems and approximation algorithms

Recent work in the analysis of randomized approximation algorithms for NP‐hard optimization problems has involved approximating the solution to a problem by the solution of a related subproblem of constant size, where the subproblem is constructed by sampling elements of the original problem uniformly at random. In light of interest in problems with a heterogeneous structure, for which uniform sampling might be expected to yield suboptimal results, we investigate the use of nonuniform sampling probabilities. We develop and analyze an algorithm which uses a novel sampling method to obtain improved bounds for approximating the Max‐Cut of a graph. In particular, we show that by judicious choice of sampling probabilities one can obtain error bounds that are superior to the ones obtained by uniform sampling, both for unweighted and weighted versions of Max‐Cut. Of at least as much interest as the results we derive are the techniques we use. The first technique is a method to compute a compressed approximate decomposition of a matrix as the product of three smaller matrices, each of which has several appealing properties. The second technique is a method to approximate the feasibility or infeasibility of a large linear program by checking the feasibility or infeasibility of a nonuniformly randomly chosen subprogram of the original linear program. We expect that these and related techniques will prove fruitful for the future development of randomized approximation algorithms for problems whose input instances contain heterogeneities. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Probabilistic abductive logic programming using Dirichlet priors

Probabilistic programming is an area of research that aims to develop general inference algorithms for probabilistic models expressed as probabilistic programs whose execution corresponds to inferring the parameters of those models. In this paper, we introduce a probabilistic programming language (PPL) based on abductive logic programming for performing inference in probabilistic models involving categorical distributions with Dirichlet priors. We encode these models as abductive logic programs enriched with probabilistic definitions and queries, and show how to execute and compile them to boolean formulas. Using the latter, we perform generalized inference using one of two proposed Markov Chain Monte Carlo (MCMC) sampling algorithms: an adaptation of uncollapsed Gibbs sampling from related work and a novel collapsed Gibbs sampling (CGS). We show that CGS converges faster than the uncollapsed version on a latent Dirichlet allocation (LDA) task using synthetic data. On similar data, we compare our PPL with LDA-specific algorithms and other PPLs. We find that all methods, except one, perform similarly and that the more expressive the PPL, the slower it is. We illustrate applications of our PPL on real data in two variants of LDA models (Seed and Cluster LDA), and in the repeated insertion model (RIM). In the latter, our PPL yields similar conclusions to inference with EM for Mallows models.     

A General Sampling Theorem Associated with Differential Operators

In this paper we prove a general sampling theorem associated with differential operators with compact resolvent. Thus, we are able to recover, through a Lagrange-type interpolatory series, functions defined by means of a linear integral transform. The kernel of this transform is related with the resolvent of the differential operator. Most of the well-known sampling theorems associated with differential operators are shown to be nothing but limit cases of this result.     

On Periodic Asymmetric Extrapolation

In this paper, we develop a new technique for the asymmetric approximation of discrete functions arising in seasonal customer demand extrapolation. We adapt the technique for two different settings, the so-called pull and push models. Our main goal here is to find effectively extrapolations minimizing the loss. For bothmodels, we discuss several features related to sampling, approximation, and extrapolation.     

Unique Reconstruction of Band-limited Signals by a Mallat-Zhong Wavelet Transform Algorithm

We show that uniqueness and existence for signal reconstruction from multiscale edges in the Mallat and Zhong algorithm become possible if we restrict our signals to Paley-Wiener space, band-limit our wavelets, and irregularly sample at the wavelet transform (absolute) maxima—the edges—while possibly including (enough) extra points at each level. We do this in a setting that closely resembles the numerical analysis setting of Mallat and Zhong and that seems to capture something of the essence of their (practical) reconstruction method. Our work builds on a uniqueness result for reconstructing an L² signal from irregular sampling of its wavelet transform of Gröchenig and the related work of Benedetto, Heller, Mallat, and Zhong. We show that the rate of convergence for this reconstruction algorithm is geometric and computable in advance. Finally, we consider the effect on the rate of convergence of not sampling enough local maxima.     

Unique reconstruction of band-limited signals by a Mallat-Zhong wavelet transform algorithm

We show that uniqueness and existence for signal reconstruction from multiscale edges in the Mallat and Zhong algorithm become possible if we restrict our signals to Paley-Wiener space, band-limit our wavelets, and irregularly sample at the wavelet transform (absolute) maxima—the edges—while possibly including (enough) extra points at each level. We do this in a setting that closely resembles the numerical analysis setting of Mallat and Zhong and that seems to capture something of the essence of their (practical) reconstruction method. Our work builds on a uniqueness result for reconstructing an L² signal from irregular sampling of its wavelet transform of Grochenig and the related work of Benedetto, Heller, Mallat, and Zhong. We show that the rate of convergence for this reconstruction algorithm is geometric and computable in advance. Finally, we consider the effect on the rate of convergence of not sampling enough local maxima.     

Computational Aspects of Nonparametric Bayesian Analysis with Applications to the Modeling of Multiple Binary Sequences

Abstract

We consider Markov mixture models for multiple longitudinal binary sequences. Prior uncertainty in the mixing distribution is characterized by a Dirichlet process centered on a matrix beta measure. We use this setting to evaluate and compare the performance of three competing algorithms that arise more generally in Dirichlet process mixture calculations: sequential imputations, Gibbs sampling, and a predictive recursion, for which an extension of the sequential calculations is introduced. This facilitates the estimation of quantities related to clustering structure which is not available in the original formulation. A numerical comparison is carried out in three examples. Our findings suggest that the sequential imputations method is most useful for relatively small problems, and that the predictive recursion can be an efficient preliminary tool for more reliable, but computationally intensive, Gibbs sampling implementations.     

A matrix pencil approach to the existence of compactly supported reconstruction functions in average sampling

The aim of this work is to solve a question raised for average sampling in shift-invariant spaces by using the well-known matrix pencil theory. In many common situations in sampling theory, the available data are samples of some convolution operator acting on the function itself: this leads to the problem of average sampling, also known as generalized sampling. In this paper we deal with the existence of a sampling formula involving these samples and having reconstruction functions with compact support. Thus, low computational complexity is involved and truncation errors are avoided. In practice, it is accomplished by means of a FIR filter bank. An answer is given in the light of the generalized sampling theory by using the oversampling technique: more samples than strictly necessary are used. The original problem reduces to finding a polynomial left inverse of a polynomial matrix intimately related to the sampling problem which, for a suitable choice of the sampling period, becomes a matrix pencil. This matrix pencil approach allows us to obtain a practical method for computing the compactly supported reconstruction functions for the important case where the oversampling rate is minimum. Moreover, the optimality of the obtained solution is established.     

Half Sampling on Bipartite Graphs

On a bipartite graph G we consider the half sampling problem of uniquely recovering a function from its values on the even vertices, under the appropriate half bandlimited assumption with respect to a Laplacian on the graph. We discuss both finite and infinite graphs, give the appropriate definition of “half bandlimited” that involves splitting the mid frequency, and give an explicit solution to the problem. We discuss in detail the example of a regular tree. We also consider a related sampling problem on graphs that are generated by edge substitution.     

Bilinear biorthogonal expansions and the Dunkl kernel on the real line

We study an extension of the classical Paley–Wiener space structure, which is based on bilinear expansions of integral kernels into biorthogonal sequences of functions. The structure includes both sampling expansions and Fourier–Neumann type series as special cases, and it also provides a bilinear expansion for the Dunkl kernel (in the rank 1 case) which is a Dunkl analogue of Gegenbauer’s expansion of the plane wave and the corresponding sampling expansions. In fact, we show how to derive sampling and Fourier–Neumann type expansions from the results related to the bilinear expansion for the Dunkl kernel.     

Maintenance models based on the <Emphasis Type="Italic">np</Emphasis> control charts with respect to the sampling interval

This paper develops models for the maintenance of a system based on np control charts with respect to the sampling interval. At any given time, the system is assumed to be in one of the three possible states; in-control, out-of-control and failure. If the control chart signals, suggesting the possibility of an out-of-control state, an investigation will be carried out. We assume that this investigation is perfect in that it reveals the true state of the system. If an assignable cause is confirmed by the investigation, a minor repair will be carried out to remove the cause. If the assignable cause is not attended to, it will gradually develop into a failure. When a failure occurs, the system cannot operate and a major repair is needed. We discuss three models depending on the assumptions related to the renewal mechanism, the occurrence of failures, and the time between minor repairs. The paper seeks to optimise the performance of such a system in terms of the sampling interval. Geometric processes are utilised for modelling the lifetimes between minor repairs if the minor repair cannot bring the system back to an as good as new condition. The expected cost per unit time for maintaining the systems with respect to the sampling interval of the control chart is obtained. Numerical examples are conducted to demonstrate the applicability of the methodology derived.     

Universal sampling,quasicrystals and bounded remainder sets

We examine the result due to Matei and Meyer that simple quasicrystals are universal sampling sets, in the critical case when the density of the sampling set is equal to the measure of the spectrum. We show that in this case, an arithmetical condition on the quasicrystal determines whether it is a universal set of “stable and non-redundant” sampling.