On the Solution to QBD Processes with Finite State Space

Abstract

In this article, we present a solution to a class of Quasi-Birth-and-Death processes with finite state space and show that the stationary probability vector has a matrix geometric representation. We show that such models have a level-dependent rate matrix. The corresponding rate matrix is given explicitly in terms of the model parameters. The resulting closed-form expression is proposed as a basis for efficient calculation of the stationary probabilities. The method proposed in this article can be applied to several queueing systems.     

Building a completely positive factorization

A symmetric matrix of order n is called completely positive if it has a symmetric factorization by means of a rectangular matrix with n columns and no negative entries (a so-called cp factorization), i.e., if it can be interpreted as a Gram matrix of n directions in the positive orthant of another Euclidean space of possibly different dimension. Finding this factor therefore amounts to angle packing and finding an appropriate embedding dimension. Neither the embedding dimension nor the directions may be unique, and so many cp factorizations of the same given matrix may coexist. Using a bordering approach, and building upon an already known cp factorization of a principal block, we establish sufficient conditions under which we can extend this cp factorization to the full matrix. Simulations show that the approach is promising also in higher dimensions.

     

Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction

Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP) to reconstruct such faithful representations. While those SDP models are capable of producing high quality configuration numerically, they suffer two major drawbacks. One is that there exist no theoretically guaranteed bounds on the quality of the configuration. The other is that they are slow in computation when the data points are beyond moderate size. In this paper, we propose a convex optimization model of Euclidean distance matrices. We establish a non-asymptotic error bound for the random graph model with sub-Gaussian noise, and prove that our model produces a matrix estimator of high accuracy when the order of the uniform sample size is roughly the degree of freedom of a low-rank matrix up to a logarithmic factor. Our results partially explain why MVU and MVE often work well. Moreover, the convex optimization model can be efficiently solved by a recently proposed 3-block alternating direction method of multipliers. Numerical experiments show that the model can produce configurations of high quality on large data points that the SDP approach would struggle to cope with.

     

Hypothesis tests for high-dimensional covariance structures

We consider hypothesis testing for high-dimensional covariance structures in which the covariance matrix is a (i) scaled identity matrix, (ii) diagonal matrix, or (iii) intraclass covariance matrix. Our purpose is to systematically establish a nonparametric approach for testing the high-dimensional covariance structures (i)–(iii). We produce a new common test statistic for each covariance structure and show that the test statistic is an unbiased estimator of its corresponding test parameter. We prove that the test statistic establishes the asymptotic normality. We propose a new test procedure for (i)–(iii) and evaluate its asymptotic size and power theoretically when both the dimension and sample size increase. We investigate the performance of the proposed test procedure in simulations. As an application of testing the covariance structures, we give a test procedure to identify an eigenvector. Finally, we demonstrate the proposed test procedure by using a microarray data set.

     

InfoVis Is So Much More: A Comment on Gelman and Unwin and an Invitation to Consider the Opportunities

We propose new tools for visualizing large amounts of functional data in the form of smooth curves. The proposed tools include functional versions of the bagplot and boxplot, which make use of the first two robust principal component scores, Tukey’s data depth and highest density regions.

By-products of our graphical displays are outlier detection methods for functional data. We compare these new outlier detection methods with existing methods for detecting outliers in functional data, and show that our methods are better able to identify outliers.

An R-package containing computer code and datasets is available in the online supplements.     

A linearly convergent iterative method for identifying H-matrices

ABSTRACT

H-matrices play an important role in applied sciences such as numerical analysis and optimization theory. An attractive question is to identify whether a given matrix is an H-matrix. In this paper, we propose a new iterative algorithm for identifying H-matrices. We show that the proposed algorithm has linear convergence and can determine the H-matrix characterization for any given matrix. Its performance is illustrated in a set of numerical tests.     

Robust kernel-based regression with bounded influence for outliers

The kernel-based regression (KBR) method, such as support vector machine for regression (SVR) is a well-established methodology for estimating the nonlinear functional relationship between the response variable and predictor variables. KBR methods can be very sensitive to influential observations that in turn have a noticeable impact on the model coefficients. The robustness of KBR methods has recently been the subject of wide-scale investigations with the aim of obtaining a regression estimator insensitive to outlying observations. However, existing robust KBR (RKBR) methods only consider Y-space outliers and, consequently, are sensitive to X-space outliers. As a result, even a single anomalous outlying observation in X-space may greatly affect the estimator. In order to resolve this issue, we propose a new RKBR method that gives reliable result even if a training data set is contaminated with both Y-space and X-space outliers. The proposed method utilizes a weighting scheme based on the hat matrix that resembles the generalized M-estimator (GM-estimator) of conventional robust linear analysis. The diagonal elements of hat matrix in kernel-induced feature space are used as leverage measures to downweight the effects of potential X-space outliers. We show that the kernelized hat diagonal elements can be obtained via eigen decomposition of the kernel matrix. The regularized version of kernelized hat diagonal elements is also proposed to deal with the case of the kernel matrix having full rank where the kernelized hat diagonal elements are not suitable for leverage. We have shown that two kernelized leverage measures, namely, the kernel hat diagonal element and the regularized one, are related to statistical distance measures in the feature space. We also develop an efficiently kernelized training algorithm for the parameter estimation based on iteratively reweighted least squares (IRLS) method. The experimental results from simulated examples and real data sets demonstrate the robustness of our proposed method compared with conventional approaches.     

