Search

Restoring the controllability of networked control systems is a fundamental issue that needs to be settled, especially when malicious attacks or malfunctions occur. Previous studies tried to address such an issue by adding extra driver nodes or rewiring edges, which will inevitably change the original network structure. In this paper, an algorithm to restore the controllability of networked systems while preserving the integrity of the original network structure is proposed. Specifically, a static uncontrollable network will be transformed into a controllable temporal network by means of the cactus‐based segmentation method. The original problem will be equivalent to the classical set cover problem, which is known to be NP‐Hard, if the least number of segmentations is considered. An approximation algorithm with polynomial time complexity is proposed and it is proved that the solution to the problem is two‐optimal. Finally, simulations are carried out to verify the effectiveness and feasibility of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a numerical method for solving nonlinear quadratic optimal control problems with inequality constraints is presented. The method is based upon cardinal Hermite interpolant multiscaling function approximation. The properties of these multiscaling functions are presented first. These properties are then utilized to reduce the solution of the nonlinear constrained optimal control to a nonlinear programming one, to which existing algorithms may be applied. Illustrative examples are included to demonstrate the efficiency and applicability of the technique. [ABSTRACT FROM AUTHOR]

In this paper, a new recursive algorithm is proposed for tracking parameter changes of a time-varying linear system. Since a bounded error approach is adopted for both modeling the measurement noise and the parameter change process, the problem addressed amounts to the design of a procedure for updating an estimate of the feasible parameter set. The approximating regions considered are in the form of outbounding orthotopes. The novelty of the approach lies in the use of a selection technique which keeps track only of a special subset of the constraints defining the feasible set. These inequalities represent the binding constraints of suitable linear programs of limited size. The devised algorithm is tested on several numerical examples, showing remarkable performance both in computational burden, which is comparable to that of classical recursive estimation algorithms like recursive least squares (RLS) and quality of the set estimate as compared to alternative techniques available in the literature. [ABSTRACT FROM AUTHOR]

This paper shows that two complex coefficient transfer functions can be realized by a single hypercomplex coefficient network, utilizing all four outputs of the hypercomplex network. The realization is considered for the case where the two arbitrary complex coefficient transfer functions do and do not have a common denominator. It is shown that the transfer functions can he realized by the hypercomplex coefficient network of the same order in the former case and by the hypercomplex coefficient network with the half-order in the latter case. The realization of the transfer functions with the common denominator is interesting, but the general method to derive the transfer functions is not known. From such a viewpoint, this paper proposes the discrete-type Kautz approximation with the positive frequency as the domain of approximation, including the optimal pole determination algorithm. By this approach, two complex coefficient transfer functions with an n-th-order common denominator are derived from the two 2n-th-order real or complex coefficient transfer functions. The method can be considered as one that simultaneously approximates the amplitude and the phase. The proposed approximation method is an approximation only for the positive frequency domain, and the property of the analytic signal that the negative frequency component is zero can be utilized. As a result, the method proposed in this paper has the advantages that the degree of freedom in the filter design is enhanced and the sampling frequency can be halved. In addition, the network structure can be simplified. [ABSTRACT FROM AUTHOR]

This paper proposes a first-order algorithm for unconstrained nonlinear optimal control problems based on the fixed point theorem. The method has the following features: (a) the algorithm is simple; (b) unlike second-order algorithms, the choice of the first approximation is less critical; and (c) unlike gradient methods, experimental selections of parameters during iterative calculations are not required. This paper also describes the conditions of convergence of the algorithm in the space of continuous functions, and the optimality of a solution derived. [ABSTRACT FROM AUTHOR]

This paper is concerned with the rejection of sinusoidal disturbances of unknown frequency acting at the output of unknown plants. Disturbance rejection is based on an adaptive harmonic steady-state ( ADHSS) algorithm combined with a magnitude/phase locked-loop ( MPLL) frequency estimator. The harmonic steady-state method assumes that the plant can be approximated by its steady-state frequency response. For high-order plants such as those encountered in active noise and vibration control ( ANVC), this assumption greatly reduces the number of parameters and enables online estimation of the plant response using simple algorithms. The paper shows that when the MPLL is integrated with the ADHSS algorithm, the two components work together in such a way that the control input does not prevent frequency tracking by the MPLL, and so that the order of the ADHSS can be reduced. Thus, the addition of the MPLL allows disturbances of unknown frequency to be considered without significantly increasing the complexity of the original ADHSS. After analyzing the reduced-order ADHSS in the ideal case, the equations describing the complete system are considered. The theory of averaging is used to gain insight into the steady-state behavior of the algorithm. It is found that the system has a two-dimensional equilibrium surface such that the disturbance is cancelled exactly. A subset of the surface is proved to be locally stable. Extensive active noise control experiments demonstrate the performance of the algorithm, even when disturbance and plant parameters are changing. [ABSTRACT FROM AUTHOR]

