Search

In this paper, a novel algorithm “firework optimization” (FO) is introduced, as well as its hybridization with generating set search (GSS). FO is an exploration algorithm, which intends to explore a vast region within the search space in order to determine regions that may contain a regional optimum. As the regions with potential are defined, GSS, the exploitation algorithm is applied to determine whether regions determined by FO contain a local or a global optimum. The validity of FO and GSS hybridization algorithm is verified using Branin and Six-Hump Camel test functions, and the hybridization algorithm is applied to an interior permanent magnet synchronous motor, in order to minimize torque ripple. [ABSTRACT FROM AUTHOR]

Diagnosis by comparison is a realistic approach to detect faults of multiprocessor systems. This paper considers a pessimistic diagnostic strategy for hypercube-like multiprocessor systems under the comparison model. The pessimistic strategy is a diagnostic process whereby all faulty nodes can be correctly identified and at most one fault-free node may be misjudged as a faulty node. We propose a pessimistic diagnosis algorithm based on the largest component in the faulty system. For a system with N = 2n nodes and n ≥ 5 , when the number of faulty nodes is bounded by 2n − 2 , the algorithm can correctly identify all nodes except at most one node left undiagnosed. The time complexity of the algorithm is O(Nlog2N). [ABSTRACT FROM PUBLISHER]

This paper introduces a mathematical model that incorporates the pertinent optical and physiological properties of skin reflections with the objective to increase our understanding of the algorithmic principles behind remote photoplethysmography (rPPG). The model is used to explain the different choices that were made in existing rPPG methods for pulse extraction. The understanding that comes from the model can be used to design robust or application-specific rPPG solutions. We illustrate this by designing an alternative rPPG method, where a projection plane orthogonal to the skin tone is used for pulse extraction. A large benchmark on the various discussed rPPG methods shows that their relative merits can indeed be understood from the proposed model. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of mining frequent sequences under the rigorous differential privacy model. We explore the possibility of designing a differentially private frequent sequence mining (FSM) algorithm which can achieve both high data utility and a high degree of privacy. We found, in differentially private FSM, the amount of required noise is proportionate to the number of candidate sequences. If we could effectively prune those unpromising candidate sequences, the utility and privacy tradeoff can be significantly improved. To this end, by leveraging a sampling-based candidate pruning technique, we propose PFS $^2$, a novel differentially private FSM algorithm. It is the first algorithm that supports the general gap-constrained FSM in the context of differential privacy. The gap constraints in FSM can be used to limit the mining results to a controlled set of frequent sequences. In our PFS$^2$ algorithm, the core is to utilize sample databases to prune the candidate sequences generated based on the downward closure property. In particular, we use the noisy local support of candidate sequences in the sample databases to estimate which candidate sequences are potentially frequent. To improve the accuracy of such private estimations, a gap-aware sequence shrinking method is proposed to enforce the length constraint on the sample databases. Moreover, to calibrate the amount of noise required by differential privacy, a gap-aware sensitivity computation method is proposed to obtain the sensitivity of the local support computations with different gap constraints. Furthermore, to decrease the probability of misestimating frequent sequences as infrequent, a threshold relaxation method is proposed to relax the user-specified threshold for the sample databases. Through formal privacy analysis, we show that our PFS $^2$ algorithm is $\epsilon$ -differentially private. Extensive experiments on real datasets illustrate that our PFS$^2$ algorithm can privately find frequent sequences with high accuracy. [ABSTRACT FROM PUBLISHER]

This paper presents a comprehensive study of the computation of square roots over finite extension fields. We propose two novel algorithms for computing square roots over even field extensions of the form \BBF{q^2}, with q = p^n, p an odd prime and n \geq 1. Both algorithms have an associate computational cost roughly equivalent to one exponentiation in \BBF{q^2}. The first algorithm is devoted to the case when q \equiv 1\, mod\, 4, whereas the second one handles the case when q \equiv 3\, mod\,4. Numerical comparisons show that the two algorithms presented in this paper are competitive and in some cases more efficient than the square root methods previously known. [ABSTRACT FROM AUTHOR]

In this paper we propose a modified Elliptic Net algorithm to compute pairings. By reducing the number of the intermediate variables which should be updated in the iteration loop of the Elliptic Net algorithm, we speed up the computation of pairings. Experimental results show that the proposed method is more efficient than the original Elliptic Net algorithm on Barreto-Naehrig (BN) curves which are the best choice for implementing pairings at 128-bit security level. [ABSTRACT FROM PUBLISHER]

IC3 is one of the most successful algorithms for hardware model checking. Since its invention in 2010, several variants of the original algorithm have been published, proposing optimizations and/or alternative procedures for many different steps of the algorithm. In this paper, we present a thorough empirical comparison of a large set of optimizations and procedures for the steps of IC3, considering “high-level” variants/extensions to the basic algorithm, as well as “low-level” optimizations/configuration settings. We implemented each of them in the same tool, optimizing the implementations to the best of our knowledge. This enabled for a flexible experimentation in a controlled environment, and to gain new insights about their most important differences and commonalities, as well as about their performance characteristics. We conducted the experiments using as benchmarks the problems used in the last four editions of the hardware model checking competition. The analysis helped us to identify several settings leading to significant improvements with respect to a basic implementation of IC3. [ABSTRACT FROM AUTHOR]

