Zhe LI Yili XIA Qian WANG Wenjiang PEI Jinguang HAO
A novel time-series relationship among four consecutive real-valued single-tone sinusoid samples is proposed based on their linear prediction property. In order to achieve unbiased frequency estimates for a real sinusoid in white noise, based on the proposed four-point time-series relationship, a constrained least squares cost function is minimized based on the unit-norm principle. Closed-form expressions for the variance and the asymptotic expression for the variance of the proposed frequency estimator are derived, facilitating a theoretical performance comparison with the existing three-point counterpart, called as the reformed Pisarenko harmonic decomposer (RPHD). The region of performance advantage of the proposed four-point based constrained least squares frequency estimator over the RPHD is also discussed. Computer simulations are conducted to support our theoretical development and to compare the proposed estimator performance with the RPHD as well as the Cramer-Rao lower bound (CRLB).
Shengyu YAO Ruohua ZHOU Pengyuan ZHANG
This paper proposes a speaker-phonetic i-vector modeling method for text-dependent speaker verification with random digit strings, in which enrollment and test utterances are not of the same phrase. The core of the proposed method is making use of digit alignment information in i-vector framework. By utilizing force alignment information, verification scores of the testing trials can be computed in the fixed-phrase situation, in which the compared speech segments between the enrollment and test utterances are of the same phonetic content. Specifically, utterances are segmented into digits, then a unique phonetically-constrained i-vector extractor is applied to obtain speaker and channel variability representation for every digit segment. Probabilistic linear discriminant analysis (PLDA) and s-norm are subsequently used for channel compensation and score normalization respectively. The final score is obtained by combing the digit scores, which are computed by scoring individual digit segments of the test utterance against the corresponding ones of the enrollment. Experimental results on the Part 3 of Robust Speaker Recognition (RSR2015) database demonstrate that the proposed approach significantly outperforms GMM-UBM by 52.3% and 53.5% relative in equal error rate (EER) for male and female respectively.
Keisuke OSAWA Hiromasa HABUCHI Yusuke KOZAWA
Lighting constrained visible-light communications are expected as indoor communications of next generation. In lighting constrained visible-light communications, lighting devices are used not only for illuminating rooms but also for optical wireless communications. For lighting constrained visible-light communications, we have been proposed a variable N-parallel code-shift-keying (VN-CSK) using a modified prime sequence code (MPSC). The VN-CSK system using MPSC has not only a suppression function for reducing co-channel interference from neighboring lighting devices, but also a function for keeping constant data transmission regardless of dimming control. In this paper, the bit error rate (BER) of the VN-CSK system using MPSC is derived under an indoor visible-light communication channel by theoretical analysis. Moreover, we evaluate the BER performance for the brightness level (dimming control stage).
Wei XUE Junhong REN Xiao ZHENG Zhi LIU Yueyong LIANG
Dai-Yuan (DY) conjugate gradient method is an effective method for solving large-scale unconstrained optimization problems. In this paper, a new DY method, possessing a spectral conjugate parameter βk, is presented. An attractive property of the proposed method is that the search direction generated at each iteration is descent, which is independent of the line search. Global convergence of the proposed method is also established when strong Wolfe conditions are employed. Finally, comparison experiments on impulse noise removal are reported to demonstrate the effectiveness of the proposed method.
Bilkisu Larai MUHAMMAD-BELLO Masayoshi ARITSUGI
The Infrastructure as a Service (IaaS) Clouds are emerging as a promising platform for the execution of resource demanding and computation intensive workflow applications. Scheduling the execution of scientific applications expressed as workflows on IaaS Clouds involves many uncertainties due to the variable and unpredictable performance of Cloud resources. These uncertainties are modeled by probability distribution functions in past researches or totally ignored in some cases. In this paper, we propose a novel robust deadline constrained workflow scheduling algorithm which handles the uncertainties in scheduling workflows in the IaaS Cloud environment. Our proposal is a static scheduling algorithm aimed at addressing the uncertainties related to: the estimation of task execution times; and, the delay in provisioning computational Cloud resources. The workflow scheduling problem was considered as a cost-optimized, deadline-constrained optimization problem. Our uncertainty handling strategy was based on the consideration of knowledge of the interval of uncertainty, which we used to modeling the execution times rather than using a known probability distribution function or precise estimations which are known to be very sensitive to variations. Experimental evaluations using CloudSim with synthetic workflows of various sizes show that our proposal is robust to fluctuations in estimates of task runtimes and is able to produce high quality schedules that have deadline guarantees with minimal penalty cost trade-off depending on the length of the interval of uncertainty. Scheduling solutions for varying degrees of uncertainty resisted against deadline violations at runtime as against the static IC-PCP algorithm which could not guarantee deadline constraints in the face of uncertainty.
In many applications, tables are distributively stored in different data sources, but the frequency of updates on each data source is different. Some techniques have been proposed to effectively express the temporal orders between different values, and the most current, i.e. up-to-date, value of a given data item can be easily picked up according to the temporal orders. However, the currency of the data items in the same table may be different. That is, when a user asks for a table D, it cannot be ensured that all the most current values of the data items in D are stored in a single table. Since different data sources may have overlaps, we can construct a conjunctive query on multiple tables to get all the required current values. In this paper, we formalize the conjunctive query as currency preserving query, and study how to generate the minimized currency preserving query to reduce the cost of visiting different data sources. First, a graph model is proposed to represent the distributed tables and their relationships. Based on the model, we prove that a currency preserving query is equivalent to a terminal tree in the graph, and give an algorithm to generate a query from a terminal tree. After that, we study the problem of finding minimized currency preserving query. The problem is proved to be NP-hard, and some heuristics strategies are provided to solve the problem. Finally, we conduct experiments on both synthetic and real data sets to verify the effectiveness and efficiency of the proposed techniques.
Tadashi WADAYAMA Taisuke IZUMI
Several types of capacitive crosstalk avoidance codes have been devised in order to prevent capacitive crosstalk in on-chip buses. These codes are designed to prohibit transition patterns prone to capacitive crosstalk from any two consecutive words transmitted to on-chip buses. The present paper provides a rigorous analysis of the asymptotic rate for (p,q)-transition free word sequences under the assumption that coding is based on a stateful encoder and a stateless decoder. Here, p and q represent k-bit transition patterns that should not appear in any two consecutive words at the same adjacent k-bit positions. The maximum rate for the sequences is proven to be equal to the subgraph domatic number of the (p,q)-transition free graph. Based on the theoretical results for the subgraph domatic partition problem, lower and upper bounds on the asymptotic rate are derived. We also show that the asymptotic rate 0.8325 is achievable for p=01 and q=10 transition free word sequences.
In an X channel, multiple transmitters transmit independent signals to different receivers. Separate zero-forcing (ZF) precoding is used at transmitters in the two-user X channel with two transmitters and two receivers. A closed-form optimal power allocation is derived under the sum power constraint (SPC) to maximize the squared minimum distance. The ZF strategy with optimal power allocation achieves a significant signal to noise ratio (SNR) improvement. Under the individual power constraint (IPC), a suboptimal power allocation that achieves better performance compared to the existing algorithms is also proposed.
Yosuke MIZUNO Goki NUMATA Tomohito KAWA Heeyoung LEE Neisei HAYASHI Kentaro NAKAMURA
We review the recent advances on strain and temperature sensing techniques based on multimodal interference in perfluorinated (PF) graded-index (GI) polymer optical fibers (POFs). First, we investigate their fundamental characteristics at 1300nm. When the core diameter is 62.5µm, we obtain strain and temperature sensitivities of -112pm/µε and +49.8nm/°C, the absolute values of which are, by simple calculation, approximately 13 and over 1800 times as large as those in silica GI multimode fibers, respectively. These ultra-high strain and temperature sensitivities probably originate from the unique PF polymer used as core material. Subsequently, we show that the temperature sensitivity (absolute value) is significantly enhanced with increasing temperature toward ∼70°C, which is close to the glass-transition temperature of the core polymer. When the core diameter is 62.5µm, the sensitivity at 72°C at 1300nm is 202nm/°C, which is approximately 26 times the value obtained at room temperature and >7000 times the highest value previously reported using a silica multimode fiber. Then, we develop a single-end-access configuration of this strain and temperature sensing system, which enhances the degree of freedom in embedding the sensors into structures. The light Fresnel-reflected at the distal open end of the POF is exploited. The obtained strain and temperature sensitivities are shown to be comparable to those in two-end-access configurations. Finally, we discuss the future prospects and give concluding remarks.
Tianyi XIE Bin LYU Zhen YANG Feng TIAN
In this letter, we study a wireless powered communication network (WPCN) with non-orthogonal multiple access (NOMA), where the user clustering scheme that groups each two users in a cluster is adopted to guarantee the system performance. The two users in a cluster transmit data simultaneously via NOMA, while time division multiple access (TDMA) is used among clusters. We aim to maximize the system throughput by finding the optimal cluster permutation and the optimal time allocation, which can be obtained by solving the optimization problems corresponding to all cluster permutations. The closed-form solution of each optimization problem is obtained by exploiting its constraint structures. However, the complexity of this exhaustive method is quite high, we further propose a sub-optimal clustering scheme with low complexity. The simulation results demonstrate the superiority of the proposed scheme.
This paper studies a wireless powered communication network (WPCN) with non-orthogonal multiple access (NOMA) under successive interference cancellation (SIC) constraints, where the users first harvest energy from the power station and then transmit data to the information receiver simultaneously. Under this setup, we investigate the system throughput maximization problem. We first formulate an optimization problem for a general case, which is non-convex. To derive the optimal solution, new variables are introduced to transform the initial problem into a convex optimization problem. For a special case, i.e., two-user case, the optimal solution is derived as a closed-form expression. Simulations on the effect of SIC constraints show the importance of the distinctness among users' channels for the proposed model.
Yasuhiro MOCHIDA Daisuke SHIRAI Tatsuya FUJII
Existing remote collaboration systems are not suitable for a collaboration style where distributed users touch work tools at the same time, especially in demanding use cases or in severe network situations. To cover a wider range of use cases, we propose a novel concept of a remote collaboration platform that enables the users to share currently-used work tools with a high quality A/V transmission module, while maintaining the advantages of web-based systems. It also provides functions to deal with long transmission delay using relay servers, packet transmission instability using visual feedback of audio delivery and limited bandwidth using dynamic allocation of video bitrate. We implemented the platform and conducted evaluation tests. The results show the feasibility of the proposed concept and its tolerance to network constraints, which indicates that the proposed platform can construct unprecedented collaboration systems.
Kazuhiko KINOSHITA Masahiko AIHARA Shiori KONO Nariyoshi YAMAI Takashi WATANABE
In recent years, the number of requests to transfer large files via large high-speed computer networks has been increasing rapidly. Typically, these requests are handled in the “best effort” manner which results in unpredictable completion times. In this paper, we consider a model where a transfer request either must be completed by a user-specified deadline or must be rejected if its deadline cannot be satisfied. We propose a bandwidth scheduling method and a routing method for reducing the call-blocking probability in a bandwidth-guaranteed network. Finally, we show their excellent performance by simulation experiments.
Satoshi TAOKA Tadachika OKI Toshiya MASHIMA Toshimasa WATANABE
The k-edge-connectivity augmentation problem with multipartition constraints (kECAMP, for short) is defined by “Given a multigraph G=(V,E) and a multipartition π={V1,...,Vr} (r≥2) of V, that is, $V = igcup_{h = 1}^r V_h$ and Vi∩Vj=∅ (1≤i
Akimitsu DOI Takao HINAMOTO Wu-Sheng LU
Block-state realization of state-space digital filters offers reduced implementation complexity relative to canonical state-space filters while filter's internal structure remains accessible. In this paper, we present a quantitative analysis on l2 coefficient sensitivity of block-state digital filters. Based on this, we develop two techniques for minimizing average l2-sensitivity subject to l2-scaling constraints. One of the techniques is based on a Lagrange function and some matrix-theoretic techniques. The other solution method converts the problem at hand into an unconstrained optimization problem which is solved by using an efficient quasi-Newton algorithm where the key gradient evaluation is done in closed-form formulas for fast and accurate execution of quasi-Newton iterations. A case study is presented to demonstrate the validity and effectiveness of the proposed techniques.
Maxime CLEMENT Tenda OKIMOTO Katsumi INOUE
Many real world optimization problems involving sets of agents can be modeled as Distributed Constraint Optimization Problems (DCOPs). A DCOP is defined as a set of variables taking values from finite domains, and a set of constraints that yield costs based on the variables' values. Agents are in charge of the variables and must communicate to find a solution minimizing the sum of costs over all constraints. Many applications of DCOPs include multiple criteria. For example, mobile sensor networks must optimize the quality of the measurements and the quality of communication between the agents. This introduces trade-offs between solutions that are compared using the concept of Pareto dominance. Multi-Objective Distributed Constraint Optimization Problems (MO-DCOPs) are used to model such problems where the goal is to find the set of Pareto optimal solutions. This set being exponential in the number of variables, it is important to consider fast approximation algorithms for MO-DCOPs. The bounded multi-objective max-sum (B-MOMS) algorithm is the first and only existing approximation algorithm for MO-DCOPs and is suited for solving a less-constrained problem. In this paper, we propose a novel approximation MO-DCOP algorithm called Distributed Pareto Local Search (DPLS) that uses a local search approach to find an approximation of the set of Pareto optimal solutions. DPLS provides a distributed version of an existing centralized algorithm by complying with the communication limitations and the privacy concerns of multi-agent systems. Experiments on a multi-objective extension of the graph-coloring problem show that DPLS finds significantly better solutions than B-MOMS for problems with medium to high constraint density while requiring a similar runtime.
In this paper, we propose a construction of non-binary WOM (Write-Once-Memory) codes for WOM storages such as flash memories. The WOM codes discussed in this paper are fixed rate WOM codes where messages in a fixed alphabet of size M can be sequentially written in the WOM storage at least t*-times. In this paper, a WOM storage is modeled by a state transition graph. The proposed construction has the following two features. First, it includes a systematic method to determine the encoding regions in the state transition graph. Second, the proposed construction includes a labeling method for states by using integer programming. Several novel WOM codes for q level flash memories with 2 cells are constructed by the proposed construction. They achieve the worst numbers of writes t* that meet the known upper bound in the range 4≤q≤8, M=8. In addition, we constructed fixed rate non-binary WOM codes with the capability to reduce ICI (inter cell interference) of flash cells. One of the advantages of the proposed construction is its flexibility. It can be applied to various storage devices, to various dimensions (i.e, number of cells), and various kind of additional constraints.
Saori TAKEYAMA Shunsuke ONO Itsuo KUMAZAWA
Existing image deblurring methods with a blurred/noisy image pair take a two-step approach: blur kernel estimation and image restoration. They can achieve better and much more stable blur kernel estimation than single image deblurring methods. On the other hand, in the image restoration step, they do not exploit the information on the noisy image, or they require ad hoc tuning of interdependent parameters. This paper focuses on the image restoration step and proposes a new restoration method of using a blurred/noisy image pair. In our method, the image restoration problem is formulated as a constrained convex optimization problem, where data-fidelity to a blurred image and that to a noisy image is properly taken into account as multiple hard constraints. This offers (i) high quality restoration when the blurred image also contains noise; (ii) robustness to the estimation error of the blur kernel; and (iii) easy parameter setting. We also provide an efficient algorithm for solving our optimization problem based on the so-called alternating direction method of multipliers (ADMM). Experimental results support our claims.
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.
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.