Search

The goal of optimal transport (OT) is to find optimal assignments or matchings between data sets which minimize the total cost for a given cost function. However, sometimes the cost function is unknown but we have access to (parts of) the solution to the OT problem, e.g. the OT plan or the value of the objective function. Recovering the cost from such information is called inverse OT and has become recently of certain interest triggered by novel applications, e.g. in social science and economics. This raises the issue under which circumstances such cost is identifiable, i.e., it can be uniquely recovered from other OT quantities. In this work we provide sufficient and necessary conditions for the identifiability of the cost function on finite ground spaces. We find that such conditions correspond to the combinatorial structure of the corresponding linear program., Comment: 24 pages, 2 figures

Graph cuts are among the most prominent tools for clustering and classification analysis. While intensively studied from geometric and algorithmic perspectives, graph cut-based statistical inference still remains elusive to a certain extent. Distributional limits are fundamental in understanding and designing such statistical procedures on randomly sampled data. We provide explicit limiting distributions for balanced graph cuts in general on a fixed but arbitrary discretization. In particular, we show that Minimum Cut, Ratio Cut and Normalized Cut behave asymptotically as the minimum of Gaussians as sample size increases. Interestingly, our results reveal a dichotomy for Cheeger Cut: The limiting distribution of the optimal objective value is the minimum of Gaussians only when the optimal partition yields two sets of unequal volumes, while otherwise the limiting distribution is the minimum of a random mixture of Gaussians. Further, we show the bootstrap consistency for all types of graph cuts by utilizing the directional differentiability of cut functionals. We validate these theoretical findings by Monte Carlo experiments, and examine differences between the cuts and the dependency on the underlying distribution. Additionally, we expand our theoretical findings to the Xist algorithm, a computational surrogate of graph cuts recently proposed in Suchan, Li and Munk (arXiv, 2023), thus demonstrating the practical applicability of our findings e.g. in statistical tests., Comment: 59 pages, 11 figures

Recent experimental studies have shed light on the intriguing possibility that ion channels exhibit cooperative behaviour. However, a comprehensive understanding of such cooperativity remains elusive, primarily due to limitations in measuring separately the response of each channel. Rather, only the superimposed channel response can be observed, challenging existing data analysis methods. To address this gap, we propose IDC (Idealisation, Discretisation, and Cooperativity inference), a robust statistical data analysis methodology that requires only voltage-clamp current recordings of an ensemble of ion channels. The framework of IDC enables us to integrate recent advancements in idealisation techniques and coupled Markov models. Further, in the cooperativity inference phase of IDC, we introduce a minimum distance estimator and establish its statistical guarantee in the form of asymptotic consistency. We demonstrate the effectiveness and robustness of IDC through extensive simulation studies. As an application, we investigate gramicidin D channels. Our findings reveal that these channels act independently, even at varying applied voltages during voltage-clamp experiments. An implementation of IDC is available from GitLab., Comment: Codes in R are available at https://gitlab.gwdg.de/requadt/idc

The inverse optimal transport problem is to find the underlying cost function from the knowledge of optimal transport plans. While this amounts to solving a linear inverse problem, in this work we will be concerned with the nonlinear inverse problem to identify the cost function when only a set of marginals and its corresponding optimal values are given. We focus on absolutely continuous probability distributions with respect to the $d$-dimensional Lebesgue measure and classes of concave and convex cost functions. Our main result implies that the cost function is uniquely determined from the union of the ranges of the gradients of the optimal potentials. Since, in general, the optimal potentials may not be observed, we derive sufficient conditions for their identifiability - if an open set of marginals is observed, the optimal potentials are then identified via the value of the optimal costs. We conclude with a more in-depth study of this problem in the univariate case, where an explicit representation of the transport plan is available. Here, we link the notion of identifiability of the cost function with that of statistical completeness., Comment: 23 pages

Due to their computational complexity, graph cuts for cluster detection and identification are used mostly in the form of convex relaxations. We propose to utilize the original graph cuts such as Ratio, Normalized or Cheeger Cut to detect clusters in weighted undirected graphs by restricting the graph cut minimization to $st$-MinCut partitions. Incorporating a vertex selection technique and restricting optimization to tightly connected clusters, we combine the efficient computability of $st$-MinCuts and the intrinsic properties of Gomory-Hu trees with the cut quality of the original graph cuts, leading to linear runtime in the number of vertices and quadratic in the number of edges. Already in simple scenarios, the resulting algorithm Xist is able to approximate graph cut values better empirically than spectral clustering or comparable algorithms, even for large network datasets. We showcase its applicability by segmenting images from cell biology and provide empirical studies of runtime and classification rate., Comment: 34 pages, 5 figures