Pooling plays an important role in generating a discriminative video representation. In this paper, we propose a new semantic pooling approach for challenging event analysis tasks (e.g., event detection, recognition, and recounting) in long untrimmed Internet videos, especially when only a few shots/segments are relevant to the event of interest while many other shots are irrelevant or even misleading. The commonly adopted pooling strategies aggregate the shots indifferently in one way or another, resulting in a great loss of information. Instead, in this work we first define a novel notion of semantic saliency that assesses the relevance of each shot with the event of interest. We then prioritize the shots according to their saliency scores since shots that are semantically more salient are expected to contribute more to the final event analysis. Next, we propose a new isotonic regularizer that is able to exploit the constructed semantic ordering information. The resulting nearly-isotonic support vector machine classifier exhibits higher discriminative power in event analysis tasks. Computationally, we develop an efficient implementation using the proximal gradient algorithm, and we prove new and closed-form proximal steps. We conduct extensive experiments on three real-world video datasets and achieve promising improvements. [ABSTRACT FROM PUBLISHER]

We study optimal multirobot path planning on graphs (\textMPP ) over four minimization objectives: the makespan (last arrival time), the maximum (single-robot traveled) distance, the total arrival time, and the total distance. Having established previously that these objectives are distinct and NP-hard to optimize, in this paper, we focus on efficient algorithmic solutions for solving these optimal \textMPP problems. Toward this goal, we first establish a one-to-one solution mapping between \textMPP and a special type of multiflow network. Based on this equivalence and integer linear programming (ILP), we design novel and complete algorithms for optimizing over each of the four objectives. In particular, our exact algorithm for computing optimal makespan solutions is a first that is capable of solving extremely challenging problems with robot-vertex ratios as high as $100\%$ . Then, we further improve the computational performance of these exact algorithms through the introduction of principled heuristics, at the expense of slight optimality loss. The combination of ILP model based algorithms and the heuristics proves to be highly effective, allowing the computation of $1.x$-optimal solutions for problems containing hundreds of robots, densely populated in the environment, often in just seconds. [ABSTRACT FROM AUTHOR]

Topic modeling has become a widely used tool for document management. However, there are few topic models distinguishing the importance of documents on different topics. In this paper, we propose a framework LIMTopic to incorporate link based importance into topic modeling. To instantiate the framework, RankTopic and HITSTopic are proposed by incorporating topical pagerank and topical HITS into topic modeling respectively. Specifically, ranking methods are first used to compute the topical importance of documents. Then, a generalized relation is built between link importance and topic modeling. We empirically show that LIMTopic converges after a small number of iterations in most experimental settings. The necessity of incorporating link importance into topic modeling is justified based on KL-Divergences between topic distributions converted from topical link importance and those computed by basic topic models. To investigate the document network summarization performance of topic models, we propose a novel measure called log-likelihood of ranking-integrated document-word matrix. Extensive experimental results show that LIMTopic performs better than baseline models in generalization performance, document clustering and classification, topic interpretability and document network summarization performance. Moreover, RankTopic has comparable performance with relational topic model (RTM) and HITSTopic performs much better than baseline models in document clustering and classification. [ABSTRACT FROM AUTHOR]

This paper introduces the minimum-time arbitrarily constrained distributed scheduling problem. The optimal distributed nonsequential backtracking algorithm is used by agents to schedule tasks where the tasks are related by constraints and where the assignment of tasks to agents may change during scheduling. The problem is distributed in that no agent has full knowledge either of the communication network or of the scheduling constraints. Each agent knows the assignments of the agents with which it can communicate and the scheduled times of the tasks assigned to those agents. The minimum-time arbitrarily constrained distributed scheduling problem is for the agents to use this local knowledge to find a schedule that satisfies all constraints and minimizes the time needed to complete all tasks. The optimal distributed nonsequential backtracking algorithm is able to find minimum-time schedules that satisfy all constraints. This algorithm is designed to work concurrently with a distributed assignment algorithm that satisfies certain communication requirements detailed in this paper. This paper presents proof of the algorithm’s correctness, completeness, and optimality. [ABSTRACT FROM PUBLISHER]