SUMMARY A new multi-scale image segmentation algorithm based on support vector machine (SVM) approximation criteria has been discussed in this paper. Most current multi-scale image segmentation algorithms are based on the restricted empirical risk minimization, and the approximation of multi-scale image segmentation was poor. As the SVM theory was one based on the structural risk minimization, the best approximation results could be reached. So, it was combined with multi-scale image segmentation algorithms, and one-image multi-resolution analysis approximation algorithms based on the SVM theory were presented in this paper, which could obtain more accurate multi-scale image segmentation. By numerical results, the algorithm was further verified that more accurate image segmentation results were unfolded. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Recognizing characters in scene images suffering from perspective distortion is a challenge. Although there are some methods to overcome this difficulty, they are time-consuming. In this paper, we propose a set of affine-invariant features and a new recognition scheme called 'progressive removing' that can help reduce the processing time. Progressive removing gradually removes less feasible categories and skew angles by using multiple classifiers. We observed that progressive removing and the use of the affine invariant features reduced the processing time by about 60% in comparison to a trivial algorithm without decreasing the recognition rate. © 2012 Wiley Periodicals, Inc. Electr Eng Jpn, 180(2): 55-63, 2012; Published online in Wiley Online Library (). DOI 10.1002/eej.22276 [ABSTRACT FROM AUTHOR]

We envision a large-scale multiclass optical network in which lightpaths are dynamically set up and terminated between source and destination nodes and these lightpaths traverse through a number of interconnected WDM networks in different administrative domains. In this envisioned multiclass network, calls are classified by the number of wavelengths demanded per call and the statistics of call holding times (or service subscription periods). We present an approximation method for the performance analysis of such a large-scale multiclass optical WDM network. We model the large-scale optical network as a two-level hierarchical multiclass loss network; the lower level of hierarchy consists of individual optical WDM networks (network segments). Each of these network segments is abstracted to a logical node at the higher level of hierarchy, and these logical nodes are connected to each other through logical links. We also assume that the call processing mechanism in this large-scale optical network resorts to hierarchical routing. The algorithms presented in this paper compute per-class end-to-end approximate blocking probabilities. Our experiments show that the simulation results match closely with the results of the proposed analytical approximation methods, thus validating the proposed methodology. Copyright © 2010 John Wiley & Sons, Ltd. For multiclass optical WDM networks, we developed and tested novel algorithms that efficiently compute approximate perclass blocking probabilities by employing reduced-load approximation and fixedpoint iterations, and our earlier results showed good performance of this methodology. In the present paper, we tailor this methodology for large-scale multiclass optical WDM networks that use hierarchical routing. Then, through our extensive simulation results we show that the proposed methodology of approximation is useful even for large-scale hierarchical WDM networks. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This article develops a simple approach to solving continuous-time portfolio choice problems. Portfolio problems for which no closed-form solutions are available may be handled by this technique, which substitutes the numerical solution of partial differential equations with a non-linear numerical algorithm approximating the solution. This paper complements the wide literature in economics on the solution of dynamic problems in discrete time using projection methods. Our approach extends the approximation function to power forms, which are shown to fit finance type problems well. The algorithm is parsimonious, and is first illustrated by solving two basic examples, first, the standard Merton problem, and second, a jump-diffusion problem. Then, we demonstrate that the model is easy to implement on a larger scale, by optimizing a portfolio of six stock indexes, and stochastic volatility driven by two correlated state variables. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In the field of system modeling, circuit synthesis and filter design, it is very important to approximate a given characteristic function by a rational function of an appropriate order. Padé approximation has been known for a long time and is one of the rational function approximation methods used extensively because of its simplicity. This paper proposes to investigate N-point Padé approximation, from the system-theoretic viewpoint. The N-point Padé approximation is a rational function interpolation including the derivative of arbitrary order and, compared to regular Padé approximation and rational Hermite interpolation. In this paper we discuss the following subjects on rational function approximation of given characteristic function: its explicit form, minimal order realization problem, Nuttall's compact form, its relation to continued fractions, and the numerical efficient iterative algorithm. These are more general discussions, even including regular Padé approximation. Also, we give numerical results of the approximation of a transfer function for continuous and discrete systems as an example of application of N-point Padé approximation. [ABSTRACT FROM AUTHOR]

This paper proposes a method for the representation of functions describing a measured geophysical property (via sparsely scattered ordensely defined point data) by tensor and triple product interval B-splines (IBS). The spline representation facilitates archiving, data storage reduction, visualization and more general high-level interrogation. Interval methods allow Tor the representation of the function values together with their uncertainty. The uncertainty is introduced, for example, because the measurement (or dependent variable) or the location of the sensor (the independent variable(s)) is known only to a finite precision. In this paper, we present algorithms for the creation of IBS geometries based on minimization with linear constraints and we illustrate the method using geophysical ocean data and their interrogation. [ABSTRACT FROM AUTHOR]

This paper considers an unknown nonlinear static system with an adjustable parameter (input parameter). The problem is to find the least-square approximation input parameter. A recursive algorithm is proposed that estimates this least-square approximation parameter without an identification of the system. An output of the system is observed under a noisy environment. Suppose that the dimension of the output is equal to that of the input. In this case, the system characteristic can be regarded as a regression function, hence a recursive algorithm that can be constructed that minimizes tile difference between the expectation of the output and a desired value of the output by using the stochastic approximation method or the adaptive Robbins-Monro procedure. On the other hand, if the dimension of the output is greater than that of the input, the regression equation has no solution. Therefore, the usual stochastic approximation method or the adaptive Robbins-Monro procedure cannot be used. The algorithm proposed in this paper estimates the least-square approximation input parameter that minimizes the squared error of the output. Especially, this algorithm agrees with the usual adaptive Rohbins-Monro procedure if the dimension of the output is equal to that of the input. Some numerical simulations ale shown and the availability of the algorithm presented herein is confirmed. [ABSTRACT FROM AUTHOR]