We develop a multiscale scanning method to find anomalies in a $d$-dimensional random field in the presence of nuisance parameters. This covers the common situation that either the baseline-level or additional parameters such as the variance are unknown and have to be estimated from the data. We argue that state of the art approaches to determine asymptotically correct critical values for multiscale scanning statistics will in general fail when such parameters are naively replaced by plug-in estimators. Instead, we suggest to estimate the nuisance parameters on the largest scale and to use (only) smaller scales for multiscale scanning. We prove a uniform invariance principle for the resulting adjusted multiscale statistic (AMS), which is widely applicable and provides a computationally feasible way to simulate asymptotically correct critical values. We illustrate the implications of our theoretical results in a simulation study and in a real data example from super-resolution STED microscopy. This allows us to identify interesting regions inside a specimen in a pre-scan with controlled family-wise error rate.

Hidden Markov models (HMMs) are characterized by an unobservable (hidden) Markov chain and an observable process, which is a noisy version of the hidden chain. Decoding the original signal (i.e., hidden chain) from the noisy observations is one of the main goals in nearly all HMM based data analyses. Existing decoding algorithms such as the Viterbi algorithm have computational complexity at best linear in the length of the observed sequence, and sub-quadratic in the size of the state space of the Markov chain. We present Quick Adaptive Ternary Segmentation (QATS), a divide-and-conquer procedure which decodes the hidden sequence in polylogarithmic computational complexity in the length of the sequence, and cubic in the size of the state space, hence particularly suited for large scale HMMs with relatively few states. The procedure also suggests an effective way of data storage as specific cumulative sums. In essence, the estimated sequence of states sequentially maximizes local likelihood scores among all local paths with at most three segments. The maximization is performed only approximately using an adaptive search procedure. The resulting sequence is admissible in the sense that all transitions occur with positive probability. To complement formal results justifying our approach, we present Monte-Carlo simulations which demonstrate the speedups provided by QATS in comparison to Viterbi, along with a precision analysis of the returned sequences. An implementation of QATS in C++ is provided in the R-package QATS and is available from GitHub.

Optimal transport (OT) based data analysis is often faced with the issue that the underlying cost function is (partially) unknown. This paper is concerned with the derivation of distributional limits for the empirical OT value when the cost function and the measures are estimated from data. For statistical inference purposes, but also from the viewpoint of a stability analysis, understanding the fluctuation of such quantities is paramount. Our results find direct application in the problem of goodness-of-fit testing for group families, in machine learning applications where invariant transport costs arise, in the problem of estimating the distance between mixtures of distributions, and for the analysis of empirical sliced OT quantities. The established distributional limits assume either weak convergence of the cost process in uniform norm or that the cost is determined by an optimization problem of the OT value over a fixed parameter space. For the first setting we rely on careful lower and upper bounds for the OT value in terms of the measures and the cost in conjunction with a Skorokhod representation. The second setting is based on a functional delta method for the OT value process over the parameter space. The proof techniques might be of independent interest., Comment: 62 pages

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., Comment: 61 pages

Quantifying the number of molecules from fluorescence microscopy measurements is an important topic in cell biology and medical research. In this work, we present a consecutive algorithm for super-resolution (STED) scanning microscopy that provides molecule counts in automatically generated image segments and offers statistical guarantees in form of asymptotic confidence intervals. To this end, we first apply a multiscale scanning procedure on STED microscopy measurements of the sample to obtain a system of significant regions, each of which contains at least one molecule with prescribed uniform probability. This system of regions will typically be highly redundant and consists of rectangular building blocks. To choose an informative but non-redundant subset of more naturally shaped regions, we hybridize our system with the result of a generic segmentation algorithm. The diameter of the segments can be of the order of the resolution of the microscope. Using multiple photon coincidence measurements of the same sample in confocal mode, we are then able to estimate the brightness and number of the molecules and give uniform confidence intervals on the molecule counts for each previously constructed segment. In other words, we establish a so-called molecular map with uniform error control. The performance of the algorithm is investigated on simulated and real data.

In this paper, we consider a certain convolutional Laplacian for metric measure spaces and investigate its potential for the statistical analysis of complex objects. The spectrum of that Laplacian serves as a signature of the space under consideration and the eigenvectors provide the principal directions of the shape, its harmonics. These concepts are used to assess the similarity of objects or understand their most important features in a principled way which is illustrated in various examples. Adopting a statistical point of view, we define a mean spectral measure and its empirical counterpart. The corresponding limiting process of interest is derived and statistical applications are discussed.

