Search

In this paper, a computational method based on parameterizing state and control variables is presented for solving Stochastic Optimal Control (SOC) problems. By using Chebyshev wavelets with unknown coefficients, state and control variables are parameterized, and then a stochastic optimal control problem is converted to a stochastic optimization problem. The expected cost functional of the resulting stochastic optimization problem is approximated by sample average approximation thereby the problem can be solved by optimization methods more easily. For facilitating and guaranteeing convergence of the presented method, a new theorem is proved. Finally, the proposed method is implemented based on a newly designed algorithm for solving one of the well-known problems in mathematical finance, the Merton portfolio allocation problem in finite horizon. The simulation results illustrate the improvement of the constructed portfolio return. [ABSTRACT FROM AUTHOR]

Fuzzy rough set theory has been successfully applied to many attribute reduction methods, in which the lower approximation set plays a pivotal role. However, the definition of lower approximation used has ignored the information conveyed by the upper approximation and the boundary region. This oversight has resulted in an unreasonable relation representation of the target set. Despite the fact that scholars have proposed numerous enhancements to rough set models, such as the variable precision model, none have successfully resolved the issues inherent in the classical models. To address this limitation, this paper proposes an unsupervised attribute reduction algorithm for mixed data based on an improved optimal approximation set. Firstly, the theory of an improved optimal approximation set and its associated algorithm are proposed. Subsequently, we extend the classical theory of optimal approximation sets to fuzzy rough set theory, leading to the development of a fuzzy improved approximation set method. Finally, building on the proposed theory, we introduce a novel, fuzzy optimal approximation-set-based unsupervised attribute reduction algorithm (FOUAR). Comparative experiments conducted with all the proposed algorithms indicate the efficacy of FOUAR in selecting fewer attributes while maintaining and improving the performance of the machine learning algorithm. Furthermore, they highlight the advantage of the improved optimal approximation set algorithm, which offers higher similarity to the target set and provides a more concise expression. [ABSTRACT FROM AUTHOR]

In this paper, we present a new low-complexity iterative joint phase estimation and decoding algorithm which can be applied to low-density-parity-check (or turbo) codes for channels affected by strong phase noise. The algorithm exhibits a very good performance and a very low complexity even in strong phase noise, high code rate, and high-order constellations. The proposed algorithm works by first obtaining a preliminary pilots-aided phase estimation. Next, the expressions for the belief propagation messages are approximated around that reference and reduced to a Gaussian canonical form. This results in a simple closed form of a recursive update. Simulations results for phase-shift-keying modulation of size 8 and quadrature-amplitude modulation of size 64 are presented and compared with other algorithms in the literature. [ABSTRACT FROM AUTHOR]

Cross-validation (CV) is a widely adopted approach for selecting the optimal model. However, the computation of empirical cross-validation error (CVE) has high complexity due to multiple times of learner training. In this paper, we develop a novel approximation theory of CVE and present an approximate approach to CV based on the Bouligand influence function (BIF) for kernel-based algorithms. We first represent the BIF and higher order BIFs in Taylor expansions, and approximate CV via the Taylor expansions. We then derive an upper bound of the discrepancy between the original and approximate CV. Furthermore, we provide a novel computing method to calculate the BIF for general distribution, and evaluate BIF criterion for sample distribution to approximate CV. The proposed approximate CV requires training on the full data set only once and is suitable for a wide variety of kernel-based algorithms. Experimental results demonstrate that the proposed approximate CV is sound and effective. [ABSTRACT FROM AUTHOR]

Visually analyzing citation networks poses challenges to many fields of the data mining research. How can we summarize a large citation graph according to the user’s interest? In particular, how can we illustrate the impact of a highly influential paper through the summarization? Can we maintain the sensory node-link graph structure while revealing the flow-based influence patterns and preserving a fine readability? The state-of-the-art influence maximization algorithms can detect the most influential node in a citation network, but fail to summarize a graph structure to account for its influence. On the other hand, existing graph summarization methods fold large graphs into clustered views, but can not reveal the hidden influence patterns underneath the citation network. In this paper, we first formally define the Influence Graph Summarization problem on citation networks. Second, we propose a matrix decomposition based algorithm pipeline to solve the IGS problem. Our method can not only highlight the flow-based influence patterns, but also easily extend to support the rich attribute information. A prototype system called VEGAS implementing this pipeline is also developed. Third, we present a theoretical analysis on our main algorithm, which is equivalent to the kernel k-mean clustering. It can be proved that the matrix decomposition based algorithm can approximate the objective of the proposed IGS problem. Last, we conduct comprehensive experiments with real-world citation networks to compare the proposed algorithm with classical graph summarization methods. Evaluation results demonstrate that our method significantly outperforms the previous ones in optimizing both the quantitative IGS objective and the quality of the visual summarizations. [ABSTRACT FROM PUBLISHER]

Dynamic spectrum leasing (DSL) is a promising method to improve the spectrum efficiency. A lot of work has been done about spectrum sharing issues with static models. In this paper, we want to study the behavior of the primary users (PUs) under uncertainty. For this objective, we propose a model with time-varying parameters. The model captures both technical and economic features. We study the long-term behavior of the PUs in the model with stochastic Cournot game theory and variational inequality theory. We show that the PUs can maximize their long-term utilities with a static supply of spectrum. In addition, we also propose two algorithms based on stochastic approximation theory. The convergence and performance of the algorithms are demonstrated theoretically and numerically. The proposed model and analytical framework can be used to study and predict the behaviors of PUs given a DSL system and provide design insights for the DSL system. [ABSTRACT FROM AUTHOR]

