Adaptive weights smoothing with applications to image restoration

We propose a new method of nonparametric estimation which is based on locally constant smoothing with an adaptive choice of weights for every pair of data points. Some theoretical properties of the procedure are investigated. Then we demonstrate the performance of the method on some simulated univariate and bivariate examples and compare it with other nonparametric methods. Finally we discuss applications of this procedure to magnetic resonance and satellite imaging.     

On the robustness of the generalized fused lasso to prior specifications

Using networks as prior knowledge to guide model selection is a way to reach structured sparsity. In particular, the fused lasso that was originally designed to penalize differences of coefficients corresponding to successive features has been generalized to handle features whose effects are structured according to a given network. As any prior information, the network provided in the penalty may contain misleading edges that connect coefficients whose difference is not zero, and the extent to which the performance of the method depend on the suitability of the graph has never been clearly assessed. In this work we investigate the theoretical and empirical properties of the adaptive generalized fused lasso in the context of generalized linear models. In the fixed \(p\) setting, we show that, asymptotically, adding misleading edges in the graph does not prevent the adaptive generalized fused lasso from enjoying asymptotic oracle properties, while forgetting suitable edges can be more problematic. These theoretical results are complemented by an extensive simulation study that assesses the robustness of the adaptive generalized fused lasso against misspecification of the network as well as its applicability when theoretical coefficients are not exactly equal. Our contribution is also to evaluate the applicability of the generalized fused lasso for the joint modeling of multiple sparse regression functions. Illustrations are provided on two real data examples.     

Spanning trees and identifiability of a single-factor model

The aim of this paper is to propose conditions for exploring the class of identifiable Gaussian models with one latent variable. In particular, we focus attention on the topological structure of the complementary graph of the residuals. These conditions are mainly based on the presence of odd cycles and bridge edges in the complementary graph. We propose to use the spanning tree representation of the graph and the associated matrix of fundamental cycles. In this way it is possible to obtain an algorithm able to establish in advance whether modifying the graph corresponding to an identifiable model, the resulting graph still denotes identifiability.     

Comparison of a genetic algorithm and simulated annealing in an application to statistical image reconstruction

Genetic algorithms (GAs) are adaptive search techniques designed to find near-optimal solutions of large scale optimization problems with multiple local maxima. Standard versions of the GA are defined for objective functions which depend on a vector of binary variables. The problem of finding the maximum a posteriori (MAP) estimate of a binary image in Bayesian image analysis appears to be well suited to a GA as images have a natural binary representation and the posterior image probability is a multi-modal objective function. We use the numerical optimization problem posed in MAP image estimation as a test-bed on which to compare GAs with simulated annealing (SA), another all-purpose global optimization method. Our conclusions are that the GAs we have applied perform poorly, even after adaptation to this problem. This is somewhat unexpected, given the widespread claims of GAs' effectiveness, but it is in keeping with work by Jennison and Sheehan (1995) which suggests that GAs are not adept at handling problems involving a great many variables of roughly equal influence.We reach more positive conclusions concerning the use of the GA's crossover operation in recombining near-optimal solutions obtained by other methods. We propose a hybrid algorithm in which crossover is used to combine subsections of image reconstructions obtained using SA and we show that this algorithm is more effective and efficient than SA or a GA individually.     

On an adaptive version of the Metropolis–Hastings algorithm with independent proposal distribution

In this paper, we present a general formulation of an algorithm, the adaptive independent chain (AIC), that was introduced in a special context in Gåsemyr et al . [ Methodol. Comput. Appl. Probab. 3 (2001)]. The algorithm aims at producing samples from a specific target distribution Π, and is an adaptive, non-Markovian version of the Metropolis–Hastings independent chain. A certain parametric class of possible proposal distributions is fixed, and the parameters of the proposal distribution are updated periodically on the basis of the recent history of the chain, thereby obtaining proposals that get ever closer to Π. We show that under certain conditions, the algorithm produces an exact sample from Π in a finite number of iterations, and hence that it converges to Π. We also present another adaptive algorithm, the componentwise adaptive independent chain (CAIC), which may be an alternative in particular in high dimensions. The CAIC may be regarded as an adaptive approximation to the Gibbs sampler updating parametric approximations to the conditionals of Π.     

Mixed Graphical Models with Missing Data and the Partial Imputation EM Algorithm