Alternating least squares (ALS) is often considered the workhorse algorithm for computing the rank- R canonical tensor approximation, but for certain problems, its convergence can be very slow. The nonlinear conjugate gradient (NCG) method was recently proposed as an alternative to ALS, but the results indicated that NCG is usually not faster than ALS. To improve the convergence speed of NCG, we consider a nonlinearly preconditioned NCG (PNCG) algorithm for computing the rank- R canonical tensor decomposition. Our approach uses ALS as a nonlinear preconditioner in the NCG algorithm. Alternatively, NCG can be viewed as an acceleration process for ALS. We demonstrate numerically that the convergence acceleration mechanism in PNCG often leads to important pay-offs for difficult tensor decomposition problems, with convergence that is significantly faster and more robust than for the stand-alone NCG or ALS algorithms. We consider several approaches for incorporating the nonlinear preconditioner into the NCG algorithm that have been described in the literature previously and have met with success in certain application areas. However, it appears that the nonlinearly PNCG approach has received relatively little attention in the broader community and remains underexplored both theoretically and experimentally. Thus, this paper serves several additional functions, by providing in one place a concise overview of several PNCG variants and their properties that have only been described in a few places scattered throughout the literature, by systematically comparing the performance of these PNCG variants for the tensor decomposition problem, and by drawing further attention to the usefulness of nonlinearly PNCG as a general tool. In addition, we briefly discuss the convergence of the PNCG algorithm. In particular, we obtain a new convergence result for one of the PNCG variants under suitable conditions, building on known convergence results for non-preconditioned NCG. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The most popular algorithm for aligning of three‐dimensional point data is the iterative closest point (ICP). In this paper, a new algorithm for orthogonal registration of point clouds based on the point‐to‐plane ICP algorithm is proposed. The algorithm consists of three steps: first, a matrix of affine transformation between two given point clouds are calculated; second, the affine transformation matrix is projected onto the manifold SO(3) of orthonormal matrices; finally, a translation vector is reestimated. The proposed algorithm does not require an approximate initial estimate. At each iterative step of the ICP algorithm, an approximated closed‐form solution for the orthogonal transformation is derived. The performance of the proposed algorithm is compared with that of common algorithms for the geometrical transformations estimation. [ABSTRACT FROM AUTHOR]

Extracting a faithful and compact representation of an animated surface mesh is an important problem for computer graphics. However, the surface‐based methods have limited approximation power for volume preservation when the animated sequences are extremely simplified. In this paper, we introduce Deformable Medial Axis Transform (DMAT), which is deformable medial mesh composed of a set of animated spheres. Starting from extracting an accurate and compact representation of a static MAT as the template and partitioning the vertices on the input surface as the correspondences for each medial primitive, we present a correspondence‐based approximation method equipped with an As‐Rigid‐As‐Possible (ARAP) deformation energy defined on medial primitives. As a result, our algorithm produces DMAT with consistent connectivity across the whole sequence, accurately approximating the input animated surfaces. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, a rapid iterative algorithm is proposed to find robust approximations for the inverse of nonsingular matrices. The analysis of convergence reveals that this high-order method possesses eighth-order convergence. The interesting point is that, this rate is attained using less number of matrix-by-matrix multiplications in contrast to the existing methods of the same type in the literature. The extension of the method for finding Moore-Penrose inverse of singular or rectangular matrices is also presented. Numerical comparisons will be given to show the applicability, stability and consistency of the new scheme by paying special attention on the computational time. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The article presents the response of Abou El-Makarim Aboueissa to the comments made by Igor Kovasev about his paper describing a proposed algorithm to approximate the maximum likelihood estimates (MLE) equations using a computer algorithm. He offers some clarifications about a new computer algorithm for obtaining the Cohen's MLE which does not require auxiliary tables. He argues that equations 12 and 13 as explained in the paper are equal.