Electromagnetic devices containing permanent magnet (PM) are common and typical electromagnetic devices that have advantages of low-power consumption, small size, high sensitivity, and its optimization problem has aroused widespread concern. Calculation accuracy of electromagnetic properties and efficiency of optimization processes are two important factors that affect the optimization effect of electromagnetic devices. A fast calculation method was proposed in this paper that aimed at electromagnetic devices with PM characteristics of strong non-linearity and low solving precision. The response surface method was used to derive the basis function, and the error between actual measured values and calculated values was modified by the Kriging method. On the basis of the calculation model, the distributed collaborative strategy was adopted to fulfill the parallel execution of the fast computation. Simultaneously, the updating strategy of particles was improved, and the robustness of the multi-objective particle swarm optimization algorithm in solving the optimization problem of electromagnetic devices with PM was enhanced. Effectiveness of the method proposed in this paper was verified by the case study of a specific type of electromagnetic relay with PM. [ABSTRACT FROM AUTHOR]

Koblitz curves have been an important subject of consideration for both theoretical and practical interests. The window τ-adic algorithm of Solinas (window τNAF) is the most powerful method for computing point multiplication for Koblitz curves. Pre-computation plays an important role in improving the performance of point multiplication. In this paper, the concept of optimal pre-computation for window τNAF is formulated. In this setting, an optimal pre-computation has some mathematically natural and clean forms, and requires 2w−2−1 point additions and two evaluations of the Frobenius map τ, where w is the window width. One of the main results of this paper is to construct an optimal pre-computation scheme for each window width w from 4 to 15 (more than practical needs).These pre-computations can be easily incorporated into implementations of window τNAF. The ideas in the paper can also be used to construct other suitable pre-computations. This paper includes a discussion of coefficient sets for window τNAF and the divisibility by powers of τ through different approaches. Some issues of implementation are also discussed. [ABSTRACT FROM PUBLISHER]

Milano Retinex is a family of spatial color algorithms inspired by Retinex and mainly devoted to the image enhancement. In the so-called point-based sampling Milano Retinex algorithms, this task is accomplished by processing the color of each image pixel based on a set of colors sampled in its surround. This paper presents STAR, a segmentation based approximation of the point-based sampling Milano Retinex approaches: it replaces the pixel-wise image sampling by a novel, computationally efficient procedure that detects once for all the color and spatial information relevant to image enhancement from clusters of pixels output by a segmentation. The experiments reported here show that STAR performs similarly to previous point-based sampling Milano Retinex approaches and that STAR enhancement improves the accuracy of the well-known algorithm scale-invariant feature transform on the description and matching of photographs captured under difficult light conditions. [ABSTRACT FROM AUTHOR]

The probability ranking conclusion is an extension of the absolute form evaluation conclusion. Firstly, the random simulation evaluation model is introduced; then, the general idea of converting the traditional evaluation method to the random simulation evaluation model is analyzed; on this basis, based on the rule of "further ensuring the stability of the ranking chain on the basis of increasing the possibility of the ranking chain," two methods of solving the probability ranking conclusion are given. Based on the rule of "further guaranteeing the stability of the ranking chain on the basis of improving the likelihood of the ranking chain," two methods are given to solve the likelihood conclusion. This paper argues that this absolute form of conclusion hinders the approximation of the theory to the essence of the actual problem and is an important reason for the problem of "non-consistency of multi-evaluation conclusions." To address this problem, a stochastic simulation-based comprehensive evaluation solution algorithm based on the idea of "Monte Carlo simulation" is proposed, and the corresponding ranking method is investigated, which is characterized by generating evaluation conclusions with probability (reliability) information, and thus has more advantages than the absolute conclusion form in terms of problem interpretability. The method is characterized by the generation of evaluation conclusions with probabilistic (reliability) information and thus has more advantages than the absolute conclusion form in terms of problem interpretation. Because of the independence of the stochastic simulation solution method, it is applied to the "bottom-up" evaluation model as an example, and a novel autonomous evaluation method is constructed. Finally, the application of the stochastic simulation evaluation model is illustrated by an example and compared with the absolute form evaluation. The evaluation model is an extension of the traditional evaluation model, which can further broaden the practical application of comprehensive evaluation theory. [ABSTRACT FROM AUTHOR]

Remote sensing has been used widely in studying the earth terrain such as snow or sea ice due to its fast, convenient and long-term monitoring capabilities. SAR images acquired could be used to analyze the condition of snow, snow water equivalent (SWE), surface roughness and others. Theoretical models have also been developed to understand how microwave interacts with the snow medium and the scatterers embedded inside the medium. Conventionally, spherical shape of scatterers is commonly used to represent the ice particles embedded inside snow where the actual shape of scatterers can vary. This paper is to present a theoretical model based on radiative transfer formulation that utilizes computational electromagnetics in the modelling of scattering from arbitrary shape of scatterers. The paper also studies the effect of scatterer shape on scattering mechanisms and total backscattering coefficient. Numerical solution of Relaxed Hierarchical Equivalent Source Algorithm (RHESA) was integrated with existing radiative transfer theoretical model to simulate a layer of random discrete snow medium. Several shapes of scatterers were simulated, and theoretical simulation were compared with ground truth measurement data with promising results. [ABSTRACT FROM AUTHOR]

The normal or Gaussian distribution plays a prominent role in almost all fields of science. However, it is well known that the Gauss (or Euler–Poisson) integral over a finite boundary, as is necessary, for instance, for the error function or the cumulative distribution of the normal distribution, cannot be expressed by analytic functions. This is proven by the Risch algorithm. Regardless, there are proposals for approximate solutions. In this paper, we give a new solution in terms of normal distributions by applying a geometric procedure iteratively to the problem. [ABSTRACT FROM AUTHOR]