In this paper we discuss graphical models for mixed types of continuous and discrete variables with incomplete data. We use a set of hyperedges to represent an observed data pattern. A hyperedge is a set of variables observed for a group of individuals. In a mixed graph with two types of vertices and two types of edges, dots and circles represent discrete and continuous variables respectively. A normal graph represents a graphical model and a hypergraph represents an observed data pattern. In terms of the mixed graph, we discuss decomposition of mixed graphical models with incomplete data, and we present a partial imputation method which can be used in the EM algorithm and the Gibbs sampler to speed their convergence. For a given mixed graphical model and an observed data pattern, we try to decompose a large graph into several small ones so that the original likelihood can be factored into a product of likelihoods with distinct parameters for small graphs. For the case that a graph cannot be decomposed due to its observed data pattern, we can impute missing data partially so that the graph can be decomposed.     

Localized classification

The main problem with localized discriminant techniques is the curse of dimensionality, which seems to restrict their use to the case of few variables. However, if localization is combined with a reduction of dimension the initial number of variables is less restricted. In particular it is shown that localization yields powerful classifiers even in higher dimensions if localization is combined with locally adaptive selection of predictors. A robust localized logistic regression (LLR) method is developed for which all tuning parameters are chosen data-adaptively. In an extended simulation study we evaluate the potential of the proposed procedure for various types of data and compare it to other classification procedures. In addition we demonstrate that automatic choice of localization, predictor selection and penalty parameters based on cross validation is working well. Finally the method is applied to real data sets and its real world performance is compared to alternative procedures.     

A simple,automatic and adaptive bivariate density estimator based on conditional densities

The standard approach to non-parametric bivariate density estimation is to use a kernel density estimator. Practical performance of this estimator is hindered by the fact that the estimator is not adaptive (in the sense that the level of smoothing is not sensitive to local properties of the density). In this paper a simple, automatic and adaptive bivariate density estimator is proposed based on the estimation of marginal and conditional densities. Asymptotic properties of the estimator are examined, and guidance to practical application of the method is given. Application to two examples illustrates the usefulness of the estimator as an exploratory tool, particularly in situations where the local behaviour of the density varies widely. The proposed estimator is also appropriate for use as a pilot estimate for an adaptive kernel estimate, since it is relatively inexpensive to calculate.     

Quantifying the similarity of 2D images using edge pixels: an application to the forensic comparison of footwear impressions

We propose a novel method to quantify the similarity between an impression (Q) from an unknown source and a test impression (K) from a known source. Using the property of geometrical congruence in the impressions, the degree of correspondence is quantified using ideas from graph theory and maximum clique (MC). The algorithm uses the x and y coordinates of the edges in the images as the data. We focus on local areas in Q and the corresponding regions in K and extract features for comparison. Using pairs of images with known origin, we train a random forest to classify pairs into mates and non-mates. We collected impressions from 60 pairs of shoes of the same brand and model, worn over six months. Using a different set of very similar shoes, we evaluated the performance of the algorithm in terms of the accuracy with which it correctly classified images into source classes. Using classification error rates and ROC curves, we compare the proposed method to other algorithms in the literature and show that for these data, our method shows good classification performance relative to other methods. The algorithm can be implemented with the R package shoeprintr.     

Tree consistency and bounds on the performance of the max-product algorithm and its generalizations

Finding the maximum a posteriori (MAP) assignment of a discrete-state distribution specified by a graphical model requires solving an integer program. The max-product algorithm, also known as the max-plus or min-sum algorithm, is an iterative method for (approximately) solving such a problem on graphs with cycles. We provide a novel perspective on the algorithm, which is based on the idea of reparameterizing the distribution in terms of so-called pseudo-max-marginals on nodes and edges of the graph. This viewpoint provides conceptual insight into the max-product algorithm in application to graphs with cycles. First, we prove the existence of max-product fixed points for positive distributions on arbitrary graphs. Next, we show that the approximate max-marginals computed by max-product are guaranteed to be consistent, in a suitable sense to be defined, over every tree of the graph. We then turn to characterizing the nature of the approximation to the MAP assignment computed by max-product. We generalize previous work by showing that for any graph, the max-product assignment satisfies a particular optimality condition with respect to any subgraph containing at most one cycle per connected component. We use this optimality condition to derive upper bounds on the difference between the log probability of the true MAP assignment, and the log probability of a max-product assignment. Finally, we consider extensions of the max-product algorithm that operate over higher-order cliques, and show how our reparameterization analysis extends in a natural manner.     