Outlier detection of air temperature series data using probabilistic finite state automata‐based algorithm

This article proposes a probability finite state automata‐based algorithm (PFSAA) for detecting outliers of air temperature series data caused by sensor errors. This algorithm first divides the training samples of air temperature series data into subclusters that will be further used to build finite state automata by splitting and combining techniques. Then, it creates a dynamic transition matrix of PFSA based on probability theories. Finally, the outliers of the remaining test samples are detected by PFSAA. The proposed algorithm is quantitatively validated by the reference data and a traditional backpropagation neural net model. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

Model-based two-way clustering of second-level units in ordinal multilevel latent Markov models

In this paper, an ordinal multilevel latent Markov model based on separate random effects is proposed. In detail, two distinct second-level discrete effects are considered in the model, one affecting the initial probability vector and the other affecting the transition probability matrix of the first-level ordinal latent Markov process. To model these separate effects, we consider a bi-dimensional mixture specification that allows to avoid unverifiable assumptions on the random effect distribution and to derive a two-way clustering of second-level units. Starting from a general model where the two random effects are dependent, we also obtain the independence model as a special case. The proposal is applied to data on the physical health status of a sample of elderly residents grouped into nursing homes. A simulation study assessing the performance of the proposal is also included.

     

Levenberg–Marquardt method based on probabilistic Jacobian models for nonlinear equations

In this paper, we propose a Levenberg–Marquardt method based on probabilistic models for nonlinear equations for which the Jacobian cannot be computed accurately or the computation is very expensive. We introduce the definition of the first-order accurate probabilistic Jacobian model, and show how to construct such a model with sample points generated by standard Gaussian distribution. Under certain conditions, we prove that the proposed method converges to a first order stationary point with probability one. Numerical results show the efficiency of the method.

     

Robust algorithms for multiphase regression models

This paper proposes a robust procedure for solving multiphase regression problems that is efficient enough to deal with data contaminated by atypical observations due to measurement errors or those drawn from heavy-tailed distributions. Incorporating the expectation and maximization algorithm with the M-estimation technique, we simultaneously derive robust estimates of the change-points and regression parameters, yet as the proposed method is still not resistant to high leverage outliers we further suggest a modified version by first moderately trimming those outliers and then implementing the new procedure for the trimmed data. This study sets up two robust algorithms using the Huber loss function and Tukey's biweight function to respectively replace the least squares criterion in the normality-based expectation and maximization algorithm, illustrating the effectiveness and superiority of the proposed algorithms through extensive simulations and sensitivity analyses. Experimental results show the ability of the proposed method to withstand outliers and heavy-tailed distributions. Moreover, as resistance to high leverage outliers is particularly important due to their devastating effect on fitting a regression model to data, various real-world applications show the practicability of this approach.     

Parameter estimation under ambiguity and contamination with the spurious model

Recently, we proposed variants as a statistical model for treating ambiguity. If data are extracted from an object with a machine then it might not be able to give a unique safe answer due to ambiguity about the correct interpretation of the object. On the other hand, the machine is often able to produce a finite number of alternative feature sets (of the same object) that contain the desired one. We call these feature sets variants of the object. Data sets that contain variants may be analyzed by means of statistical methods and all chapters of multivariate analysis can be seen in the light of variants. In this communication, we focus on point estimation in the presence of variants and outliers. Besides robust parameter estimation, this task requires also selecting the regular objects and their valid feature sets (regular variants). We determine the mixed MAP-ML estimator for a model with spurious variants and outliers as well as estimators based on the integrated likelihood. We also prove asymptotic results which show that the estimators are nearly consistent.The problem of variant selection turns out to be computationally hard; therefore, we also design algorithms for efficient approximation. We finally demonstrate their efficacy with a simulated data set and a real data set from genetics.     

Embedding Semigroups into Idempotent Generated Ones

We present a concrete model of the embedding due to Pastijn and Yan of a semigroup S into an idempotent generated semigroup now in terms of a Rees matrix semigroup over S¹. The paper starts with a comparison of the two embeddings. Studying the properties of this embedding, we prove that it is functorial. We show that a number of usual semigroup properties is preserved by this embedding, such as periodicity, finiteness, the cryptic property, regularity, complete semisimplicity and various local properties, but complete regularity is not one of them.     

Embedding Semigroups into Idempotent Generated Ones

We present a concrete model of the embedding due to Pastijn and Yan of a semigroup S into an idempotent generated semigroup now in terms of a Rees matrix semigroup over S¹. The paper starts with a comparison of the two embeddings. Studying the properties of this embedding, we prove that it is functorial. We show that a number of usual semigroup properties is preserved by this embedding, such as periodicity, finiteness, the cryptic property, regularity, complete semisimplicity and various local properties, but complete regularity is not one of them.     