Uncertainty in consumption is a key challenge at energy utility companies, which are faced with balancing highly stochastic demand with increasingly volatile supply characterized by significant penetration rates of intermittent renewable sources. This paper proposes a methodology to quantify uncertainty in consumption that highlights the dependence of the cost-of-service with volatility in demand. We use a large and rich dataset of consumption time series to provide evidence that there is a substantial degree of high-level structure in the statistics of consumption across users which may be partially explained by certain characteristics of the users. To uncover this structure, we propose a new technique for extracting typical statistical signatures of consumption—energy demand distributions (EDDs)—that is based on clustering distributions using a fast, approximated algorithm. We next study the factors influencing the choice of consumption signature and identify certain types of appliances and behaviors related to appliance operation that are most predictive. Finally, we comment on how structure in consumption statistics may be used to target residential energy efficiency programs to achieve greatest impact in curtailing cost of service. [ABSTRACT FROM AUTHOR]

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]

Small cells are introduced to cellular systems to enhance coverage and improve capacity. Densely deploying small cells can not only offload the traffic of macrocells but also provide an energy- and cost-efficient way to meet the sharp increase in traffic demands in mobile networks. However, such a cell deployment paradigm also leads to heterogeneous network (HetNet) infrastructure and raises new challenges for cell planning. In this paper, we study the cell planning issue in the HetNet. Our optimization task is to select a subset of candidate sites to deploy macro or small cells to minimize the total cost of ownership (TCO) or the energy consumption of the cellular system while satisfying practical constraints. We introduce approximation algorithms to cope with two different cell-planning cases, which are both NP-hard. First, we discuss the macrocell-only case. Our proposed algorithm achieves an approximation ratio of O(\log R) in this scenario, where R is the maximum achievable capacity of macrocells. Then, we introduce an O(\log \widetildeR)-approximation algorithm to the small-cell scenario, where \widetildeR is the maximum achievable capacity of a macrocell with small cells overlaid on it. Numerical results indicate that the HetNet can significantly reduce the TCO and the energy consumption of the cellular system. [ABSTRACT FROM PUBLISHER]

There are more and more structured traffic flows (a.k.a coflow) in today's data center networks. Completing a coflow is extremely important for various applications, e.g., MapReduce. To reduce the coflow completion time or CCT, one may increase the link capacity by applying advanced optical circuit switches in data center networks. Due to special features of optical circuit switches, both traffic scheduling and circuit scheduling will influence the CCT. However, previous solutions have some significant limitations: they consider either coflow scheduling, or circuit scheduling for only one optical circuit switch, which are both insufficient. In this paper, we study the integrated coflow and circuit scheduling (GCCS) problem with the objective to minimize the CCT, and prove its NP-hardness. We present an integrated algorithm which includes two steps, coflow scheduling and circuit scheduling, respectively. We also analyze that the proposed algorithm can achieve the approximation ratio $O(h)$O(h) in most practical situations, where $h$h is the maximum number of ports among all lightpaths. Through large-scale simulations, we demonstrate that the integrated solution can significantly reduce the CCT by about 43-70 percent compared with the state-of-the-art coflow scheduler for optical networks. [ABSTRACT FROM AUTHOR]

This paper addresses a travel time reliable signal control problem. Travel time distributional estimates are obtained from a stochastic microscopic traffic simulator. The estimates are embedded within a simulation-based optimization algorithm. Analytical approximations of the simulated metrics are combined with the simulated data in order to enhance the computational efficiency of the algorithm. The signal control problems are formulated based on the expectation and the standard deviation of travel time metrics. The proposed approach goes beyond the traditional use of first-order simulated information, it addresses a problem that embeds higher-order distributional information. It is used to solve a large-scale signal control problem. The approach addresses these challenging simulation-based optimization problems in a computationally efficient manner. Its performance is compared to that of a traditional simulation-based optimization approach. The proposed method systematically outperforms the traditional approach. Such an approach can be used to inform the design and operations of transportation systems by, for instance, addressing reliable and/or robust formulations of traditional transportation problems. The online appendix is available at https://doi.org/10.1287/trsc.2017.0812. [ABSTRACT FROM AUTHOR]

This paper presents a macromodeling technique for modeling distributed circuits characterized by noisy frequency-domain data. The proposed method is based on an iterative Loewner matrix (LM) approach. Using the LM approximation of previous iterations, the singular values and orthonormal matrices of the Loewner pencil are made to be more accurate. This approach is shown to minimize the biasing effect of the noisy data due to the nonlinearity of the singular value decomposition operation, resulting in more accurate poles and residues. Numerical examples illustrate that for noisy frequency-domain data, the proposed algorithm creates more accurate macromodels when compared with the traditional LM approach. [ABSTRACT FROM AUTHOR]

In this paper, we study a kind of conjugate gradient viscosity approximation algorithm for finding a common solution of split generalized equilibrium problem and variational inequality problem. Under mild conditions, we prove that the sequence generated by the proposed iterative algorithm converges strongly to the common solution. The conclusion presented in this paper is the generalization, extension, and supplement of the previously known results in the corresponding references. Some numerical results are illustrated to show the feasibility and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The prediction of RNA structure with pseudoknots is a nondeterministic polynomial-time hard (NP-hard) problem; according to minimum free energy models and computational methods, we investigate the RNA-pseudoknotted structure. Our paper presents an efficient algorithm for predicting RNA structure with pseudoknots, and the algorithm takes O(n3) time and O(n2) space, the experimental tests in Rfam10.1 and PseudoBase indicate that the algorithm is more effective and precise. The predicting accuracy, the time complexity and space complexity outperform existing algorithms, such as Maximum Weight Matching (MWM) algorithm, PKNOTS algorithm and Inner Limiting Layer (ILM) algorithm, and the algorithm can predict arbitrary pseudoknots. And there exists a 1+ε (ε>0) polynomial time approximation scheme in searching maximum number of stackings, and we give the proof of the approximation scheme in RNA-pseudoknotted structure. We have improved several types of pseudoknots considered in RNA folding structure, and analyze their possible transitions between types of pseudoknots. [ABSTRACT FROM AUTHOR]