We provide a unifying approach to central limit type theorems for empirical optimal transport (OT). In general, the limit distributions are characterized as suprema of Gaussian processes. We explicitly characterize when the limit distribution is centered normal or degenerates to a Dirac measure. Moreover, in contrast to recent contributions on distributional limit laws for empirical OT on Euclidean spaces which require centering around its expectation, the distributional limits obtained here are centered around the population quantity, which is well-suited for statistical applications. At the heart of our theory is Kantorovich duality representing OT as a supremum over a function class $\mathcal{F}_{c}$ for an underlying sufficiently regular cost function $c$. In this regard, OT is considered as a functional defined on $\ell^{\infty}(\mathcal{F}_{c})$ the Banach space of bounded functionals from $\mathcal{F}_{c}$ to $\mathbb{R}$ and equipped with uniform norm. We prove the OT functional to be Hadamard directional differentiable and conclude distributional convergence via a functional delta method that necessitates weak convergence of an underlying empirical process in $\ell^{\infty}(\mathcal{F}_{c})$. The latter can be dealt with empirical process theory and requires $\mathcal{F}_{c}$ to be a Donsker class. We give sufficient conditions depending on the dimension of the ground space, the underlying cost function and the probability measures under consideration to guarantee the Donsker property. Overall, our approach reveals a noteworthy trade-off inherent in central limit theorems for empirical OT: Kantorovich duality requires $\mathcal{F}_{c}$ to be sufficiently rich, while the empirical processes only converges weakly if $\mathcal{F}_{c}$ is not too complex., Comment: 29 pages, 1 figure

The empirical optimal transport (OT) cost between two probability measures from random data is a fundamental quantity in transport based data analysis. In this work, we derive novel guarantees for its convergence rate when the involved measures are different, possibly supported on different spaces. Our central observation is that the statistical performance of the empirical OT cost is determined by the less complex measure, a phenomenon we refer to as lower complexity adaptation of empirical OT. For instance, under Lipschitz ground costs, we find that the empirical OT cost based on $n$ observations converges at least with rate $n^{-1/d}$ to the population quantity if one of the two measures is concentrated on a $d$-dimensional manifold, while the other can be arbitrary. For semi-concave ground costs, we show that the upper bound for the rate improves to $n^{-2/d}$. Similarly, our theory establishes the general convergence rate $n^{-1/2}$ for semi-discrete OT. All of these results are valid in the two-sample case as well, meaning that the convergence rate is still governed by the simpler of the two measures. On a conceptual level, our findings therefore suggest that the curse of dimensionality only affects the estimation of the OT cost when both measures exhibit a high intrinsic dimension. Our proofs are based on the dual formulation of OT as a maximization over a suitable function class $\mathcal{F}_c$ and the observation that the $c$-transform of $\mathcal{F}_c$ under bounded costs has the same uniform metric entropy as $\mathcal{F}_c$ itself., Comment: 28 pages, 4 figures

Kantorovich potentials denote the dual solutions of the renowned optimal transportation problem. Uniqueness of these solutions is relevant from both a theoretical and an algorithmic point of view, and has recently emerged as a necessary condition for asymptotic results in the context of statistical and entropic optimal transport. In this work, we challenge the common perception that uniqueness in continuous settings is reliant on the connectedness of the support of at least one of the involved measures, and we provide mild sufficient conditions for uniqueness even when both measures have disconnected support. Since our main finding builds upon the uniqueness of Kantorovich potentials on connected components, we revisit the corresponding arguments and provide generalizations of well-known results. Several auxiliary findings regarding the continuity of Kantorovich potentials, for example in geodesic spaces, are established along the way., Comment: 33 pages, 3 figures

We investigate minimax testing for detecting local signals or linear combinations of such signals when only indirect data is available. Naturally, in the presence of noise, signals that are too small cannot be reliably detected. In a Gaussian white noise model, we discuss upper and lower bounds for the minimal size of the signal such that testing with small error probabilities is possible. In certain situations we are able to characterize the asymptotic minimax detection boundary. Our results are applied to inverse problems such as numerical differentiation, deconvolution and the inversion of the Radon transform.

The purpose of this paper is to provide a systematic discussion of a generalized barycenter based on a variant of unbalanced optimal transport (UOT) that defines a distance between general non-negative, finitely supported measures by allowing for mass creation and destruction modeled by some cost parameter. They are denoted as Kantorovich-Rubinstein (KR) barycenter and distance. In particular, we detail the influence of the cost parameter to structural properties of the KR barycenter and the KR distance. For the latter we highlight a closed form solution on ultra-metric trees. The support of such KR barycenters of finitely supported measures turns out to be finite in general and its structure to be explicitly specified by the support of the input measures. Additionally, we prove the existence of sparse KR barycenters and discuss potential computational approaches. The performance of the KR barycenter is compared to the OT barycenter on a multitude of synthetic datasets. We also consider barycenters based on the recently introduced Gaussian Hellinger-Kantorovich and Wasserstein-Fisher-Rao distances.

