Search

The main contribution of this paper is to present a recursive estimation/detection technique for reduced-order state-space systems. The recursive state and parameter estimator is built on the framework of polynomial chaos theory and maximum likelihood estimation. The estimator quantifies the reliability of its estimate in real-time by recursively calculating a signal-to-noise ratio. The signal-to-noise ratio (SNR) indicates how well the output of the reduced-order estimation model matches the actual system output. A detection algorithm makes decisions to trust or distrust the current estimate by comparing the current value of the SNR ratio against a threshold value. This paper applies the proposed techniques to estimate the sprung mass of an actual vehicle. It uses a reduced-order model to approximate the complex ride dynamics of the vehicle. Despite the modeling approximations and simplifications, the proposed technique is able to reliably estimate the sprung mass of the vehicle to within 10% of the true value. [ABSTRACT FROM AUTHOR]

This paper is focused on the development and analysis of suboptimal decision algorithms for a collection of robots that assist a remotely located operator in perimeter surveillance. The operator is tasked with the classification of incursions across the perimeter. whenever there is an incursion into the perimeter, an unattended ground sensor (UGS) in the vicinity, signals an alert. A robot services the alert by visiting the alert location, collecting information, e.g., photo and video imagery, and transmitting it to the operator. The accuracy of operator's classification depends on the volume and freshness of information gathered and provided by the robots at locations where incursions occur. There are two competing objectives for a robot: it needs to spend adequate time at an alert location to collect evidence for aiding the operator in accurate classification but it also needs to service other alerts as soon as possible, so that the evidence collected is relevant. The decision problem is to determine the optimal amount of time a robot must spend servicing an alert. The incursions are stochastic and their statistics are assumed to be known. This problem can be posed as a Markov Decision Problem. However, even for two robots and five UGS locations, the number of states is of the order of billions rendering exact dynamic programming methods intractable. Approximate dynamic programming (ADP) via linear programming (LP) provides a way to approximate the value function and derive suboptimal strategies. The novel feature of this paper is the derivation of a tractable lower bound via LP and the construction of a suboptimal policy whose performance improves upon the lower bound. An illustrative perimeter surveillance example corroborates the results derived in this paper. [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]

This paper considers multirobot task allocation problems where the estimated costs for performing tasks are interrelated, and the overall team objective need not be a standard sum-of-costs (or utilities) model, enabling straightforward treatment of the additional costs incurred by resource contention. In the model we introduce, a team may choose one of a set of shared resources to perform a task (e.g., several routes to reach a destination), and interference is modeled when multiple robots use the same resource. We show that the general problem is NP-hard, and investigate specialized subinstances with particular cost structures. For the general problem, we describe an exact algorithm which finds an optimal assignment in a reasonable time on small instances. Aiming at larger problems, we turn two particular subinstances, introducing an two algorithms that find assignments quickly even for problems of considerable size, the first being optimal, the second being an approximation algorithm but also producing high-quality solutions with bounded suboptimality. [ABSTRACT FROM PUBLISHER]

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 greedy maximal scheduling (GMS) and maximal scheduling (MS) algorithms are well-known low-complexity scheduling policies with guaranteed capacity region in the context of single-radio single-channel (SR-SC) wireless networks. However, how to design maximal scheduling algorithms for multiradio multichannel (MR-MC) wireless networks and the associated capacity analysis are not well understood yet. In this paper, we develop a new model by transforming an MR-MC network node to multiple node-radio-channel (NRC) tuples. Such a framework facilitates the derivation of a tuple-based back-pressure algorithm for throughput-optimal control in MR-MC wireless networks and enables the tuple-based GMS and MS scheduling as low-complexity approximation algorithms with guaranteed performance. An important existing work on GMS and MS for MR-MC networks is that of Lin and Rasool (IEEE/ACM Trans. Networking, vol. 17, no. 6, 1874–1887, Dec. 2009), where link-based algorithms are developed. Compared to the link-based algorithms, the tuple-based modeling has significant advantages in enabling a fully decomposable cross-layer control framework. Another theoretical contribution in this paper is that we, for the first time, extend the local-pooling factor analysis to study the capacity efficiency ratio of the tuple-based GMS in MR-MC networks and obtain a lower bound that is much tighter than those known in the literature. Moreover, we analyze the communications and computation overhead in implementing the distributed MS algorithm and present simulation results to demonstrate the performance of the tuple-based maximal scheduling algorithms. [ABSTRACT FROM PUBLISHER]

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]

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]