In the theory of belief functions, the approximation of a basic belief assignment (BBA) is for reducing the high computational cost especially when large number of focal elements are available. In traditional BBA approximation approaches, a focal element’s own characteristics such as the mass assignment and the cardinality, are usually used separately or jointly as criteria for the removal of focal elements. Besides the computational cost, the distance between the original BBA and the approximated one is also concerned, which represents the loss of information in BBA approximation. In this paper, an iterative approximation approach is proposed based on maximizing the closeness, i.e., minimizing the distance between the approximated BBA in current iteration and the BBA obtained in the previous iteration, where one focal element is removed in each iteration. The iteration stops when the desired number of focal elements is reached. The performance evaluation approaches for BBA approximations are also discussed and used to compare and evaluate traditional BBA approximations and the newly proposed one in this paper, which include traditional time-based way, closeness-based way and new proposed ones. Experimental results and related analyses are provided to show the rationality and efficiency of our proposed new BBA approximation. [ABSTRACT FROM AUTHOR]

Nonlinear oscillations are an essential fact in physical science, mechanical structures, and other engineering problems. Some of the popular analytical solutions to analyze nonlinear differential equations governing the behavior of strongly nonlinear oscillators are the Energy Balance Method (EBM), and He's Amplitude Frequency Formulation (HAFF). The lack of precision and accuracy despite needing several computational steps to resolve the system frequency is the main demerit of these methods. This research creates a novel analytical approximation approach with a very efficient algorithm that can perform the calculation procedure much easier and with much higher accuracy than classic EBM and HAFF. The presented method's steps rely on Hamiltonian relations described in EBM and the defined relationship between frequency and amplitude in HAFF. This paper demonstrates the substantial precision of the presented method compared to common EBM and HAFF applied in different and well-known engineering phenomena. For instance, the approximate solutions of the equations govern some strongly nonlinear oscillators, including the two-massspring systems, buckling of a column, and duffing relativistic oscillators are presented here. Subsequently, their results are compared with the Runge-Kutta method and exact solutions obtained from the previous research. The proposed novel approach resultant error percentages show an excellent agreement with the numerical solutions and illustrate a very quickly convergent and more precise than mentioned typical methods. [ABSTRACT FROM AUTHOR]

The natural-element method (NEM) has proved to be able to provide more accurate and computationally efficient solutions than the finite-element method (FEM) for first-order consistency approximations. However, higher order approximations in the NEM framework are not obtained straightforwardly. This paper addresses a method of constructing higher order approximations out of the standard first-order NEM shape functions. This process is achieved through the de Boor algorithm. Accuracy of the scheme is compared with FEM. Results show that in second-order approximations context the NEM is still able to provide better accuracies for a given number of degrees of freedom. [ABSTRACT FROM PUBLISHER]

We consider a generalization of both the classic Steiner tree problem and the terminal Steiner tree problem. Given a complete graph G = (V,E) with a metric cost function c:E \rightarrow \BBQ_ \geq and two proper subsets R \subset V and R^\prime \subseteq R, a partial-terminal Steiner tree is a Steiner tree which contains all vertices in \it R such that all vertices in R^\prime must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum cost in G. The previously best-known approximation ratio of the problem is 2\rho, where \bf \rho is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from 2\rho to 2\rho - \rho \over 3\rho - 2 - f, where f is a non-negative function whose value is between 0 and \rho - \rho \over 3\rho - 2. [ABSTRACT FROM AUTHOR]

Direction of arrival (DOA) estimation algorithms based on sparse Bayesian inference (SBI) can effectively estimate coherent sources without recurring to extra decorrelation techniques, and their estimation performance is highly dependent on the selection of sparse prior. Specifically, the specified sparse prior is expected to concentrate its mass on the zero and distribute with heavy tails; otherwise, these algorithms may suffer from performance degradation. In this paper, we introduce a new sparse-encouraging prior, referred to as “Gauss-Exp-Chi2” prior, and develop an efficient DOA estimation algorithm for a mixture of uncorrelated and coherent sources under a hierarchical SBI framework. The Gauss-Exp-Chi2 prior distribution exhibits a sharp peak at the origin and heavy tails, and this property makes it an appropriate prior to encourage sparse solutions. A three-layer hierarchical sparse Bayesian model is established. Then, by exploiting variational Bayesian approximation, the model parameters are estimated by alternately updating until Kullback-Leibler (KL) divergence between the true posterior and the variational approximation becomes zero. By constructing the source power spectra with the estimated model parameters, the number and locations of the highest peaks are extracted to obtain source number and DOA estimates. In addition, some implementation details for algorithm optimization are discussed and the Cramér-Rao bound (CRB) of DOA estimation is derived. Simulation results demonstrate the effectiveness and favorable performance of the proposed algorithm as compared with the state-of-the-art sparse Bayesian algorithms. [ABSTRACT FROM AUTHOR]

