We analyze statistical properties of plug-in estimators for unbalanced optimal transport quantities between finitely supported measures in different prototypical sampling models. Specifically, our main results provide non-asymptotic bounds on the expected error of empirical Kantorovich-Rubinstein (KR) distance, plans, and barycenters for mass penalty parameter $C>0$. The impact of the mass penalty parameter $C$ is studied in detail. Based on this analysis, we mathematically justify randomized computational schemes for KR quantities which can be used for fast approximate computations in combination with any exact solver. Using synthetic and real datasets, we empirically analyze the behavior of the expected errors in simulation studies and illustrate the validity of our theoretical bounds.

Change point estimation is often formulated as a search for the maximum of a gain function describing improved fits when segmenting the data. Searching one change point through all candidates requires $O(n)$ evaluations of the gain function for an interval with $n$ observations. If each evaluation is computationally demanding (e.g. in high-dimensional models), this can become infeasible. Instead, we propose optimistic search, a methodology that only requires $O(\log n)$ evaluations of the gain function, leading to huge computational gains for massive (large-scale, high-dimensional) data for single and multiple change point estimation. Towards solid understanding of our strategy, we investigate in detail the $p$-dimensional Gaussian changing means setup, including high-dimensional scenarios. For some of our proposals, we prove asymptotic minimax optimality for detecting change points and derive sharp asymptotic rates for localizing change points. Our search strategy generalizes far beyond the theoretically analyzed setup. We illustrate, as an example, massive computational speedup in change point detection for high-dimensional Gaussian graphical models.

We propose a simple subsampling scheme for fast randomized approximate computation of optimal transport distances on finite spaces. This scheme operates on a random subset of the full data and can use any exact algorithm as a black-box back-end, including state-of-the-art solvers and entropically penalized versions. It is based on averaging the exact distances between empirical measures generated from independent samples from the original measures and can easily be tuned towards higher accuracy or shorter computation times. To this end, we give non-asymptotic deviation bounds for its accuracy in the case of discrete optimal transport problems. In particular, we show that in many important instances, including images (2D-histograms), the approximation error is independent of the size of the full problem. We present numerical experiments that demonstrate that a very good approximation in typical applications can be obtained in a computation time that is several orders of magnitude smaller than what is required for exact computation of the full problem.

We consider the kernel partial least squares algorithm for non- parametric regression with stationary dependent data. Probabilistic convergence rates of the kernel partial least squares estimator to the true regression function are established under a source and an effective dimensionality condition. It is shown both theoretically and in simulations that long range dependence results in slower convergence rates. A protein dynamics example shows high predictive power of kernel partial least squares.

We give under weak assumptions a complete combinatorial characterization of identifiability for linear mixtures of finite alphabet sources, with unknown mixing weights and unknown source signals, but known alphabet. This is based on a detailed treatment of the case of a single linear mixture. Notably, our identifiability analysis applies also to the case of unknown number of sources. We provide sufficient and necessary conditions for identifiability and give a simple sufficient criterion together with an explicit construction to determine the weights and the source signals for deterministic data by taking advantage of the hierarchical structure within the possible mixture values. We show that the probability of identifiability is related to the distribution of a hitting time and converges exponentially fast to one when the underlying sources come from a discrete Markov process. Finally, we explore our theoretical results in a simulation study. This paper extends and clarifies the scope of scenarios for which blind source separation becomes meaningful.

The fuzzy vault scheme is a cryptographic primitive that can be used to protect human fingerprint templates where stored. Analyses for most implementations account for brute-force security only. There are, however, other risks that have to be consider, such as false-accept attacks, record multiplicity attacks, and information leakage from auxiliary data, such as alignment parameters. In fact, the existing work lacks analyses of these weaknesses and are even susceptible to a variety of them. In view of these vulnerabilities, we redesign a minutiae-based fuzzy vault implementation preventing an adversary from running attacks via record multiplicity. Furthermore, we propose a mechanism for robust absolute fingerprint prealignment. In combination, we obtain a fingerprint-based fuzzy vault that resists known record multiplicity attacks and that does not leak information about the protected fingerprints from auxiliary alignment data. By experiments, we evaluate the performance of our security-improved implementation that, even though it has slight usability merits as compared with other minutiae-based implementations, provides improved security. However, despite heavy efforts spent in improving security, our implementation is, like all other implementations based on a single finger, subjected to a fundamental security limitation related to the false acceptance rate, i.e., false-accept attack. Consequently, this paper supports the notion that a single finger is not sufficient to provide acceptable security. Instead, implementations for multiple finger or even multiple modalities should be deployed the security of which may be improved by the technical contributions of this paper.