The video surveillance market is increasingly moving toward cheaper, efficient, portable, and high resolution systems. A typical video surveillance system consists of several cameras, which issue warnings or initiate smart reactions according to the analysis results of the captured video data. Many algorithms in video surveillance systems assume fixed lighting conditions for the monitored area. The performance of these algorithms is severely affected by the illumination changes of the monitored area. This paper presents an efficient intensity correction algorithm for high definition video surveillance applications. The new algorithm corrects both the global and the local intensity changes. It uses an apparent gain factor to correct the global intensity changes. In addition it corrects the local intensity changes using the local intensity mean and standard deviation. The proposed algorithm shows a promising performance when compared with other intensity correction algorithms. It has a low computational cost that makes it a suitable choice for real-time hardware implementation. This paper also presents a hardware implementation of the proposed algorithm using Xilinx Spartan3A digital signal processor (DSP) XC3SD3400A device. The targeted resolution is 1920\,\times\,1080 at 30 f/s. The hardware prototype utilizes 17% of the slices, 21% of the block random access memories, and 24% of the DSP48As available in Spartan3A DSP XC3SD3400A device. [ABSTRACT FROM AUTHOR]

A typical low- or medium-voltage distribution feeder consists of numerous branches as well as laterals and heterogenic conductor lines. The lack of measurement points and the presence of unbalanced loads make it more complicated for the construction of fault-location algorithms. In this paper, a brief and comprehensive review is presented which introduces and compares published papers in this area to date. In addition, the authors have devised a single-end fault-location algorithm using the distributed parameter model to overcome all of the aforementioned limitations in distribution feeders. The validity of the devised algorithm is studied within the PSCAD-EMTDC environment. This model provides more accurate results as the distributed nature of losses and capacitive effects are considered whereas in the available algorithms, these are ignored. A comparison which is made between the proposed method and two of the most complete available algorithms shows the superiority of our algorithm. Also, the proposed algorithm is able to locate various fault types in the network that has different phase laterals unbalanced loads and heterogeneity of the feeder line. [ABSTRACT FROM AUTHOR]

Automatic differentiation (AD) is introduced as a powerful technique to compute derivatives of functions given in the form of computer programs in high-level programming languages such as FORTRAN, C, or C++. This paper applies AD to compute error-free gradients of electromagnetic device sizing models. Then, the obtained gradients are exploited in optimization to size electromagnetic devices by means of minimizing a cost function with constrained parameters and performances. Often, the electromagnetic devices models have to be described not only by analytical formulas, but also by algorithms. This paper proposes an electromagnetic model of a linear actuator dealing with implicit equations solved by numerical algorithms. The ADOL-C package is considered for automatic differentiation. [ABSTRACT FROM PUBLISHER]

This paper describes a new, physically interpretable, fully automatic algorithm for removal of tissue autofluorescence (AF) from fluorescence microscopy images, by non-negative matrix factorization. Measurement of signal intensities from the concentration of certain fluorescent reporter molecules at each location within a sample of biological tissue is confounded by fluorescence produced by the tissue itself (autofluorescence). Spectral mixing models use mixing coefficients to specify how much fluorescence from each source is present and unmixing algorithms separate the two fluorescent sources. Current spectral unmixing methods for AF removal often require a priori knowledge of mixing coefficients. Those which do not, such as principal component analysis, generate negative mixing coefficients that are not physically meaningful. Non-negative matrix factorization constrains mixing coefficients to be non-negative, and has been used for spectral unmixing, but not AF removal. This paper describes a novel non-negative matrix factorization algorithm which separates fluorescent images into true signal and AF components utilizing an estimate of the dark current. We also present a test-bed, based on fluorescent beads, to compare the performance of different AF removal algorithms. Our algorithm out-performed previous state of the art on validation images. [ABSTRACT FROM PUBLISHER]

We present, in this paper, the FAIR algorithm: a fast algorithm for document image restoration. This algorithm has been submitted to different contests where it showed good performance in comparison to the state of the art. In addition, this method is scale invariant and fast enough to be used in real-time applications. The method is based on a double-threshold edge detection approach that makes it possible to detect small details while remaining robust against noise. The performance of the proposition is evaluated on several types of degraded document images where considerable background noise or variation in contrast and illumination exist. [ABSTRACT FROM PUBLISHER]

In this paper, we analyze a collaborative filter that answers the simple question: What is popular amongst your “friends”? While this basic principle seems to be prevalent in many practical implementations, there does not appear to be much theoretical analysis of its performance. In this paper, we partly fill this gap. While recent works on this topic, such as the low-rank matrix completion literature, consider the probability of error in recovering the entire rating matrix, we consider probability of an error in an individual recommendation [bit error rate (BER)]. For a mathematical model introduced by Aditya in 2009 and 2011, we identify three regimes of operation for our algorithm (named Popularity Amongst Friends) in the limit as the matrix size grows to infinity. In a regime characterized by large number of samples and small degrees of freedom (defined precisely for the model in the paper), the asymptotic BER is zero; in a regime characterized by large number of samples and large degrees of freedom, the asymptotic BER is bounded away from 0 and 1/2 (and is identified exactly except for a special case); and in a regime characterized by a small number of samples, the algorithm fails. We then compare these results with the performance of the optimal recommender. We also present numerical results for the MovieLens and Netflix datasets. We discuss the empirical performance in light of our theoretical results and compare with an approach based on low-rank matrix completion. [ABSTRACT FROM AUTHOR]

