Rachelle RIVERO Richard LEMENCE Tsuyoshi KATO
With the huge influx of various data nowadays, extracting knowledge from them has become an interesting but tedious task among data scientists, particularly when the data come in heterogeneous form and have missing information. Many data completion techniques had been introduced, especially in the advent of kernel methods — a way in which one can represent heterogeneous data sets into a single form: as kernel matrices. However, among the many data completion techniques available in the literature, studies about mutually completing several incomplete kernel matrices have not been given much attention yet. In this paper, we present a new method, called Mutual Kernel Matrix Completion (MKMC) algorithm, that tackles this problem of mutually inferring the missing entries of multiple kernel matrices by combining the notions of data fusion and kernel matrix completion, applied on biological data sets to be used for classification task. We first introduced an objective function that will be minimized by exploiting the EM algorithm, which in turn results to an estimate of the missing entries of the kernel matrices involved. The completed kernel matrices are then combined to produce a model matrix that can be used to further improve the obtained estimates. An interesting result of our study is that the E-step and the M-step are given in closed form, which makes our algorithm efficient in terms of time and memory. After completion, the (completed) kernel matrices are then used to train an SVM classifier to test how well the relationships among the entries are preserved. Our empirical results show that the proposed algorithm bested the traditional completion techniques in preserving the relationships among the data points, and in accurately recovering the missing kernel matrix entries. By far, MKMC offers a promising solution to the problem of mutual estimation of a number of relevant incomplete kernel matrices.
Yufei HAN Mingjiang WANG Boya ZHAO
Improved fractional variable tap-length adaptive algorithm that contains Sigmoid limited fluctuation function and adaptive variable step-size of tap-length based on fragment-full error is presented. The proposed algorithm can solve many deficiencies in previous algorithm, comprising small convergence rate and weak anti-interference ability. The parameters are able to modify reasonably on the basis of different situations. The Sigmoid constrained function can decrease the fluctuant amplitude of the instantaneous errors effectively and improves the ability of anti-noise interference. Simulations demonstrate that the proposed algorithm equips better performance.
Jianfeng LU Zheng WANG Dewu XU Changbing TANG Jianmin HAN
The user authorization query (UAQ) problem determines whether there exists an optimum set of roles to be activated to provide a set of permissions requested by a user. It has been deemed as a key issue for efficiently handling user's access requests in role-based access control (RBAC). Unfortunately, the weight is a value attached to a permission/role representing its importance, should be introduced to UAQ, has been ignored. In this paper, we propose a comprehensive definition of the weighted UAQ (WUAQ) problem with the role-weighted-cardinality and permission-weighted-cardinality constraints. Moreover, we study the computational complexity of different subcases of WUAQ, and show that many instances in each subcase are intractable. In particular, inspired by the idea of the genetic algorithm, we propose an algorithm to approximate solve an intractable subcase of the WUAQ problem. An important observation is that this algorithm can be efficiently modified to handle the other subcases of the WUAQ problem. The experimental results show the advantage of the proposed algorithm, which is especially fit for the case that the computational overhead is even more important than the accuracy in a large-scale RBAC system.
Mitsuyoshi HAGIWARA Toshihiko NISHIMURA Takeo OHGANE Yasutaka OGAWA
Recently, much progress has been made in the study of belief propagation (BP) based signal detection with large-scale factor graphs. When we apply the BP algorithm to equalization in a SISO multipath channel, the corresponding factor graph has many short loops and patterns in an edge connection/strength. Thus, proper convergence may not be achieved. In general, the log-likelihood ratio (LLR) oscillates in ill-converged cases. Therefore, LLR oscillation avoidance is important for BP-based equalization. In this paper, we propose applying node selection (NS) to prevent the LLR from oscillating. The NS extends the loop length virtually by a serial LLR update. Thus, some performance improvement is expected. Simulation results show that the error floor is significantly reduced by NS in the uncoded case and that the NS works very well in the coded case.
Shunichi BUSHISUE Satoshi SUYAMA Satoshi NAGATA Nobuhiko MIKI
In the future, 5G radio access and support for the internet of things (IoT) is becoming more important, which is called machine type communications. Different from current mobile communication systems, machine type communications generates relatively small packets. In order to support such small packets with high reliability, channel coding techniques are inevitable. One of the most effective channel codes in such conditions is the tail-biting convolutional code, since it is used in LTE systems due to its good performance for small packet sizes. By employing a list Viterbi algorithm for the tail-biting convolutional code, the block error rate (BLER) performances is further improved. Therefore, this paper evaluates the BLER performances of several list Viterbi algorithms, i.e., circular parallel list Viterbi algorithm (CPLVA), per stage CPLVA (PSCPLVA), and successive state and sequence estimation (SSSE). In the evaluation, computational complexity is also taken into account. It is shown that the performance of the CPLVA is better in the wide range of computational complexity defined in this paper.
Bin YANG Yuliang LU Kailong ZHU Guozheng YANG Jingwei LIU Haibo YIN
The rapid development of information techniques has lead to more and more high-dimensional datasets, making classification more difficult. However, not all of the features are useful for classification, and some of these features may even cause low classification accuracy. Feature selection is a useful technique, which aims to reduce the dimensionality of datasets, for solving classification problems. In this paper, we propose a modified bat algorithm (BA) for feature selection, called MBAFS, using a SVM. Some mechanisms are designed for avoiding the premature convergence. On the one hand, in order to maintain the diversity of bats, they are guided by the combination of a random bat and the global best bat. On the other hand, to enhance the ability of escaping from local optimization, MBAFS employs one mutation mechanism while the algorithm trapped into local optima. Furthermore, the performance of MBAFS was tested on twelve benchmark datasets, and was compared with other BA based algorithms and some well-known BPSO based algorithms. Experimental results indicated that the proposed algorithm outperforms than other methods. Also, the comparison details showed that MBAFS is competitive in terms of computational time.
As autonomous underwater vehicles (AUVs) have been widely used to perform cooperative works with sensor nodes for data-gathering, the need for long-range AUVs has further grown to support the long-duration cooperation with sensor nodes. However, as existing data-gathering protocols for the cooperative works have not considered AUVs' energy consumption, AUVs can deplete their energy more quickly before fulfilling their missions. The objective of this work is to develop an AUV based data-gathering protocol that maximizes the duration for the cooperative works. Simulation results show that the proposed protocol outperforms existing protocols with respect to the long-range AUVs.
Takeshi IHARA Toshiyuki HONGO Atsushi TAKAHASHI Chikaaki KODAMA
Self-Aligned Quadruple Patterning (SAQP) is an important manufacturing technique for sub 14nm technology node. Although various routing algorithms for SAQP have been proposed, it is not easy to find a dense SAQP compliant routing pattern efficiently. Even though a grid for SAQP compliant routing pattern was proposed, it is not easy to find a valid routing pattern on the grid. The routing pattern of SAQP on the grid consists of three types of routing. Among them, third type has turn prohibition constraint on the grid. Typical routing algorithms often fail to find a valid routing for third type. In this paper, a simple directed grid-graph for third type is proposed. Valid SAQP compliant two dimensional routing patterns are found effectively by utilizing the proposed directed grid-graph. Experiments show that SAQP compliant routing patterns are found efficiently by our proposed method.
Shunsuke KOSHITA Hiroyuki MUNAKATA Masahide ABE Masayuki KAWAMATA
In the field of adaptive notch filtering, Monotonically Increasing Gradient (MIG) algorithm has recently been proposed by Sugiura and Shimamura [1], where it is claimed that the MIG algorithm shows monotonically increasing gradient characteristics. However, our analysis has found that the underlying theory in [1] includes crucial errors. This letter shows that the formulation of the gradient characteristics in [1] is incorrect, and reveals that the MIG algorithm fails to realize monotonically increasing gradient characteristics when the input signal includes white noise.
This letter proposes a heuristic algorithm to select check variables, which are points of comparison for error detection, for soft-error tolerant datapaths. Our soft-error tolerance scheme is based on check-and-retry computation and an efficient resource management named speculative resource sharing (SRS). Starting with the smallest set of check variables, the proposed algorithm repeats to add new check variable one by one incrementally and find the minimum latency solution among the series of generated solutions. During the process, each new check variable is selected so that the opportunity of SRS is enlarged. Experimental results show that improvements in latency are achieved compared with the choice of the smallest set of check variables.
Runze WU Jiajia ZHU Liangrui TANG Chen XU Xin WU
Deploying low power nodes (LPNs), which reuse the spectrum licensed to a macrocell network, is considered to be a promising way to significantly boost network capacity. Due to the spectrum-sharing, the deployment of LPNs could trigger the severe problem of interference including intra-tier interference among dense LPNs and inter-tier interference between LPNs and the macro base station (MBS), which influences the system performance strongly. In this paper, we investigate a spectrum-sharing approach in the downlink for two-tier networks, which consists of small cells (SCs) with several LPNs and a macrocell with a MBS, aiming to mitigate the interference and improve the capacity of SCs. The spectrum-sharing approach is described as a multi-objective optimization problem. The problem is solved by the nondominated sorting genetic algorithm version II (NSGA-II), and the simulations show that the proposed spectrum-sharing approach is superior to the existing one.
Haibo DAI Chunguo LI Luxi YANG
In this letter, we propose two robust and distributed game-based algorithms, which are the modifications of two algorithms proposed in [1], to solve the joint base station selection and resource allocation problem with imperfect information in heterogeneous cellular networks (HCNs). In particular, we repeatedly sample the received payoffs in the exploitation stage of each algorithm to guarantee the convergence when the payoffs of some users (UEs) in [1] cannot accurately be acquired for some reasons. Then, we derive the rational sampling number and prove the convergence of the modified algorithms. Finally, simulation results demonstrate that two modified algorithms achieve good convergence performances and robustness in the incomplete information scheme.
Wenhao FU Huiqun YU Guisheng FAN Xiang JI
Regression testing is essential for assuring the quality of a software product. Because rerunning all test cases in regression testing may be impractical under limited resources, test case prioritization is a feasible solution to optimize regression testing by reordering test cases for the current testing version. In this paper, we propose a novel test case prioritization approach that combines the clustering algorithm and the scheduling algorithm for improving the effectiveness of regression testing. By using the clustering algorithm, test cases with same or similar properties are merged into a cluster, and the scheduling algorithm helps allocate an execution priority for each test case by incorporating fault detection rates with the waiting time of test cases in candidate set. We have conducted several experiments on 12 C programs to validate the effectiveness of our proposed approach. Experimental results show that our approach is more effective than some well studied test case prioritization techniques in terms of average percentage of fault detected (APFD) values.
Daehun KIM Bonhwa KU David K. HAN Hanseok KO
In this paper, an algorithm is proposed for license plate recognition (LPR) in video traffic surveillance applications. In an LPR system, the primary steps are license plate detection and character segmentation. However, in practice, false alarms often occur due to images of vehicle parts that are similar in appearance to a license plate or detection rate degradation due to local illumination changes. To alleviate these difficulties, the proposed license plate segmentation employs an adaptive binarization using a superpixel-based local contrast measurement. From the binarization, we apply a set of rules to a sequence of characters in a sub-image region to determine whether it is part of a license plate. This process is effective in reducing false alarms and improving detection rates. Our experimental results demonstrate a significant improvement over conventional methods.
Yin ZHU Fanman MENG Jian XIONG Guan GUI
Multiple image group cosegmentation (MGC) aims at segmenting common object from multiple group of images, which is a new cosegmentation research topic. The existing MGC methods formulate MGC as label assignment problem (Markov Random Field framework), which is observed to be sensitive to parameter setting. Meanwhile, it is also observed that large object variations and complicated backgrounds dramatically decrease the existing MGC performance. To this end, we propose a new object proposal based MGC model, with the aim of avoiding tedious parameter setting, and improving MGC performance. Our main idea is to formulate MGC as new region proposal selection task. A new energy function in term of proposal is proposed. Two aspects such as the foreground consistency within each single image group, and the group consistency among image groups are considered. The energy minimization method is designed in EM framework. Two steps such as the loop belief propagation and foreground propagation are iteratively implemented for the minimization. We verify our method on ICoseg dataset. Six existing cosegmentation methods are used for the comparison. The experimental results demonstrate that the proposed method can not only improve MGC performance in terms of larger IOU values, but is also robust to the parameter setting.
In this paper, we consider a coherently distributed (CD) source model. Since the CD source is characterized by four parameters: central azimuth direction-of-arrival (DOA), azimuth angular spread, central elevation DOA and elevation angular spread, the parameter estimation is normally complex. We propose an algorithm that combines the rotational invariance techniques (ESPRIT) and the generalized ESPRIT algorithm for the 2-dimensional (2D) central DOA estimation of CD sources. Using a pair of uniform circular arrays (UCAs), the proposed solution is able to obtain the central DOAs with both high accuracy and low computational complexity. The central elevation DOAs are estimated by using the rotational invariance relation between the two uniform circular sub-arrays. Based on the centrosymmetric structure of UCA, the generalized ESPRIT algorithm is then applied to estimate the central azimuth DOAs through one-dimensional searching. It is noteworthy that the central DOAs are estimated without any information of the deterministic angular distribution function (DADF). The performance of the proposed algorithm is demonstrated via computer simulations.
Yingjing QIAN Ni ZHOU Dajiang HE
Device-to-device (D2D) communication enables two local users to communicate with each other directly instead of relaying through a third party, e.g., base station. In this paper, we study a subchannel sharing strategy underlaying multichannel cellular network for D2D pairs and existing cellular users (CUs). In the investigated scenario, we try to improve the spectrum efficiency of D2D pairs, but inevitably brings cross interference between two user groups. To combat interference, we attempt to assign each D2D pair with appropriate subchannels, which may belong to different CUs, and manipulate transmission power of all users so as to maximize the sum rate of all D2D pairs, while assuring each CU with a minimum data rate on its subchannel set. The formulated problem is a nonconvex problem and thus, obtaining its optimal solution is a tough task. However, we can find optimal power and subchannel assignment for a special case by setting an independent data rate constraint on each subchannel. Then we find an efficient method to calculate a gradient for our original problem. Finally, we propose a gradient-based search method to address the problem with coupled minimum data rate constraint. The performance of our proposed subchannel sharing strategy is illustrated via extensive simulation results.
Yasuhiro FUJIWARA Makoto NAKATSUJI Hiroaki SHIOKAWA Takeshi MISHIMA Makoto ONIZUKA
Personalized PageRank (PPR) is a typical similarity metric between nodes in a graph, and node searches based on PPR are widely used. In many applications, graphs change dynamically, and in such cases, it is desirable to perform ad hoc searches based on PPR. An ad hoc search involves performing searches by varying the search parameters or graphs. However, as the size of a graph increases, the computation cost of performing an ad hoc search can become excessive. In this paper, we propose a method called Castanet that offers fast ad hoc searches of PPR. The proposed method features (1) iterative estimation of the upper and lower bounds of PPR scores, and (2) dynamic pruning of nodes that are not needed to obtain a search result. Experiments confirm that the proposed method does offer faster ad hoc PPR searches than existing methods.
Tomoki MATSUZAWA Eisuke ITO Raissa RELATOR Jun SESE Tsuyoshi KATO
In recent years, covariance descriptors have received considerable attention as a strong representation of a set of points. In this research, we propose a new metric learning algorithm for covariance descriptors based on the Dykstra algorithm, in which the current solution is projected onto a half-space at each iteration, and which runs in O(n3) time. We empirically demonstrate that randomizing the order of half-spaces in the proposed Dykstra-based algorithm significantly accelerates convergence to the optimal solution. Furthermore, we show that the proposed approach yields promising experimental results for pattern recognition tasks.
Zhenyu SONG Shangce GAO Yang YU Jian SUN Yuki TODO
This paper proposes a novel multiple chaos embedded gravitational search algorithm (MCGSA) that simultaneously utilizes multiple different chaotic maps with a manner of local search. The embedded chaotic local search can exploit a small region to refine solutions obtained by the canonical gravitational search algorithm (GSA) due to its inherent local exploitation ability. Meanwhile it also has a chance to explore a huge search space by taking advantages of the ergodicity of chaos. To fully utilize the dynamic properties of chaos, we propose three kinds of embedding strategies. The multiple chaotic maps are randomly, parallelly, or memory-selectively incorporated into GSA, respectively. To evaluate the effectiveness and efficiency of the proposed MCGSA, we compare it with GSA and twelve variants of chaotic GSA which use only a certain chaotic map on a set of 48 benchmark optimization functions. Experimental results show that MCGSA performs better than its competitors in terms of convergence speed and solution accuracy. In addition, statistical analysis based on Friedman test indicates that the parallelly embedding strategy is the most effective for improving the performance of GSA.