Biterm Topic Model (BTM) is an effective topic model proposed to handle short texts. However, its standard gibbs sampling inference method (StdBTM) costs much more time than that (StdLDA) of Latent Dirichlet Allocation (LDA). To solve this problem we propose two time-efficient gibbs sampling inference methods, SparseBTM and ESparseBTM, for BTM by making a tradeoff between space and time consumption in this paper. The idea of SparseBTM is to reduce the computation in StdBTM by both recycling intermediate results and utilizing the sparsity of count matrix NWT. Theoretically, SparseBTM reduces the time complexity of StdBTM from O(|B| K) to O(|B| Kw) which scales linearly with the sparsity of count matrix NWT (Kw) instead of the number of topics (K) (Kw < K, Kw is the average number of non-zero topics per word type in count matrix NWT). Experimental results have shown that in good conditions SparseBTM is approximately 18 times faster than StdBTM. Compared with SparseBTM, ESparseBTM is a more time-efficient gibbs sampling inference method proposed based on SparseBTM. The idea of ESparseBTM is to reduce more computation by recycling more intermediate results through rearranging biterm sequence. In theory, ESparseBTM reduces the time complexity of SparseBTM from O(|B|Kw) to O(R|B|Kw) (0 < R < 1, R is the ratio of the number of biterm types to the number of biterms). Experimental results have shown that the percentage of the time efficiency improved by ESparseBTM on SparseBTM is between 6.4% and 39.5% according to different datasets. [ABSTRACT FROM AUTHOR]

Sample Entropy is the most popular definition of entropy and is widely used as a measure of the regularity/complexity of a time series. On the other hand, it is a computationally expensive method which may require a large amount of time when used in long series or with a large number of signals. The computationally intensive part is the similarity check between points in m dimensional space. In this paper, we propose new algorithms or extend already proposed ones, aiming to compute Sample Entropy quickly. All algorithms return exactly the same value for Sample Entropy, and no approximation techniques are used. We compare and evaluate them using cardiac inter-beat (RR) time series. We investigate three algorithms. The first one is an extension of the kd-trees algorithm, customized for Sample Entropy. The second one is an extension of an algorithm initially proposed for Approximate Entropy, again customized for Sample Entropy, but also improved to present even faster results. The last one is a completely new algorithm, presenting the fastest execution times for specific values of m, r, time series length, and signal characteristics. These algorithms are compared with the straightforward implementation, directly resulting from the definition of Sample Entropy, in order to give a clear image of the speedups achieved. All algorithms assume the classical approach to the metric, in which the maximum norm is used. The key idea of the two last suggested algorithms is to avoid unnecessary comparisons by detecting them early. We use the term unnecessary to refer to those comparisons for which we know a priori that they will fail at the similarity check. The number of avoided comparisons is proved to be very large, resulting in an analogous large reduction of execution time, making them the fastest algorithms available today for the computation of Sample Entropy. [ABSTRACT FROM AUTHOR]

In this paper we study the bounded perturbation resilience of the extragradient and the subgradient extragradient methods for solving a variational inequality (VI) problem in real Hilbert spaces. This is an important property of algorithms which guarantees the convergence of the scheme under summable errors, meaning that an inexact version of the methods can also be considered. Moreover, once an algorithm is proved to be bounded perturbation resilience, superiorization can be used, and this allows flexibility in choosing the bounded perturbations in order to obtain a superior solution, as well explained in the paper. We also discuss some inertial extragradient methods. Under mild and standard assumptions of monotonicity and Lipschitz continuity of the VI's associated mapping, convergence of the perturbed extragradient and subgradient extragradient methods is proved. In addition we show that the perturbed algorithms converge at the rate of $O(1/t)$ . Numerical illustrations are given to demonstrate the performances of the algorithms. [ABSTRACT FROM AUTHOR]

This work focuses on optimal harvesting problems for a stochastic competitive ecosystem subject to Lévy noise. A verification theorem for corresponding harvesting strategy is established, which offers sufficient conditions for deriving an optimal harvesting strategy and an upper bound of the value function. For a given instantaneous marginal yields function, a concrete upper bound of value function is constructed by applying the verification theorem obtained in this paper. Meanwhile, the monotonicity of value function is investigated. Also, an ε-optimal harvesting strategy is designed to find an approximate optimal harvesting strategy for those harvesting problems with no exact optimal harvesting strategy. Finally, by choosing appropriately Markov decision process defined on a discrete state space, a computational method for an optimal harvesting strategy is designed and a concrete example is also given to show the implementation of the algorithm. [ABSTRACT FROM AUTHOR]

Probabilistic principal component regression (PPCR) has been introduced for soft sensor modeling as a probabilistic projection regression method, which is effective in handling data collinearity and random noises. However, the linear limitation of data relationships may cause its performance deterioration when applied to nonlinear processes. Therefore, a novel weighted PPCR (WPPCR) algorithm is proposed in this paper for soft sensing of nonlinear processes. In WPPCR, by including the most relevant samples for local modeling, different weights will be assigned to these samples according to their similarities with the testing sample. Then, a weighted log-likelihood function is constructed, and expectation-maximization algorithm can be carried out iteratively to obtain the optimal model parameters. In this way, the nonlinear data relationship can be locally approximated by WPPCR. The effectiveness and flexibility of the proposed method are validated on a numerical example and an industrial process. [ABSTRACT FROM AUTHOR]

Geometrical wavelets have already proved their strength in approximation, compression, and denoising of piecewise constant and piecewise linear images. In this paper, we extend this family by introducing planelets toward an effective representation of indoor depth images. It uses a linear fractional model to capture non-linearity of depth values in the planar regions of the output images of Kinect-like sensors. A block-based compression framework based on planelet approximation is then presented, which uses quadtree decomposition along with spatial predictions as an effective intra-coding scheme. Compared with both classical geometric wavelets and some state-of-the-art image coding algorithms, our method provides desirable quality by explicitly representing edges and planar patches. [ABSTRACT FROM AUTHOR]