Edge selection based on the geometry of dually flat spaces for Gaussian graphical models

We propose a method for selecting edges in undirected Gaussian graphical models. Our algorithm takes after our previous work, an extension of Least Angle Regression (LARS), and it is based on the information geometry of dually flat spaces. Non-diagonal elements of the inverse of the covariance matrix, the concentration matrix, play an important role in edge selection. Our iterative method estimates these elements and selects covariance models simultaneously. A sequence of pairs of estimates of the concentration matrix and an independence graph is generated, whose length is the same as the number of non-diagonal elements of the matrix. In our algorithm, the next estimate of the graph is the nearest graph to the latest estimate of the concentration matrix. The next estimate of the concentration matrix is not just the projection of the latest estimate, and it is shrunk to the origin. We describe the algorithm and show results for some datasets. Furthermore, we give some remarks on model identification and prediction.     

Edge Estimation in the Population of a Binary Tree Using Node-Sampling

Suppose a finite population of several vertices, each connected to single or multiple edges. This constitutes a structure of graphical population of vertices and edges. As a special case, the graphical population like a binary tree having only two child vertices associated to parent vertex is taken into consideration. The entire binary tree is divided into two sub-graphs such as a group of left-nodes and a group of right-nodes. This paper takes into account a mixture of graph structured and population sampling theory together and presents a methodology for mean-edge-length estimation of left sub-graph using right edge sub-graph as an auxiliary source of information. A node-sampling procedure is developed for this purpose and a class of estimators is proposed containing several good estimators. Mathematical conditions for minimum bias and optimum mean squared error of the class are derived and theoretical results are numerically supported with a test of 99% confidence intervals. It is shown that suggested class has a sub-class of optimum estimators, and sample-based estimates are closer to the true value of the population parameter.     

An efficient and fast algorithm for estimating the parameters of two-dimensional sinusoidal signals

In this paper we propose a computationally efficient algorithm to estimate the parameters of a 2-D sinusoidal model in the presence of stationary noise. The estimators obtained by the proposed algorithm are consistent and asymptotically equivalent to the least squares estimators. Monte Carlo simulations are performed for different sample sizes and it is observed that the performances of the proposed method are quite satisfactory and they are equivalent to the least squares estimators. The main advantage of the proposed method is that the estimators can be obtained using only finite number of iterations. In fact it is shown that starting from the average of periodogram estimators, the proposed algorithm converges in three steps only. One synthesized texture data and one original texture data have been analyzed using the proposed algorithm for illustrative purpose.     

Autoregressive Model with Partial Forgetting within Rao-Blackwellized Particle Filter

The authors are concerned with Bayesian identification and prediction of a nonlinear discrete stochastic process. The fact that a nonlinear process can be approximated by a piecewise linear function advocates the use of adaptive linear models. They propose a linear regression model within Rao-Blackwellized particle filter. The parameters of the linear model are adaptively estimated using a finite mixture, where the weights of components are tuned with a particle filter. The mixture reflects a priori given hypotheses on different scenarios of (expected) parameters' evolution. The resulting hybrid filter locally optimizes the weights to achieve the best fit of a nonlinear signal with a single linear model.     

Uncertain evidence and artificial analysis

A belief function measure of uncertainty, associated with a network based knowledge structure, effectively defines an artificial analyst (e.g., an expert system) capable of making uncertain judgements. In practice, a belief function is typically constructed by combining independent components developed on local areas of the network from inputs such as accepted causal theories, probabilistic judgements by experts, or empirical sample data. Representation of the network in a special form called a ‘tree of cliques’ leads to a locally controlled algorithm that propagates locally defined beliefs through the tree, and fuses the resulting beliefs at the nodes, in such a way as to simultaneously compute marginal beliefs over all nodes of the tree. The paper develops a simple hypothetical example from the field of reliability to illustrate these ideas.     

Generic Identifiability of Linear Structural Equation Models by Ancestor Decomposition

