Search

In Blind Hyperspectral Unmixing, the accuracy of the estimated number of endmembers affects the succeeding steps of extraction of endmember signatures and acquiring their fractional abundances. The characteristics of endmember signature depend on the nature of the material on the ground and share similar characteristics for variants of the same material. In this paper, we introduce a new concept of sub-endmembers to identify similar materials that are variants of a global endmember. Identifying the sub-endmembers will provide a meaningful interpretation of the endmember variability along with increased unmixing accuracy. This paper proposes a new algorithm exploiting both the spatial and spectral information present in hyperspectral data. The hyperspectral data are segmented into homogenous regions (superpixels) based on the Simple Linear Iterative Clustering (SLIC) algorithm, and the mean spectral of each region is accounted for in finding the global endmembers. The difference of eigenvalues-based thresholding method is used to find the number of global and sub-endmembers. The method has been tested on synthetic and real hyperspectral data and has successfully estimated the number of global endmembers as well as sub-endmembers. The method is also compared with other state-of-the-art methods, and better performances are obtained at a reasonably lower computational complexity. [ABSTRACT FROM AUTHOR]

The three-level inverter is extensively preferred in medium-voltage industrial applications over the conventional inverter due to its benefits. The performance of inverter is better when the space vector modulation (SVM) approach is preferred. However, the implementation of conventional SVM approach is more complex. In this paper, a decomposition-based new SVM algorithm for three-level inverter is proposed to reduce computational complexity and implementation time using a low-cost digital controller. Initially, the performance of the proposed SVM algorithm is studied through MATLAB simulation using the conventional switching sequence 0127. Further enhancing the performance, the proposed algorithm is implemented with various advanced discontinuous SVPWM strategies using the advanced switching sequences of 1012–2721 and 0121–7212. The no-load motor current THD and switching loss analysis for ADSVPWM and conventional SVPWM strategies at different modulation indices are presented is this paper for a comparison point of view. The no load motor current THD results obtained through simulation are validated experimentally by implementing the proposed algorithm on real-time interface tool through dSPACE, which is used to control constant V/F-controlled three-level inverter-fed induction motor. Further to show the effectiveness of the proposed technique, the experimental investigation is done on induction motor at loaded condition and the results are presented. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 , 3 } which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of G with weight h (V) = ∑ p ∈ V h (p) : (C1) For every vertex u ∈ V if h (u) = 0 , then u has m (m ≥ 1) neighbors such that whose sum is at least 3, and if h (u) = 1 , then u has n (n ≥ 1) neighbors such that whose sum is at least 2. (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. For a graph G , the smallest possible weight of a TR3DF of G denoted γ t { R 3 } (G) is known as the total Roman { 3 } -domination number of G. The problem of determining γ t { R 3 } (G) of a graph G is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if G has a TR3DF of weight at most l for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a 3 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for the MTR3DP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless NP ⊆ DTIME (| V | O (log log | V |)). Next, we show that MTR3DP is APX-complete for graphs with Δ = 4. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP. [ABSTRACT FROM AUTHOR]

Identifying critical nodes in complex networks has gained increasing attention in recent years. However, how to design an algorithm that has low computational complexity but can accurately identify important network nodes is still a challenge. Considering the role of structural holes in shaping communication channels, this paper presents an effective method based on local characteristics to identify critical nodes that play important roles in maintaining network connectivity. Our method considers the connections of a node as well as the connectivity of the neighborhood of the node. Through numerical simulations on various real-world networks, we have demonstrated that the proposed approach outperforms some other well-known heuristic algorithms in identifying vital nodes and leads to faster network collapse in target destruction. [ABSTRACT FROM AUTHOR]

Prolonging the lifetime of wireless sensor networks (WSN) is the biggest challenging issue. In wireless multimedia sensor networks (WMSNs), sensor nodes have limited energy resource and to increase the lifetime of the network, it is necessary to design an effective fast algorithm that aims at reducing the consumed power. This paper proposes an energy-efficient discrete cosine transform (DCT) approximation requiring only 12 additions. Associated with a JPEG compression chain, this DCT approximation ensures a very good rate-distortion compromise, but above all, a very low computational complexity and significant compatibility with the exact DCT. Simulation results clearly show that the proposed fast transform algorithm achieves a better trade-off between image quality, computational complexity and energy consumption compared to any existing pruned DCT approximations. Furthermore, it is very suitable for the resource constrained wireless visual sensor networks (WVSNs) requiring low bitrates. [ABSTRACT FROM AUTHOR]

Complex networks depict the individual relationship in a population, which can help to deeply mine the characteristics of complex networks and predict the potential collaboration between individuals by analyzing their interaction within different groups or clusters. However, the existing algorithms are with high complexity, which cost much computational time. In this paper, an efficient graph clustering algorithm based on spectral coarsening is proposed, to deal with the large time complexity of the traditional spectral algorithm. We first find the subset most possibly belonged to the same cluster in the original network, and merge them into a single node. The scale of the network will decrease with the network being coarsened. Then, the spectral clustering algorithm is performed on the coarsened network with the maintained advantages and the improved time efficiency. Finally, the experimental results on the multiple datasets demonstrate that the proposed algorithm, compared with the current state-of-the-art methods, has superior performance. [ABSTRACT FROM AUTHOR]

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices' resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges, H admits an orientation optimizing some objective involving the vertices' outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p -DEL-MAX, p -INS-MIN, p -INS-MAX, and p -DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the direction of arrival (DOA) estimation problem of noncircular signals for coprime linear array (CLA). From the perspective of the CLA as extracted from a filled uniform linear array (ULA), a noncircular root-MUSIC algorithm is proposed to estimate the DOA which can avoid the spectral peak search and lower the computational complexity. Due to the noncircular characteristic, the proposed algorithm enables to resolve more sources than sensors. Meanwhile, the proposed algorithm has better angle estimation performance than some conventional DOA estimation algorithms. Numerical simulation results illustrate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

For the virtual reality 360 ∘ videos, equirectangular projection (ERP) is a commonly used projection format. However, its high resolution brings extraordinary huge computational complexity in encoding. In order to speed up the intra coding process, a fast coding unit (CU) partitioning algorithm based on regional decision tree is proposed in this paper. The frame image is divided into two regions from a statistical point of view, and the earlysplit and pruned decision trees are established using light weight sample attributes for each region. With the help of these decision trees, the CU partitioning process is accelerated. Compared with the original algorithm of HM16.20, the proposed algorithm can reduce the encoding time by 28%, while BD-rate only increases by 0.27%. [ABSTRACT FROM AUTHOR]

In this paper, a new auto-scoring algorithm that automatically evaluates the Berg balance scale (BBS) tasks is proposed. The BBS can be used as an indicator for patients to analyze their rehabilitation status by themselves. In the proposed method, the patient must use a wearable inertial measurement unit (IMU) sensor, and the result of the patient's BBS task execution would be scored automatically by the evaluation algorithm. The proposed evaluation algorithm involves only few computations and has high scoring accuracy. Nonlinear kernel principal component analysis and a small number of linear features were combined to reduce the features from each sensor, and the algorithm model was implemented using a support vector machine (SVM), a machine learning technique with low computational complexity. The effectiveness of the algorithm was evaluated through clinical evaluation of 53 subjects with up to eight IMU sensors. The average accuracy of the proposed algorithm using eight sensors was 93.2%, and that using five sensors was 91.5%. There was a 12.6% and 10.9% increase in accuracy, respectively, compared to a previous study. The training and testing times of the proposed SVM model were over 38 times faster than the multi-layer perceptron model used in a previous study. [ABSTRACT FROM AUTHOR]

The security of chaotic cryptographic system can be theoretically evaluated by using conventional statistical tests and numerical simulations, such as the character frequency test, entropy test, avalanche test and SP 800-22 tests. However, when the cryptographic algorithm operates on a cryptosystem, the leakage information such as power dissipation, electromagnetic emission and time-consuming can be used by attackers to analyze the secret keys, namely the Side Channel Analysis (SCA) attack. In this paper, a cryptanalysis method is proposed for evaluating the security of a chaotic block cryptographic system from a hardware perspective by utilizing the Template Attacks (TAs). Firstly, a chaotic block cryptographic system is described briefly and implemented based on an Atmel XMEGA microcontroller. Then the TA using a multivariate Gaussian model is introduced. In order to reduce computational complexity and improve the efficiency of TA, the Hamming weight is used in this work to model power consumption traces. The proposed TA method has the following advantages including (a) using the sum of difference to select points of interest of traces, (b) using a data processing method to minimize the influences on power information modeling from the redundant sampling points, and (c) all the traces are aligned precisely before establishing the templates. Experimental results show that the TA can be used to attack the chaotic cryptographic systems and is more efficient, i.e. ∼ 32% less attack traces than correlation power analysis, when the templates are properly built. [ABSTRACT FROM AUTHOR]

In this paper, we propose a scheme to implement hybrid encryption of images using generalized Arnold transformation and matrix nonlinear operations. This scheme consists of two stages. In the first stage, the pixels scrambling encryption is achieved by using generalized Arnold transformation. In the second stage, the pixels sequence encryption is carried out by a nonlinear matrix operation based on the key stream generated by a random matrix. Accordingly, the decryption process is completed by two steps inverse transformations. The hybrid encryption algorithm is one-time pad, and therefore has good anti-attack performance. The algorithm is featured by good confidentiality, low computational complexity, and easy-to-program processing. Moreover, the effectiveness, security and robustness of the algorithm are demonstrated by an image encryption simulation and the encryption performance analysis. Compared with the traditional Arnold scrambling encryption scheme and the chaotic encryption method based on the generalized standard mapping, the superiority of the proposed algorithm is demonstrated. [ABSTRACT FROM AUTHOR]

Deep learning based on structured deep neural networks has provided powerful applications in various fields. The structures imposed on the deep neural networks are crucial, which makes deep learning essentially different from classical schemes based on fully connected neural networks. One of the commonly used deep neural network structures is generated by convolutions. The produced deep learning algorithms form the family of deep convolutional neural networks. Despite of their power in some practical domains, little is known about the mathematical foundation of deep convolutional neural networks such as universality of approximation. In this paper, we propose a family of new structured deep neural networks: deep distributed convolutional neural networks. We show that these deep neural networks have the same order of computational complexity as the deep convolutional neural networks, and we prove their universality of approximation. Some ideas of our analysis are from ridge approximation, wavelets, and learning theory. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the runtime complexity of programs based on multiset rewriting. The motivation behind this work is the study of the complexity of chemistry-inspired programming models, which recently regained momentum due to their adequacy to large autonomous systems. In these models, data are most of the time left unstructured in a container, formally, a multiset. The program to be applied to this multiset is specified as a set of conditioned rules rewriting the multiset. At run time, these rewrite operations are applied concurrently, until no rule can be applied anymore (the set of elements they need cannot be found in the multiset anymore). A limitation of these models stand in their complexity: each computation step may require a complexity in where n denotes the number of elements in the multiset, and k is the size of the subset of elements needed to trigger a given rule. By analogy with chemistry, such elements can be called reactants. In this paper, we explore the possibility of improving the complexity of searching reactants through a static analysis of the rules' condition. In particular, we give a characterisation of this complexity, by analogy to the subgraph isomorphism problem. Given a rule R, we define its rank rk(R) and its calibre C(R), allowing us to exhibit an algorithm with a complexity in for searching reactants, while showing that and that most of the time. [ABSTRACT FROM AUTHOR]

The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we tour a fragment of the literature and summarize results on upper and lower bounds on the conversion of finite automata to regular expressions and vice versa. As an interesting special case also one-unambiguous regular expressions, a sort of a deterministic version of a regular expression, are considered. We also briefly recall the known bounds for the removal of spontaneous transitions ( ε-transitions) on non- ε-free nondeter-ministic devices. Moreover, we report on recent results on the average case descriptional complexity bounds for the conversion of regular expressions to finite automata and new developments on the state elimination algorithm that converts finite automata to regular expressions. [ABSTRACT FROM AUTHOR]

This paper discusses a computational treatment of the localization of an affine coordinate ring at a prime ideal and its associated graded algebra with the means of computer algebra. Building on Mora's paper [T. Mora, La queste del Saint : A computational approach to local algebra, Discrete Appl. Math. 33 (1991) 161-190], we present shorter proofs on two of the central statements and expand on the applications touched by Mora: resolutions of ideals, systems of parameters and Hilbert polynomials, as well as dimension and regularity of . All algorithms are implemented in the library graal.lib for the computer algebra system Singular. [ABSTRACT FROM AUTHOR]

At present many algorithms for mining association rules have been proposed, but most of them are only suitable for discovering specific frequent itemsets from characteristic data sets on the appointed environments, namely, these algorithms are not general enough when mining association rules. In this paper, a general framework based on composite granules for mining association rules is proposed, which is a general data mining model without appointed restriction from frequent itemsets, data sets or mining environments and so on. An iterative method is efficiently applied to the general mining framework for discovering frequent itemsets, which adopts repartitioning frequent attributes to iteratively reconstruct the mixed radix information system for reducing a relational database. In order that the framework for discovering frequent itemsets has a generality, in discussing and establishing the general mining framework, this paper introduces a novel conception and data model, namely, a mixed radix information system is applied to describe a relational database, and a composite granules is used to build a specific relationship between an information system and a mixed radix information system, which can hold the same extension and simultaneously exist in two different information systems. The mixed radix information system can help the general framework to reduce information data and improve the performance of the framework for generating frequent itemsets. The composite granules model can create a relationship between an information granule and a digital information granule, and help the framework for computing the support to avoid reading the database repeatedly or using the complex data structure. Finally, a new taxonomy is presented to verify the generality and the high efficiency of the mining framework and all the experiments based on the taxonomy indicate that the general mining framework has the required generality, and the performance of the framework is better than these classical mining frameworks. [ABSTRACT FROM AUTHOR]

The formality of signed relationships has been recently adopted in a lot of complicated systems. The relations among these entities are complicated and multifarious. We cannot indicate these relationships only by positive links, and signed networks have been becoming more and more universal in the study of social networks when community is being significant. In this paper, to identify communities in signed networks, we exploit a new greedy algorithm, taking signs and the density of these links into account. The main idea of the algorithm is the initial procedure of signed modularity and the corresponding update rules. Specially, we employ the 'Asymmetric and Constrained Belief Evolution' procedure to evaluate the optimal number of communities. According to the experimental results, the algorithm is proved to be able to run well. More specifically, the proposed algorithm is very efficient for these networks with medium size, both dense and sparse. [ABSTRACT FROM AUTHOR]

Given a source node and a node set, the node-to-set disjoint paths problem is to find disjoint paths from the source node to all nodes from the node set. In this paper, we propose an improved algorithm for the node-to-set disjoint paths problem on bi-rotator graphs. Our result improves the complexity of previous result from to , where n is the dimension of the input graph. [ABSTRACT FROM AUTHOR]

Motion estimation (ME) accounts for the major part of computational complexity of any video coding standard. The diamond search (DS) algorithm is widely used as a fast search technique to perform motion estimation. In this paper, a novel architecture for the diamond search technique is proposed that efficiently handles memory addressing and reduces hardware complexity. The proposed architecture meets the speed requirements for real-time video processing without compromising the area. The design when implemented in Verilog HDL on Virtex-5 technology and synthesized using Xilinx ISE Design Suite 12.4, gives rise to a critical path delay of 3.25 ns and the equivalent area is calculated to be 3.5K gate equivalent. Working at a frequency of 308 MHz, the proposed design can process 128 CIF frames per second. So, the proposed architecture can be incorporated in a video codec targeted for commercial devices like smart-phones, camcorders and video conferencing system. [ABSTRACT FROM AUTHOR]

Community detection is an important issue to understand the structural and functional properties of complex networks, which still remains a challenging subject. In some complex networks, a node may belong to multiple communities, implying overlapping community structure. Moreover, complex networks often show a hierarchical structure where small communities group together to form larger ones. In this paper, we propose a novel parameter-free algorithm called agglomerative clustering based on label propagation algorithm (ACLPA) to detect both overlapping and hierarchical community structure in complex networks. By combining the advantages of agglomerative clustering and label propagation, our algorithm can build the hierarchical tree of overlapping communities in large-scale networks. The tests on both synthetic and real-world networks give excellent results and demonstrate the effectiveness and efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

We present a self-directed method for image segmentation using a modified top-down region dividing (TDRD) approach. The TDRD-based image segmentation method solves some of the issues with histogram and region growing-based segmentation techniques. The process is efficient and achieves proper results without over segmentation or spatial-structure destruction. In this paper, we examine seven user-defined parameters of the method. These parameters are converted from human inputs to values derived from in-class information created by the algorithm allowing for autonomous image segmentation, without the need of human input or feedback. Our new autonomous implementation also reduces the computational complexity of the algorithm. This reduction will produce significant savings for the total number of computations the algorithm needs to perform image segmentation. Experimental results show that the images using these new derived values yield superior results as compared to other methods, including the original TDRD method. We compare our results visually and numerically based on the within-class standard deviation (WCSD) and the number of connected components (NCC). [ABSTRACT FROM AUTHOR]