This paper contributes to a point-to-point iterative learning control problem for stochastic systems without prior information on system matrices. The stochastic approximation technique with gradient estimation by random difference is introduced to design the update law for input. It is strictly proved that the input sequence would converge almost surely to the optimal one, which minimizes the averaged tracking performance index. An illustrative simulation shows the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

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 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]

Most partitioning algorithms iteratively partition a space into cells that contain underlying linear or nonlinear structures using linear partitioning strategies. The compactness of each cell depends on how well the (locally) linear partitioning strategy approximates the intrinsic structure. To partition a compact structure for complex data in a nonlinear context, this paper proposes a nonlinear partition strategy. This is a principal curve tree (PC-tree), which is implemented iteratively. Given that a PC passes through the middle of the data distribution, it allows for partitioning based on the arc length of the PC. To enhance the partitioning of a given space, a residual version of the PC-tree algorithm is developed, denoted here as the principal component analysis tree (PCR-tree) algorithm. Because of its residual property, the PCR-tree can yield the intrinsic dimension of high-dimensional data. Comparisons presented in this paper confirm that the proposed PC-tree and PCR-tree approaches show a better performance than several other competing partitioning algorithms in terms of vector quantization error and nearest neighbor search. The comparison also shows that the proposed algorithms outperform competing linear methods in total average coverage which measures the nonlinear compactness of partitioning algorithms. [ABSTRACT FROM AUTHOR]

Extended Jacobian inverse kinematics algorithms for redundant robotic manipulators are defined by combining the manipulator's kinematics with an augmenting kinematics map in such a way that the combination becomes a local diffeomorphism of the augmented taskspace. A specific choice of the augmentation relies on the optimal approximation by the extended Jacobian of the Jacobian pseudoinverse (the Moore—Penrose inverse of the Jacobian). In this paper, we propose a novel formulation of the approximation problem, rooted conceptually in the Riemannian geometry. The resulting optimality conditions assume the form of a Poisson equation involving the Laplace—Beltrami operator. Two computational examples illustrate the theory. [ABSTRACT FROM AUTHOR]

This paper is concerned with tracking control problems for nonlinear systems that are not affine in the control signal and that contain unknown nonlinearities in the system dynamic equations. This paper develops a piecewise linear approximation to the unknown functions during the system operation. New control and parameter adaptation algorithms are designed and analyzed using Lyapunov-like methods. The objectives are to achieve semiglobal stability of the state, accurate tracking of bounded reference signals contained within a known domain D, and at least boundedness of the function approximator parameter estimates. Numerical simulations are included to illustrate the effectiveness of the learning algorithm. [ABSTRACT FROM AUTHOR]

N-partite networks are natural representations of complex multi-entity databases. However, processing these networks can be a highly memory and computation-intensive task, especiaIIy when positive correlation exists between the degrees of vertices from different partitions. In order to improve the scalability of this process, this paper proposes two algorithms that make use of sampling for obtaining less expensive approximate results. The first algorithm is optimal for obtaining homogeneous discovery rates with a low memory requirement, but can be very slow in cases where the combined branching factor of these networks is too large. A second algorithm that incorporates concepts from evolutionary computation aims toward dealing with this slow convergence in the case when it is more interesting to increase approximation convergence speed of elements with high feature values. This algorithm makes use of the positive correlation between "local" branching factors and the feature values. Two applications examples are demonstrated in searching for most influential authors in collections of journal articles and in analyzing most active earthquake regions from a collection of earthquake events. [ABSTRACT FROM AUTHOR]

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]

We present a stable and practical algorithm that uses QR factors of the Sylvester matrix to compute the greatest common divisor (GCD) of univariate approximate polynomials over R[x] or C[x]. An approximate polynomial is a polynomial with coefficients that are not known with certainty. The algorithm of this paper improves over previously published algorithms by handling the case when common roots are near to or outside the unit circle, by splitting and reversal if necessary. The algorithm has been tested on thousands of examples, including pairs of polynomials of up to degree 1000, and is now distributed as the program QRGCD in the SNAP package of Maple 9. [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]

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]