We present a unifying view on various statistical estimation techniques including penalization, variational and thresholding methods. These estimators will be analyzed in the context of statistical linear inverse problems including nonparametric and change point regression, and high dimensional linear models as examples. Our approach reveals many seemingly unrelated estimation schemes as special instances of a general class of variational multiscale estimators, named MIND (MultIscale Nemirovskii--Dantzig). These estimators result from minimizing certain regularization functionals under convex constraints that can be seen as multiple statistical tests for local hypotheses. For computational purposes, we recast MIND in terms of simpler unconstraint optimization problems via Lagrangian penalization as well as Fenchel duality. Performance of several MINDs is demonstrated on numerical examples.

Finding meaningful ways to measure the statistical dependency between random variables $\xi$ and $\zeta$ is a timeless statistical endeavor. In recent years, several novel concepts, like the distance covariance, have extended classical notions of dependency to more general settings. In this article, we propose and study an alternative framework that is based on optimal transport. The transport dependency $\tau \ge 0$ applies to general Polish spaces and intrinsically respects metric properties. For suitable ground costs, independence is fully characterized by $\tau = 0$. Via proper normalization of $\tau$, three transport correlations $\rho_\alpha$, $\rho_\infty$, and $\rho_*$ with values in $[0, 1]$ are defined. They attain the value $1$ if and only if $\zeta = \varphi(\xi)$, where $\varphi$ is an $\alpha$-Lipschitz function for $\rho_\alpha$, a measurable function for $\rho_\infty$, or a multiple of an isometry for $\rho_*$. The transport dependency can be estimated consistently by an empirical plug-in approach, but alternative estimators with the same convergence rate but significantly reduced computational costs are also proposed. Numerical results suggest that $\tau$ robustly recovers dependency between data sets with different internal metric structures. The usage for inferential tasks, like transport dependency based independence testing, is illustrated on a data set from a cancer study., Comment: 37 pages main text (15 figures), 79 pages in total (49 figures)

For probability measures on countable spaces we derive distributional limits for empirical entropic optimal transport quantities. More precisely, we show that the empirical optimal transport plan weakly converges to a centered Gaussian process and that the empirical entropic optimal transport value is asymptotically normal. The results are valid for a large class of cost functions and generalize distributional limits for empirical entropic optimal transport quantities on finite spaces. Our proofs are based on a sensitivity analysis with respect to norms induced by suitable function classes, which arise from novel quantitative bounds for primal and dual optimizers, that are related to the exponential penalty term in the dual formulation. The distributional limits then follow from the functional delta method together with weak convergence of the empirical process in that respective norm, for which we provide sharp conditions on the underlying measures. As a byproduct of our proof technique, consistency of the bootstrap for statistical applications is shown., Comment: 68 pages

Empirical optimal transport (OT) plans and distances provide effective tools to compare and statistically match probability measures defined on a given ground space. Fundamental to this are distributional limit laws and we derive a central limit theorem for the empirical OT distance of circular data. Our limit results require only mild assumptions in general and include prominent examples such as the von Mises or wrapped Cauchy family. Most notably, no assumptions are required when data are sampled from the probability measure to be compared with, which is in strict contrast to the real line. A bootstrap principle follows immediately as our proof relies on Hadamard differentiability of the OT functional. This paves the way for a variety of statistical inference tasks and is exemplified for asymptotic OT based goodness of fit testing for circular distributions. We discuss numerical implementation, consistency and investigate its statistical power. For testing uniformity, it turns out that this approach performs particularly well for unimodal alternatives and is almost as powerful as Rayleigh's test, the most powerful invariant test for von Mises alternatives. For regimes with many modes the circular OT test is less powerful which is explained by the shape of the corresponding transport plan., Comment: 24 pages, 9 figures

We propose and investigate a hidden Markov model (HMM) for the analysis of dependent, aggregated, superimposed two-state signal recordings. A major motivation for this work is that often these signals cannot be observed individually but only their superposition. Among others, such models are in high demand for the understanding of cross-talk between ion channels, where each single channel cannot be measured separately. As an essential building block, we introduce a parameterized vector norm dependent Markov chain model and characterize it in terms of permutation invariance as well as conditional independence. This building block leads to a hidden Markov chain sum process which can be used for analyzing the dependence structure of superimposed two-state signal observations within an HMM. Notably, the model parameters of the vector norm dependent Markov chain are uniquely determined by the parameters of the sum process and are therefore identifiable. We provide algorithms to estimate the parameters, discuss model selection and apply our methodology to real-world ion channel data from the heart muscle, where we show competitive gating., Comment: 49 pages, 11 figures. An R package can be found at: https://github.com/ljvanegas/VND