MOTIVATION: DNA segmentation, i.e. the partitioning of DNA in compositionally homogeneous segments, is a basic task in bioinformatics. Different algorithms have been proposed for various partitioning criteria such as Guanine/Cytosine (GC) content, local ancestry in population genetics or copy number variation. A critical component of any such method is the choice of an appropriate number of segments. Some methods use model selection criteria and do not provide a suitable error control. Other methods that are based on simulating a statistic under a null model provide suitable error control only if the correct null model is chosen. RESULTS: Here, we focus on partitioning with respect to GC content and propose a new approach that provides statistical error control: as in statistical hypothesis testing, it guarantees with a user-specified probability [Formula: see text] that the number of identified segments does not exceed the number of actually present segments. The method is based on a statistical multiscale criterion, rendering this as a segmentation method that searches segments of any length (on all scales) simultaneously. It is also accurate in localizing segments: under benchmark scenarios, our approach leads to a segmentation that is more accurate than the approaches discussed in the comparative review of Elhaik et al. In our real data examples, we find segments that often correspond well to features taken from standard University of California at Santa Cruz (UCSC) genome annotation tracks. AVAILABILITY AND IMPLEMENTATION: Our method is implemented in function smuceR of the R-package stepR available at http://www.stochastik.math.uni-goettingen.de/smuce.

We study the effect of growth on the fingerprints of adolescents, based on which we suggest a simple method to adjust for growth when trying to recover a juvenile's fingerprint in a database years later. Based on longitudinal data sets in juveniles' criminal records, we show that growth essentially leads to an isotropic rescaling, so that we can use the strong correlation between growth in stature and limbs to model the growth of fingerprints proportional to stature growth as documented in growth charts. The proposed rescaling leads to a 72% reduction of the distances between corresponding minutiae for the data set analyzed. These findings were corroborated by several verification tests. In an identification test on a database containing 3.25 million right index fingers at the Federal Criminal Police Office of Germany, the number of identification errors was reduced from 10 errors in 48 identification attempts to 1 in 48 by rescaling. The presented method is of striking simplicity and can easily be integrated into existing automated fingerprint identification systems.

One of the main reason for false recognition is noise added to fingerprint images during the acquisition step. Hence, the improvement of the enhancement step affects general accuracy of automatic recognition systems. In one of our previous publications we introduced hierarchically linked extended features - the new set of features which not only includes additional fingerprint features individually but also contains the information about their relationships such as line adjacency information at minutiae points or links between neighbouring fingerprint lines. In this work we present the application of the extended features to preprocessing and enhancement. We use structural information for improving the segmentation step, as well as connecting disrupted fingerprint lines and recovering missing minutiae. Experiments show a decrease in the error rate in matching.

We propose an intrinsic multifactorial model for data on Riemannian manifolds that typically occur in the statistical analysis of shape. Due to the lack of a linear structure, linear models cannot be defined in general; to date only one-way MANOVA is available. For a general multifactorial model, we assume that variation not explained by the model is concentrated near elements defining the effects. By determining the asymptotic distributions of respective sample covariances under parallel transport, we show that they can be compared by standard MANOVA. Often in applications manifolds are only implicitly given as quotients, where the bottom space parallel transport can be expressed through a differential equation. For Kendall's space of planar shapes, we provide an explicit solution. We illustrate our method by an intrinsic two-way MANOVA for a set of leaf shapes. While biologists can identify genotype effects by sight, we can detect height effects that are otherwise not identifiable.

Orientation field (OF) estimation is a crucial preprocessing step in fingerprint image processing. In this paper, we present a novel method for OF estimation that uses traced ridge and valley lines. This approach provides robustness against disturbances caused, e.g., by scars, contamination, moisture, or dryness of the finger. It considers pieces of flow information from a larger region and makes good use of fingerprint inherent properties like continuity of ridge flow perpendicular to the flow. The performance of the line-sensor method is compared with the gradients-based method and a multiscale directional operator. Its robustness is tested in experiments with simulated scar noise which is drawn on top of good quality fingerprint images from the FVC2000 and FVC2002 databases. Finally, the effectiveness of the line-sensor-based approach is demonstrated on 60 naturally poor quality fingerprint images from the FVC2004 database. All orientations marked by a human expert are made available at the journal's and the authors' website for comparative tests.

Quadratic differentials naturally define analytic orientation fields on planar surfaces. We propose to model orientation fields of fingerprints by specifying quadratic differentials. Models for all fingerprint classes such as arches, loops and whorls are laid out. These models are parametrised by few, geometrically interpretable parameters which are invariant under Euclidean motions. We demonstrate their ability in adapting to given, observed orientation fields, and we compare them to existing models using the fingerprint images of the NIST Special Database 4. We also illustrate that these model allow for extrapolation into unobserved regions. This goes beyond the scope of earlier models for the orientation field as those are restricted to the observed planar fingerprint region. Within the framework of quadratic differentials we are able to verify analytically Penrose's formula for the singularities on a palm. Potential applications of these models are the use of their parameters as indices of large fingerprint databases, as well as the definition of intrinsic coordinates for single fingerprint images.

This paper considers the problem of testing parametric assumptions on signals f from which only noisy observations y/sub k/=f(/spl tau/k)+/spl epsi//sub k/ are available, and where the signal is assumed to be either band-limited or time-limited. To this end, the signal is reconstructed by an estimator based on the Whittaker-Shannon (WS) sampling theorem with oversampling. As test statistic, the minimal L/sub 2/ distance between the estimated signal and the parametric model is used. To construct appropriate tests, the asymptotic distribution of the test statistic is derived both under the hypothesis of the validity of the parametric model and under fixed local alternatives. As a byproduct, the asymptotic distribution of the integrated square error of the estimator is computed, which is of interest by itself, e.g., for the analysis of a cross-validated bandwidth selector.