In this paper, an adaptive motion/force control system is proposed for condenser cleaning crawler-type mobile manipulator robot (CCCMMR). With the merits of recurrent fuzzy wavelet cerebellar model articulation control neural networks, the unknown dynamics and parameter variations of the CCCMMR control system are relaxed by an approximation process. In addition, an adaptive robust compensator is also proposed to eliminate uncertainties that consist of the unknown approximation errors and disturbances. According to the adaptive position tracking control design, we develop an adaptive robust control strategy for the nonholonomic constraint force of the CCCMMR. The design of the adaptive online learning algorithms is derived using the Lyapunov stability theorem. Therefore, the proposed controllers prove that they not only can guarantee the stability and robustness, but also the tracking performances of the CCCMMR control system. The effectiveness and robustness of the proposed control system are verified by comparative simulation and experimental results. [ABSTRACT FROM PUBLISHER]

In this paper, we present a Bayesian-based super-resolution algorithm that uses approximations of symmetric alpha-stable ( \(S\alpha S\) ) Markov random fields as prior. The approximated \(S\alpha S\) prior is used to perform maximum a posteriori (MAP) estimation for the high-resolution (HR) image reconstruction process. Compared with other state-of-the-art prior models, the proposed prior can better capture the heavy tails of the distribution of the HR image. Thus, the edges of the reconstructed HR image are preserved better in our method. As the corresponding energy function is nonconvex, the graduated nonconvexity method is used to solve the MAP estimation. Experiments confirm the better fit achieved by the proposed model to the actual data distribution and the consequent improvement in terms of visual quality over previously proposed super-resolution algorithms. [ABSTRACT FROM PUBLISHER]

In this paper, the performance of a parallel sparse direct solver on a shared-memory multicore system is presented. Large size test matrices arising from finite element simulation of induction heating industrial applications are used to evaluate the performance improvements due to low-rank representations and multicore parallelization. [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]

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]

