Search

This paper presents a novel learning algorithm for efficient construction of the radial basis function (RBF) networks that can deliver the same level of accuracy as the support vector machines (SVMs) in data classification applications. The proposed learning algorithm works by constructing one RBF subnetwork to approximate the probability density function of each class of objects in the training data set. With respect to algorithm design, the main distinction of the proposed learning algorithm is the novel kernel density estimation algorithm that features an average time complexity of O(n log n), where vi is the number of samples in the training data set. One important advantage of the proposed learning algorithm, in comparison with the SVM, is that the proposed learning algorithm generally takes far less time to construct a data classifier with an optimized parameter setting. This feature is of significance for many contemporary applications, in particular, for those applications in which new objects are continuously added into an already large database. Another desirable feature of the proposed learning algorithm is that the RBF networks constructed are capable of carrying out data classification with more than two classes of objects in one single run. In other words, unlike with the SVM, there is no need to resort to mechanisms such as one-against-one or one-against-all for handling datasets with more than two classes of objects. The comparison with SVM is of particular interest, because it has been shown in a number of recent studies that SVM generally are able to deliver higher classification accuracy than the other existing data classification algorithms. As the proposed learning algorithm is instance-based, the data reduction issue is also addressed in this paper. One interesting observation in this regard is that, for all three data sets used in data reduction experiments, the number of training samples remaining after a naïve data reduction mechanism is applied is quite close to the number of support vectors identified by the SVM software. This paper also compares the performance of the RBF networks constructed with the proposed learning algorithm and those constructed with a conventional cluster-based learning algorithm. The most interesting observation learned is that, with respect to data classification, the distributions of training samples near the bound- aries between different classes of objects carry more crucial information than the distributions of samples in the inner parts of the clusters. [ABSTRACT FROM AUTHOR]

Device-to-Device (D2D) networks impose a significant challenge on delay-sensitive crowdsourcing due to the highly non-deterministic and intermittent network connectivity. Under this setting, the paper investigates a participant recruitment problem in which an initial set of recruited nodes, which we call seeds, need to make an optimal decision on what other nodes to recruit to perform the crowdsourcing task. These seeds face the dilemma that recruiting more nodes increases their own payment but on the other hand also increases the risk of being excluded from the crowdsourcing task. As a first attack to this problem, we propose a dynamic programming algorithm. However, it is a centralized solution and hence the practicality is compromised. Therefore, we introduce two distributed alternatives. One is based on the divide-and-conquer paradigm by first partitioning a network into a set of opportunistic Voronoi cells and then running an optimization algorithm in each cell. The other is a task-splitting scheme which recursively delegates the recruitment task to newly joined nodes. We implemented our proposed solutions on an Android-based prototype and built a testbed using 25 Dell Streak tablets. Our experiments which lasted for 24 days demonstrate that the distributed schemes approximate the theoretical optimum with affordable complexity. Moreover, we conducted simulations with a much larger scale and more diverse settings. The simulation results corroborate the experimental data and confirm that our proposed distributed solutions closely approach the performance of the centralized solution while satisfying the optimization goal under different network configurations. [ABSTRACT FROM AUTHOR]

Algorithms that make use of the gradient, i.e., the direction of maximum improvement, to search for the optimum of a single-objective function have been around for decades. They are commonly accepted to be important and have been applied to tackle single-objective optimization problems in many fields. For multiobjective optimization problems, much less is known about the gradient and its algorithmic use. In this paper, we aim to contribute to the understanding of gradients for numerical, i.e., real-valued, multiobjective optimization. Specifically, we provide an analytical parametric description of the set of all nondominated, i.e., most promising, directions in which a solution can be moved such that the objective values either improve or remain the same. This result completes previous work where this set is described only for one particular case, namely when some of the nondominated directions have positive, i.e., nonimproving, components and the final set can be computed by taking the subset of directions that are all nonpositive. In addition we use our result to assess the utility of using gradient information for multiobjective optimization where the goal is to obtain a Pareto set of solutions that approximates the optimal Pareto set. To this end, we design and consider various multiobjective gradient-based optimization algorithms. One of these algorithms uses the description of the multiobjective gradient provided here. Also, we hybridize an existing multiobjective evolutionary algorithm (MOEA) with the various multiobjective gradient-based optimization algorithms. During optimization, the performance of the gradient-based optimization algorithms is monitored and the available computational resources are redistributed to allow the (currently) most effective algorithm to spend the most resources. We perform an experimental analysis using a few well-known benchmark problems to compare the performance of different optimization methods. The results underline that the use of a population of solutions that is characteristic of MOEAs is a powerful concept if the goal is to obtain a good Pareto set, i.e., instead of only a single solution. This makes it hard to increase convergence speed in the initial phase using gradient information to improve any single solution. However, in the longer run, the use of gradient information does ultimately allow for better fine-tuning of the results and thus better overall convergence. [ABSTRACT FROM PUBLISHER]

