Robust support vector regression with generic quadratic nonconvex ε-insensitive loss

In this paper, we propose a robust support vector regression with a novel generic nonconvex quadratic ε-insensitive loss function. The proposed method is robust to outliers or noise since it can adaptively control the loss value and decrease the negative influence of outliers or noise on the decision function by adjusting the elastic interval parameter and adaptive robustification parameter. Given the nature of the nonconvexity of the optimization problem, a concave-convex programming procedure is employed to solve the proposed problem. Experimental results on two artificial data sets and three real-world data sets indicate that the proposed method outperforms support vector regression, L₁-norm support vector regression, least squares support vector regression, robust least squares support vector regression, and support vector regression with the Huber loss function on both robustness and generalization ability.     

Robust goodness-of-fit tests for AR(p) models based onL 1-norm fitting

A robustified residual autocorrelation is defined based onL ₁-regression. Under very general conditions, the asymptotic distribution of the robust residual autocorrelation is obtained. A robustified portmanteau statistic is then constructed which can be used in checking the goodness-of-fit of AR(p) models when usingL ₁-norm fitting. Empirical results show thatL ₁-norm estimators and the proposed portmanteau statistic are robust against outliers, error distributions, and accuracy for a given finite sample. Project supported by the Foundation of State Educational Commission and a research grant from the Doctoral Program Foundation of China (#97000139).     

ERROR ESTIMATES FOR SPARSE OPTIMAL CONTROL PROBLEMS BY PIECEWISE LINEAR FINITE ELEMENT APPROXIMATION

Optimization problems with L¹-control cost functional subject to an elliptic partial differential equation(PDE)are considered.However,different from the finite dimensiona l¹-regularization optimization,the resulting discretized L¹norm does not have a decoupled form when the standard piecewise linear finite element is employed to discretize the continuous problem.A common approach to overcome this difficulty is employing a nodal quadrature formula to approximately discretize the L¹-norm.In this paper,a new discretized scheme for the L¹-norm is presented.Compared to the new discretized scheme for L¹-norm with the nodal quadrature formula,the advantages of our new discretized scheme can be demonstrated in terms of the order of approximation.Moreover,finite element error estimates results for the primal problem with the new discretized scheme for the L¹-norm are provided,which confirms that this approximation scheme will not change the order of error estimates.To solve the new discretized problem,a symmetric Gauss-Seidel based majorized accelerated block coordinate descent(sGS-mABCD)method is introduced to solve it via its dual.The proposed sGS-mABCD algorithm is illustrated at two numerical examples.Numerical results not only confirm the finite element error estimates,but also show that our proposed algorithm is efficient.     

Robust regression for mixed Poisson–Gaussian model

This paper focuses on efficient computational approaches to compute approximate solutions of a linear inverse problem that is contaminated with mixed Poisson–Gaussian noise, and when there are additional outliers in the measured data. The Poisson–Gaussian noise leads to a weighted minimization problem, with solution-dependent weights. To address outliers, the standard least squares fit-to-data metric is replaced by the Talwar robust regression function. Convexity, regularization parameter selection schemes, and incorporation of non-negative constraints are investigated. A projected Newton algorithm is used to solve the resulting constrained optimization problem, and a preconditioner is proposed to accelerate conjugate gradient Hessian solves. Numerical experiments on problems from image deblurring illustrate the effectiveness of the methods.     

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.     

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.     

Robust estimation in generalized semiparametric mixed models for longitudinal data

In this paper, we consider robust generalized estimating equations for the analysis of semiparametric generalized partial linear mixed models (GPLMMs) for longitudinal data. We approximate the non-parametric function in the GPLMM by a regression spline, and make use of bounded scores and leverage-based weights in the estimating equation to achieve robustness against outliers and influential data points, respectively. Under some regularity conditions, the asymptotic properties of the robust estimators are investigated. To avoid the computational problems involving high-dimensional integrals in our estimators, we adopt a robust Monte Carlo Newton-Raphson (RMCNR) algorithm for fitting GPLMMs. Small simulations are carried out to study the behavior of the robust estimates in the presence of outliers, and these estimates are also compared to their corresponding non-robust estimates. The proposed robust method is illustrated in the analysis of two real data sets.     

Robust multicategory support vector machines using difference convex algorithm

The support vector machine (SVM) is one of the most popular classification methods in the machine learning literature. Binary SVM methods have been extensively studied, and have achieved many successes in various disciplines. However, generalization to multicategory SVM (MSVM) methods can be very challenging. Many existing methods estimate k functions for k classes with an explicit sum-to-zero constraint. It was shown recently that such a formulation can be suboptimal. Moreover, many existing MSVMs are not Fisher consistent, or do not take into account the effect of outliers. In this paper, we focus on classification in the angle-based framework, which is free of the explicit sum-to-zero constraint, hence more efficient, and propose two robust MSVM methods using truncated hinge loss functions. We show that our new classifiers can enjoy Fisher consistency, and simultaneously alleviate the impact of outliers to achieve more stable classification performance. To implement our proposed classifiers, we employ the difference convex algorithm for efficient computation. Theoretical and numerical results obtained indicate that for problems with potential outliers, our robust angle-based MSVMs can be very competitive among existing methods.     

Influence measures and robust estimators of dependence in multivariate extremes

We develop a simple influence measure to assess whether Bayesian estimators in multivariate extreme value problems are sensitive to outliers. The proposed measure is easy to compute by importance sampling and successfully captures two effects on the functional: the “data effect” and the “parameter uncertainty effect”. We also propose a new Bayesian estimator which is easy to implement and is robust. The methods are tested and illustrated using simulated data and then applied to stock market data.     

A Class of Robust Principal Component Vectors

This paper is concerned with a study of robust estimation in principal component analysis. A class of robust estimators which are characterized as eigenvectors of weighted sample covariance matrices is proposed, where the weight functions recursively depend on the eigenvectors themselves. Also, a feasible algorithm based on iterative reweighting of the covariance matrices is suggested for obtaining these estimators in practice. Statistical properties of the proposed estimators are investigated in terms of sensitivity to outliers and relative efficiency via their influence functions, which are derived with the help of Stein's lemma. We give a simple condition on the weight functions which ensures robustness of the estimators. The class includes, as a typical example, a method by the self-organizing rule in the neural computation. A numerical experiment is conducted to confirm a rapid convergence of the suggested algorithm.     

Robust optimal control of stochastic hyperelastic materials

Soft robots are highly nonlinear systems made of deformable materials such as elastomers, fluids and other soft matter, that often exhibit intrinsic uncertainty in their elastic responses under large strains due to microstructural inhomogeneity. These sources of uncertainty might cause a change in the dynamics of the system leading to a significant degree of complexity in its controllability. This issue poses theoretical and numerical challenges in the emerging field of optimal control of stochastic hyperelasticity. This paper states and solves the robust averaged control in stochastic hyperelasticity where the underlying state system corresponds to the minimization of a stochastic polyconvex strain energy function. Two bio-inspired optimal control problems under material uncertainty are addressed. The expected value of the L²-norm to a given target configuration is minimized to reduce the sensitivity of the spatial configuration to variations in the material parameters. The existence of optimal solutions for the robust averaged control problem is proved. Then the problem is solved numerically by using a gradient-based method. Two numerical experiments illustrate both the performance of the proposed method to ensure the robustness of the system and the significant differences that may occur when uncertainty is incorporated in this type of control problems.     

Massive Data Classification via Unconstrained Support Vector Machines

A highly accurate algorithm, based on support vector machines formulated as linear programs (Refs. 1–2), is proposed here as a completely unconstrained minimization problem (Ref. 3). Combined with a chunking procedure (Ref. 4), this approach, which requires nothing more complex than a linear equation solver, leads to a simple and accurate method for classifying million-point datasets. Because a 1-norm support vector machine underlies the proposed approach, the method suppresses input space features as well. A state-of-the-art linear programming package (CPLEX, Ref. 5) fails to solve problems handled by the proposed algorithm.This research was supported by National Science Foundation Grants CCR-0138308 and IIS-0511905.     

On scenario aggregation to approximate robust combinatorial optimization problems

As most robust combinatorial min–max and min–max regret problems with discrete uncertainty sets are NP-hard, research in approximation algorithm and approximability bounds has been a fruitful area of recent work. A simple and well-known approximation algorithm is the midpoint method, where one takes the average over all scenarios, and solves a problem of nominal type. Despite its simplicity, this method still gives the best-known bound on a wide range of problems, such as robust shortest path or robust assignment problems. In this paper, we present a simple extension of the midpoint method based on scenario aggregation, which improves the current best K-approximation result to an \((\varepsilon K)\)-approximation for any desired \(\varepsilon > 0\). Our method can be applied to min–max as well as min–max regret problems.     

A Second Order Nonconforming Triangular Mixed Finite Element Scheme for the Stationary Navier-Stokes Equations

In this paper,a nonconforming triangular mixed finite element scheme with second order convergence behavior is proposed for the stationary Navier-Stokes equations.The new nonconforming triangular element is taken as approximation space for the velocity and the linear element for the pressure.The convergence analysis is presented and optimal error estimates of both broken H1-norm and L2-norm for velocity as well as the L2-norm for the pressure are derived.     

Robust Model Averaging Method Based on LOF Algorithm

Model averaging is a good alternative to model selection, which can deal with the uncertainty from model selection process and make full use of the information from various candidate models. However, most of the existing model averaging criteria do not consider the influence of outliers on the estimation procedures. The purpose of this paper is to develop a robust model averaging approach based on the local outlier factor (LOF) algorithm which can downweight the outliers in the covariates. Asymptotic optimality of the proposed robust model averaging estimator is derived under some regularity conditions. Further, we prove the consistency of the LOF-based weight estimator tending to the theoretically optimal weight vector. Numerical studies including Monte Carlo simulations and a real data example are provided to illustrate our proposed methodology.     

Proximity algorithms for the L1/TV image denoising model

This paper introduces a proximity operator framework for studying the L1/TV image denoising model which minimizes the sum of a data fidelity term measured in the ?¹-norm and the total-variation regularization term. Both terms in the model are non-differentiable. This causes algorithmic difficulties for its numerical treatment. To overcome the difficulties, we formulate the total-variation as a composition of a convex function (the ?¹-norm or the ?²-norm) and the first order difference operator, and then express the solution of the model in terms of the proximity operator of the composition. By developing a “chain rule” for the proximity operator of the composition, we identify the solution as fixed point of a nonlinear mapping expressed in terms of the proximity operator of the ?¹-norm or the ?²-norm, each of which is explicitly given. This formulation naturally leads to fixed-point algorithms for the numerical treatment of the model. We propose an alternative model by replacing the non-differentiable convex function in the formulation of the total variation with its differentiable Moreau envelope and develop corresponding fixed-point algorithms for solving the new model. When partial information of the underlying image is available, we modify the model by adding an indicator function to the minimization functional and derive its corresponding fixed-point algorithms. Numerical experiments are conducted to test the approximation accuracy and computational efficiency of the proposed algorithms. Also, we provide a comparison of our approach to two state-of-the-art algorithms available in the literature. Numerical results confirm that our algorithms perform favorably, in terms of PSNR-values and CPU-time, in comparison to the two algorithms.     

Robust clustering around regression lines with high density regions

Robust methods are needed to fit regression lines when outliers are present. In a clustering framework, outliers can be extreme observations, high leverage points, but also data points which lie among the groups. Outliers are also of paramount importance in the analysis of international trade data, which motivate our work, because they may provide information about anomalies like fraudulent transactions. In this paper we show that robust techniques can fail when a large proportion of non-contaminated observations fall in a small region, which is a likely occurrence in many international trade data sets. In such instances, the effect of a high-density region is so strong that it can override the benefits of trimming and other robust devices. We propose to solve the problem by sampling a much smaller subset of observations which preserves the cluster structure and retains the main outliers of the original data set. This goal is achieved by defining the retention probability of each point as an inverse function of the estimated density function for the whole data set. We motivate our proposal as a thinning operation on a point pattern generated by different components. We then apply robust clustering methods to the thinned data set for the purposes of classification and outlier detection. We show the advantages of our method both in empirical applications to international trade examples and through a simulation study.     

Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs

A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0255.     

A robust regression based on weighted LSSVM and penalized trimmed squares

Least squares support vector machine (LS-SVM) for nonlinear regression is sensitive to outliers in the field of machine learning. Weighted LS-SVM (WLS-SVM) overcomes this drawback by adding weight to each training sample. However, as the number of outliers increases, the accuracy of WLS-SVM may decrease. In order to improve the robustness of WLS-SVM, a new robust regression method based on WLS-SVM and penalized trimmed squares (WLSSVM–PTS) has been proposed. The algorithm comprises three main stages. The initial parameters are obtained by least trimmed squares at first. Then, the significant outliers are identified and eliminated by the Fast-PTS algorithm. The remaining samples with little outliers are estimated by WLS-SVM at last. The statistical tests of experimental results carried out on numerical datasets and real-world datasets show that the proposed WLSSVM–PTS is significantly robust than LS-SVM, WLS-SVM and LSSVM–LTS.