In this paper, we investigate compact ultrametric measure spaces which form a subset $\mathcal{U}^w$ of the collection of all metric measure spaces $\mathcal{M}^w$. Similar as for the ultrametric Gromov-Hausdorff distance on the collection of ultrametric spaces $\mathcal{U}$, we define ultrametric versions of two metrics on $\mathcal{U}^w$, namely of Sturm's distance of order $p$ and of the Gromov-Wasserstein distance of order $p$. We study the basic topological and geometric properties of these distances as well as their relation and derive for $p=\infty$ a polynomial time algorithm for their calculation. Further, several lower bounds for both distances are derived and some of our results are generalized to the case of finite ultra-dissimilarity spaces.

We propose a hybrid resampling method to approximate finitely supported Wasserstein barycenters on large-scale datasets, which can be combined with any exact solver. Nonasymptotic bounds on the expected error of the objective value as well as the barycenters themselves allow to calibrate computational cost and statistical accuracy. The rate of these upper bounds is shown to be optimal and independent of the underlying dimension, which appears only in the constants. Using a simple modification of the subgradient descent algorithm of Cuturi and Doucet, we showcase the applicability of our method on a myriad of simulated datasets, as well as a real-data example from cell microscopy which are out of reach for state of the art algorithms for computing Wasserstein barycenters.

Many modern statistically efficient methods come with tremendous computational challenges, often leading to large-scale optimisation problems. In this work, we examine such computational issues for recently developed estimation methods in nonparametric regression with a specific view on image denoising. We consider in particular certain variational multiscale estimators which are statistically optimal in minimax sense, yet computationally intensive. Such an estimator is computed as the minimiser of a smoothness functional (e.g., TV norm) over the class of all estimators such that none of its coefficients with respect to a given multiscale dictionary is statistically significant. The so obtained multiscale Nemirowski-Dantzig estimator (MIND) can incorporate any convex smoothness functional and combine it with a proper dictionary including wavelets, curvelets and shearlets. The computation of MIND in general requires to solve a high-dimensional constrained convex optimisation problem with a specific structure of the constraints induced by the statistical multiscale testing criterion. To solve this explicitly, we discuss three different algorithmic approaches: the Chambolle-Pock, ADMM and semismooth Newton algorithms. Algorithmic details and an explicit implementation is presented and the solutions are then compared numerically in a simulation study and on various test images. We thereby recommend the Chambolle-Pock algorithm in most cases for its fast convergence. We stress that our analysis can also be transferred to signal recovery and other denoising problems to recover more general objects whenever it is possible to borrow statistical strength from data patches of similar object structure., Comment: Codes are available at https://github.com/housenli/MIND

Change point estimation is often formulated as a search for the maximum of a gain function describing improved fits when segmenting the data. Searching 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 methods with $O(\log n)$ evaluations exploiting specific structure of the gain function. 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 their asymptotic localization rate. These rates (up to a possible log factor) are optimal for the univariate and multivariate scenarios, and are by far the fastest in the literature under the weakest possible detection condition on the signal-to-noise ratio in the high-dimensional scenario. Computationally, our proposed methodology has the worst case complexity of $O(np)$, which can be improved to be sublinear in $n$ if some a-priori knowledge on the length of the shortest segment is available. Our search strategies generalize far beyond the theoretically analyzed setup. We illustrate, as an example, massive computational speedup in change point detection for high-dimensional Gaussian graphical models., Comment: Generalize the univariate theory to Gaussian mean changes of general dimension, including high-dimensional scenarios

We propose a new model-free segmentation method for idealizing ion channel recordings. This method is designed to deal with heterogeneity of measurement errors. This in particular applies to open channel noise which, in general, is particularly difficult to cope with for model-free approaches. Our methodology is able to deal with lowpass filtered data which provides a further computational challenge. To this end we propose a multiresolution testing approach, combined with local deconvolution to resolve the lowpass filter. Simulations and statistical theory confirm that the proposed idealization recovers the underlying signal very accurately at presence of heterogeneous noise, even when events are shorter than the filter length. The method is compared to existing approaches in computer experiments and on real data. We find that it is the only one which allows to identify openings of the PorB porine at two different temporal scales. An implementation is available as an R package.

We consider a general linear program in standard form whose right-hand side constraint vector is subject to random perturbations. This defines a stochastic linear program for which, under general conditions, we characterize the fluctuations of the corresponding empirical optimal solution by a central limit-type theorem. Our approach relies on the combinatorial nature and the concept of degeneracy inherent in linear programming, in strong contrast to well-known results for smooth stochastic optimization programs. In particular, if the corresponding dual linear program is degenerate the asymptotic limit law might not be unique and is determined from the way the empirical optimal solution is chosen. Furthermore, we establish consistency and convergence rates of the Hausdorff distance between the empirical and the true optimality sets. As a consequence, we deduce a limit law for the empirical optimal value characterized by the set of all dual optimal solutions which turns out to be a simple consequence of our general proof techniques. Our analysis is motivated from recent findings in statistical optimal transport that will be of special focus here. In addition to the asymptotic limit laws for optimal transport solutions, we obtain results linking degeneracy of the dual transport problem to geometric properties of the underlying ground space, and prove almost sure uniqueness statements that may be of independent interest.