SUMMARY In this paper, we revisit the steady-state solution method for Markov Regenerative Processes (MRP) proposed in the work by German. This method solves the embedded Markov chain P of the MRP without storing the matrix P explicitly. We address three issues left open in German's Work: 1) the solution method is restricted to Power method; 2) it has been defined only for ergodic MRPs; and 3) no preconditioning is available to speed-up the computation. This paper discusses how to lift these limitations by extending the algorithm to preconditioned Krylov-subspace methods and by generalizing it to the non-ergodic case. An MRP-specific preconditioner is also proposed, which is built from a sparse approximation of the MRP matrix, computed via simulation. An experimental assessment of the proposed preconditioner is then provided. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We study large-scale, continuous-time linear time-invariant control systems with a sparse or structured state matrix and a relatively small number of inputs and outputs. The main contributions of this paper are numerical algorithms for the solution of large algebraic Lyapunov and Riccati equations and linear-quadratic optimal control problems, which arise from such systems. First, we review an alternating direction implicit iteration-based method to compute approximate low-rank Cholesky factors of the solution matrix of large-scale Lyapunov equations, and we propose a refined version of this algorithm. Second, a combination of this method with a variant of Newton's method (in this context also called Kleinman iteration) results in an algorithm for the solution of large-scale Riccati equations. Third, we describe an implicit version of this algorithm for the solution of linear-quadratic optimal control problems, which computes the feedback directly without solving the underlying algebraic Riccati equation explicitly. Our algorithms are efficient with respect to both memory and computation. In particular, they can be applied to problems of very large scale, where square, dense matrices of the system order cannot be stored in the computer memory. We study the performance of our algorithms in numerical experiments. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper extends the weighted low rank approximation (WLRA) approach to linearly structured matrices. In the case of Hankel matrices with a special block structure, an equivalent unconstrained optimization problem is derived and an algorithm for solving it is proposed. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Gasunie buys and sells gas. This paper is about calculating the failure rate of the gas transport system of Gasunie in the Netherlands. The pipes in the network are connected at certain stations which may operate at degraded levels due to technical problems. The transport system, modelled as an optimization problem, needs to be checked for feasibility for every configuration of the degradation levels at all stations in order to see whether the system fails or not. The discrete probability distributions of the degradation levels at every station in the network are given. The number of possible combinations of degradation levels is huge and the computations for the feasibility of the gas network are computer-intensive. This paper presents a new algorithm for approximating this rate and it is parsimonious in actually checking for feasibility. [ABSTRACT FROM AUTHOR]

In this paper, we study an a posteriori error indicator introduced in E. Dari, R.G. Durán, and C. Padra, Appl. Numer. Math., 2012, for the approximation of the Laplace eigenvalue problem with Crouzeix-Raviart nonconforming finite elements. In particular, we show that the estimator is robust also in presence of eigenvalues of multiplicity greater than one. Some numerical examples confirm the theory and illustrate the convergence of an adaptive algorithm when dealing with multiple eigenvalues. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, two accelerated divide-and-conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N2r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy-like matrices and are off-diagonally low-rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low-rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off-diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. [ABSTRACT FROM AUTHOR]

While it is usually not difficult to compute principal curvatures of a smooth surface of sufficient differentiability, it is a rather difficult task when only a polygonal approximation of the surface is available, because of the inherent ambiguity of such representation. A number of different approaches has been proposed in the past that tackle this problem using various techniques. Most papers tend to focus on a particular method, while an comprehensive comparison of the different approaches is usually missing. We present results of a large experiment, involving both common and recently proposed curvature estimation techniques, applied to triangle meshes of varying properties. It turns out that none of the approaches provides reliable results under all circumstances. Motivated by this observation, we investigate mesh statistics, which can be computed from vertex positions and mesh connectivity information only, and which can help in deciding which estimator will work best for a particular case. Finally, we propose a meta-estimator, which makes a choice between existing algorithms based on the value of the mesh statistics, and we demonstrate that such meta-estimator, despite its simplicity, provides considerably more robust results than any existing approach. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the quadratic cost 0–1 mixed integer programming problem. First, we formulate the problem as a two-level programming problem that consists of a lower-level continuous quadratic programming problem with 0–1 variables fixed and an upper-level nonlinear 0–1 programming problem. We propose an approximation algorithm for solving the upper-level 0–1 programming problem. This algorithm approximately solves a subproblem obtained by linearizing the objective function at a current point. To guarantee the descent property of the generated sequence, we use a trust region technique that adaptively controls a penalty constant in the objective function of the subproblem. To solve subproblems, we apply a Hopfield network with a new transition rule that allows a temporary state transition based on the variable depth method. Some numerical experiments for a location-transportation problem with quadratic costs indicate that the proposed algorithm is practically effective. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(6): 9–17, 1999 [ABSTRACT FROM AUTHOR]

The local neighborhood search method is one of the efficient strategies for approximation algorithms for many combinatorial problems contained in the NP-complete class. To evaluate this kind of approximation method, the average case analysis is considered to be better than the worst case analysis. This paper considers the 0 - 1 knapsack problem, one of the representative problems included in the NP-complete class of problems. Then the behavior of the local neighborhood search method is analyzed for the problem using a flow model we proposed on a previous occasion. By comparing the analytical result for the 0 - 1 knapsack problem instances with up to 200 variables, we show that the flow model is useful as the means of analyzing the behavior of the local neighborhood search method for the 0 - 1 knapsack problem. [ABSTRACT FROM AUTHOR]