This paper proposes an approach for the optimal design of fault-tolerant Petri net controllers using arc weights minimization. Given a system controller that is modeled as a Petri net, a fault-tolerant Petri net controller is obtained by embedding the given Petri net controller into a larger (redundant) Petri net controller that retains the properties of the original controller and allows the detection and identification of faults that may occur in the controller places. An algorithm is developed to systematically design this fault-tolerant Petri net controller in an optimal sense. The optimality is in terms of minimizing the sum of the entries in the input and output incident matrices of the fault-tolerant controller. Examples of the optimal design of fault-tolerant Petri net controllers for a manufacturing system are also provided to illustrate our approach. [ABSTRACT FROM PUBLISHER]

Dummy fill has been demonstrated to be an effective technique to reduce process variation and improve manufacturability for advanced integrated circuit (IC) designs. However, the computation load, often several days for a realistic IC design, is a significant portion of the cycle time for delivering first silicon on new or modified designs. In this paper, we propose a novel design flow and dummy-fill algorithm based on Boolean operations, which greatly improves computational efficiency and pattern density uniformity, and enables dummy generation to be combined with the mask-preparation Boolean operations performed by the mask-fabrication facility. Mask data preparation can be performed in parallel with dummy generation and post-dummy simulation checks at the design house, resulting in improved first-silicon cycle time. Experimental results demonstrate these benefits in the context of an advanced foundry process technology. [ABSTRACT FROM PUBLISHER]

Dynamic system modeling plays a crucial role in the development of techniques for stationary and nonstationary signal processing. Due to the inherent physical characteristics of systems under investigation, nonnegativity is a desired constraint that can usually be imposed on the parameters to estimate. In this paper, we propose a general method for system identification under nonnegativity constraints. We derive the so-called nonnegative least-mean-square algorithm (NNLMS) based on stochastic gradient descent, and we analyze its convergence. Experiments are conducted to illustrate the performance of this approach and consistency with the analysis. [ABSTRACT FROM AUTHOR]

This paper presents a method for determining the double outage contingencies that threaten the system without solving the full contingency set. Two methods for contingency screening with complementary properties are presented. The results of the algorithms are compared to the full double outage contingency analysis results for a large North American case. The results show that the screening algorithms are able to detect nearly all of the contingencies that will result in violations, while requiring only a small fraction of the contingencies to be solved. [ABSTRACT FROM PUBLISHER]

Adaptive dynamic programming (ADP) is a promising research field for design of intelligent controllers, which can both learn on-the-fly and exhibit optimal behavior. Over the past decades, several generations of ADP design have been proposed in the literature, which have demonstrated many successful applications in various benchmarks and industrial applications. While many of the existing researches focus on multiple-inputs-single-output system with steepest descent search, in this paper we investigate a generalized multiple-input-multiple-output (GMIMO) ADP design for online learning and control, which is more applicable to a wide range of practical real-world applications. Furthermore, an improved weight-updating algorithm based on recursive Levenberg–Marquardt methods is presented and embodied in the GMIMO approach to improve its performance. Finally, we test the performance of this approach based on a practical complex system, namely, the learning and control of the tension and height of the looper system in a hot strip mill. Experimental results demonstrate that the proposed approach can achieve effective and robust performance. [ABSTRACT FROM AUTHOR]

This correspondence paper presents an algorithm in which the independent components of link lengths are used as a medium to analyze the forward kinematics of a six-degree-of-freedom Stewart platform. The link lengths are firstly transformed into independent components through independent component analysis. Then, the value of positional variables is computed by using the Nelder–Mead algorithm by taking advantage of the relationships between the independent components and the positional variables. Simulations have been conducted to test the proposed algorithm. The experimental results show that the proposed algorithm can achieve a better performance than the other published algorithms. [ABSTRACT FROM PUBLISHER]

Multistate systems (MSS) are systems in which the system and its components are characterized by multiple states or performance levels. Component importance or sensitivity analysis facilitates the identification of vulnerabilities within the system, and aids in the quantification of criticalities of the system components. Multistate component importance analysis poses unique challenges to existing methods that are primarily based on binary-state applications. This paper presents an analytical method based on multistate multivalued decision diagrams (MMDD) for multistate component importance analysis. The contribution of this work is two-fold: 1) a novel, efficient algorithm for directly generating an MMDD model from multistate capacity network specifications without inefficient enumeration of multistate minimal path or cut vectors; and 2) an efficient, exact MMDD-based approach for evaluating MSS reliability and importance measures. The advantages of the proposed method are illustrated through a comparison with existing methods, and through detailed analyses of three case studies. [ABSTRACT FROM AUTHOR]