In this paper, we aim to provide a statistical theory for object matching based on the Gromov-Wasserstein distance. To this end, we model general objects as metric measure spaces. Based on this, we propose a simple and efficiently computable asymptotic statistical test for pose invariant object discrimination. This is based on an empirical version of a $\beta$-trimmed lower bound of the Gromov-Wasserstein distance. We derive for $\beta\in[0,1/2)$ distributional limits of this test statistic. To this end, we introduce a novel $U$-type process indexed in $\beta$ and show its weak convergence. Finally, the theory developed is investigated in Monte Carlo simulations and applied to structural protein comparisons., Comment: For a version with the complete supplement see [v2]

As a general rule of thumb the resolution of a light microscope (i.e. the ability to discern objects) is predominantly described by the full width at half maximum (FWHM) of its point spread function (psf)---the diameter of the blurring density at half of its maximum. Classical wave optics suggests a linear relationship between FWHM and resolution also manifested in the well known Abbe and Rayleigh criteria, dating back to the end of 19th century. However, during the last two decades conventional light microscopy has undergone a shift from microscopic scales to nanoscales. This increase in resolution comes with the need to incorporate the random nature of observations (light photons) and challenges the classical view of discernability, as we argue in this paper. Instead, we suggest a statistical description of resolution obtained from such random data. Our notion of discernability is based on statistical testing whether one or two objects with the same total intensity are present. For Poisson measurements we get linear dependence of the (minimax) detection boundary on the FWHM, whereas for a homogeneous Gaussian model the dependence of resolution is nonlinear. Hence, at small physical scales modeling by homogeneous gaussians is inadequate, although often implicitly assumed in many reconstruction algorithms. In contrast, the Poisson model and its variance stabilized Gaussian approximation seem to provide a statistically sound description of resolution at the nanoscale. Our theory is also applicable to other imaging setups, such as telescopes.

In recent years, there has been an increasing demand on efficient algorithms for large scale change point detection problems. To this end, we propose seeded binary segmentation, an approach relying on a deterministic construction of background intervals, called seeded intervals, in which single change points are searched. The final selection of change points based on the candidates from seeded intervals can be done in various ways, adapted to the problem at hand. Thus, seeded binary segmentation is easy to adapt to a wide range of change point detection problems, let that be univariate, multivariate or even high-dimensional. We consider the univariate Gaussian change in mean setup in detail. For this specific case we show that seeded binary segmentation leads to a near-linear time approach (i.e. linear up to a logarithmic factor) independent of the underlying number of change points. Furthermore, using appropriate selection methods, the methodology is shown to be asymptotically minimax optimal. While computationally more efficient, the finite sample estimation performance remains competitive compared to state of the art procedures. Moreover, we illustrate the methodology for high-dimensional settings with an inverse covariance change point detection problem where our proposal leads to massive computational gains while still exhibiting good statistical performance.

We provide the asymptotic minimax detection boundary for a bump, i.e. an abrupt change, in the mean function of a stationary Gaussian process. This will be characterized in terms of the asymptotic behavior of the bump length and height as well as the dependency structure of the process. A major finding is that the asymptotic minimax detection boundary is generically determined by the value of its spectral density at zero. Finally, our asymptotic analysis is complemented by non-asymptotic results for AR($p$) processes and confirmed to serve as a good proxy for finite sample scenarios in a simulation study. Our proofs are based on laws of large numbers for non-independent and non-identically distributed arrays of random variables and the asymptotically sharp analysis of the precision matrix of the process.

Even though the statistical theory of linear inverse problems is a well-studied topic, certain relevant cases remain open. Among these is the estimation of functions of bounded variation ($BV$), meaning $L^1$ functions on a $d$-dimensional domain whose weak first derivatives are finite Radon measures. The estimation of $BV$ functions is relevant in many applications, since it involves minimal smoothness assumptions and gives simplified, interpretable cartoonized reconstructions. In this paper we propose a novel technique for estimating $BV$ functions in an inverse problem setting, and provide theoretical guaranties by showing that the proposed estimator is minimax optimal up to logarithms with respect to the $L^q$-risk, for any $q\in[1,\infty)$. This is to the best of our knowledge the first convergence result for $BV$ functions in inverse problems in dimension $d\geq 2$, and it extends the results by Donoho (Appl. Comput. Harmon. Anal., 2(2):101--126, 1995) in $d=1$. Furthermore, our analysis unravels a novel regime for large $q$ in which the minimax rate is slower than $n^{-1/(d+2\beta+2)}$, where $\beta$ is the degree of ill-posedness: our analysis shows that this slower rate arises from the low smoothness of $BV$ functions. The proposed estimator combines variational regularization techniques with the wavelet-vaguelette decomposition of operators., Comment: 24 pages