In this paper, a new Chebyshev approximation (amplitude and phase simultaneous approximation) method for IIR digital filters is proposed. The proposed algorithm is based on the Remez algorithm. By solving the eigenvalue problem at each iteration, the frequency characteristic of the filter is interpolated so that the error function in the complex domain is made with equal ripples. Since the previously proposed amplitude and phase simultaneous approximation methods for the IIR digital filters are based on the nonlinear equation, they all require substantial computation. On the other hand, the present method is extremely simple and the amount of computation can be reduced significantly. Nevertheless, the performance equal to or more than the conventional one can be obtained. Further, the present method can be applied not only for the real coefficient filters but also for the characteristic approximations limited to the positive frequency range. Hence, a further reduction of the filter order needed for signal processing can be attempted. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to reappraise the linearizing methods frequently used to solve inverse scattering problems. We describe inversion algorithms based on the Born and the Rytov approximations and the nature of the distortions obtained in the reconstructions when using them. We present extensions of these methods, namely, the distorted-wave Born and the distorted-wave Rytov approximations, which incorporate prior knowledge about part of the scattering structure. A method for inverting scattered held data using these distorted-wave approximations is described, which retains the computational simplicity of the Born and the Rytov techniques. Some examples of their use with simulated and real data are given. A further extension of our distorted-wave formalism, which leads to improvements of the reconstructed image, is suggested. This entails a spectral estimation procedure also based on the incorporation of prior knowledge about the scatterer. This spectral estimation procedure can be useful for interpolation of scattered field data as well as resolution enhancement. [ABSTRACT FROM AUTHOR]

The input variable selection problem has recently garnered much interest in the time series modeling community, especially within water resources applications, demonstrating that information theoretic (nonlinear)-based input variable selection algorithms such as partial mutual information (PMI) selection (PMIS) provide an improved representation of the modeled process when compared to linear alternatives such as partial correlation input selection (PCIS). PMIS is a popular algorithm for water resources modeling problems considering nonlinear input variable selection; however, this method requires the specification of two nonlinear regression models, each with parametric settings that greatly influence the selected input variables. Other attempts to develop input variable selection methods using conditional mutual information (CMI) (an analog to PMI) have been formulated under different parametric pretenses such as k nearest-neighbor (KNN) statistics or kernel density estimates (KDE). In this paper, we introduce a new input variable selection method based on CMI that uses a nonparametric multivariate continuous probability estimator based on Edgeworth approximations (EA). We improve the EA method by considering the uncertainty in the input variable selection procedure by introducing a bootstrap resampling procedure that uses rank statistics to order the selected input sets; we name our proposed method bootstrap rank-ordered CMI (broCMI). We demonstrate the superior performance of broCMI when compared to CMI-based alternatives (EA, KDE, and KNN), PMIS, and PCIS input variable selection algorithms on a set of seven synthetic test problems and a real-world urban water demand (UWD) forecasting experiment in Ottawa, Canada. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a method based on risk minimization to hedge observable but nontradable source of risk on financial or energy markets. The optimal portfolio strategy is obtained by minimizing dynamically the conditional value-at-risk (CVaR) using three main tools: a stochastic approximation algorithm, optimal quantization, and variance reduction techniques (importance sampling and linear control variable), as the quantities of interest are naturally related to rare events. As a first step, we investigate the problem of CVaR regression, which corresponds to a static portfolio strategy where the number of units of each tradable assets is fixed at time 0 and remains unchanged till maturity. We devise a stochastic approximation algorithm and study its a.s. convergence and weak convergence rate. Then, we extend our approach to the dynamic case under the assumption that the process modeling the nontradable source of risk and financial assets prices is Markovian. Finally, we illustrate our approach by considering several portfolios in connection with energy markets. [ABSTRACT FROM AUTHOR]

In this paper, we adapt lazy abstraction with interpolants for reachability analysis of timed automaton. It involves computing an abstract reachability tree whose nodes are labeled by a location and a given set of predicates. The set of predicates over-approximates the reachable clock valuations of the corresponding location, and the approximation is refined when a spurious counterexample appears. A more precise approximation usually contains fewer spurious counterexamples that require refinement, but as a result it may delay the convergence of the algorithm. The state-of-the-art lazy abstraction algorithms employ interpolants to produce an approximation that is closer to the actual reachable clock valuation to eliminate the spurious errors. However, interpolant also cannot ensure the quality of the resulting approximation, as it blindly relies on the SMT solver. In order to produce optimal approximation, we assign to each node a maximal lower and upper bounds (LU-bounds) function to produce a node-specific LU-bounds abstraction; the abstraction can further over-approximate the reachable clock valuations without introducing extra spurious counterexamples. Furthermore, in our algorithm, LU-bounds are refined only when a spurious counterexample occurs. Hence, only those clock valuations that lead to error nodes are excluded. An alternative benefit of the LU-bounds abstraction is that it ensures that the abstraction-refinement loop terminates. © 2015 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc. [ABSTRACT FROM AUTHOR]

We revisit the shift-and-invert Arnoldi method proposed in [S. Lee, H. Pang, and H. Sun. Shift-invert Arnoldi approximation to the Toeplitz matrix exponential, SIAM J. Sci. Comput., 32: 774-792, 2010] for numerical approximation to the product of Toeplitz matrix exponential with a vector. In this approach, one has to solve two large-scale Toeplitz linear systems in advance. However, if the desired accuracy is high, the cost will be prohibitive. Therefore, it is interesting to investigate how to solve the Toeplitz systems inexactly in this method. The contribution of this paper is in three regards. First, we give a new stability analysis on the Gohberg-Semencul formula (GSF) and define the GSF condition number of a Toeplitz matrix. It is shown that when the size of the Toeplitz matrix is large, our result is sharper than the one given in [M. Gutknecht and M. Hochbruck. The stability of inversion formulas for Toeplitz matrices, Linear Algebra Appl., 223/224: 307-324, 1995]. Second, we establish a relation between the error of Toeplitz systems and the residual of Toeplitz matrix exponential. We show that if the GSF condition number of the Toeplitz matrix is medium-sized, then the Toeplitz systems can be solved in a low accuracy. Third, based on this relationship, we present a practical stopping criterion for relaxing the accuracy of the Toeplitz systems and propose an inexact shift-and-invert Arnoldi algorithm for the Toeplitz matrix exponential problem. Numerical experiments illustrate the numerical behavior of the new algorithm and show the effectiveness of our theoretical results. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The article presents a call for papers for a special issue of this periodical about the contributions to be presented at a workshop on applied combinatorial optimization in Buenos Aires, Argentina, on December 15-17, 2008. The topics included in the workshop are network synthesis and design, transportation problems, integer programming, and approximation algorithms.