Linear structural equation models, which relate random variables via linear interdependencies and Gaussian noise, are a popular tool for modelling multivariate joint distributions. The models correspond to mixed graphs that include both directed and bidirected edges representing the linear relationships and correlations between noise terms, respectively. A question of interest for these models is that of parameter identifiability, whether or not it is possible to recover edge coefficients from the joint covariance matrix of the random variables. For the problem of determining generic parameter identifiability, we present an algorithm building upon the half‐trek criterion. Underlying our new algorithm is the idea that ancestral subsets of vertices in the graph can be used to extend the applicability of a decomposition technique.     

Smooth backfitting in practice

Summary.  Compared with the classical backfitting of Buja, Hastie and Tibshirani, the smooth backfitting estimator (SBE) of Mammen, Linton and Nielsen not only provides complete asymptotic theory under weaker conditions but is also more efficient, robust and easier to calculate. However, the original paper describing the SBE method is complex and the practical as well as the theoretical advantages of the method have still neither been recognized nor accepted by the statistical community. We focus on a clear presentation of the idea, the main theoretical results and practical aspects like implementation and simplification of the algorithm. We introduce a feasible cross-validation procedure and apply it to the problem of data-driven bandwidth choice for the SBE. By simulations it is shown that the SBE and our cross-validation work very well indeed. In particular, the SBE is less affected by sparseness of data in high dimensional regression problems or strongly correlated designs. The SBE has reasonable performance even in 100-dimensional additive regression problems.     

Local likelihood tracking of fault lines and boundaries

We suggest locally parametric methods for estimating curves, such as boundaries of density supports or fault lines in response surfaces, in a variety of spatial problems. The methods are based on spatial approximations to the local likelihood that the curve passes through a given point in the plane, as a function of that point. The local likelihood might be a regular likelihood computed locally, with kernel weights (e.g. in the case of support boundary estimation) or a local version of a likelihood ratio statistic (e.g. in fault line estimation). In either case, the local likelihood surface represents a function which is relatively large near the target curve, and relatively small elsewhere. Therefore, the curve may be estimated as a ridge line of the surface; we require only a numerical algorithm for tracking the projection of a ridge into the plane. This approach offers several potential advantages over alternative methods. First, the local (log-)likelihood surface can be graphed, and the degree of 'ridginess' assessed visually, to determine how the level of local smoothing should be varied in different spatial locations in order to emphasize the ridge and hence the curve adequately. Secondly, the local likelihood surface does not need to be computed in anything like its entirety; once we have a reasonable approximation to a point on the curve we may track it by numerically 'walking along' the ridge line. Thirdly, the method is appropriate without change for many different types of spatial explanatory variables—gridded, stochastic or otherwise. Three examples are explored in detail; fault lines in response surfaces and in intensity or density surfaces, and boundaries of supports of probability densities.     

Frequency Domain Tests of Semiparametric Hypotheses for Locally Stationary Processes

Abstract.  Many time series in applied sciences obey a time-varying spectral structure. In this article, we focus on locally stationary processes and develop tests of the hypothesis that the time-varying spectral density has a semiparametric structure, including the interesting case of a time-varying autoregressive moving-average (tvARMA) model. The test introduced is based on a L ₂ -distance measure of a kernel smoothed version of the local periodogram rescaled by the time-varying spectral density of the estimated semiparametric model. The asymptotic distribution of the test statistic under the null hypothesis is derived. As an interesting special case, we focus on the problem of testing for the presence of a tvAR model. A semiparametric bootstrap procedure to approximate more accurately the distribution of the test statistic under the null hypothesis is proposed. Some simulations illustrate the behaviour of our testing methodology in finite sample situations.     

A Comparison of Partially Adaptive and Reweighted Least Squares Estimation

The small sample performance of least median of squares, reweighted least squares, least squares, least absolute deviations, and three partially adaptive estimators are compared using Monte Carlo simulations. Two data problems are addressed in the paper: (1) data generated from non-normal error distributions and (2) contaminated data. Breakdown plots are used to investigate the sensitivity of partially adaptive estimators to data contamination relative to RLS. One partially adaptive estimator performs especially well when the errors are skewed, while another partially adaptive estimator and RLS perform particularly well when the errors are extremely leptokur-totic. In comparison with RLS, partially adaptive estimators are only moderately effective in resisting data contamination; however, they outperform least squares and least absolute deviation estimators.