Best merge region growing normally produces segmentations with closed connected region objects. Recognizing that spectrally similar objects often appear in spatially separate locations, we present an approach for tightly integrating best merge region growing with nonadjacent region object aggregation, which we call hierarchical segmentation or HSeg. However, the original implementation of nonadjacent region object aggregation in HSeg required excessive computing time even for moderately sized images because of the required intercomparison of each region with all other regions. This problem was previously addressed by a recursive approximation of HSeg, called RHSeg. In this paper, we introduce a refined implementation of nonadjacent region object aggregation in HSeg that reduces the computational requirements of HSeg without resorting to the recursive approximation. In this refinement, HSeg's region intercomparisons among nonadjacent regions are limited to regions of a dynamically determined minimum size. We show that this refined version of HSeg can process moderately sized images in about the same amount of time as RHSeg incorporating the original HSeg. Nonetheless, RHSeg is still required for processing very large images due to its lower computer memory requirements and amenability to parallel processing. We then note a limitation of RHSeg with the original HSeg for high spatial resolution images and show how incorporating the refined HSeg into RHSeg overcomes this limitation. The quality of the image segmentations produced by the refined HSeg is then compared with other available best merge segmentation approaches. Finally, we comment on the unique nature of the hierarchical segmentations produced by HSeg. [ABSTRACT FROM AUTHOR]

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2^\log^1-\epsilonn unless NP\subseteq RTIME(2^polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2^\log^1-\epsilonn unless NP\subseteq DTIME(2^polylog(n)). As the main technical contribution, for any constant 2/3 < \rho < 1, we present a deterministic algorithm that given a positive integer s, runs in time poly(s) and constructs a code \cal C of length poly(s) with an explicit Hamming ball of radius \rho d(\cal C), such that the projection at the first s coordinates sends the codewords in the ball surjectively onto a linear subspace of dimension s, where d(\cal C) denotes the minimum distance of \cal C. The codes are obtained by concatenating Reed–Solomon codes with Hadamard codes. [ABSTRACT FROM PUBLISHER]

The general theory of greedy approximation is well developed. Much less is known about how specific features of a dictionary can be used to our advantage. In this paper, we discuss incoherent dictionaries. We build a new greedy algorithm which is called the orthogonal super greedy algorithm (OSGA). We show that the rates of convergence of OSGA and the orthogonal matching pursuit (OMP) with respect to incoherent dictionaries are the same. Based on the analysis of the number of orthogonal projections and the number of iterations, we observed that OSGA(s) is s times simpler (more efficient) than OMP. Greedy approximation is also a fundamental tool for sparse signal recovery. The performance of orthogonal multimatching pursuit, a counterpart of OSGA in the compressed sensing setting, is also analyzed under restricted isometry property conditions. [ABSTRACT FROM AUTHOR]

A concave finite element-boundary integral-multilevel fast multipole algorithm (FE-BI-MLFMA) is presented for scattering by a large body with nonuniform deep cavities. Different from the conventional FE-BI-MLFMA, the boundary integral equation in this concave FE-BI-MLFMA is established on a concave surface to reduce the region of the finite element method (FEM), which can significantly reduce the dispersion error from the FEM and improve the efficiency of FE-BI-MLFMA especially for nonuniform cavities. To eliminate the problem of slow convergence caused by concave surface, an efficient preconditioner based on the sparse approximate inverse (SAI) is constructed in this paper. Numerical performance of the constructed preconditioner based on the SAI is investigated in detail. Numerical experiments demonstrate the accuracy and efficiency of this SAI preconditioned concave FE-BI-MLFMA for nonuniform deep and large cavites. This SAI preconditioned concave FE-BI-MLFMA is parallelized to further improve its capability in this paper. An extremely big and deep nonuniform cavity has been calculated, demonstrating the great capability of this parallel concave FE-BI-MLFMA. [ABSTRACT FROM PUBLISHER]

This paper presents a global task coordinate frame (TCF) (GTCF)-based integrated direct/indirect adaptive robust contouring controller for linear-motor-driven biaxial systems that achieves both stringent contouring performance and accurate parameter estimations. In contrast to the past research works those use various locally defined TCFs “attached” to the desired contour to approximately calculate the contouring error for feedback controller designs, this paper first formulates the contouring control problem using a recently developed GTCF, in which calculation of the contouring error is rather accurate and not affected by the curvature of the desired contour. A physical-model-based indirect-type parameter-estimation algorithm is then synthesized to obtain accurate online estimates of unknown physical model parameters. An integrated direct/indirect adaptive robust controller with dynamic-compensation-type fast adaptation is also constructed to preserve the excellent transient and steady-state performance of the direct adaptive robust control (ARC) designs. Comparative experimental results show that the proposed GTCF-based integrated direct/indirect ARC algorithm not only achieves the best contouring performance but also possesses rather accurate estimations of physical parameters. [ABSTRACT FROM PUBLISHER]

In this paper, the problem of adaptive distributed learning in diffusion networks is considered. The algorithms are developed within the convex set theoretic framework. More specifically, they are based on computationally simple geometric projections onto closed convex sets. The paper suggests a novel combine-project-adapt protocol for cooperation among the nodes of the network; such a protocol fits naturally with the philosophy that underlies the projection-based rationale. Moreover, the possibility that some of the nodes may fail is also considered and it is addressed by employing robust statistics loss functions. Such loss functions can easily be accommodated in the adopted algorithmic framework; all that is required from a loss function is convexity. Under some mild assumptions, the proposed algorithms enjoy monotonicity, asymptotic optimality, asymptotic consensus, strong convergence and linear complexity with respect to the number of unknown parameters. Finally, experiments in the context of the system-identification task verify the validity of the proposed algorithmic schemes, which are compared to other recent algorithms that have been developed for adaptive distributed learning. [ABSTRACT FROM PUBLISHER]

Recently, multipath solutions have been proposed to improve the quality-of-service of the source to destination (s,t)-path in communication networks (CNs). This paper describes the \lambdaDP/DR problem to obtain \lambda\geq 1 edge-disjoint (s,t)-paths (\lambdaDP) such that its reliability is maximized while keeping its delay no longer than a delay constraint D\geq 1. This problem is NP-hard, and thus this paper proposes an approximate solution using Lagrange-relaxation. Our algorithm generates \lambdaDP with \delta(\lambdaDP)\leqD, and reliability bounded by \vert\log(R\min)\vert\leq\vert\log(\rho(\lambdaDP))\vert\leq(1+k)^{\ast}\vert\log(R\min)\vert, where R\min is the minimum reliability of any (s,t)-path in the CN, and k\geq 1. Our simulations on forty random CNs and large grid networks show that our solution produces \lambdaDP with delay and reliability comparable to those obtained by the optimal but exponential time algorithm. [ABSTRACT FROM AUTHOR]

In this paper, some new probabilistic upper bounds are presented for the online learning algorithm proposed in refid="ref1"/ , and more generally for linear stochastic approximations in Hilbert spaces. With these upper bounds not only does one recover almost sure convergence, but also relaxes the square summable condition on the step size appeared in the early work. Furthermore two probabilistic upper bounds are given for an averaging process, both of which achieve the same rate with respect to sample size as in “batch learning” algorithms, and one of which is tight in both sample size and regularization parameter. [ABSTRACT FROM AUTHOR]

In many real applications, graph data is subject to uncertainties due to incompleteness and imprecision of data. Mining such uncertain graph data is semantically different from and computationally more challenging than mining conventional exact graph data. This paper investigates the problem of mining uncertain graph data and especially focuses on mining frequent subgraph patterns on an uncertain graph database. A novel model of uncertain graphs is presented, and the frequent subgraph pattern mining problem is formalized by introducing a new measure, called expected support. This problem is proved to be NP-hard. An approximate mining algorithm is proposed to find a set of approximately frequent subgraph patterns by allowing an error tolerance on expected supports of discovered subgraph patterns. The algorithm uses efficient methods to determine whether a subgraph pattern can be output or not and a new pruning method to reduce the complexity of examining subgraph patterns. Analytical and experimental results show that the algorithm is very efficient, accurate, and scalable for large uncertain graph databases. To the best of our knowledge, this paper is the first one to investigate the problem of mining frequent subgraph patterns from uncertain graph data. [ABSTRACT FROM AUTHOR]

An algorithm that is capable not only of tracking multiple targets but also of "track management"-meaning that it does not need to know the number of targets as a user input-is of considerable interest. In this paper we devise a recursive track-managed filter via a quantized state-space ("bin") model. In the limit, as the discretization implied by the bins becomes as refined as possible (infinitesimal bins) we find that the filter equations are identical to Mahier's probability hypothesis density (PHD) filter, a novel trackmanaged filtering scheme that is attracting increasing attention. Thus, one contribution of this paper is an interpretation of, if not the PHD itself, at least what the PHD is doing. This does offer some intuitive appeal, but has some practical use as well: with this model it is possible to identify the PHD's "target-death" problem, and also the statistical inference structures of the PHD filters. To obviate the target death problem, PHD originator Mahler developed a new "cardinalized" version of PHD (CPHD). The second contribution of this paper is to extend the "bin-occupancy" model such that the resulting recursive filter is identical to the cardinalized PHD filter. [ABSTRACT FROM AUTHOR]

Most existing multiobjective evolutionary algorithms aim at approximating the Pareto front (PF), which is distribution of the Pareto-optimal solutions in the objective space. In many real-life applications, however, a good approximation to the Pareto set (PS), which is the distribution of the Pareto-optimal solutions in the decision space, is also required by decision maker. This paper considers a class of multiobjective optimization problems (MOPs), in which the dimensionalities the PS and the PF manifolds are different so that a good approximation to the PF might not approximate the PS very well. It proposes a probabilistic model-based multiobjective evolutionary algorithm, called MMEA, for approximating the PS and PF simultaneously for an MOP in this class. In the modeling phase of MMEA, the population is clustered into a number subpopulations based on their distribution in the objective space, the principal component analysis technique is used to estimate the dimensionality of the PS manifold in each subpopulation, then a probabilistic model is built for modeling the distribution of the Pareto-optimal solutions in the decision space. Such modeling procedure could promote the population diversity both the decision and objective spaces. MMEA is compared with three other methods, KP1, Omni-Optimizer and RM-MEDA, a set of test instances, five of which are proposed in this paper. The experimental results clearly suggest that, overall, MMEA performs significantly better than the three compared algorithms in approximating both the PS and the PF. [ABSTRACT FROM AUTHOR]

In this paper, we give an analytical justification how to control the QoS parameters using a throughput approximation model for IEEE 802.11e EDCA. Using the model, we propose a new parameter control algorithm which successfully achieves the dynamic parameter assignment under desired throughput ratio constraints. [ABSTRACT FROM AUTHOR]

Simultaneous localization and mapping (SLAM) algorithms based on local maps have been demonstrated to be well suited for mapping large environments as they reduce the computational cost and improve the consistency of the final estimation. The main contribution of this paper is a novel submapping technique that does not require independence between maps. The technique is based on the intrinsic structure of the SLAM problem that allows the building of submaps that can share information, remaining conditionally independent. The resulting algorithm obtains local maps in constant time during the exploration of new terrain and recovers the global map in linear time after simple loop closures without introducing any approximations besides the inherent ex- tended Kalman filter linearizations. The memory requirements are also linear with the size of the map. As the algorithm works in a covariance form, well-known data-association techniques can be used in the usual manner. We present experimental results using a handheld monocular camera, building a map along a closed-loop trajectory of 140 m in a public square, with people and other clutter. Our results show that the combination of conditional independence, which enables the system to share the camera and feature states between submaps, and local coordinates, which reduce the effects of linearization errors, allow us to obtain precise maps of large areas with pure monocular SLAM in real time. [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]

Low-rank matrix approximation has applications in many fields, such as 2-D filter design and 3-D reconstruction from an image sequence. In this paper, one issue with low-rank matrix approximation is investigated: heteroscedastic noise. In most of previous research, the covariance matrix of the heteroscedastic noise is assumed to be positive definite. This requirement restricts the usefulness of results derived from such research. In this paper, we extend the Wiberg algorithm, which originally deals with the missing data problem with low-rank approximation, to the cases, where the heteroscedastic noise has a singular covariance matrix. Experiments show that the proposed Wiberg algorithm converges much faster than the bilinear approach, and consequently avoids many nonconvergent cases in the bilinear approach. Experiments also show that, to some extent, the Wiberg algorithm can tolerate outliers and is not sensitive to parameter variation. [ABSTRACT FROM AUTHOR]

Aerial and buried electric conductors often share the same right of way. When a phase-to-ground fault occurs, high transient-induced overvoltages appear from short-circuit currents to the ground. The mutual ground-loop impedances between both systems are given by the Pollaczek coupling integral that does not possess an analytic closed-form solution, and its integrand is highly oscillatory to perform a direct numerical integration. An efficient and accurate algorithmic evaluation of the Pollaczek coupling integral is presented in this paper. The obtained result is used in the numerical assessment of approximated formulas previously issued by Lucca, Wedepohl, and Comité Consultatif International Téléphonique et Télégraphique. [ABSTRACT FROM AUTHOR]

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining κ-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a κ-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an O(κα)-approximation where α is the best approximation factor for the related problem in wired networks (the best α so far is O (log κ).) With a more careful analysis, we show our second (slightly more complicated) algorithm is an O(κ)-approximation. Our third algorithm assumes that the edge lengths of the network graph form a metric. In this case, we present simple and practical distributed algorithms for the cases of 2- and 3-connectivity with constant approximation factors. We generalize this algorithm to obtain an O (κ2c+2)-approximation for general κ-connectivity (2 ≤ c ≤ 4 is the power attenuation exponent). Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power while maintaining κ-edge connectivity with guaranteed approximation factors. Recently, different set of authors used the notion of κ-connectivity and the results of this paper to deal with the fault-tolerance issues for static wireless network settings. [ABSTRACT FROM AUTHOR]

This paper concentrates on two critical aspects to improve the performance of maximum power point tracking (MPPT). One improvement is to accurately locate the position of the maximum power point (MPP) by using the centered differentiation. Another effort is to reduce the oscillation around the MPP in steady state by controlling active perturbations. This paper also adopts the method of steepest descent for MPPT, which shows faster dynamic response and smoother steady state than the method of hill climbing. Comprehensive experimental evaluations have successfully illustrated the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In dealing with large data sets, the reduced support vector machine (RSVM) was proposed for the practical objective to overcome some computational difficulties as well as to reduce the model complexity. In this paper, we study the RSVM from the viewpoint of sampling design, its robustness, and the spectral analysis of the reduced kernel. We consider the nonlinear separating surface as a mixture of kernels. Instead of a full model, the RSVM uses a reduced mixture with kernels sampled from certain candidate set. Our main results center on two major themes. One is the robustness of the random subset mixture model. The other is the spectral analysis of the reduced kernel. The robustness is judged by a few criteria as follows: 1) model variation measure; 2) model bias (deviation) between the reduced model and the full model; and 3) test power in distinguishing the reduced model from the full one. For the spectral analysis, we compare the eigenstructures of the full kernel matrix and the approximation kernel matrix. The approximation kernels are generated by uniform random subsets. The small discrepancies between them indicate that the approximation kernels can retain most of the relevant information for learning tasks in the full kernel. We focus on some statistical theory of the reduced set method mainly in the context of the RSVM. The use of a uniform random subset is not limited to the RSVM. This approach can act as a supplemental algorithm on top of a basic optimization algorithm, wherein the actual optimization takes place on the subset-approximated data. The statistical properties discussed in this paper are still valid. [ABSTRACT FROM AUTHOR]