The conventional interacting multiple models (IMM) approach for a hybrid system under the Gaussian assumption is limited for most real applications due to the noisy measurements often being in the presence of outliers. This paper aims at accommodating the IMM approach to the non-Gaussian cases where outliers exist. In the proposed IMM algorithm, the Student-t distribution is used to model the non-Gaussian measurement noise. At the interaction step, the mixed statistics of the noise parameter under a Bayesian framework are obtained via a Gamma approximation and a recently reported moments matching method. To address the state noise-coupled intractability in Bayesian filtering, a variational Bayesian method is utilized to approximate the posterior distributions of the noise and state recursively. The proposed algorithm is tested with a maneuvering target tracking example and is shown to be robust to the outliers. [ABSTRACT FROM AUTHOR]

The problem of max-kernel search arises everywhere: given a query point \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$p_q$ \end{document}, a set of reference objects \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$S_r$ \end{document} and some kernel \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$\mathcal{K}$ \end{document}, find \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$arg\,max_{p_r \in S_r} \mathcal{K}(p_q, p_r)$ \end{document}. Max-kernel search is ubiquitous and appears in countless domains of science, thanks to the wide applicability of kernels. A few domains include image matching, information retrieval, bio-informatics, similarity search, and collaborative filtering (to name just a few). However, there is no generalized technique for efficiently solving max-kernel search. This paper presents a single-tree algorithm called single-tree FastMKS which returns the max-kernel solution for a single query point in provably \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$O(\log N)$ \end{document} time (where \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$N$ \end{document} is the number of reference objects), and also a dual-tree algorithm ( dual-tree FastMKS) which is useful for max-kernel search with many query points. If the set of query points is of size \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$O(N)$ \end{document}, this algorithm returns a solution in provably \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$O(N)$ \end{document} time, which is significantly better than the \documentclass{article}\usepackage{amsmath}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{amsfonts}\pagestyle{empty}\begin{document}$O(N^2)$ \end{document} linear scan solution; these bounds are dependent on the expansion constant of the data. These algorithms work for abstract objects, as they do not require explicit representation of the points in kernel space. Empirical results for a variety of datasets show up to five orders of magnitude speedup in some cases. In addition, we present approximate extensions of the FastMKS algorithms that can achieve further speedups. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, we discuss the issue of fairness in the IEEE802.11e over wireless mesh networks. Fairness is an important factor that we have to achieve before talking about QoS. Inspired by social networks approximations, and to achieve fairness and provide QoS by regulating heterogeneous traffic, we extended the original IEEE802.11e protocol by introducing a new algorithm based on the 'token bucket' concept. We also treat the problem of exposed/hidden nodes. Simulation results show that the proposed approach offers better performance than the IEEE802.11e one. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, an inner-outer preconditioner for symmetric positive definite matrices based on hierarchically semi-separable (HSS) matrix representation is presented. A sequence of new HSS algorithms are developed, including some ULV-type HSS methods and triangular HSS methods. During the construction of this preconditioner, off-diagonal blocks are compressed in parallel, and an approximate HSS form is used as the outer HSS representation. In the meantime, the internal dense diagonal blocks are approximately factorized into HSS Cholesky factors. Such inner factorizations are guaranteed to exist for any approximation accuracy. The inner-outer preconditioner combines the advantages of both direct HSS and triangular HSS methods, and are both scalable and robust. Systematic complexity analysis and discussions of the errors are presented. Various tests on some practical numerical problems are used to demonstrate the efficiency and robustness. In particular, the effectiveness of the preconditioner in iterative solutions has been shown for some ill-conditioned problems. This work also gives a practical way of developing inner-outer preconditioners using direct rank structured factorizations (other than iterative methods). Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Purpose: Compressed sensing theory has enabled an accurate, low-dose cone-beam computed tomography (CBCT) reconstruction using a minimal number of noisy projections. However, the reconstruction time remains a significant challenge for practical implementation in the clinic. In this work, we propose a novel gradient projection algorithm, based on the Gradient-Projection-Barzilai-Borwein formulation (GP-BB), that handles the total variation (TV)-norm regularization-based least squares problem for the CBCT reconstruction in a highly efficient manner, with speed acceptable for routine use in the clinic. Methods: CBCT is reconstructed by minimizing an energy function consisting of a data fidelity term and a TV-norm regularization term. Both terms are simultaneously minimized by calculating the gradient projection of the energy function with the step size determined using an approximate Hessian calculation at each iteration, based on the Barzilai-Borwein formulation. To speed up the process, a multiresolution optimization is used. In addition, the entire algorithm was designed to run with a single graphics processing unit (GPU) card. To evaluate the performance, the Shepp-Logan numerical phantom, the CatPhan 600 physical phantom, and a clinically-treated head-and-neck patient were acquired from the TrueBeam™ system (Varian Medical Systems, Palo Alto, CA). For each scan, in total, 364 projections were acquired in a 200° rotation. The imager has 1024 × 768 pixels with 0.388 × 0.388-mm resolution. This was down-sampled to 512 × 384 pixels with 0.776 × 0.776-mm resolution for reconstruction. Evenly spaced angles were subsampled and used for varying the number of projections for the image reconstruction. To assess the performance of our GP-BB algorithm, we have implemented and compared with three compressed sensing-type algorithms, the two of which are popular and published (forward-backward splitting techniques), and the other one with a basic line-search technique. In addition, the conventional Feldkamp-Davis-Kress (FDK) reconstruction of the clinical patient data is compared as well. Results: In comparison with the other compressed sensing-type algorithms, our algorithm showed convergence in ≤30 iterations whereas other published algorithms need at least 50 iterations in order to reconstruct the Shepp-Logan phantom image. With the CatPhan phantom, the GP-BB algorithm achieved a clinically-reasonable image with 40 projections in 12 iterations, in less than 12.6 s. This is at least an order of magnitude faster in reconstruction time compared with the most recent reports utilizing GPU technology given the same input projections. For the head-and-neck clinical scan, clinically-reasonable images were obtained from 120 projections in 34-78 s converging in 12-30 iterations. In this reconstruction range (i.e., 120 projections) the image quality is visually similar to or better than the conventional FDK reconstructed images using 364 projections. This represents a dose reduction of nearly 67% (120/364 projections) while maintaining a reasonable speed in clinical implementation. Conclusions: In this paper, we proposed a novel, fast, low-dose CBCT reconstruction algorithm using the Barzilai-Borwein step-size calculation. A clinically viable head-and-neck image can be obtained within ∼34-78 s while simultaneously cutting the dose by approximately 67%. This makes our GP-BB algorithm potentially useful in an on-line image-guided radiation therapy (IGRT). [ABSTRACT FROM AUTHOR]