Super-resolution microscopy is rapidly gaining importance as an analytical tool in the life sciences. A compelling feature is the ability to label biological units of interest with fluorescent markers in living cells and to observe them with considerably higher resolution than conventional microscopy permits. The images obtained this way, however, lack an absolute intensity scale in terms of numbers of fluorophores observed. We provide an elaborate model to estimate this information from the raw data. To this end we model the entire process of photon generation in the fluorophore, their passage trough the microscope, detection and photo electron amplification in the camera, and extraction of time series from the microscopic images. At the heart of these modeling steps is a careful description of the fluorophore dynamics by a novel hidden Markov model that operates on two time scales (HTMM). Besides the fluorophore number, information about the kinetic transition rates of the fluorophore's internal states is also inferred during estimation. We comment on computational issues that arise when applying our model to simulated or measured fluorescence traces and illustrate our methodology on simulated data., Comment: 49 pages, 7 figures, 1 table

We introduce a new methodology for analyzing serial data by quantile regression assuming that the underlying quantile function consists of constant segments. The procedure does not rely on any distributional assumption besides serial independence. It is based on a multiscale statistic, which allows to control the (finite sample) probability for selecting the correct number of segments S at a given error level, which serves as a tuning parameter. For a proper choice of this parameter, this tends exponentially fast to the true S, as sample size increases. We further show that the location and size of segments are estimated at minimax optimal rate (compared to a Gaussian setting) up to a log-factor. Thereby, our approach leads to (asymptotically) uniform confidence bands for the entire quantile regression function in a fully nonparametric setup. The procedure is efficiently implemented using dynamic programming techniques with double heap structures, and software is provided. Simulations and data examples from genetic sequencing and ion channel recordings confirm the robustness of the proposed procedure, which at the same hand reliably detects changes in quantiles from arbitrary distributions with precise statistical guarantees., Comment: 39 pages, 7 figures

We derive limit distributions for certain empirical regularized optimal transport distances between probability distributions supported on a finite metric space and show consistency of the (naive) bootstrap. In particular, we prove that the empirical regularized transport plan itself asymptotically follows a Gaussian law. The theory includes the Boltzmann-Shannon entropy regularization and hence a limit law for the widely applied Sinkhorn divergence. Our approach is based on an application of the implicit function theorem to necessary and sufficient optimality conditions for the regularized transport problem. The asymptotic results are investigated in Monte Carlo simulations. We further discuss computational and statistical applications, e.g. confidence bands for colocalization analysis of protein interaction networks based on regularized optimal transport.

Estimating the parameters from $k$ independent Bin$(n,p)$ random variables, when both parameters $n$ and $p$ are unknown, is relevant to a variety of applications. It is particularly difficult if $n$ is large and $p$ is small. Over the past decades, several articles have proposed Bayesian approaches to estimate $n$ in this setting, but asymptotic results could only be established recently in \cite{Schneider}. There, posterior contraction for $n$ is proven in the problematic parameter regime where $n\rightarrow\infty$ and $p\rightarrow0$ at certain rates. In this article, we study numerically how far the theoretical upper bound on $n$ can be relaxed in simulations without losing posterior consistency.

Estimation of the population size $n$ from $k$ i.i.d.\ binomial observations with unknown success probability $p$ is relevant to a multitude of applications and has a long history. Without additional prior information this is a notoriously difficult task when $p$ becomes small, and the Bayesian approach becomes particularly useful. For a large class of priors, we establish posterior contraction and a Bernstein-von Mises type theorem in a setting where $p\rightarrow0$ and $n\rightarrow\infty$ as $k\to\infty$. Furthermore, we suggest a new class of Bayesian estimators for $n$ and provide a comprehensive simulation study in which we investigate their performance. To showcase the advantages of a Bayesian approach on real data, we also benchmark our estimators in a novel application from super-resolution microscopy., Comment: 66 pages; 37 pages main text and 29 pages supplement; contains link to a supplementary microscopy video