This paper studies a problem of image restoration that observed images are contaminated by Gaussian and impulse noise. Existing methods for this problem in the literature are based on minimizing an objective functional having the \ell^1 fidelity term and the Mumford–Shah regularizer. We present an algorithm on this problem by minimizing a new objective functional. The proposed functional has a content-dependent fidelity term which assimilates the strength of fidelity terms measured by the \ell^1 and \ell^2 norms. The regularizer in the functional is formed by the \ell^1 norm of tight framelet coefficients of the underlying image. The selected tight framelet filters are able to extract geometric features of images. We then propose an iterative framelet-based approximation/sparsity deblurring algorithm (IFASDA) for the proposed functional. Parameters in IFASDA are adaptively varying at each iteration and are determined automatically. In this sense, IFASDA is a parameter-free algorithm. This advantage makes the algorithm more attractive and practical. The effectiveness of IFASDA is experimentally illustrated on problems of image deblurring with Gaussian and impulse noise. Improvements in both PSNR and visual quality of IFASDA over a typical existing method are demonstrated. In addition, Fast_IFASDA, an accelerated algorithm of IFASDA, is also developed. [ABSTRACT FROM AUTHOR]

In this paper, low-complexity joint power assignment algorithms are developed for multi-source multi-destination relay networks where multiple sources share a common relay that forwards all received signals simultaneously to destinations. In particular, we consider the following power optimization strategies: (i) Minimization of the total transmission power of the sources and the relay under the constraint that the signal-to-interference-plus-noise ratio (SINR) requirement of each source-destination pair is satisfied, and (ii) Maximization of the minimum SINR among all source-destination pairs subject to any given total power budget. Both optimization problems involve K power variables, where K is the number of source-destination pairs in the network, and an exhaustive search is prohibitive for large K. In this work, we develop a methodology that allows us to obtain an asymptotically tight approximation of the SINR and reformulate the original optimization problems to single-variable optimization problems, which can be easily solved by numerical search of the single variable. Then, the corresponding optimal transmission power at each source and relay can be calculated directly. The proposed optimization schemes are scalable and lead to power assignment algorithms that exhibit the same optimization complexity for any number (K) of source-destination pairs in the network. Moreover, we apply the methodology that we developed to solve a related max-min SINR based optimization problem in which we determine power assignment for the sources and the relay to maximize the minimum SINR among all source-destination pairs subject to any given total power budget. Extensive numerical studies illustrate and validate our theoretical developments. [ABSTRACT FROM AUTHOR]

In evolutionary multiobjective optimization, the task of the optimizer is to obtain an accurate and useful approximation of the true Pareto-optimal front. Proximity to the front and diversity of solutions within the approximation set are important requirements. Most established multiobjective evolutionary algorithms (MOEAs) have mechanisms that address these requirements. However, in many-objective optimization, where the number of objectives is greater than 2 or 3, it has been found that these two requirements can conflict with one another, introducing problems such as dominance resistance and speciation. In this paper, two diversity management mechanisms are introduced to investigate their impact on overall solution convergence. They are introduced separately, and in combination, and tested on a set of test functions with an increasing number of objectives (6–20). It is found that the inclusion of one of the mechanisms improves the performance of a well-established MOEA in many-objective optimization problems, in terms of both convergence and diversity. The relevance of this for many-objective MOEAs is discussed. [ABSTRACT FROM AUTHOR]

High availability communication networks with very low failure rates are often designed by using physical diversity, i.e., the traffic between a given pair of nodes is routed by using several physically disjoint paths. The selection of the pair of routes that maximizes the connectivity of a node is not an easy problem, because such connectivity cannot be expressed as an additive function of the availability of links and nodes in the path pairs. Previous algorithms for searching the optimal route use additive costs, which can be a loose assumption either when high failure rates can be locally present, or when fully disjoints paths do not exist. In this paper, we construct a Bayesian network to encode the probabilistic relation between the connectivity of a node and the availability of nodes and links. The problem of selecting an optimal pair of routes becomes equivalent to optimizing the structure of the Bayesian network. By introducing appropriate approximations on the double route availability equations, we propose a new algorithm, which outperforms other classical methods when there are sporadic high error rate elements in the network. Simulations and an application example in an electric transport telecontrol network show the performance of the method when compared to standard search. [ABSTRACT FROM AUTHOR]