For ensemble learning, how to select and combine the candidate classifiers are two key issues which influence the performance of the ensemble system dramatically. Random vector functional link networks (RVFL) without direct input-to-output links is one of suitable base-classifiers for ensemble systems because of its fast learning speed, simple structure and good generalization performance. In this paper, to obtain a more compact ensemble system with improved convergence performance, an improved ensemble of RVFL based on attractive and repulsive particle swarm optimization (ARPSO) with double optimization strategy is proposed. In the proposed method, ARPSO is applied to select and combine the candidate RVFL. As for using ARPSO to select the optimal base RVFL, ARPSO considers both the convergence accuracy on the validation data and the diversity of the candidate ensemble system to build the RVFL ensembles. In the process of combining RVFL, the ensemble weights corresponding to the base RVFL are initialized by the minimum norm least-square method and then further optimized by ARPSO. Finally, a few redundant RVFL is pruned, and thus the more compact ensemble of RVFL is obtained. Moreover, in this paper, theoretical analysis and justification on how to prune the base classifiers on classification problem is presented, and a simple and practically feasible strategy for pruning redundant base classifiers on both classification and regression problems is proposed. Since the double optimization is performed on the basis of the single optimization, the ensemble of RVFL built by the proposed method outperforms that built by some single optimization methods. Experiment results on function approximation and classification problems verify that the proposed method could improve its convergence accuracy as well as reduce the complexity of the ensemble system. [ABSTRACT FROM AUTHOR]

The Booth multiplier has been widely used for high performance signed multiplication by encoding and thereby reducing the number of partial products. A multiplier using the radix-4 (or modified Booth) algorithm is very efficient due to the ease of partial product generation, whereas the radix-8 Booth multiplier is slow due to the complexity of generating the odd multiples of the multiplicand. In this paper, this issue is alleviated by the application of approximate designs. An approximate 2-bit adder is deliberately designed for calculating the sum of 1× and 2× of a binary number. This adder requires a small area, a low power and a short critical path delay. Subsequently, the 2-bit adder is employed to implement the less significant section of a recoding adder for generating the triple multiplicand with no carry propagation. In the pursuit of a trade-off between accuracy and power consumption, two signed 16 × 16 bit approximate radix-8 Booth multipliers are designed using the approximate recoding adder with and without the truncation of a number of less significant bits in the partial products. The proposed approximate multipliers are faster and more power efficient than the accurate Booth multiplier. The multiplier with 15-bit truncation achieves the best overall performance in terms of hardware and accuracy when compared to other approximate Booth multiplier designs. Finally, the approximate multipliers are applied to the design of a low-pass FIR filter and they show better performance than other approximate Booth multipliers. [ABSTRACT FROM AUTHOR]

This paper reports applying Minimax principle and impulsive differential inequality to derive the existence of multiple stationary solutions and the global stability of a positive stationary solution for a delayed feedback Gilpin–Ayala competition model with impulsive disturbance. The conclusion obtained in this paper reduces the conservatism of the algorithm compared with the known literature, for the impulsive disturbance is not limited to impulsive control. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of fast and efficient indexing techniques for sequences evolving in non-Euclidean spaces. This problem has several applications in the areas of human activity analysis, where there is a need to perform fast search, and recognition in very high dimensional spaces. The problem is made more challenging when representations such as landmarks, contours, and human skeletons etc. are naturally studied in a non-Euclidean setting where even simple operations are much more computationally intensive than their Euclidean counterparts. We propose a geometry and data adaptive symbolic framework that is shown to enable the deployment of fast and accurate algorithms for activity recognition, dynamic texture recognition, motif discovery. Toward this end, we present generalizations of key concepts of piece-wise aggregation and symbolic approximation for the case of non-Euclidean manifolds. We show that one can replace expensive geodesic computations with much faster symbolic computations with little loss of accuracy in activity recognition and discovery applications. The framework is general enough to work across both Euclidean and non-Euclidean spaces, depending on appropriate feature representations without compromising on the ultra-low bandwidth, high speed and high accuracy. The proposed methods are ideally suited for real-time systems and low complexity scenarios. [ABSTRACT FROM AUTHOR]

CANDECOMP/PARAFAC (CP) approximates multiway data by sum of rank-1 tensors. Unlike matrix decomposition, the procedure which estimates the best rank-R tensor approximation through R sequential best rank-1 approximations does not work for tensors, because the deflation does not always reduce the tensor rank. In this paper, we propose a novel deflation method for the problem. When one factor matrix of a rank-R CP decomposition is of full column rank, the decomposition can be performed through (R-1) rank-1 reductions. At each deflation stage, the residue tensor is constrained to have a reduced multilinear rank. For decomposition of order-3 tensors of size R\times R\times R and rank-R, estimation of one rank-1 tensor has a computational cost of \cal O(R^3) per iteration which is lower than the cost \cal O(R^4) of the ALS algorithm for the overall CP decomposition. The method can be extended to tracking one or a few rank-one tensors of slow changes, or inspect variations of common patterns in individual datasets. [ABSTRACT FROM PUBLISHER]