Despite the popularity and practical success of total variation (TV) regularization for function estimation, surprisingly little is known about its theoretical performance in a statistical setting. While TV regularization has been known for quite some time to be minimax optimal for denoising one-dimensional signals, for higher dimensions this remains elusive until today. In this paper we consider frame-constrained TV estimators including many well-known (overcomplete) frames in a white noise regression model, and prove their minimax optimality w.r.t. $L^q$-risk ($1\leq q<\infty$) up to a logarithmic factor in any dimension $d\geq 1$. Overcomplete frames are an established tool in mathematical imaging and signal recovery, and their combination with TV regularization has been shown to give excellent results in practice, which our theory now confirms. Our results rely on a novel connection between frame-constraints and certain Besov norms, and on an interpolation inequality to relate them to the risk functional., Comment: 27 pages main text, 7 pages appendix, 2 figures. In this updated version we have simplied the proof of the upper bound and extended the convergence to the complete range $q\in[1,\infty)$ of $L^q$ risks, rather than the range $q\in(1,1+2/d]$ that we had in the first version. Further, the rates in the extended range are shown to be minimax optimal

We consider parameter estimation in finite hidden state space Markov models with time-dependent inhomogeneous noise, where the inhomogeneity vanishes sufficiently fast. Based on the concept of asymptotic mean stationary processes we prove that the maximum likelihood and a quasi-maximum likelihood estimator (QMLE) are strongly consistent. The computation of the QMLE ignores the inhomogeneity, hence, is much simpler and robust. The theory is motivated by an example from biophysics and applied to a Poisson- and linear Gaussian model., Comment: 31 pages, 6 figures, Accepted for publication in ESAIM Probab. Stat

We consider the problem of finding anomalies in a $d$-dimensional field of independent random variables $\{Y_i\}_{i \in \left\{1,...,n\right\}^d}$, each distributed according to a one-dimensional natural exponential family $\mathcal F = \left\{F_\theta\right\}_{\theta \in\Theta}$. Given some baseline parameter $\theta_0 \in\Theta$, the field is scanned using local likelihood ratio tests to detect from a (large) given system of regions $\mathcal{R}$ those regions $R \subset \left\{1,...,n\right\}^d$ with $\theta_i \neq \theta_0$ for some $i \in R$. We provide a unified methodology which controls the overall family wise error (FWER) to make a wrong detection at a given error rate. Fundamental to our method is a Gaussian approximation of the distribution of the underlying multiscale test statistic with explicit rate of convergence. From this, we obtain a weak limit theorem which can be seen as a generalized weak invariance principle to non identically distributed data and is of independent interest. Furthermore, we give an asymptotic expansion of the procedures power, which yields minimax optimality in case of Gaussian observations.

We propose a simple subsampling scheme for fast randomized approximate computation of optimal transport distances. 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., Comment: to appear in Journal of Machine Learning Research

We provide a minimax optimal estimation procedure for F and W in matrix valued linear models Y = F W + Z where the parameter matrix W and the design matrix F are unknown but the latter takes values in a known finite set. The proposed finite alphabet linear model is justified in a variety of applications, ranging from signal processing to cancer genetics. We show that this allows to separate F and W uniquely under weak identifiability conditions, a task which is not doable, in general. To this end we quantify in the noiseless case, that is, Z = 0, the perturbation range of Y in order to obtain stable recovery of F and W. Based on this, we derive an iterative Lloyd's type estimation procedure that attains minimax estimation rates for W and F for Gaussian error matrix Z. In contrast to the least squares solution the estimation procedure can be computed efficiently and scales linearly with the total number of observations. We confirm our theoretical results in a simulation study and illustrate it with a genetic sequencing data example.

Modern multiscale type segmentation methods are known to detect multiple change-points with high statistical accuracy, while allowing for fast computation. Underpinning theory has been developed mainly for models that assume the signal as a piecewise constant function. In this paper this will be extended to certain function classes beyond such step functions in a nonparametric regression setting, revealing certain multiscale segmentation methods as robust to deviation from such piecewise constant functions. Our main finding is the adaptation over such function classes for a universal thresholding, which includes bounded variation functions, and (piecewise) H\"{o}lder functions of smoothness order $ 0 < \alpha \le1$ as special cases. From this we derive statistical guarantees on feature detection in terms of jumps and modes. Another key finding is that these multiscale segmentation methods perform nearly (up to a log-factor) as well as the oracle piecewise constant segmentation estimator (with known jump locations), and the best piecewise constant approximants of the (unknown) true signal. Theoretical findings are examined by various numerical simulations.

We derive distributional limits for empirical transport distances between probability measures supported on countable sets. Our approach is based on sensitivity analysis of optimal values of infinite dimensional mathematical programs and a delta method for non-linear derivatives. A careful calibration of the norm on the space of probability measures is needed in order to combine differentiability and weak convergence of the underlying empirical process. Based on this we provide a sufficient and necessary condition for the underlying distribution on the countable metric space for such a distributional limit to hold. We give an explicit form of the limiting distribution for ultra-metric spaces. Finally, we apply our findings to optimal transport based inference in large scale problems. An application to nanoscale microscopy is given.

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.