Using surrogate models in evolutionary search provides an efficient means of handling today's complex applications plagued with increasing high-computational needs. Recent surrogate-assisted evolutionary frameworks have relied on the use of a variety of different modeling approaches to approximate the complex problem landscape. From these recent studies, one main research issue is with the choice of modeling scheme used, which has been found to affect the performance of evolutionary search significantly. Given that theoretical knowledge available for making a decision on an approximation model a priori is very much limited, this paper describes a generalization of surrogate-assisted evolutionary frameworks for optimization of problems with objectives and constraints that are computationally expensive to evaluate. The generalized evolutionary framework unifies diverse surrogate models synergistically in the evolutionary search. In particular, it focuses on attaining reliable search performance in the surrogate-assisted evolutionary framework by working on two major issues: 1) to mitigate the 'curse of uncertainty' robustly, and 2) to benefit from the 'bless of uncertainty.' The backbone of the generalized framework is a surrogate-assisted memetic algorithm that conducts simultaneous local searches using ensemble and smoothing surrogate models, with the aims of generating reliable fitness prediction and search improvements simultaneously. Empirical study on commonly used optimization benchmark problems indicates that the generalized framework is capable of attaining reliable, high quality, and efficient performance under a limited computational budget. [ABSTRACT FROM AUTHOR]

The goal of the sparse approximation problem is to approximate a target signal using a linear combination of a few elementary signals drawn from a fixed collection. This paper surveys the major practical algorithms for sparse approximation. Specific attention is paid to computational issues, to the circumstances in which individual methods tend to perform well, and to the theoretical guarantees available. Many fundamental questions in electrical engineering, statistics, and applied mathematics can be posed as sparse approximation problems, making these algorithms versatile and relevant to a plethora of applications. [ABSTRACT FROM AUTHOR]

Dynamic spectrum management (DSM) has been recognized as a key technology to significantly improve the performance of digital subscriber line (DSL) broadband access networks. The basic concept of DSM is to coordinate transmission over multiple DSL lines so as to mitigate the impact of crosstalk interference amongst them. Many algorithms have been proposed to tackle the nonconvex optimization problems appearing in DSM, many of them relying on a standard subgradient based dual decomposition approach. In practice however, this approach is often found to lead to extremely slowconvergence or even no convergence at all, one of the reasons being the very difficult tuning of the stepsize parameters. In this paper we propose a novel improved dual decomposition approach inspired by recent advances in mathematical programming. It uses a smoothing technique for the Lagrangian combined with an optimal gradient based scheme for updating the Lagrange multipliers. The stepsize parameters are furthermore selected optimally removing the need for a tuning strategy. With this approach we show how the convergence of current state-of-the-art DSM algorithms based on iterative convex approximations (SCALE and CA-DSB)can be improvedby one order of magnitude. Furthermore we apply the improved dual decomposition approach to otherDSM algorithms (OSB, ISB, ASB, (MS)-DSB, and MIW) and propose further improvements to obtain fast and robust DSM algorithms. Finally, we demonstrate the effectiveness of the improved dual decomposition approach for a number of realistic multiuser DSL scenarios. [ABSTRACT FROM AUTHOR]

ℓ0 norm based algorithms have numerous potential applications where a sparse signal is recovered from a small number of measurements. The direct ℓ0 norm optimization problem is NP-hard. In this paper we work with the the smoothed ℓ0 (SL0) approximation algorithm for sparse representation. We give an upper bound on the run-time estimation error. This upper bound is tighter than the previously known bound. Subsequently, we develop a reliable stopping criterion. This criterion is helpful in avoiding the problems due to the underlying discontinuities of the ℓ0 cost function. Furthermore, we propose an alternative optimization strategy, which results in a Newton like algorithm. [ABSTRACT FROM AUTHOR]

Assuming that evolutionary multiobjective optimization (EMO) mainly deals with set problems, one can identify three core questions in this area of research: 1) how to formalize what type of Pareto set approximation is sought; 2) how to use this information within an algorithm to efficiently search for a good Pareto set approximation; and 3) how to compare the Pareto set approximations generated by different optimizers with respect to the formalized optimization goal. There is a vast amount of studies addressing these issues from different angles, but so far only a few studies can be found that consider all questions under one roof. This paper is an attempt to summarize recent developments in the EMO field within a unifying theory of set-based multiobjective search. It discusses how preference relations on sets can be formally defined, gives examples for selected user preferences, and proposes a general preference-independent hill climber for multiobjective optimization with theoretical convergence properties. Furthermore, it shows how to use set preference relations for statistical performance assessment and provides corresponding experimental results. The proposed methodology brings together preference articulation, algorithm design, and performance assessment under one framework and thereby opens up a new perspective on EMO. [ABSTRACT FROM AUTHOR]