This paper proposes a multidimensional recursive ambient modal analysis algorithm called recursive frequency domain decomposition (recursive FDD or RFDD). The method enables simultaneous processing of a large number of synchrophasor measurements for real-time ambient modal estimation. The method combines a previously proposed multidimensional block processing algorithm FDD with a single input recursive least square (RLS) algorithm into developing a new frequency domain multidimensional recursive algorithm. First, an auto-regressive model is fitted onto the sampled data of each signal using the time-domain RLS approach. Subsequent modal analysis is carried out in frequency domain in the spirit of FDD. The conventional FDD method uses non-parametric methods for power spectrum density (PSD) estimation. The proposed method in this paper by estimating PSD with a parametric method provides smoother PSD estimation which results in less standard deviation in RFDD estimates compared to FDD. The algorithm is tested on archived synchrophasor data from a real power system. [ABSTRACT FROM AUTHOR]

We present a comprehensive, self-contained, and mechanically verified proof of correctness of a maximally redundant SRT design for floating-point division and square root extraction, supported by verified procedures that 1) test the admissibility of a proposed digit selection table, 2) determine the minimal dimensions of an admissible table for a given arbitrary radix, and 3) generate these tables. For square root extraction, we also provide a verified procedure for generating an initial approximation that meets the accuracy requirement of the algorithm and ensures that the digit selection index derived from successive partial roots remains static throughout the computation. A radix-8 instantiation of these algorithms has been implemented in the floating-point unit of the AMD processor code-named Steamroller. To ensure their correctness, all of our results and procedures have been formalized and mechanically checked by the ACL2 prover. We present evidence of the value of this approach by comparing it to that of a more conventional published paper that reports similar results, which are shown to be fatally flawed. [ABSTRACT FROM AUTHOR]

Cardiac repolarization alternans is an electrophysiologic condition identified by a beat-to-beat fluctuation in action potential waveform. It has been mechanistically linked to instances of T-wave alternans, a clinically defined ECG alternation in T-wave morphology, and associated with the onset of cardiac reentry and sudden cardiac death. Many alternans detection algorithms have been proposed in the past, but the majority have been designed specifically for use with T-wave alternans. Action potential duration (APD) signals obtained from experiments (especially those derived from optical mapping) possess unique characteristics, which requires the development and use of a more appropriate alternans detection method. In this paper, we present a new class of algorithms, based on the Monte Carlo method, for the detection and quantitative measurement of alternans. Specifically, we derive a set of algorithms (one an analytical and more efficient version of the other) and compare its performance with the standard spectral method and the generalized likelihood ratio test algorithm using synthetic APD sequences and optical mapping data obtained from an alternans control experiment. We demonstrate the benefits of the new algorithm in the presence of Gaussian and Laplacian noise and frame-shift errors. The proposed algorithms are well suited for experimental applications, and furthermore, have low complexity and are implementable using fixed-point arithmetic, enabling potential use with implantable cardiac devices. [ABSTRACT FROM PUBLISHER]

A family of the block matching 3-D (BM3D) algorithms for various imaging problems has been recently proposed within the framework of nonlocal patchwise image modeling refid="ref1"/, refid="ref2"/. In this paper, we construct analysis and synthesis frames, formalizing BM3D image modeling, and use these frames to develop novel iterative deblurring algorithms. We consider two different formulations of the deblurring problem, i.e., one given by the minimization of the single-objective function and another based on the generalized Nash equilibrium (GNE) balance of two objective functions. The latter results in the algorithm where deblurring and denoising operations are decoupled. The convergence of the developed algorithms is proved. Simulation experiments show that the decoupled algorithm derived from the GNE formulation demonstrates the best numerical and visual results and shows superiority with respect to the state of the art in the field, confirming a valuable potential of BM3D-frames as an advanced image modeling tool. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new demosaicing algorithm that can be used for various sensor images captured by digital cameras equipped with various red–green–blue color filter arrays. Our algorithm enhances the universal demosaicing algorithm of Lukac et al by defining a new spectral interpolation model that exploits not only the information on the color of pixels but also the relative distance between neighboring pixels within an image. Moreover, we include an edge-detection model that makes our algorithm adaptive and reduces the presence of color shifts and artifacts. A series of tests has been made on images of the Kodak database, and our algorithm performs better than the universal demosaicing algorithm with regard to both subjective and objective evaluation. The versatility of our demosaicing algorithm is also highlighted through an application to the issue of color image resampling, and we obtain conclusive experimental results. [ABSTRACT FROM PUBLISHER]

The weighted multi-commodity multistate unreliable network (WMMUN) is an extension of the multistate network. It is a new network composed of multistate unreliable components (such as arcs and nodes) with various weight capacities which is able to transmit different types of commodities. Currently, the method used to calculate the direct WMMUN reliability is derived from algorithms based on D-minimal path (D-MP). The best-known method may fail to find real D-MPs, and therefore requires more comparison and verification. A very simple algorithm based on the sequential decomposition method has been developed for finding all real D-MPs before calculating the WMMUN reliability. The relationships among the different versions of WMMUN reliability problems have also been clarified. The correctness and computational complexity of the proposed algorithm will be analysed and proven in this paper. An example will be given to illustrate how the WMMUN reliability is evaluated using the proposed algorithm. Computational results compare favorably with existing methods in terms of the running time, the number of d-MPs, and the number of D-MP candidates. [ABSTRACT FROM AUTHOR]