In many real applications such as virtual metrology in semiconductor manufacturing, face recognition, and gait recognition in computer vision, the input data is naturally expressed as tensors or multi-dimensional arrays. Furthermore, in addition to the known label information, domain knowledge can often be obtained from various sources, e.g., multiple domain experts. To address such problems, in this paper, we propose a general optimization framework for dealing with tensor inputs while taking into consideration domain knowledge. To be specific, our framework is based on a linear model, and we obtain the weight tensor in a hierarchical way-first approximate it by a low-rank tensor, and then estimate the low-rank approximation using the domain knowledge from various sources. This is motivated by wafer quality prediction in semiconductor manufacturing. We also propose an effective algorithm named H-MOTE for solving this framework, which is guaranteed to converge. For each iteration, the time complexity of H-MOTE is linear with respect to the number of examples as well as the size of the weight tensor. Therefore, H-MOTE is scalable to large-scale problems. Experimental results show that H-MOTE outperforms state-of-the-art techniques on both synthetic and real data sets. [ABSTRACT FROM AUTHOR]

This paper presents a derivation of four radix-2 division algorithms by digit recurrence. Each division algorithm selects a quotient digit from the over-redundant digit set {−2, −1, 0, 1, 2}, and the selection of each quotient digit depends only on the two most-significant digits of the partial remainder in a redundant representation. Two algorithms use a two’s complement representation for the partial remainder and carry-save additions, and the other two algorithms use a binary signed-digit representation for the partial remainder and carry-free additions. Three algorithms are novel. The fourth algorithm has been presented before. Results from the synthesized netlists show that two of our fastest algorithms achieve an improvement of 10 percent in latency per iteration over a standard radix-2 SRT algorithm at the cost of 36 percent more power and 50 percent more area. [ABSTRACT FROM PUBLISHER]

Given an undirected graph G = (V,E) with a nonnegative edge length function and an integer p, 0 < p < |V |, the p-centdian problem is to find p vertices (called the centdian set) of V such that the eccentricity plus median-distance is minimized, in which the eccentricity is the maximum (length) distance of all vertices to their nearest centdian set and the median-distance is the total (length) distance of all vertices to their nearest centdian set. The eccentricity plus median-distance is called the centdian-distance. The purpose of the p-centdian problem is to find p open facilities (servers) which satisfy the quality-of-service of the minimum total distance (median-distance) and the maximum distance (eccentricity) to their service customers, simultaneously. If we converse the two criteria, that is given the bound of the centdian-distance and the objective function is to minimize the cardinality of the centdian set, this problem is called the converse centdian problem. In this paper, we prove the p-centdian problem is NP-Complete. Then we design the first non-trivial brute force exact algorithms for the p-centdian problem and the converse centdian problem, respectively. Finally, we design two approximation algorithms for both problems. [ABSTRACT FROM AUTHOR]

This paper proposes an adaptive approximation-based controller for uncertain strict-feedback nonlinear systems with unknown dead-zone nonlinearity. Dead-zone constraint is represented as a combination of a linear system with a disturbance-like term. This work invokes neural networks (NNs) as a linear-in-parameter approximator to model uncertain nonlinear functions that appear in virtual and actual control laws. Minimal learning parameter (MLP) algorithm is proposed to decrease the computational load, the number of adjustable parameters, and to avoid the "explosion of learning parameters" problem. An adaptive TSK-type fuzzy system is proposed to estimate the disturbance-like term in the dead-zone description which further will be used to compensate the effect of the dead-zone, and it does not require the availability of the dead-zone input. Then, the proposed method based on the dynamic surface control (DSC) method is designed which avoids the "explosion of complexity" problem. Proposed scheme deals with dead-zone nonlinearity and uncertain dynamics without requiring the availability of any knowledge about them, and it develops a control input without singularity concern. Stability analysis shows that all the signals of the closed-loop system are semi-globally uniformly ultimately bounded and the tracking error converges to the vicinity of the origin. Simulation and comparison results verify the acceptable performance of the presented controller. [ABSTRACT FROM AUTHOR]

Randomized algorithms provide a powerful tool for scientific computing. Compared with standard deterministic algorithms, randomized algorithms are often faster and robust. The main purpose of this paper is to design adaptive randomized algorithms for computing the approximate tensor decompositions. We give an adaptive randomized algorithm for the computation of a low multilinear rank approximation of the tensors with unknown multilinear rank and analyze its probabilistic error bound under certain assumptions. Finally, we design an adaptive randomized algorithm for computing the tensor train approximations of the tensors. Based on the bounds about the singular values of sub-Gaussian matrices with independent columns or independent rows, we analyze these randomized algorithms. We illustrate our adaptive randomized algorithms via several numerical examples. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization (NMF) provides a lower rank approximation of a matrix by a product of two nonnegative factors. NMF has been shown to produce clustering results that are often superior to those by other methods such as K-means. In this paper, we provide further interpretation of NMF as a clustering method and study an extended formulation for graph clustering called Symmetric NMF (SymNMF). In contrast to NMF that takes a data matrix as an input, SymNMF takes a nonnegative similarity matrix as an input, and a symmetric nonnegative lower rank approximation is computed. We show that SymNMF is related to spectral clustering, justify SymNMF as a general graph clustering method, and discuss the strengths and shortcomings of SymNMF and spectral clustering. We propose two optimization algorithms for SymNMF and discuss their convergence properties and computational efficiencies. Our experiments on document clustering, image clustering, and image segmentation support SymNMF as a graph clustering method that captures latent linear and nonlinear relationships in the data. [ABSTRACT FROM AUTHOR]