The goal of multiobjective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multiobjective optimizers providing them, unary quality measures are usually applied. Among these, the hypervolume indicator (or S-metric) is of particular relevance due to its favorable properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as guidance criterion for finding good approximations to the Pareto front. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee's Measure Problem. In general, Klee's Measure Problem can solved with O(n log n + nd/2 log n) comparisons for an input instance of size n in d dimensions; as of this writing, it unknown whether a lower bound higher than Ω (n log n) be proven. In this paper, we derive a lower bound of Ω (n log n) for the complexity of computing the hypervolume indicator any number of dimensions d > 1 by reducing the so-called UNIFORMGAP problem to it. For the 3-D case, we also present matching upper bound of O (n log n) comparisons that is obtained by extending an algorithm for finding the maxima of a point set. [ABSTRACT FROM AUTHOR]

This paper investigates how recursive partitioning methods can be adapted to the bipartite ranking problem. In ranking, the pursued goal is global: based on past data, define an order on the whole input space X, so that positive instances take up the top ranks with maximum probability. The most natural way to order all instances consists of projecting the input data onto the real line through a real-valued scoring function s and use the natural order on ℝ. The accuracy of the ordering induced by a candidate s is classically measured in terms of the ROC curve or the AUC. Here we discuss the design of tree-structured scoring functions obtained by recursively maximizing the AUC criterion. The connection with recursive piecewise linear approximation of the optimal ROC curve both in the L1-sense and in the L∞-sense is highlighted. A novel tree-based algorithm for ranking, called TREERANK, is proposed. Consistency results and generalization bounds of functional nature are established for this ranking method, when considering either the L1 or L∞ distance. We also describe committee-based learning procedures using TREERANK as a "base ranker," in order to overcome obvious drawbacks of such a top-down partitioning technique. Simulation results on artificial data are also displayed. [ABSTRACT FROM AUTHOR]

In this paper, we introduce an approach for the design of electromagnetic devices based on the use of Estimation of Distribution Algorithms (EDAs), coupled with approximation-based local search around the most promising solutions. The main idea is to combine the power of EDAs in the solution of hard optimization problems with the faster convergence provided by the local search using local approximations. The resulting hybrid algorithm is tested on a numerical benchmark problem. [ABSTRACT FROM AUTHOR]

Worldwide interoperability for microwave access (WiMAX) is a promising technology for last-mile Internet access, particularly in the areas where wired infrastructures are not available. In a WiMAX network, call admission control (CAC) is deployed to effectively control different traffic loads and prevent the network from being overloaded. In this paper, we propose a framework of a 2-D CAC to accommodate various features of WiMAX networks. Specifically, we decompose the 2-D uplink and downlink WiMAX CAC problem into two independent 1-D CAC problems and formulate the 1-D CAC optimization, in which the demands of service providers and subscribers are jointly taken into account. To solve the optimization problem, we develop a utility- and fairness-constrained optimal revenue policy, as well as its corresponding approximation algorithm. Simulation results are presented to demonstrate the effectiveness of the proposed WiMAX CAC approach. [ABSTRACT FROM AUTHOR]

In this paper, a motion-compensated de-interlacing algorithm using the Markov random field (MRF) model is proposed. The de-interlacing problem is formulated as a maximum a posteriori (MAP) MRF problem. The MAP solution is the one that minimizes an energy function, which imposes discontinuity-adaptive smoothness (DAS) spatial constraint on the de-interlaced frame. The edge direction information, which is used to formulate the DAS constraint, is implicitly indicated by weight vectors (weights for 16 digitized directions). Generally, large weights are assigned to along-edge directions and relatively small weights are assigned to across-edge directions. As a local statistical-based method, the proposed weighting method should be more robust than traditional edge-directed interpolation methods in deciding local edge directions. The proposed algorithm is implemented by an iterative optimization process, which guarantees convergence. However, a global optimal solution is not guaranteed due to computational complexity concern. Simulation results compare the proposed algorithm to other motion compensated de-interlacing algorithms. Significant improvements of de-interlaced edges are observed. [ABSTRACT FROM AUTHOR]