Discovering model structure for partially linear models

Partially linear models (PLMs) have been widely used in statistical modeling, where prior knowledge is often required on which variables have linear or nonlinear effects in the PLMs. In this paper, we propose a model-free structure selection method for the PLMs, which aims to discover the model structure in the PLMs through automatically identifying variables that have linear or nonlinear effects on the response. The proposed method is formulated in a framework of gradient learning, equipped with a flexible reproducing kernel Hilbert space. The resultant optimization task is solved by an efficient proximal gradient descent algorithm. More importantly, the asymptotic estimation and selection consistencies of the proposed method are established without specifying any explicit model assumption, which assure that the true model structure in the PLMs can be correctly identified with high probability. The effectiveness of the proposed method is also supported by a variety of simulated and real-life examples.

     

Large deviations of the extreme eigenvalues of random deformations of matrices

Consider a real diagonal deterministic matrix X _n of size n with spectral measure converging to a compactly supported probability measure. We perturb this matrix by adding a random finite rank matrix, with delocalized eigenvectors. We show that the joint law of the extreme eigenvalues of the perturbed model satisfies a large deviation principle in the scale n, with a good rate function given by a variational formula. We tackle both cases when the extreme eigenvalues of X _n converge to the edges of the support of the limiting measure and when we allow some eigenvalues of X _n , that we call outliers, to converge out of the bulk. We can also generalise our results to the case when X _n is random, with law proportional to e ^{?n Tr V(X)} dX, for V growing fast enough at infinity and any perturbation of finite rank.     

Multivariate polynomial regression for identification of chaotic time series

Multivariate polynomial regression was used to generate polynomial iterators for time series exhibiting autocorrelations. A stepwise technique was used to add and remove polynomial terms to ensure the model contained only those terms that produce a statistically significant contribution to the fit. An approach is described in which datasets are divided into three subsets for identification, estimation, and validation. This produces a parsimonious global model that is can greatly reduce the tendency towards undesirable behaviours such as overfitting or instability. The technique was found to be able to identify the nonlinear dynamic behaviour of simulated time series, as reflected in the geometry of the attractor and calculation of multiple Lyapunov exponents, even in noisy systems.

The technique was applied to times series data obtained from simulations of the Lorenz and Mackey – Glass equations with and without measurement noise. The model was also used to determine the embedding dimension of the Mackey – Glass equation.     

A novel robust principal component analysis method for image and video processing

The research on the robust principal component analysis has been attracting much attention recently. Generally, the model assumes sparse noise and characterizes the error term by the λ₁-norm. However, the sparse noise has clustering effect in practice so using a certain λ_p-norm simply is not appropriate for modeling. In this paper, we propose a novel method based on sparse Bayesian learning principles and Markov random fields. The method is proved to be very effective for low-rank matrix recovery and contiguous outliers detection, by enforcing the low-rank constraint in a matrix factorization formulation and incorporating the contiguity prior as a sparsity constraint. The experiments on both synthetic data and some practical computer vision applications show that the novel method proposed in this paper is competitive when compared with other state-of-the-art methods.     

线性模型参数的稳健化有偏估计

本文讨论复共线性和粗差同时存在时线性模型的参数估计问题,基于等价权原理提出了一个稳健有偏估计类（稳健压缩估计）,并且建立了稳健压缩估计的计算方法,为了满足实际问题的需要,构造了许多很有意义的稳健有偏估计,例如稳健岭估计、稳健主成分估计,稳健组合主成估计、稳健单参数主成分估计、稳健根方估计等等,最后通过一个算例表明,本文提出的稳健有偏估计具有既可克服复共线性影响又可抵抗粗差干扰的良好性质。     

Multiple outlier detection in multivariate data using self-organizing maps title

Summary  The problem of detection of multidimensional outliers is a fundamental and important problem in applied statistics. The unreliability of multivariate outlier detection techniques such as Mahalanobis distance and hat matrix leverage has led to development of techniques which have been known in the statistical community for well over a decade. The literature on this subject is vast and growing. In this paper, we propose to use the artificial intelligence technique ofself-organizing map (SOM) for detecting multiple outliers in multidimensional datasets. SOM, which produces a topology-preserving mapping of the multidimensional data cloud onto lower dimensional visualizable plane, provides an easy way of detection of multidimensional outliers in the data, at respective levels of leverage. The proposed SOM based method for outlier detection not only identifies the multidimensional outliers, it actually provides information about the entire outlier neighbourhood. Being an artificial intelligence technique, SOM based outlier detection technique is non-parametric and can be used to detect outliers from very large multidimensional datasets. The method is applied to detect outliers from varied types of simulated multivariate datasets, a benchmark dataset and also to real life cheque processing dataset. The results show that SOM can effectively be used as a useful technique for multidimensional outlier detection.