The form, waviness and roughness components of a measured profile are separated by means of digital filters. The aim of analysis was to develop an algorithm for one-dimensional filtering of profiles using approximation by means of B-splines. The theory of B-spline functions introduced by Schoenberg and extended by Unser et al. was used. Unlike the spline filter proposed by Krystek, which is described in ISO standards, the algorithm does not take into account the bending energy of a filtered profile in the functional whose minimization is the principle of the filter. Appropriate smoothness of a filtered profile is achieved by selecting an appropriate distance between nodes of the spline function. In this paper, we determine the Fourier transforms of the filter impulse response at different impulse positions, with respect to the nodes. We show that the filter cutoff length is equal to half of the node-to-node distance. The inclination of the filter frequency characteristic in the transition band can be adjusted by selecting an appropriate degree of the B-spline function. The paper includes examples of separation of 2D roughness, as well as separation of form and waviness of roundness profiles. [ABSTRACT FROM AUTHOR]

This paper addresses a scheduling problem with continuous resources and energy constraints. Given a set of non-preemptive activities, each activity requires a continuously divisible resource whose instantaneous usage is limited in maximum and minimum, its processing satisfying a time window and a total energy (time $$\times $$ resource-usage) requirement. The goal consists of getting a schedule satisfying all the constraints. The problem, which we refer to as the Energy-Constrained Scheduling Problem with Continuous Resources (CECSP), is a generalization of the well-known cumulative scheduling problem for which the 'energetic reasoning' or 'left-shift/right-shift' necessary feasibility condition yielded a popular polynomially computable satisfiability test. The paper presents a generalization of the energetic reasoning for the CECSP, defining precisely the activity minimum consumptions and exhibiting a polynomial number of relevant time intervals on which it is sufficient to apply the satisfiability tests. A strongly polynomial energetic reasoning satisfiability test can be derived for the considered generalization, which also yields a short proof for the complexity of the original algorithm. Some limits of the approach, as well as an approximation framework for more general resource consumption functions, are also addressed. [ABSTRACT FROM AUTHOR]

Bipartite (BP) has been seen to be a fast and accurate suboptimal algorithm to solve the Error-Tolerant Graph Matching problem. Recently, Fast Bipartite (FBP) has been presented that obtains the same distance value and node labelings but in a reduced time. Both algorithms approximate the quadratic problem in a linear problem and they do it through a specific cost matrix. FBP imposes the Edit costs to be defined such as the Edit distance is a distance function. Originally, the Hungarian method was used but it has been seen the Jonker-Volgenant linear solver obtains similar results than the Hungarian method but with an important run time reduction. Nevertheless, this second solver has some convergence problems on some specific cost matrices. The aim of this paper is to define a new cost matrix such that the Jonker-Volgenant solver converges and the matching algorithm obtains the same distance value than the BP algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new viscosity approximation method by using the shrinking projection algorithm to approximate a common fixed point of a countable family of nonlinear mappings in a Banach space. Under quite mild assumptions, we establish the strong convergence of the sequence generated by the proposed algorithm and provide an affirmative answer to an open problem posed by Maingé (Comput. Math. Appl. 59:74-79, 2010) for quasi-nonexpansive mappings. In contrast with related processes, our method does not require any demiclosedness principle condition imposed on the involved operators belonging to the wide class of quasi-nonexpansive operators. As an application, we also introduce an iterative algorithm for finding a common element of the set of common fixed points of an infinite family of quasi-nonexpansive mappings and the set of solutions of a mixed equilibrium problem in a real Banach space. We prove a strong convergence theorem by using the proposed algorithm under some suitable conditions. Our results improve and generalize many known results in the current literature. [ABSTRACT FROM AUTHOR]

In this paper, we address the theoretical aspects of coherence region modeling and its inversion methods for polarimetric interferometric synthetic aperture radar (PolInSAR). Instead of only considering the geometrical shape of the coherence region, we focus on directly modeling the whitened interferometric cross-correlation matrix of the PolInSAR data. In particular, we consider three classes of generic scattering models that respectively contain single, double, and triple phase centers within one resolution cell. We then demonstrate, for each class, that the modeled whitened interferometric cross-correlation matrix is normal. Based on this property, we propose, for each case, efficient algorithms to obtain the best normal matrix approximation solution for model inversion from the observed whitened interferometric cross-correlation matrix. In addition, we show how a simple and effective criterion can be designed from the derived solutions for model validation. Finally, we verify the solutions with both simulated and real data. The results prove the proposed method to be a very promising tool for PolInSAR applications. [ABSTRACT FROM PUBLISHER]

Very recently Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] initiate a new systematic way of studying online problems by introducing the competitive ratio approximation scheme (simplified as competitive schemes in this paper), which is a class of algorithms {Aϵ|ϵ > 0} with a competitive ratio at most ρ*(1 + ϵ), where ρ* is the best possible competitive ratio over all online algorithms. Along this line, Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] provide competitive schemes for several online over time scheduling problems like Qm|rj, (pmtn)|∑wjcj, while the running times are polynomial if the number of machines is a constant. In this paper, we consider the classical online scheduling problems, where jobs arrive in a list. We present competitive schemes for Rm‖Cmax and Rm‖ ∑iCip , where the running times are polynomial if the number of machines is a constant. Specifically, we are able to derive a competitive scheme for P‖Cmax which runs in polynomial time even if the number of machines is an input. Our method is novel and more efficient than that of Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] Indeed, by utilizing the standard rounding technique for the off-line scheduling problems, we reformulate the online scheduling problem into a game on an infinite graph, through which we arrive at the following key point: Assuming that the best competitive ratio is ρ*, for any online algorithm there exists a list of a polynomial number of jobs showing that its competitive ratio is at least ρ* - O(ϵ). Interestingly such a result is achieved via a dynamic programming algorithm. Our framework is also applicable to other online problems. [ABSTRACT FROM AUTHOR]