The proper choice of mapping used in space-mapping optimization algorithms is typically problem dependent. The number of parameters of the space-mapping surrogate model must be adjusted so that the model is flexible enough to reflect the features of the fine model, but at the same time is not over flexible. Its extrapolation capability should allow the prediction of the fine model response in the neighborhood of the current iteration point. A wrong choice of space-mapping type may lead to poor performance of the space-mapping optimization algorithm. In this paper, we consider a space-mapping optimization algorithm with an adaptive surrogate model. This allows us to adjust the type of space-mapping surrogate model used in a given iteration based on the approximation/extrapolation capability of the model. The technique does not require any additional fine model evaluations. [ABSTRACT FROM AUTHOR]

The aim of this paper is to develop discrete stochastic approximation algorithms that adaptively optimize the spreading codes of users in a code-division multiple-access (CDMA) system employing linear minimum mean-square error (MMSE) receivers. The proposed algorithms are able to adapt to slowly time-varying channel conditions. One of the most important properties of the algorithms is their self-learning capability-they spend most of the computational effort at the global optimizer of the objective function. Tracking analysis of the adaptive algorithms is presented together with mean-square convergence. An adaptive-step-size algorithm is also presented for optimally adjusting the step size based on the observations. Numerical examples, illustrating the performance of the algorithms in multipath fading channels, show substantial improvement over heuristic algorithms. [ABSTRACT FROM AUTHOR]

Image interpolation is a key aspect of digital image processing. This paper presents a novel interpolation method based on optimal recovery and adaptively determining the quadratic signal class from the local image behavior. The advantages of the new interpolation method are the ability to interpolate directly by any factor and to model properties of the data acquisition system into the algorithm itself. Through comparisons with other algorithms it is shown that the new interpolation is not only mathematically optimal with respect to the underlying image model, but visually it is very efficient at reducing jagged edges, a place where most other interpolation algorithms fail. [ABSTRACT FROM AUTHOR]

A greedy algorithm for a class of convex optimization problems is presented in this paper. The algorithm is motivated from function approximation using sparse combination of basis functions as well as some of its variants. We derive a bound on the rate of approximate minimization for this algorithm, and present examples of its application. Our analysis generalizes a number of earlier studies. [ABSTRACT FROM AUTHOR]

In this paper, we prove some convergence properties for a class of ant colony optimization algorithms. In particular, we prove that for any small constant ∈ > 0 and for a sufficiently large number of algorithm iterations t, the probability of finding an optimal solution at least once is P* (t) ≥ 1 -- ∈ and that this probability tends to 1 for t → ∞. We also prove that, after an optimal solution has been found, it takes a finite number of iterations for the pheromone trails associated to the found optimal solution to grow higher than any other pheromone trail and that, for t → ∞, any fixed ant will produce the optimal solution during the tth iteration with probability P ≥ 1 -- ∈ (τ[submin], τ[submax]), where τ[submin] and τ[submax], are the minimum and maximum values that can be taken by pheromone trails. [ABSTRACT FROM AUTHOR]

While noise is a phenomenon present in many real-world optimization problems, the understanding of its potential effects on the performance of evolutionary algorithms is still incomplete. This paper investigates the effects of fitness proportionate Gaussian noise for a (1 + 1)-ES with isotropic normal mutations on the quadratic sphere in the limit of infinite search-space dimensionality. It is demonstrated experimentally that the results provide a good approximation for finite space dimensionality. It is shown that overvaluation as a result of failure to reevaluate parental fitness leads to both reduced success probabilities and improved performance. Implications for mutation strength adaptation rules are discussed and optimal resampling rates are computed. [ABSTRACT FROM AUTHOR]

This paper presents a novel parametric representation for bidirectional texture functions. Our method mainly relies on two original techniques, namely, multivariate spherical radial basis functions (SRBFs) and optimized parameterization. First, since the surface appearance of a real-world object is frequently a mixed effect of different physical factors, the proposed sum-of-products model based on multivariate SRBFs especially provides an intrinsic and efficient representation for heterogenous materials. Second, optimized parameterization particularly aims at overcoming the major disadvantage of traditional fixed parameterization. By using a parametric model to account for variable transformations, the parameterization process can be tightly integrated with multivariate SRBFs into a unified framework. Finally, a hierarchical fitting algorithm for bidirectional texture functions is developed to exploit spatial coherence and reduce computational cost. Our experimental results further reveal that the proposed representation can easily achieve high-quality approximation and real-time rendering performance. [ABSTRACT FROM AUTHOR]