Analog very large scale integration implementations of neural networks can compute using a fraction of the size and power required by their digital counterparts. However, intrinsic limitations of analog hardware, such as device mismatch, charge leakage, and noise, reduce the accuracy of analog arithmetic circuits, degrading the performance of large-scale adaptive systems. In this paper, we present a detailed mathematical analysis that relates different parameters of the hardware limitations to specific effects on the convergence properties of linear perceptrons trained with the least-mean-square (LMS) algorithm. Using this analysis, we derive design guidelines and introduce simple on-chip calibration techniques to improve the accuracy of analog neural networks with a small cost in die area and power dissipation. We validate our analysis by evaluating the performance of a mixed-signal complementary metal-oxide-semiconductor implementation of a 32-input perceptron trained with LMS. [ABSTRACT FROM AUTHOR]

The residue number system (RNS) has been an important research field in computer arithmetic for many decades, mainly because of its carry-free nature, which can provide high-performance computing architectures with superior delay specifications. Recently, research on RNS has found new directions that have resulted in the introduction of efficient algorithms and hardware implementations for RNS with much better performance than previous ones. Furthermore, the applicability of RNS in many computer and digital signal processing (DSP) applications has simultaneously greatly increased. Hence, the need is evident for the development of a new and well-organized RNS teaching method with emphasis on recent achievements. In this paper, a step-by-step teaching process for RNS that describes RNS design in separate parts is presented. Each part is investigated in detail, taking into account the recent research performed on RNS. The compatibility of the proposed method with the new RNS research trends makes this method suitable for researchers as well as students. [ABSTRACT FROM AUTHOR]

Inference problems in graphical models can be represented as a constrained optimization of a free-energy function. In this paper, we treat both forms of probabilistic inference, estimating marginal probabilities of the joint distribution and finding the most probable assignment, through a unified message-passing algorithm architecture. In particular we generalize the belief propagation (BP) algorithms of sum-product and max-product and tree-reweighted (TRW) sum and max product algorithms (TRBP) and introduce a new set of convergent algorithms based on “convex-free-energy” and linear-programming (LP) relaxation as a zero-temperature of a convex-free-energy. The main idea of this work arises from taking a general perspective on the existing BP and TRBP algorithms while observing that they all are reductions from the basic optimization formula of f+\sumihi where the function f is an extended-valued, strictly convex but nonsmooth and the functions hi are extended-valued functions (not necessarily convex). We use tools from convex duality to present the “primal-dual ascent” algorithm which is an extension of the Bregman successive projection scheme and is designed to handle optimization of the general type f+\sumihi. We then map the fractional-free-energy variational principle for approximate inference onto the optimization formula above and introduce the “norm-product” message-passing algorithm. Special cases of the norm-product include sum-product and max-product (BP algorithms), TRBP and NMPLP algorithms. When the fractional-free-energy is set to be convex (convex-free-energy) the norm-product is globally convergent for the estimation of marginal probabilities and for approximating the LP-relaxation. We also introduce another branch of the norm-product which arises as the “zero-temperature” of the convex-free-energy which we refer to as the “convex-max-product”. The convex-max-product is convergent (unlike max-product) and aims at solving the LP- relaxation. [ABSTRACT FROM PUBLISHER]

Conventional linear subspace learning methods like principal component analysis (PCA), linear discriminant analysis (LDA) derive subspaces from the whole data set. These approaches have limitations in the sense that they are linear while the data distribution we are trying to model is typically nonlinear. Moreover, these algorithms fail to incorporate local variations of the intrinsic sample distribution manifold. Therefore, these algorithms are ineffective when applied on large scale datasets. Kernel versions of these approaches can alleviate the problem to certain degree but face a serious computational challenge when data set is large, where the computing involves Eigen/QP problems of size N\,\times\,N. When N is large, kernel versions are not computationally practical. To tackle the aforementioned problems and improve recognition/searching performance, especially on large scale image datasets, we propose a novel local subspace indexing model for image search termed Subspace Indexing Model on Grassmann Manifold (SIM-GM). SIM-GM partitions the global space into local patches with a hierarchical structure; the global model is, therefore, approximated by piece-wise linear local subspace models. By further applying the Grassmann manifold distance, SIM-GM is able to organize localized models into a hierarchy of indexed structure, and allow fast query selection of the optimal ones for classification. Our proposed SIM-GM enjoys a number of merits: 1) it is able to deal with a large number of training samples efficiently; 2) it is a query-driven approach, i.e., it is able to return an effective local space model, so the recognition performance could be significantly improved; 3) it is a common framework, which can incorporate many learning algorithms. Theoretical analysis and extensive experimental results confirm the validity of this model. [ABSTRACT FROM PUBLISHER]