SUMMARY Multimedia transmission over the network is susceptible to various runtime impairments such as process failure, network congestion or link error. Existing work usually determines such quality of service (QoS) violations through condition-action rules, which trigger corresponding actions once pre-described conditions are satisfied. However, the results of such rigid rules are often not satisfactory in practice in that there has been little serious study with respect to the relationship between the root cause of a QoS violation and the observed violation phenomenon. In this paper, we introduce a statistical approach to the analysis of QoS violations. We propose and validate through experiments that: (1) a type of QoS violation will present consistent symptoms in terms of the observed application performance and end-to-end traffic pattern. Such a violation can be recognized once the similar symptoms repeat during a QoS session. (2) QoS violations of different nature (e.g. caused by shortage of different resources) will present diverse symptoms. Using a set of end-to-end statistics, we are able to describe and differentiate between QoS violations. We propose a fast orthonormal algorithm for real-time training/classification of QoS violations and prove that this algorithm is universal approximation. We also extend the scope of hidden neurons from kernel functions to additive functions for higher classification accuracy. Our experiments validate our ideas and show the effectiveness of our approach in terms of training overhead and classification accuracy. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

There are many nonlinear systems among process control systems. However, it is difficult to handle nonlinear properties with a linear controller. Thus, various methods have been studied in this field. On the other hand, a scheme called boosting has been proposed in the machine learning field. This scheme can obtain highly accurate conditions by combining less-accurate conditions. Boosting can obtain better results than a neural network with fewer learning data. In this paper, we propose a method for the design of nonlinear PID control systems using the boosting algorithm. The original boosting is capable of dealing only with two-valued variables, and thus we extend the algorithm for function approximation using it. Finally, simulation examples are presented in order to demonstrate the effectiveness of the proposed scheme. © 2011 Wiley Periodicals, Inc. Electron Comm Jpn, 94(9): 52-58, 2011; Published online in Wiley Online Library (). DOI 10.1002/ecj.10310 [ABSTRACT FROM AUTHOR]