We present new additive Fast Fourier Transform (FFT) algorithms based on Taylor expansions over finite fields of characteristic two. The new algorithms improve previous approaches by Wang and Zhu (1988), Cantor (1989), and von zur Gathen and Gerhard (1996). [ABSTRACT FROM PUBLISHER]

To improve the accuracy of the static contact angle measurement in the silicone rubber aging experiments, a high accurate contact angle algorithm in combination with the circle fitting algorithm and ellipse fitting algorithm is proposed. The influence of the water drop volume and noise on the calculation accuracies of the two algorithms are analyzed. The results reveal that the circle fitting algorithm is more suitable for the images with small water drop volume and contact angle. However, the ellipse fitting algorithm is more suitable for the images with relatively large water drop volume and contact angle. The critical water drop volumes of the two algorithms in different hydrophobicities are obtained by the calculation of contact angle by the two algorithms. And it is used to select which algorithm to calculate contact angles in the proposed algorithm. The tangent line method, \theta/2 method, circle fitting algorithm, ellipse fitting algorithm, and proposed algorithm are implemented. The numerically generated water drop profiles and real water drop images of aged silicone rubber are used to validate the new algorithm. The results indicate that the proposed algorithm is more accurate than the other algorithms in different water drop volumes, contact angles, and noise levels. [ABSTRACT FROM AUTHOR]

An improved set-membership affine-projection (AP) adaptive-filtering algorithm is proposed. The new algorithm uses two error bounds that are estimated during the learning phase and by this means significantly reduced steady-state misalignment is achieved as compared to those in the conventional AP and set-membership AP algorithms while achieving similar convergence speed and re-adaptation capability. In addition, the proposed algorithm offers robust performance with respect to the error bound, projection order, impulsive-noise interference, and in tracking abrupt changes in the underlying system. These features of the proposed algorithm are demonstrated through extensive simulation results in system-identification and echo-cancellation applications. [ABSTRACT FROM PUBLISHER]

The convolutional perfectly-matched-layer (CPML) absorbing boundary condition is fully capable of handling near-field wave absorption that usually combines near-grazing wave incidence with wave evanescence. The appropriate choice of the various CPML parameters to realize this potential for any given simulation problem is a challenging task that is typically achieved through exhaustive and time-consuming searches that involve large numbers of full-scale simulations. The presented work here uses a previously developed predictive system of equations that accurately determines numerical reflections off the PML interface and embeds it into a global optimization routine that reliably computes the required optimum CPML parameters. This predictive system of equations has also been extended and validated for the M24 and FV24 integral-based high-order FDTD algorithms. With this approach, the task of selecting optimum CPML parameters that would usually take several days of intense computations can now be accomplished within a few minutes on an average personal computer. [ABSTRACT FROM AUTHOR]

A new method named fast directional multilevel algorithm is proposed for analyzing wave scattering. Similar to a fast multipole method, an oct-tree structure is used in the new method. Unlike the conventional MLFMA, the kernel is evaluated by a new method, instead of approximating the Green's function by multipole expansion. The fast directional multilevel algorithm is first used to solve the wave scattering problem via combined field integral equation (CFIE) using Rao-Wilton-Glisson (RWG) basis functions. The low rank representations are extended to apply in the low frequency regime which is proved efficient and stable. The numerical results demonstrate that the computational complexity of this new multilevel algorithm can achieve the complexity of O(N\log N). This algorithm is robust and performs well on other oscillatory kernels because of its not depending on the explicit form of kernels. [ABSTRACT FROM PUBLISHER]

The four-parameter sine wave (FPSW) is commonly used to characterize noise, signal to noise, and the effective number of bits in analog-to-digital converters. An algorithm based on separable nonlinear least squares fitting is presented. In this algorithm, the frequency is the sole iterative variable. Numerical tests show that if the cycle in the record (CiR) is greater than 1, then the convergence is faster and is less dependent on the CiR and SNR. When the CiR is less than one, the convergence is significantly more sensitive to the CiR, the SNR, and the initial phase. Additionally, the lower the frequency, the more difficult the convergence. [ABSTRACT FROM PUBLISHER]

We consider perfect secret key generation for a “pairwise independent network” model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then allowed to communicate interactively over a public noiseless channel of unlimited capacity. All the terminals as well as an eavesdropper observe this communication. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible, and concealed from the eavesdropper. First, we show how the notion of perfect omniscience plays a central role in characterizing perfect secret key capacity. Second, a multigraph representation of the underlying secrecy model leads us to an efficient algorithm for perfect secret key generation based on maximal Steiner tree packing. This algorithm attains capacity when all the terminals seek to share a key, and, in general, attains at least half the capacity. Third, when a single “helper” terminal assists the remaining “user” terminals in generating a perfect secret key, we give necessary and sufficient conditions for the optimality of the algorithm; also, a “weak” helper is shown to be sufficient for optimality. [ABSTRACT FROM AUTHOR]

We consider secret key generation for a “pairwise independent network” model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate publicly with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible, with the cooperation of any remaining terminals. Secrecy is required from an eavesdropper that has access to the public interterminal communication. A (single-letter) formula for secret key capacity brings out a natural connection between the problem of secret key generation and a combinatorial problem of maximal packing of Steiner trees in an associated multigraph. An explicit algorithm is proposed for secret key generation based on a maximal packing of Steiner trees in a multigraph; the corresponding maximum rate of Steiner tree packing is thus a lower bound for the secret key capacity. When only two of the terminals or when all the terminals seek to share a secret key, the mentioned algorithm achieves secret key capacity in which case the bound is tight. [ABSTRACT FROM PUBLISHER]

In the original paper named above (ibid., vol. 20, no. 9, pp. 2627-2635, Sep 2011), Table II incorrectly appeared as a duplicate of Table III. Instead, Table II should have correctly appeared as shown here. [ABSTRACT FROM AUTHOR]

This paper addresses how to model and correct image blur that arises when a camera undergoes ego motion while observing a distant scene. In particular, we discuss how the blurred image can be modeled as an integration of the clear scene under a sequence of planar projective transformations (i.e., homographies) that describe the camera's path. This projective motion path blur model is more effective at modeling the spatially varying motion blur exhibited by ego motion than conventional methods based on space-invariant blur kernels. To correct the blurred image, we describe how to modify the Richardson-Lucy (RL) algorithm to incorporate this new blur model. In addition, we show that our projective motion RL algorithm can incorporate state-of-the-art regularization priors to improve the deblurred results. The projective motion path blur model, along with the modified RL algorithm, is detailed, together with experimental results demonstrating its overall effectiveness. Statistical analysis on the algorithm's convergence properties and robustness to noise is also provided. [ABSTRACT FROM AUTHOR]

This paper proposes a unified framework for quality-based fusion of multimodal biometrics. Quality-dependent fusion algorithms aim to dynamically combine several classifier (biometric expert) outputs as a function of automatically derived (biometric) sample quality. Quality measures used for this purpose quantify the degree of conformance of biometric samples to some predefined criteria known to influence the system performance. Designing a fusion classifier to take quality into consideration is difficult because quality measures cannot be used to distinguish genuine users from impostors, i.e., they are nondiscriminative yet still useful for classification. We propose a general Bayesian framework that can utilize the quality information effectively. We show that this framework encompasses several recently proposed quality-based fusion algorithms in the literature—Nandakumar et al., 2006; Poh et al., 2007; Kryszczuk and Drygajo, 2007; Kittler et al., 2007; Alonso-Fernandez, 2008; Maurer and Baker, 2007; Poh et al., 2010. Furthermore, thanks to the systematic study concluded herein, we also develop two alternative formulations of the problem, leading to more efficient implementation (with fewer parameters) and achieving performance comparable to, or better than, the state of the art. Last but not least, the framework also improves the understanding of the role of quality in multiple classifier combination. [ABSTRACT FROM AUTHOR]

We address the Primary User (PU) detection (spectrum sensing) problem, relevant to cognitive radio, from a finite random matrix theoretical (RMT) perspective. Specifically, we employ recently-derived closed-form and exact expressions for the distribution of the standard condition number (SCN) of uncorrelated and semi-correlated random dual central Wishart matrices of finite sizes in the design Hypothesis-Testing algorithms to detect the presence of PU signals. In particular, two algorithms are designed, with basis on the SCN distribution in the absence (H_0) and in the presence (H_1) of PU signals, respectively. Due to an inherent property of the SCN's, the H_0 test requires no estimation of SNR or any other information on the PU signal, while the H_1 test requires SNR only. Further attractive advantages of the new techniques are: a) due to the accuracy of the finite SCN distributions, superior performance is achieved under a finite number of samples, compared to asymptotic RMT-based alternatives; b) since expressions to model the SCN statistics both in the absence and presence of PU signal are used, the statistics of the spectrum sensing problem in question is completely characterized; and c) as a consequence of a) and b), accurate and simple analytical expressions for the receiver operating characteristic (ROC) — both in terms of the probability of detection as a function of the probability of false alarm (P_D versus P_F) and in terms of the probability of acquisition as a function of the probability of miss detection (P_A versus P_M) — are yielded. It is also shown that the proposed finite RMT-based algorithms outperform all similar alternatives currently known in the literature, at a substantially lower complexity. In the process, several new results on the distributions of eigenvalues and SCNs of random Wishart Matrices are offered, including a closed-form of the Marchenko-Pastur's Cumulative Density Function (CDF) and extensions of the latter, as well as variations of asymptotic the distributions of extreme eigenvalues (Tracy-Widom) and their ratio (Tracy-Widom-Curtiss), which are simpler than those obtained with the "spiked population model". [ABSTRACT FROM AUTHOR]