The paper presents an extension of the composite programmable graph grammar (CP-graph grammar) suitable for modeling the parallel direct solver algorithm utilized by the hp finite element method (hp-FEM). In the proposed graph grammar model, the computational mesh is represented by a CP-graph. The presented graph grammar models the solver algorithm by a set of graph grammar productions. The graph grammar model makes it possible to examine the concurrency of the algorithm by analyzing the interdependence between the atomic tasks, tasks and super-tasks. The atomic tasks correspond to the graph grammar productions, representing basic undividable parts of the algorithms. The level of atomic tasks models the concurrency for the shared memory architectures. On the other hand, the tasks correspond to the groups of atomic tasks with predefined inter-task communication channels. They constitute the grain for the decomposition of the parallel algorithm for the distributed memory architecture. Finally, the super-tasks correspond to a group of tasks resulting from the execution of load balancing algorithm. The solver algorithm is tested on distributed memory linux cluster for up to 192 processors. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Existing algorithms can efficiently render refractive objects of constant refractive index. For a medium with a continuously varying index of refraction, most algorithms use the ray equation of geometric optics to compute piecewise-linear approximations of the non-linear rays. By assuming a constant refractive index within each tracing step, these methods often need a large number of small steps to generate satisfactory images. In this paper, we present a new approach for tracing non-constant, refractive media based on the ray equations of gradient-index optics. We show that in a medium of constant index gradient, the ray equation has a closed-form solution, and the intersection point between a ray and the medium boundaries can be efficiently computed using the bisection method. For general non-constant media, we model the refractive index as a piecewise-linear function and render the refraction by tracing the tetrahedron-based representation of the media. Our algorithm can be easily combined with existing rendering algorithms such as photon mapping to generate complex refractive caustics at interactive frame rates. We also derive analytic ray formulations for tracing mirages – a special gradient-index optical phenomenon. [ABSTRACT FROM AUTHOR]

Implementing large-scale empirical studies can be very expensive. Therefore, it is useful to optimize study designs without losing statistical power. In this paper, we show how study designs can be improved without changing statistical power by defining power equivalence, a relation between structural equation models (SEMs) that holds true if two SEMs have the same power on a likelihood ratio test to detect a given effect. We show systematic operations of SEMs that maintain power, and give an algorithm that efficiently reduces SEMs to power-equivalent models with a minimal number of observed parameters. In this way, optimal study designs can be found without reducing statistical power. Furthermore, the algorithm can be used to drastically increase the speed of power computations when using Monte Carlo simulations or approximation methods. [ABSTRACT FROM AUTHOR]

In this paper, we study the quadratic model updating problems by using symmetric low-rank correcting, which incorporates the measured model data into the analytical quadratic model to produce an adjusted model that matches the experimental model data, and minimizes the distance between the analytical and updated models. We give a necessary and sufficient condition on the existence of solutions to the symmetric low-rank correcting problems under some mild conditions, and propose two algorithms for finding approximate solutions to the corresponding optimization problems. The good performance of the two algorithms is illustrated by numerical examples. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper extends the weighted low rank approximation (WLRA) approach towards linearly structured matrices. In the case of Hankel matrices an equivalent unconstrained optimization problem is derived and an algorithm for solving it is proposed. The correctness of the latter algorithm is verified on a benchmark problem. Finally the statistical accuracy and numerical efficiency of the proposed algorithm is compared with that of STLNB, a previously proposed algorithm for solving Hankel WLRA problems. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The paper proposes an improvement of coding performance for a color image compression scheme based on the adaptive orthogonalized transform (AOT). The paper proposes that the performance of the coder will be accelerated by reducing the dictionary size to 25% and by maintaining the approximation gain of the LBG algorithm by virtue of the fact that the AOT increases the approximation gain of the dictionary. The effectiveness of the proposal is confirmed by numerical experiments. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 33(8): 1–8, 2002; Published online in Wiley InterScience (www.interscience. wiley.com). DOI 10.1002/scj.10218 [ABSTRACT FROM AUTHOR]

In this paper, we describe various methods of deriving a parallel version of Stone's Strongly Implicit Procedure (SIP) for solving sparse linear equations arising from finite difference approximation to partial differential equations (PDEs). Sequential versions of this algorithm have been very successful in solving semi-conductor, heat conduction and flow simulation problems and an efficient parallel version would enable much larger simulations to be run. An initial investigation of various parallelizing strategies was undertaken using a version of high performance Fortran (HPF) and the best methods were reprogrammed using the MPI message passing libraries for increased efficiency. Early attempts concentrated on developing a parallel version of the characteristic wavefront computation pattern of the existing sequential SIP code. However, a red-black ordering of grid points, similar to that used in parallel versions of the Gauss–Seidel algorithm, is shown to be far more efficient. The results of both the wavefront and red-black MPI based algorithms are reported for various size problems and number of processors on a sixteen node IBM SP2. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper suggests a new algorithm, called IBBLU, for constructing incomplete LU-factorizations of general non-singular sparse matrices. This algorithm is based on the block bordering idea and uses factorized sparse approximate inverses to approximate the inverses of pivot blocks. The triangular factors L and U are represented in explicit-implicit block form, which enhances the flop performance of the preconditioning. The algorithm suggested is theoretically justified for M- and H-matrices, and its competitiveness with the best available algebraic preconditioning methods in both symmetric and unsymmetric cases is demonstrated numerically. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Model order reduction of an electromagnetic system is understood as the approximation of a continuous or discrete model of the system by one of substantially lower order, yet capable of capturing the electromagnetic behaviour of the original one with sufficient engineering accuracy. Model order reduction technqiues are reviewed and critically examined in this paper. The emphasis is on techniques suitable for the generation of high-order Padé approximations to transfer functions of electromagnetic systems discretized using finite methods. The computational complexity associated with the application of such model order reduction techniques to electromagnetic systems of practical interest is discussed, and the computationally most efficient model order reduction algorithm is identified. The benefits of model order reduction are demonstrated through a series of numerical examples from the analysis of electromagnetic waveguides. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]