Nothing Special   »   [go: up one dir, main page]
Next Issue
Volume 8, December
Previous Issue
Volume 8, June
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
4.1
1.8
Journals
Algorithms
Volume 8
Issue 3
share announcement

Algorithms, Volume 8, Issue 3 (September 2015) – 30 articles , Pages 366-798

  • Issues are regarded as officially published after their release is announced to the table of contents alert mailing list.
  • You may sign up for e-mail alerts to receive table of contents of newly released issues.
  • PDF is the official format for papers published in both, html and pdf forms. To view the papers in pdf format, click on the "PDF Full-text" link, and use the free Adobe Reader to open them.
Order results
Result details
Section
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
249 KiB  
Article
A Family of Newton Type Iterative Methods for Solving Nonlinear Equations
by Xiaofeng Wang, Yuping Qin, Weiyi Qian, Sheng Zhang and Xiaodong Fan
Algorithms 2015, 8(3), 786-798; https://doi.org/10.3390/a8030786 - 22 Sep 2015
Cited by 13 | Viewed by 5624
Abstract
In this paper, a general family of n-point Newton type iterative methods for solving nonlinear equations is constructed by using direct Hermite interpolation. The order of convergence of the new n-point iterative methods without memory is 2n requiring the evaluations of n functions [...] Read more.
In this paper, a general family of n-point Newton type iterative methods for solving nonlinear equations is constructed by using direct Hermite interpolation. The order of convergence of the new n-point iterative methods without memory is 2n requiring the evaluations of n functions and one first-order derivative in per full iteration, which implies that this family is optimal according to Kung and Traub’s conjecture (1974). Its error equations and asymptotic convergence constants are obtained. The n-point iterative methods with memory are obtained by using a self-accelerating parameter, which achieve much faster convergence than the corresponding n-point methods without memory. The increase of convergence order is attained without any additional calculations so that the n-point Newton type iterative methods with memory possess a very high computational efficiency. Numerical examples are demonstrated to confirm theoretical results. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
►▼ Show Figures

Graphical abstract

Graphical abstract
Full article ">Figure 1
<p>Iterative processes of different methods for the function <math display="inline"> <mrow> <msub> <mi>f</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>.</mo> </mrow> </math></p> Full article ">
251 KiB  
Article
Parallel Variants of Broyden’s Method
by Ioan Bistran, Stefan Maruster and Liviu Octavian Mafteiu-Scai
Algorithms 2015, 8(3), 774-785; https://doi.org/10.3390/a8030774 - 15 Sep 2015
Cited by 1 | Viewed by 5573
Abstract
In this paper we investigate some parallel variants of Broyden’s method and, for the basic variant, we present its convergence properties. The main result is that the behavior of the considered parallel Broyden’s variants is comparable with the classical parallel Newton method, and [...] Read more.
In this paper we investigate some parallel variants of Broyden’s method and, for the basic variant, we present its convergence properties. The main result is that the behavior of the considered parallel Broyden’s variants is comparable with the classical parallel Newton method, and significantly better than the parallel Cimmino method, both for linear and nonlinear cases. The considered variants are also compared with two more recently proposed parallel Broyden’s method. Some numerical experiments are presented to illustrate the advantages and limits of the proposed algorithms. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
►▼ Show Figures

Figure 1

Figure 1
<p>The graphs of <math display="inline"> <mrow> <mi>l</mi> <mi>n</mi> <mo>(</mo> <msub> <mi>ε</mi> <mi>n</mi> </msub> <mo>)</mo> </mrow> </math> generated by Algorithm 3, parallel Newton method and parallel Cimmino method in the linear case; (<b>a</b>) system well conditioned; (<b>b</b>) system medium conditioned; (<b>c</b>) system poorly conditioned.</p> Full article ">Figure 2
<p>The behavior of the sequence generated by Algorithm 3, Parallel Newton method and Parallel Cimmino method (the graphs (a)) and by Algorithm 4, Parallel Newton method and Parallel Cimmino method (the graphs (b)); (<b>a</b>) system which does not satisfy the condition (2); (<b>b</b>) system well conditioned.</p> Full article ">Figure 3
<p>The graphs of <math display="inline"> <mrow> <mi>l</mi> <mi>n</mi> <mo>(</mo> <msub> <mi>ε</mi> <mi>n</mi> </msub> <mo>)</mo> </mrow> </math> generated by Algorithm 5 and parallel Newton method; (<b>a</b>) the graph corresponding to systems (1); (<b>b</b>) the graph corresponding to systems (2) given by Algorithm 5 modified in accordance with Sherman-Morrison lemma; (<b>c</b>) example of a system verifying the condition <math display="inline"> <mrow> <mrow> <mo>∥</mo> <mi>D</mi> </mrow> <msup> <mrow> <mo>(</mo> <msub> <mi>x</mi> <mi>n</mi> </msub> <mo>)</mo> </mrow> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mrow> <mo>∥</mo> <mo>∥</mo> </mrow> <msub> <mi>E</mi> <mi>n</mi> </msub> <mrow> <mo>∥</mo> <mo>&lt;</mo> <mn>1</mn> </mrow> </mrow> </math>.</p> Full article ">Figure 4
<p>The comparison of Algorithms 3, 1 and 2 in the care of linear systems of low dimensions (m = 5); (<b>a</b>) condition number = 8.598; (<b>b</b>) condition number=4.624; (<b>c</b>) condition number = 3.624.</p> Full article ">
779 KiB  
Article
Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem
by Guillermo M. Mallén-Fullerton, J. Emilio Quiroz-Ibarra, Antonio Miranda and Guillermo Fernández-Anaya
Algorithms 2015, 8(3), 754-773; https://doi.org/10.3390/a8030754 - 10 Sep 2015
Cited by 4 | Viewed by 5809
Abstract
DNA fragment assembly represents an important challenge to the development of efficient and practical algorithms due to the large number of elements to be assembled. In this study, we present some graph theoretical linear time algorithms to solve the problem. To achieve linear [...] Read more.
DNA fragment assembly represents an important challenge to the development of efficient and practical algorithms due to the large number of elements to be assembled. In this study, we present some graph theoretical linear time algorithms to solve the problem. To achieve linear time complexity, a heap with constant time operations was developed, for the special case where the edge weights are integers and do not depend on the problem size. The experiments presented show that modified classical graph theoretical algorithms can solve the DNA fragment assembly problem efficiently. Full article
(This article belongs to the Special Issue Algorithmic Themes in Bioinformatics)
►▼ Show Figures

Figure 1

Figure 1
<p>Some fragments from the <span class="html-italic">S. aureus</span> strain MW2 problem.</p> Full article ">Figure 2
<p>Graph example: graph.</p> Full article ">
292 KiB  
Article
A CS Recovery Algorithm for Model and Time Delay Identification of MISO-FIR Systems
by Yanjun Liu and Taiyang Tao
Algorithms 2015, 8(3), 743-753; https://doi.org/10.3390/a8030743 - 10 Sep 2015
Cited by 28 | Viewed by 5532
Abstract
This paper considers identifying the multiple input single output finite impulse response (MISO-FIR) systems with unknown time delays and orders. Generally, parameters, orders and time delays of an MISO system are separately identified from different algorithms. In this paper, we aim to perform [...] Read more.
This paper considers identifying the multiple input single output finite impulse response (MISO-FIR) systems with unknown time delays and orders. Generally, parameters, orders and time delays of an MISO system are separately identified from different algorithms. In this paper, we aim to perform the model identification and time delay estimation simultaneously from a limited number of observations. For an MISO-FIR system with many inputs and unknown input time delays, the corresponding identification model contains a large number of parameters, requiring a great number of observations for identification and leading to a heavy computational burden. Inspired by the compressed sensing (CS) recovery theory, a threshold orthogonal matching pursuit algorithm (TH-OMP) is presented to simultaneously identify the parameters, the orders and the time delays of the MISO-FIR systems. The proposed algorithm requires only a small number of sampled data compared to the conventional identification methods, such as the least squares method. The effectiveness of the proposed algorithm is verified by simulation results. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>The steam water heat exchanger.</p> Full article ">Figure 2
<p>The estimation error δ <span class="html-italic">versus m</span> measurements.</p> Full article ">Figure 3
<p>The estimation error δ <span class="html-italic">versus</span> iteration <span class="html-italic">k</span> (<span class="html-italic">m</span> = 80, <math display="inline"> <mrow> <msup> <mtext>σ</mtext> <mn>2</mn> </msup> <mo>=</mo> <mn>0</mn> <mo>.</mo> <msup> <mn>10</mn> <mn>2</mn> </msup> </mrow> </math>).</p> Full article ">Figure 4
<p>The parameters estimates <span class="html-italic">versus</span> iteration <span class="html-italic">k</span>.</p> Full article ">
783 KiB  
Article
A Comparative Study of Modern Heuristics on the School Timetabling Problem
by Iosif V. Katsaragakis, Ioannis X. Tassopoulos and Grigorios N. Beligiannis
Algorithms 2015, 8(3), 723-742; https://doi.org/10.3390/a8030723 - 28 Aug 2015
Cited by 10 | Viewed by 4922
Abstract
In this contribution a comparative study of modern heuristics on the school timetabling problem is presented. More precisely, we investigate the application of two population-based algorithms, namely a Particle Swarm Optimization (PSO) and an Artificial Fish Swarm (AFS), on the high school timetabling [...] Read more.
In this contribution a comparative study of modern heuristics on the school timetabling problem is presented. More precisely, we investigate the application of two population-based algorithms, namely a Particle Swarm Optimization (PSO) and an Artificial Fish Swarm (AFS), on the high school timetabling problem. In order to demonstrate their efficiency and performance, experiments with real-world input data have been performed. Both algorithms proposed manage to create feasible and efficient high school timetables, thus fulfilling adequately the timetabling needs of the respective high schools. Computational results demonstrate that both algorithms manage to reach efficient solutions, most of the times better than existing approaches applied to the same school timetabling input instances using the same evaluation criteria. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Two fish timetables which differ in cell (<span class="html-italic">i</span>, <span class="html-italic">j</span>).</p> Full article ">Figure 2
<p>The fish f<sub>1</sub> after switching cells (<span class="html-italic">i</span>, <span class="html-italic">j</span>) and (<span class="html-italic">i</span>, <span class="html-italic">m</span>).</p> Full article ">
242 KiB  
Article
Gradient-Based Iterative Identification for Wiener Nonlinear Dynamic Systems with Moving Average Noises
by Lincheng Zhou, Xiangli Li, Huigang Xu and Peiyi Zhu
Algorithms 2015, 8(3), 712-722; https://doi.org/10.3390/a8030712 - 26 Aug 2015
Cited by 5 | Viewed by 4865
Abstract
This paper focuses on the parameter identification problem for Wiener nonlinear dynamic systems with moving average noises. In order to improve the convergence rate, the gradient-based iterative algorithm is presented by replacing the unmeasurable variables with their corresponding iterative estimates, and to compute [...] Read more.
This paper focuses on the parameter identification problem for Wiener nonlinear dynamic systems with moving average noises. In order to improve the convergence rate, the gradient-based iterative algorithm is presented by replacing the unmeasurable variables with their corresponding iterative estimates, and to compute iteratively the noise estimates based on the obtained parameter estimates. The simulation results show that the proposed algorithm can effectively estimate the parameters of Wiener systems with moving average noises. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
►▼ Show Figures

Figure 1

Figure 1
<p>The Wiener nonlinear OEMA system.</p> Full article ">Figure 2
<p>The GI estimation error <span class="html-italic">δ</span> versus <span class="html-italic">k</span>.</p> Full article ">Figure 3
<p>The GI and NI estimation error <span class="html-italic">δ</span> versus <span class="html-italic">k</span> (<math display="inline"> <mrow> <msup> <mi>σ</mi> <mn>2</mn> </msup> <mo>=</mo> <mn>0</mn> <mo>.</mo> <msup> <mn>20</mn> <mn>2</mn> </msup> </mrow> </math>).</p> Full article ">
777 KiB  
Article
Comparative Study of DE, PSO and GA for Position Domain PID Controller Tuning
by Puren Ouyang and Vangjel Pano
Algorithms 2015, 8(3), 697-711; https://doi.org/10.3390/a8030697 - 21 Aug 2015
Cited by 33 | Viewed by 7081
Abstract
Gain tuning is very important in order to obtain good performances for a given controller. Contour tracking performance is mainly determined by the selected control gains of a position domain PID controller. In this paper, three popular evolutionary algorithms are utilized to optimize [...] Read more.
Gain tuning is very important in order to obtain good performances for a given controller. Contour tracking performance is mainly determined by the selected control gains of a position domain PID controller. In this paper, three popular evolutionary algorithms are utilized to optimize the gains of a position domain PID controller for performance improvement of contour tracking of robotic manipulators. Differential Evolution (DE), Genetic Algorithm (GA), and Particle Swarm Optimization (PSO) are used to determine the optimal gains of the position domain PID controller, and three distinct fitness functions are also used to quantify the contour tracking performance of each solution set. Simulation results show that DE features the highest performance indexes for both linear and nonlinear contour tracking, while PSO is quite efficient for linear contour tracking. Both algorithms performed consistently better than GA that featured premature convergence in all cases. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Scheme of 3-DOF serial robotic manipulator.</p> Full article ">Figure 2
<p>Fitness function best values for linear contour.</p> Full article ">Figure 3
<p>Fitness function best values for nonlinear contour.</p> Full article ">Figure 4
<p>Contour errors produced by the optimized gains.</p> Full article ">Figure 5
<p>Contour performance for linear contour.</p> Full article ">Figure 6
<p>Contour performance for nonlinear contour.</p> Full article ">Figure 7
<p>Mean required torques for both contours.</p> Full article ">
158 KiB  
Article
Network Community Detection on Metric Space
by Suman Saha and Satya P. Ghrera
Algorithms 2015, 8(3), 680-696; https://doi.org/10.3390/a8030680 - 21 Aug 2015
Cited by 5 | Viewed by 5845
Abstract
Community detection in a complex network is an important problem of much interest in recent years. In general, a community detection algorithm chooses an objective function and captures the communities of the network by optimizing the objective function, and then, one uses various [...] Read more.
Community detection in a complex network is an important problem of much interest in recent years. In general, a community detection algorithm chooses an objective function and captures the communities of the network by optimizing the objective function, and then, one uses various heuristics to solve the optimization problem to extract the interesting communities for the user. In this article, we demonstrate the procedure to transform a graph into points of a metric space and develop the methods of community detection with the help of a metric defined for a pair of points. We have also studied and analyzed the community structure of the network therein. The results obtained with our approach are very competitive with most of the well-known algorithms in the literature, and this is justified over the large collection of datasets. On the other hand, it can be observed that time taken by our algorithm is quite less compared to other methods and justifies the theoretical findings. Full article
(This article belongs to the Special Issue Clustering Algorithms)
212 KiB  
Article
Expanding the Applicability of a Third Order Newton-Type Method Free of Bilinear Operators
by Sergio Amat, Sonia Busquier, Concepción Bermúdez and Ángel Alberto Magreñán
Algorithms 2015, 8(3), 669-679; https://doi.org/10.3390/a8030669 - 21 Aug 2015
Cited by 5 | Viewed by 4850
Abstract
This paper is devoted to the semilocal convergence, using centered hypotheses, of a third order Newton-type method in a Banach space setting. The method is free of bilinear operators and then interesting for the solution of systems of equations. Without imposing any type [...] Read more.
This paper is devoted to the semilocal convergence, using centered hypotheses, of a third order Newton-type method in a Banach space setting. The method is free of bilinear operators and then interesting for the solution of systems of equations. Without imposing any type of Fréchet differentiability on the operator, a variant using divided differences is also analyzed. A variant of the method using only divided differences is also presented. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
306 KiB  
Article
Fifth-Order Iterative Method for Solving Multiple Roots of the Highest Multiplicity of Nonlinear Equation
by Juan Liang, Xiaowu Li, Zhinan Wu, Mingsheng Zhang, Lin Wang and Feng Pan
Algorithms 2015, 8(3), 656-668; https://doi.org/10.3390/a8030656 - 20 Aug 2015
Cited by 2 | Viewed by 5397
Abstract
A three-step iterative method with fifth-order convergence as a new modification of Newton’s method was presented. This method is for finding multiple roots of nonlinear equation with unknown multiplicity m whose multiplicity m is the highest multiplicity. Its order of convergence is analyzed [...] Read more.
A three-step iterative method with fifth-order convergence as a new modification of Newton’s method was presented. This method is for finding multiple roots of nonlinear equation with unknown multiplicity m whose multiplicity m is the highest multiplicity. Its order of convergence is analyzed and proved. Results for some numerical examples show the efficiency of the new method. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
236 KiB  
Article
Local Convergence of an Optimal Eighth Order Method under Weak Conditions
by Ioannis K. Argyros, Ramandeep Behl and S.S. Motsa
Algorithms 2015, 8(3), 645-655; https://doi.org/10.3390/a8030645 - 19 Aug 2015
Cited by 5 | Viewed by 4712
Abstract
We study the local convergence of an eighth order Newton-like method to approximate a locally-unique solution of a nonlinear equation. Earlier studies, such as Chen et al. (2015) show convergence under hypotheses on the seventh derivative or even higher, although only the first [...] Read more.
We study the local convergence of an eighth order Newton-like method to approximate a locally-unique solution of a nonlinear equation. Earlier studies, such as Chen et al. (2015) show convergence under hypotheses on the seventh derivative or even higher, although only the first derivative and the divided difference appear in these methods. The convergence in this study is shown under hypotheses only on the first derivative. Hence, the applicability of the method is expanded. Finally, numerical examples are also provided to show that our results apply to solve equations in cases where earlier studies cannot apply. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
1643 KiB  
Article
Data Fusion Modeling for an RT3102 and Dewetron System Application in Hybrid Vehicle Stability Testing
by Zhibin Miao and Hongtian Zhang
Algorithms 2015, 8(3), 632-644; https://doi.org/10.3390/a8030632 - 12 Aug 2015
Cited by 1 | Viewed by 7108
Abstract
More and more hybrid electric vehicles are driven since they offer such advantages as energy savings and better active safety performance. Hybrid vehicles have two or more power driving systems and frequently switch working condition, so controlling stability is very important. In this [...] Read more.
More and more hybrid electric vehicles are driven since they offer such advantages as energy savings and better active safety performance. Hybrid vehicles have two or more power driving systems and frequently switch working condition, so controlling stability is very important. In this work, a two-stage Kalman algorithm method is used to fuse data in hybrid vehicle stability testing. First, the RT3102 navigation system and Dewetron system are introduced. Second, a modeling of data fusion is proposed based on the Kalman filter. Then, this modeling is simulated and tested on a sample vehicle, using Carsim and Simulink software to test the results. The results showed the merits of this modeling. Full article
(This article belongs to the Special Issue Machine Learning Algorithms for Big Data)
►▼ Show Figures

Figure 1

Figure 1
<p>RT3102 navigation system.</p> Full article ">Figure 2
<p>Schematic of the real time RT internal components.</p> Full article ">Figure 3
<p>Schematic of the strapdown navigator.</p> Full article ">Figure 4
<p>Graphical interface of the Dewetron testing system.</p> Full article ">Figure 5
<p>Connections for the Dewetron testing system.</p> Full article ">Figure 6
<p>Sideslip angle combination algorithm block.</p> Full article ">Figure 7
<p>Simulink diagram.</p> Full article ">Figure 8
<p>Testing course.</p> Full article ">Figure 9
<p>Testing car and system.</p> Full article ">Figure 10
<p>Measurement of the hybrid electric vehicle with RT3012.</p> Full article ">Figure 11
<p>Sideslip angle curve.</p> Full article ">Figure 12
<p>Sideslip angle curve.</p> Full article ">Figure 13
<p>Comparison of the sideslip angle curves.</p> Full article ">
333 KiB  
Article
One-Bit Quantization and Distributed Detection with an Unknown Scale Parameter
by Fei Gao, Lili Guo, Hongbin Li and Jun Fang
Algorithms 2015, 8(3), 621-631; https://doi.org/10.3390/a8030621 - 11 Aug 2015
Cited by 6 | Viewed by 5076
Abstract
We examine a distributed detection problem in a wireless sensor network, where sensor nodes collaborate to detect a Gaussian signal with an unknown change of power, i.e., a scale parameter. Due to power/bandwidth constraints, we consider the case where each sensor quantizes its [...] Read more.
We examine a distributed detection problem in a wireless sensor network, where sensor nodes collaborate to detect a Gaussian signal with an unknown change of power, i.e., a scale parameter. Due to power/bandwidth constraints, we consider the case where each sensor quantizes its observation into a binary digit. The binary data are then transmitted through error-prone wireless links to a fusion center, where a generalized likelihood ratio test (GLRT) detector is employed to perform a global decision. We study the design of a binary quantizer based on an asymptotic analysis of the GLRT. Interestingly, the quantization threshold of the quantizer is independent of the unknown scale parameter. Numerical results are included to illustrate the performance of the proposed quantizer and GLRT in binary symmetric channels (BSCs). Full article
(This article belongs to the Special Issue Algorithms for Sensor Networks)
►▼ Show Figures

Figure 1

Figure 1
<p>Non-centrality <span class="html-italic">λ</span> of the proposed quantization scheme over perfect and binary symmetric channels (BSCs) <span class="html-italic">versus</span> the normalized threshold <math display="inline"> <mfrac> <msub> <mi>τ</mi> <mi>n</mi> </msub> <msub> <mi>σ</mi> <mn>0</mn> </msub> </mfrac> </math>, when the number of sensors <math display="inline"> <mrow> <mi>N</mi> <mo>=</mo> <mn>100</mn> </mrow> </math>.</p> Full article ">Figure 2
<p>Performance the proposed one-bit generalized likelihood ratio test (GLRT) detector with the optimum threshold <math display="inline"> <msup> <mi>τ</mi> <mo>★</mo> </msup> </math> and the unquantized detector, when <span class="html-italic">P<sub>F A</sub></span> = 0.1 (<b>a</b>) and <math display="inline"> <mrow> <mn>0</mn> <mo>.</mo> <mn>01</mn> </mrow> </math> (<b>b</b>).</p> Full article ">Figure 3
<p>Performance the proposed one-bit GLRT detector with several choices of the threshold <span class="html-italic">τ</span> and the unquantized detector, when <math display="inline"> <mrow> <msub> <mi>P</mi> <mrow> <mi>F</mi> <mi>A</mi> </mrow> </msub> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>1</mn> </mrow> </math>.</p> Full article ">Figure 4
<p>ROC curves of the proposed one-bit GLRT in BSC channels, when <math display="inline"> <mrow> <mi>N</mi> <mo>=</mo> <mn>5</mn> </mrow> </math>.</p> Full article ">Figure 5
<p>Performance of the proposed one-bit GLRT with several estimated values <math display="inline"> <mover accent="true"> <mi>p</mi> <mo>^</mo> </mover> </math> of the crossover probability <math display="inline"> <mrow> <mover accent="true"> <mi>p</mi> <mo>˜</mo> </mover> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>2</mn> </mrow> </math>.</p> Full article ">
448 KiB  
Review
An Overview of a Class of Clock Synchronization Algorithms for Wireless Sensor Networks: A Statistical Signal Processing Perspective
by Xu Wang, Daniel Jeske and Erchin Serpedin
Algorithms 2015, 8(3), 590-620; https://doi.org/10.3390/a8030590 - 6 Aug 2015
Cited by 15 | Viewed by 6473
Abstract
Recently, wireless sensor networks (WSNs) have drawn great interest due to their outstanding monitoring and management potential in medical, environmental and industrial applications. Most of the applications that employ WSNs demand all of the sensor nodes to run on a common time scale, [...] Read more.
Recently, wireless sensor networks (WSNs) have drawn great interest due to their outstanding monitoring and management potential in medical, environmental and industrial applications. Most of the applications that employ WSNs demand all of the sensor nodes to run on a common time scale, a requirement that highlights the importance of clock synchronization. The clock synchronization problem in WSNs is inherently related to parameter estimation. The accuracy of clock synchronization algorithms depends essentially on the statistical properties of the parameter estimation algorithms. Recently, studies dedicated to the estimation of synchronization parameters, such as clock offset and skew, have begun to emerge in the literature. The aim of this article is to provide an overview of the state-of-the-art clock synchronization algorithms for WSNs from a statistical signal processing point of view. This article focuses on describing the key features of the class of clock synchronization algorithms that exploit the traditional two-way message (signal) exchange mechanism. Upon introducing the two-way message exchange mechanism, the main clock offset estimation algorithms for pairwise synchronization of sensor nodes are first reviewed, and their performance is compared. The class of fully-distributed clock offset estimation algorithms for network-wide synchronization is then surveyed. The paper concludes with a list of open research problems pertaining to clock synchronization of WSNs. Full article
(This article belongs to the Special Issue Algorithms for Sensor Networks)
►▼ Show Figures

Figure 1

Figure 1
<p>Network topology for different synchronization approaches.</p> Full article ">Figure 2
<p>Clocks of sensor nodes.</p> Full article ">Figure 3
<p>Two-way message exchange mechanism (with skew).</p> Full article ">Figure 4
<p>Two-way message exchange between nodes <span class="html-italic">i</span> and <span class="html-italic">j</span>.</p> Full article ">Figure 5
<p>The factor graph of nodes <span class="html-italic">i</span> and <span class="html-italic">j</span>.</p> Full article ">
359 KiB  
Article
Robust Rank Reduction Algorithm with Iterative Parameter Optimization and Vector Perturbation
by Peng Li, Jiao Feng and Rodrigo C. De Lamare
Algorithms 2015, 8(3), 573-589; https://doi.org/10.3390/a8030573 - 5 Aug 2015
Cited by 2 | Viewed by 4911
Abstract
In dynamic propagation environments, beamforming algorithms may suffer from strong interference, steering vector mismatches, a low convergence speed and a high computational complexity. Reduced-rank signal processing techniques provide a way to address the problems mentioned above. This paper presents a low-complexity robust data-dependent [...] Read more.
In dynamic propagation environments, beamforming algorithms may suffer from strong interference, steering vector mismatches, a low convergence speed and a high computational complexity. Reduced-rank signal processing techniques provide a way to address the problems mentioned above. This paper presents a low-complexity robust data-dependent dimensionality reduction based on an iterative optimization with steering vector perturbation (IOVP) algorithm for reduced-rank beamforming and steering vector estimation. The proposed robust optimization procedure jointly adjusts the parameters of a rank reduction matrix and an adaptive beamformer. The optimized rank reduction matrix projects the received signal vector onto a subspace with lower dimension. The beamformer/steering vector optimization is then performed in a reduced dimension subspace. We devise efficient stochastic gradient and recursive least-squares algorithms for implementing the proposed robust IOVP design. The proposed robust IOVP beamforming algorithms result in a faster convergence speed and an improved performance. Simulation results show that the proposed IOVP algorithms outperform some existing full-rank and reduced-rank algorithms with a comparable complexity. Full article
(This article belongs to the Special Issue Algorithms for Sensor Networks)
►▼ Show Figures

Figure 1

Figure 1
<p>Schematic of the proposed reduced-rank scheme.</p> Full article ">Figure 2
<p>Signal-to-interference plus noise ratio (SINR) performance <span class="html-italic">vs</span>. the number of snapshots, with steering vector mismatch due to 2°DoA mismatch. The spherical uncertainty set is assumed for robust beamformers <math display="inline"> <mrow> <mi>ϵ</mi> <mspace width="3.33333pt"/> <mo>=</mo> <mspace width="3.33333pt"/> <mn>140</mn> </mrow> </math> (RLS indicates that the value <math display="inline"> <mover accent="true"> <mi>R</mi> <mo>˰</mo> </mover> <msup> <mrow/> <mrow> <mo>−</mo> <mn>1</mn> </mrow> </msup> </math> is obtained by using RLS adaptation), non-orthogonal <math display="inline"> <mrow> <msub> <mi>S</mi> <mi>D</mi> </msub> <mrow> <mo>[</mo> <mi>i</mi> <mo>]</mo> </mrow> <mo>∈</mo> <msup> <mi mathvariant="double-struck">C</mi> <mrow> <mn>64</mn> <mo>×</mo> <mn>2</mn> </mrow> </msup> </mrow> </math> projection matrix.</p> Full article ">Figure 3
<p>SINR performance against the number of snapshots without steering vector mismatch.</p> Full article ">Figure 4
<p>SINR performance against the number of snapshots with steering vector mismatch due to 2°DoA mismatch. The spherical uncertainty set is assumed for robust beamformers with <math display="inline"> <mrow> <mi>ϵ</mi> <mo>=</mo> <mn>800</mn> </mrow> </math>, non-orthogonal <math display="inline"> <mrow> <msub> <mi>S</mi> <mi>D</mi> </msub> <mrow> <mo>[</mo> <mi>i</mi> <mo>]</mo> </mrow> <mo>∈</mo> <msup> <mi mathvariant="double-struck">C</mi> <mrow> <mn>320</mn> <mo>×</mo> <mn>2</mn> </mrow> </msup> </mrow> </math> rank reduction matrix.</p> Full article ">
1111 KiB  
Article
Modeling Documents with Event Model
by Longhui Wang, Guoguang Zhao and Donghong Sun
Algorithms 2015, 8(3), 562-572; https://doi.org/10.3390/a8030562 - 4 Aug 2015
Cited by 1 | Viewed by 5455
Abstract
Currently deep learning has made great breakthroughs in visual and speech processing, mainly because it draws lessons from the hierarchical mode that brain deals with images and speech. In the field of NLP, a topic model is one of the important ways for [...] Read more.
Currently deep learning has made great breakthroughs in visual and speech processing, mainly because it draws lessons from the hierarchical mode that brain deals with images and speech. In the field of NLP, a topic model is one of the important ways for modeling documents. Topic models are built on a generative model that clearly does not match the way humans write. In this paper, we propose Event Model, which is unsupervised and based on the language processing mechanism of neurolinguistics, to model documents. In Event Model, documents are descriptions of concrete or abstract events seen, heard, or sensed by people and words are objects in the events. Event Model has two stages: word learning and dimensionality reduction. Word learning is to learn semantics of words based on deep learning. Dimensionality reduction is the process that representing a document as a low dimensional vector by a linear mode that is completely different from topic models. Event Model achieves state-of-the-art results on document retrieval tasks. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>A language processing in neurolinguistics. This picture marks various processing stages of written and spoken word retelling tasks. The cortical regions associated with above tasks and observed by PET imaging are shown under every stage. When people recognize words by sight or hearing, next there are two processing approaches. One is directly outputting. In addition to the written word and the spoken word, the brain can transform the input signals from vision, audition, <span class="html-italic">et al.</span> to words directly. This is the “WYSIWYG” way. Another approach is to use semantic association to find semantically similar words in the brain first and output.</p> Full article ">Figure 2
<p>Vector space. For Event Model, we do not deny the existence of topics, but they are only some specific words, such as science, computer and sport in the figure. People perceive topics by semantic association. We use a same way to deal with topics and other words.</p> Full article ">Figure 3
<p>Scenes and objects.</p> Full article ">Figure 4
<p>Similar scenes. In the word learning stage, we have already got the semantics of words based on deep learning. The dimensionality reducing mode of topic model is representing a document as an approximate posterior over the latent topics. Event Model uses the semantic similarities to reduce dimensionality.</p> Full article ">Figure 5
<p>The dimensionality reducing process of Event Model.</p> Full article ">Figure 6
<p><b>Left:</b> The Relationship of <span class="html-italic">V</span> and <span class="html-italic">v</span> is linear. <span class="html-italic">V</span>(1) = <span class="html-italic">v</span>(1) + <span class="html-italic">v</span>(2), <span class="html-italic">etc.</span> <b>Right:</b> For WC-LDA, The Relationship of <span class="html-italic">v</span> and <span class="html-italic">h</span> is nonlinear, as shown in Equations 9–12.</p> Full article ">Figure 7
<p>The fraction of retrieved documents in the same class as the query when a query document from the test set is used to retrieve other test set documents. Results are averaged over all 7531 (for 20-newsgroups) and 4948(for Fudan corpus) possible queries. The Event Model performs significantly better than LDA no matter on short documents or long documents, particularly when retrieving the top few documents on 20-newsgroups, up to 25%.</p> Full article ">Figure 8
<p>The effect of parameter <span class="html-italic">N</span> on retrieval performance for Event Model. <span class="html-italic">N</span> can be changed in very large ranges (400 to 1000 for 20-newsgroups and 800 to 1400 for Fudan Corpus), which means that the degree of semantic relatedness between words in the same word class has small influence on retrieval results.</p> Full article ">Figure 9
<p>The document retrieving results of EM, WC-LDA and WC-RBM. Dimensionalities of 20-newsgroups and Fudan Corpus are reduced from 600D and 1000D to 128D and 256D. The results of EM remain stable. Although the results of WC-LDA are higher than LDA (up to 4.8% for 20-newsgroups and 2% for Fudan Corpus), they are still far away from EM. For WC-RBM, results on 20-newsgroups are not satisfactory, which may be due to the features of short documents are sparse, while on Fudan Corpus, results are a little worse than WC-LDA.</p> Full article ">
203 KiB  
Article
Some Improvements to a Third Order Variant of Newton’s Method from Simpson’s Rule
by Diyashvir Kreetee Rajiv Babajee
Algorithms 2015, 8(3), 552-561; https://doi.org/10.3390/a8030552 - 29 Jul 2015
Cited by 2 | Viewed by 5050
Abstract
In this paper, we present three improvements to a three-point third order variant of Newton’s method derived from the Simpson rule. The first one is a fifth order method using the same number of functional evaluations as the third order method, the second [...] Read more.
In this paper, we present three improvements to a three-point third order variant of Newton’s method derived from the Simpson rule. The first one is a fifth order method using the same number of functional evaluations as the third order method, the second one is a four-point 10th order method and the last one is a five-point 20th order method. In terms of computational point of view, our methods require four evaluations (one function and three first derivatives) to get fifth order, five evaluations (two functions and three derivatives) to get 10th order and six evaluations (three functions and three derivatives) to get 20th order. Hence, these methods have efficiency indexes of 1.495, 1.585 and 1.648, respectively which are better than the efficiency index of 1.316 of the third order method. We test the methods through some numerical experiments which show that the 20th order method is very efficient. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
590 KiB  
Article
Target Detection Algorithm Based on Two Layers Human Visual System
by Zheng Cui, Jingli Yang, Shouda Jiang and Changan Wei
Algorithms 2015, 8(3), 541-551; https://doi.org/10.3390/a8030541 - 29 Jul 2015
Cited by 12 | Viewed by 5041
Abstract
Robust small target detection of low signal-to-noise ratio (SNR) is very important in infrared search and track applications for self-defense or attacks. Due to the complex background, current algorithms have some unsolved issues with false alarm rate. In order to reduce the false [...] Read more.
Robust small target detection of low signal-to-noise ratio (SNR) is very important in infrared search and track applications for self-defense or attacks. Due to the complex background, current algorithms have some unsolved issues with false alarm rate. In order to reduce the false alarm rate, an infrared small target detection algorithm based on saliency detection and support vector machine was proposed. Firstly, we detect salient regions that may contain targets with phase spectrum Fourier transform (PFT) approach. Then, target recognition was performed in the salient regions. Experimental results show the proposed algorithm has ideal robustness and efficiency for real infrared small target detection applications. Full article
(This article belongs to the Special Issue Machine Learning Algorithms for Big Data)
►▼ Show Figures

Figure 1

Figure 1
<p>The proposed framework inspired by human visual system (HVS).</p> Full article ">Figure 2
<p>One of the real infrared (IR) images for experiment.</p> Full article ">Figure 3
<p>Figures of phase spectrum Fourier transform (PFT). (<b>a</b>) saliency map of PFT method; (<b>b</b>) result of threshold operation; (<b>c</b>) final result marked by blue block.</p> Full article ">Figure 4
<p>Figures of top-hat. (<b>a</b>) saliency map of top-hat method; (<b>b</b>) result of threshold operation; (<b>c</b>) final result marked by blue block.</p> Full article ">Figure 5
<p>Figures of two-dimensional least mean square (TDLMS). (<b>a</b>) saliency map of TDLMS method; (<b>b</b>) result of threshold operation; (<b>c</b>) final result marked by blue block.</p> Full article ">Figure 6
<p>Figures of hypercomplex Fourier transform (HFT). (<b>a</b>) saliency map of HFT method; (<b>b</b>) result of threshold operation; (<b>c</b>) final result marked by blue block.</p> Full article ">Figure 7
<p>The contrast of one layer method and two layers method. (<b>a</b>) Result of one layer method. (<b>b</b>) Result of two layers method.</p> Full article ">Figure 8
<p>True positive rate (TPR) of all methods.</p> Full article ">Figure 9
<p>False positive rate (FPR) of all methods.</p> Full article ">Figure 10
<p>Time of all methods.</p> Full article ">
320 KiB  
Article
A Parallel Search Strategy Based on Sparse Representation for Infrared Target Tracking
by Zhen Shi, Chang'an Wei, Ping Fu and Shouda Jiang
Algorithms 2015, 8(3), 529-540; https://doi.org/10.3390/a8030529 - 27 Jul 2015
Cited by 4 | Viewed by 4922
Abstract
A parallel search strategy based on sparse representation (PS-L1 tracker) is proposed in the particle filter framework. To obtain the weights of state particles, target templates are represented linearly with the dictionary of target candidates. Sparse constraints on the coefficient guarantee that only [...] Read more.
A parallel search strategy based on sparse representation (PS-L1 tracker) is proposed in the particle filter framework. To obtain the weights of state particles, target templates are represented linearly with the dictionary of target candidates. Sparse constraints on the coefficient guarantee that only true target candidates can be selected, and the nonnegative entries denote the associate weights of efficient target states. Then the optimal target state can be estimated by the linear combination of above weighted states. In this way, efficient target states are selected simultaneously from all the particles, which we call a parallel search strategy. Experimental results demonstrate excellent performance of the proposed method on challenging infrared images. Full article
(This article belongs to the Special Issue Machine Learning Algorithms for Big Data)
►▼ Show Figures

Figure 1

Figure 1
<p>Tracking results of three trackers for sequence LW-16-08.</p> Full article ">Figure 2
<p>Tracking results of three trackers for sequence LW-17-20.</p> Full article ">Figure 3
<p>Tracking results of three trackers for sequence LW-19-NS.</p> Full article ">Figure 4
<p>Tracking results of three trackers for sequence LW-18-15.</p> Full article ">Figure 5
<p>Quantitative comparison of three trackers in terms of position errors (in pixel). (<b>a</b>) LW-16-08; (<b>b</b>) LW-17-20; (<b>c</b>) LW-19-NS; (<b>d</b>) LW-18-15.</p> Full article ">Figure 6
<p>Quantitative comparison of three trackers in terms of F-score. (<b>a</b>) LW-16-08; (<b>b</b>) LW-17-20; (<b>c</b>) LW-19-NS; (<b>d</b>) LW-18-15.</p> Full article ">
579 KiB  
Article
On the Accessibility of Newton’s Method under a Hölder Condition on the First Derivative
by José Antonio Ezquerro and Miguel Ángel Hernández-Verón
Algorithms 2015, 8(3), 514-528; https://doi.org/10.3390/a8030514 - 23 Jul 2015
Cited by 2 | Viewed by 5090
Abstract
We see how we can improve the accessibility of Newton’s method for approximating a solution of a nonlinear equation in Banach spaces when a center Hölder condition on the first derivative is used to prove its semi-local convergence. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
►▼ Show Figures

Figure 1

Figure 1
<p>Domains of parameters of Newton’s method associated with Theorem 1 (blue region) and Corollary 4 (orange for <math display="inline"> <mrow> <mi>ε</mi> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>1</mn> </mrow> </math>, green for <math display="inline"> <mrow> <mi>ε</mi> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>2</mn> </mrow> </math>, red for <math display="inline"> <mrow> <mi>ε</mi> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>4</mn> </mrow> </math> and yellow for <math display="inline"> <mrow> <mi>ε</mi> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>8</mn> </mrow> </math>) for <math display="inline"> <mrow> <mi>p</mi> <mo>=</mo> <mfrac> <mn>1</mn> <mn>10</mn> </mfrac> <mo>,</mo> <mfrac> <mn>1</mn> <mn>5</mn> </mfrac> <mo>,</mo> <mfrac> <mn>2</mn> <mn>5</mn> </mfrac> <mo>,</mo> <mfrac> <mn>4</mn> <mn>5</mn> </mfrac> </mrow> </math>.</p> Full article ">Figure 2
<p>Domains of parameters of Newton’s method associated with Corollary 4 (magenta region) and Theorem 1 (gray region) for <math display="inline"> <mrow> <mi>p</mi> <mo>=</mo> <mfrac> <mn>1</mn> <mn>10</mn> </mfrac> <mo>,</mo> <mfrac> <mn>1</mn> <mn>5</mn> </mfrac> <mo>,</mo> <mfrac> <mn>2</mn> <mn>5</mn> </mfrac> <mo>,</mo> <mfrac> <mn>4</mn> <mn>5</mn> </mfrac> </mrow> </math>.</p> Full article ">Figure 3
<p>Approximated solution of Problems (<a href="#FD21-algorithms-08-00514" class="html-disp-formula">21</a>)–(<a href="#FD22-algorithms-08-00514" class="html-disp-formula">22</a>).</p> Full article ">
412 KiB  
Article
Multi-Feedback Interference Cancellation Algorithms for OFDM Systems over Doubly-Selective Channels
by Peng Li, Min Chen, Li (Alex) Li and Jiao Feng
Algorithms 2015, 8(3), 484-513; https://doi.org/10.3390/a8030484 - 14 Jul 2015
Cited by 3 | Viewed by 5732
Abstract
Orthogonal frequency-division multiplexing (OFDM) systems over rapidly time varying channels may suffer from significant inter-carrier interference (ICI), which destroys the orthogonality between subcarriers and degrades the detection performance. Without sufficient ICI suppression, OFDM systems usually experience an error floor. According to the approximate [...] Read more.
Orthogonal frequency-division multiplexing (OFDM) systems over rapidly time varying channels may suffer from significant inter-carrier interference (ICI), which destroys the orthogonality between subcarriers and degrades the detection performance. Without sufficient ICI suppression, OFDM systems usually experience an error floor. According to the approximate matched filter bound (AMFB), the error floor in a coded OFDM system is not irreducible. In this work, we introduce novel multiple feedback matched filter (MBMF)-based ICI cancellation receivers. Based on the output of a novel MBMF scheme, the approach employs a multiple ICI cancellation strategy with or without signal-to-interference-plus-noise-ratio (SINR) ordering. The developed schemes can significantly improve the performance and remove the error floor with a negligible complexity increase. Given the multiple cancellation approach, we compare the SINR performance of the MBMF outputs with that employing single feedback and show that the SINR performance with multiple cancellation candidates is improved over that with a single one at practical SNR values. Additionally, for time-varying channels, we exploit partial fast Fourier transform (PFFT) by splitting one OFDM symbol into multiple segments; the channel state is separately estimated by least-squares (LS) methods without inserting more pilots. Simulation results demonstrate the superiority of the proposed methods over serial and block equalizers and the robustness to the Doppler effects compared to conventional single-segment method. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>System model of multiple feedback matched filter (MBMF)-successive interference cancellation (SIC) incorporating multi-segment channel estimation (MSCE).</p> Full article ">Figure 2
<p>The matrix representations of the banded channel matrix <math display="inline"> <msub> <mi mathvariant="bold">H</mi> <mi>D</mi> </msub> </math>, the <span class="html-italic">k</span>-th truncated channel matrix <math display="inline"> <msub> <mi mathvariant="bold">H</mi> <mi>k</mi> </msub> </math> and the reduced channel matrix in the blue square.</p> Full article ">Figure 3
<p>Pre-processing and post-processing signal-to-interference-plus-noise-ratio (SINR) comparison for the <span class="html-italic">b</span>-th feedback with different <span class="html-italic">Q</span>. <math display="inline"> <mrow> <msub> <mi>N</mi> <mi>s</mi> </msub> <mo>=</mo> <mn>128</mn> <mo>,</mo> <msub> <mi>f</mi> <mi>d</mi> </msub> <msub> <mi>T</mi> <mi>OFDM</mi> </msub> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>65</mn> </mrow> </math>.</p> Full article ">Figure 4
<p>The uncoded bit error rate analysis of the system with the presence of the residual inter-carrier interference (ICI) outside the band (Q = 2,4,6). <span class="html-italic">N<sub>s</sub></span> =128, <span class="html-italic">f<sub>d</sub>T<sub>OFDM</sub></span> = 0.65, <math display="inline"> <mrow> <mi>L</mi> <mo>=</mo> <mspace width="3.33333pt"/> <mn>8</mn> </mrow> </math>.</p> Full article ">Figure 5
<p>BER performance against SNR (dB) of MF-PIC, GSG-based MBMF-SIC, ordering GSG-based MBMF (OGMBMF)-SIC, TSG-based MBMF (TMBMF)-SIC, ordering TMBMF (OTMBMF)-SIC, MF-SIC, banded MMSE-SIC and approximate matched filter bound (AMFB) in the fourth iteration with <math display="inline"> <mrow> <msub> <mi>f</mi> <mi>d</mi> </msub> <msub> <mi>T</mi> <mi>OFDM</mi> </msub> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>65</mn> </mrow> </math>.</p> Full article ">Figure 6
<p>BER performance against <math display="inline"> <mrow> <msub> <mi>f</mi> <mi>d</mi> </msub> <msub> <mi>T</mi> <mi>OFDM</mi> </msub> </mrow> </math> of MF-PIC, OGMBMF-SIC, OTMBMF-SIC, MF-SIC and banded MMSE-SIC in the fourth iteration at SNR =12 dB.</p> Full article ">Figure 7
<p>BER performance against SNR (dB) of MF-PIC, GMBMF-SIC, OGMBMF-SIC, MF-SIC, banded MMSE-SIC and AMFB using MSCE in the fourth iteration with <span class="html-italic">f<sub>d</sub>T</span><sub>OFDM</sub> = 0.65.</p> Full article ">Figure 8
<p>BER performance against <math display="inline"> <mrow> <msub> <mi>f</mi> <mi>d</mi> </msub> <msub> <mi>T</mi> <mi>OFDM</mi> </msub> </mrow> </math> of OGMBMF-SIC and MF-PIC using MSCE and single-burst channel estimation (SBCE) in the fourth iteration at SNR =16 dB.</p> Full article ">Figure 9
<p>BER performance against the number of multi-feedback candidates <span class="html-italic">B</span> with <math display="inline"> <mrow> <msub> <mi>f</mi> <mi>d</mi> </msub> <msub> <mi>T</mi> <mi>OFDM</mi> </msub> <mo>=</mo> <mn>0</mn> <mo>.</mo> <mn>65</mn> </mrow> </math> at SNR =12 dB.</p> Full article ">
1368 KiB  
Review
Conditional Random Fields for Pattern Recognition Applied to Structured Data
by Tom Burr and Alexei Skurikhin
Algorithms 2015, 8(3), 466-483; https://doi.org/10.3390/a8030466 - 14 Jul 2015
Cited by 3 | Viewed by 5428
Abstract
Pattern recognition uses measurements from an input domain, X, to predict their labels from an output domain, Y. Image analysis is one setting where one might want to infer whether a pixel patch contains an object that is “manmade” (such as [...] Read more.
Pattern recognition uses measurements from an input domain, X, to predict their labels from an output domain, Y. Image analysis is one setting where one might want to infer whether a pixel patch contains an object that is “manmade” (such as a building) or “natural” (such as a tree). Suppose the label for a pixel patch is “manmade”; if the label for a nearby pixel patch is then more likely to be “manmade” there is structure in the output domain that can be exploited to improve pattern recognition performance. Modeling P(X) is difficult because features between parts of the model are often correlated. Therefore, conditional random fields (CRFs) model structured data using the conditional distribution P(Y|X = x), without specifying a model for P(X), and are well suited for applications with dependent features. This paper has two parts. First, we overview CRFs and their application to pattern recognition in structured problems. Our primary examples are image analysis applications in which there is dependence among samples (pixel patches) in the output domain. Second, we identify research topics and present numerical examples. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Example of man-made objects in a natural scene. Pixel patches (16 × 16 pixels) containing man-made structures are outlined. (<b>a</b>) MRF result; (<b>b</b>) CRF result.</p> Full article ">Figure 2
<p>Illustration of reference labeling and corresponding feature values. The image is 16 × 24 elements, where each element represents a 16 × 16 pixel patch in the original image of 256 × 384 pixels from [<a href="#B8-algorithms-08-00466" class="html-bibr">8</a>]. (<b>a</b>) The <span class="html-italic">Y</span> labels (0 = red for natural, 1 = white for manmade); (<b>b</b>) The corresponding <span class="html-italic">X</span> values represented using a scalar (projection of <span class="html-italic">X</span> onto the first eigenvector of the covariance matrix of <span class="html-italic">X</span>; <span class="html-italic">i.e.</span>, the first principle component scores; see <a href="#sec3-algorithms-08-00466" class="html-sec">Section 3</a>). (<b>a</b>) <span class="html-italic">Y</span> values by pixel: Red is “natural” (0) White is “manmade” (1); (<b>b</b>) Scalar representation of <span class="html-italic">X</span> values at the same pixels as in plot (<b>a</b>).</p> Full article ">Figure 3
<p>Illustration of a 5 × 7 grid-like CRF graph (<b>a</b>) and corresponding two randomly generated spanning trees (<b>b</b>,<b>c</b>). In CRF setup in computer vision, the observation variable <math display="inline"> <semantics> <mrow> <msub> <mi>X</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> </semantics> </math> could be the average color of the pixel patch, and the random variable <math display="inline"> <semantics> <mrow> <msub> <mi>Y</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> </semantics> </math> is a classification label of the pixel patch. For clarity we show only one pair of <math display="inline"> <semantics> <mrow> <msub> <mi>X</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mrow> </semantics> </math> and <math display="inline"> <semantics> <mrow> <msub> <mi>Y</mi> <mrow> <mtext>ij</mtext> </mrow> </msub> </mrow> </semantics> </math>.</p> Full article ">Figure 4
<p>Example results for structure detection task. True positives are brightened and outlined with white boundaries.</p> Full article ">Figure 5
<p>Results of binary denoising task. Column (<b>1</b>) reference images; (<b>2</b>) images corrupted with bimodal noise; (<b>3</b>) logistic classifier results; (<b>4</b>) results of the grid structured CRF model with loopy belief propagation inference; (<b>5</b>) result using one spanning tree; (<b>6</b>) CRF spanning trees cascade results.</p> Full article ">
539 KiB  
Article
Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves
by Ian Parberry
Algorithms 2015, 8(3), 459-465; https://doi.org/10.3390/a8030459 - 10 Jul 2015
Cited by 11 | Viewed by 7507
Abstract
It is shown that the greedy algorithm for the \((n^2-1)\)-puzzle makes \(\tfrac{8}{3}n^3 +O(n^2)\) expected moves. This analysis is verified experimentally on 10,000 random instances each of the \((n^2-1)\)-puzzle for \(4 \leq n \leq 200\). Full article
►▼ Show Figures

Figure 1

Figure 1
<p>The solved 15-puzzle (<b>left</b>), and a random configuration (<b>right</b>).</p> Full article ">Figure 2
<p>Number of moves required to move the blank to each position from the first half of the first row of the 63-puzzle.</p> Full article ">Figure 3
<p>Number of moves required to move a tile from each position to the first half of the first row of the 63-puzzle.</p> Full article ">Figure 4
<p>Decomposing the leftmost entry of <a href="#algorithms-08-00459-f003" class="html-fig">Figure 3</a> to show the structure of Equation (<a href="#FD5-algorithms-08-00459" class="html-disp-formula">5</a>).</p> Full article ">Figure 5
<p>The average number of moves required to solve 10,000 random instances of the <math display="inline"> <mrow> <mo>(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>−</mo> <mn>1</mn> <mo>)</mo> </mrow> </math>-puzzle for <math display="inline"> <mrow> <mn>4</mn> <mo>≤</mo> <mi>n</mi> <mo>≤</mo> <mn>200</mn> </mrow> </math>.</p> Full article ">Figure 6
<p>The average number of moves required to solve 10,000 random instances of the <math display="inline"> <mrow> <mo>(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>−</mo> <mn>1</mn> <mo>)</mo> </mrow> </math>-puzzle divided by <math display="inline"> <msup> <mi>n</mi> <mn>3</mn> </msup> </math> for <math display="inline"> <mrow> <mn>4</mn> <mo>≤</mo> <mi>n</mi> <mo>≤</mo> <mn>200</mn> </mrow> </math>.</p> Full article ">
861 KiB  
Article
A Benchmarking Algorithm to Determine Minimum Aggregation Delay for Data Gathering Trees and an Analysis of the Diameter-Aggregation Delay Tradeoff
by Natarajan Meghanathan
Algorithms 2015, 8(3), 435-458; https://doi.org/10.3390/a8030435 - 10 Jul 2015
Cited by 7 | Viewed by 6635
Abstract
Aggregation delay is the minimum number of time slots required to aggregate data along the edges of a data gathering tree (DG tree) spanning all the nodes in a wireless sensor network (WSN). We propose a benchmarking algorithm to determine the minimum possible [...] Read more.
Aggregation delay is the minimum number of time slots required to aggregate data along the edges of a data gathering tree (DG tree) spanning all the nodes in a wireless sensor network (WSN). We propose a benchmarking algorithm to determine the minimum possible aggregation delay for DG trees in a WSN. We assume the availability of a sufficient number of unique CDMA (Code Division Multiple Access) codes for the intermediate nodes to simultaneously aggregate data from their child nodes if the latter are ready with the data. An intermediate node has to still schedule non-overlapping time slots to sequentially aggregate data from its own child nodes (one time slot per child node). We show that the minimum aggregation delay for a DG tree depends on the underlying design choices (bottleneck node-weight based or bottleneck link-weight based) behind its construction. We observe the bottleneck node-weight based DG trees incur a smaller diameter and a larger number of child nodes per intermediate node; whereas, the bottleneck link-weight based DG trees incur a larger diameter and a much lower number of child nodes per intermediate node. As a result, we observe a complex diameter-aggregation delay tradeoff for data gathering trees in WSNs. Full article
(This article belongs to the Special Issue Algorithms for Sensor Networks)
►▼ Show Figures

Graphical abstract

Graphical abstract
Full article ">Figure 1
<p>Examples to Determine the Minimum Aggregation Delay for a Data Gathering Tree.</p> Full article ">Figure 2
<p>Performance of the Max/Min Bottleneck Node Weight and Link Weight-based DG Trees.</p> Full article ">Figure 3
<p>Margin of Error Values for Minimum Aggregation Delay.</p> Full article ">
1274 KiB  
Article
Multi-Objective Design Optimization of an Over-Constrained Flexure-Based Amplifier
by Yuan Ni, Zongquan Deng, Junbao Li, Xiang Wu and Long Li
Algorithms 2015, 8(3), 424-434; https://doi.org/10.3390/a8030424 - 8 Jul 2015
Cited by 3 | Viewed by 5275
Abstract
The optimizing design for enhancement of the micro performance of manipulator based on analytical models is investigated in this paper. By utilizing the established uncanonical linear homogeneous equations, the quasi-static analytical model of the micro-manipulator is built, and the theoretical calculation results are [...] Read more.
The optimizing design for enhancement of the micro performance of manipulator based on analytical models is investigated in this paper. By utilizing the established uncanonical linear homogeneous equations, the quasi-static analytical model of the micro-manipulator is built, and the theoretical calculation results are tested by FEA simulations. To provide a theoretical basis for a micro-manipulator being used in high-precision engineering applications, this paper investigates the modal property based on the analytical model. Based on the finite element method, with multipoint constraint equations, the model is built and the results have a good match with the simulation. The following parametric influences studied show that the influences of other objectives on one objective are complicated. Consequently, the multi-objective optimization by the derived analytical models is carried out to find out the optimal solutions of the manipulator. Besides the inner relationships among these design objectives during the optimization process are discussed. Full article
(This article belongs to the Special Issue Machine Learning Algorithms for Big Data)
►▼ Show Figures

Figure 1

Figure 1
<p>A displacement mechanical amplifier (<b>a</b>) schematic of the amplifier (<b>b</b>) schematic of 1/2 model equivalent system.</p> Full article ">Figure 2
<p>The rigid body with displacement offsets for multipoint constraint equations (<b>a</b>) <span class="html-italic">i</span> and <span class="html-italic">j</span> group (<b>b</b>) <span class="html-italic">m</span> and <span class="html-italic">n</span> group.</p> Full article ">Figure 3
<p>The relationships among the design objectives with <span class="html-italic">r</span> and <span class="html-italic">t</span> (<b>a</b>) relationships among <span class="html-italic">R</span>-<span class="html-italic">K</span><sub>in</sub>-σ (<b>b</b>) relationship among <span class="html-italic">R</span>-<span class="html-italic">K</span><sub>in</sub>-<span class="html-italic">f</span>.</p> Full article ">Figure 4
<p>The relationships among the design objectives with <span class="html-italic">l<sub>x</sub></span> and <span class="html-italic">l<sub>y</sub></span> (<b>a</b>) relationships among <span class="html-italic">R</span>-<span class="html-italic">K</span><sub>in</sub>-σ (<b>b</b>) relationship among <span class="html-italic">R</span>-<span class="html-italic">K</span><sub>in</sub>-<span class="html-italic">f</span>.</p> Full article ">Figure 5
<p>The game relationship among different design objectives (<b>a</b>) the ratio, <span class="html-italic">R</span>, with the frequency, <span class="html-italic">f</span>, (<b>b</b>) the ratio, <span class="html-italic">R</span>, with the input stiffness, <span class="html-italic">K</span><sub>in</sub>,(<b>c</b>) the ratio, <span class="html-italic">R</span>, with the mass, <span class="html-italic">T</span>, (<b>d</b>) the frequency, <span class="html-italic">f</span>, with the input stiffness, <span class="html-italic">K</span><sub>in</sub>.</p> Full article ">
248 KiB  
Article
A Quartically Convergent Jarratt-Type Method for Nonlinear System of Equations
by Mohammad Ghorbanzadeh and Fazlollah Soleymani
Algorithms 2015, 8(3), 415-423; https://doi.org/10.3390/a8030415 - 6 Jul 2015
Cited by 5 | Viewed by 5225
Abstract
In this work, we propose a new fourth-order Jarratt-type method for solving systems of nonlinear equations. The local convergence order of the method is proven analytically. Finally, we validate our results via some numerical experiments including an application to the Chandrashekar integral equations. [...] Read more.
In this work, we propose a new fourth-order Jarratt-type method for solving systems of nonlinear equations. The local convergence order of the method is proven analytically. Finally, we validate our results via some numerical experiments including an application to the Chandrashekar integral equations. Full article
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)
741 KiB  
Article
Implementation of a Parallel Algorithm Based on a Spark Cloud Computing Platform
by Longhui Wang, Yong Wang and Yudong Xie
Algorithms 2015, 8(3), 407-414; https://doi.org/10.3390/a8030407 - 3 Jul 2015
Cited by 15 | Viewed by 9483
Abstract
Parallel algorithms, such as the ant colony algorithm, take a long time when solving large-scale problems. In this paper, the MAX-MIN Ant System algorithm (MMAS) is parallelized to solve Traveling Salesman Problem (TSP) based on a Spark cloud computing platform. We combine MMAS [...] Read more.
Parallel algorithms, such as the ant colony algorithm, take a long time when solving large-scale problems. In this paper, the MAX-MIN Ant System algorithm (MMAS) is parallelized to solve Traveling Salesman Problem (TSP) based on a Spark cloud computing platform. We combine MMAS with Spark MapReduce to execute the path building and the pheromone operation in a distributed computer cluster. To improve the precision of the solution, local optimization strategy 2-opt is adapted in MMAS. The experimental results show that Spark has a very great accelerating effect on the ant colony algorithm when the city scale of TSP or the number of ants is relatively large. Full article
(This article belongs to the Special Issue Algorithms for Managing, Querying and Processing Big Data in Cloud Environments)
►▼ Show Figures

Figure 1

Figure 1
<p>The operation process of MapReduce framework.</p> Full article ">Figure 2
<p>The working principle of Spark.</p> Full article ">Figure 3
<p>Time consumption of different number of ants.</p> Full article ">Figure 4
<p>Comparison between the speedups of Spark and Hadoop. In order to make the linear speedup to be a straight line, we let <span class="html-italic">y</span> = <span class="html-italic">log</span><sub>2</sub>(<span class="html-italic">T</span><sub>1</sub>/<span class="html-italic">T<sub>n</sub></span>). <span class="html-italic">T<sub>1</sub></span> is the running time of common program (single core).</p> Full article ">
1463 KiB  
Review
Algorithms for Computerized Fetal Heart Rate Diagnosis with Direct Reporting
by Kazuo Maeda, Yasuaki Noguchi, Masaji Utsu and Takashi Nagassawa
Algorithms 2015, 8(3), 395-406; https://doi.org/10.3390/a8030395 - 29 Jun 2015
Cited by 7 | Viewed by 6086
Abstract
Aims: Since pattern classification of fetal heart rate (FHR) was subjective and enlarged interobserver difference, objective FHR analysis was achieved with computerized FHR diagnosis. Methods: The computer algorithm was composed of an experts’ knowledge system, including FHR analysis and FHR score calculation, and [...] Read more.
Aims: Since pattern classification of fetal heart rate (FHR) was subjective and enlarged interobserver difference, objective FHR analysis was achieved with computerized FHR diagnosis. Methods: The computer algorithm was composed of an experts’ knowledge system, including FHR analysis and FHR score calculation, and also of an objective artificial neural network system with software. In addition, a FHR frequency spectrum was studied to detect ominous sinusoidal FHR and the loss of baseline variability related to fetal brain damage. The algorithms were installed in a central-computerized automatic FHR monitoring system, which gave the diagnosis rapidly and directly to the attending doctor. Results: Clinically perinatal mortality decreased significantly and no cerebral palsy developed after introduction of the centralized system. Conclusion: The automatic multichannel FHR monitoring system improved the monitoring, increased the objectivity of FHR diagnosis and promoted clinical results. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>The most upper line is a benign physiologic sinusoidal fetal heart rate (FHR), which synchronizes to the envelope of periodic fetal respiratory movements of the second and third lines recorded by actocardiogram (ACG). Since the outcome of physiologic sinusoidal FHR was favorable, it should be separated from pathologic fatal sinusoidal FHR; however, it was unable to be analyzed by CTG, while it was able as above using the ACG [<a href="#B9-algorithms-08-00395" class="html-bibr">9</a>], where FHR change was parallel to the height of fetal movement spikes. Since frequency spectrum of both sinusoidal FHR diagnosed by ACG were characteristic, pathologic sinusoidal FHR was diagnosed using the frequency spectrum in computer analysis. Outcome probability was 100% pathologic after input of the presence of pathologic sinusoidal FHR into educated neural network computer.</p> Full article ">Figure 2
<p>Quantified analysis of FHR changes for computerized experts’ knowledge system [<a href="#B3-algorithms-08-00395" class="html-bibr">3</a>]. Each deceleration was analyzed if there were multiple decelerations in 5 min, where sum of the scores of all decelerations were the FHR score in 5 min. The items of above analysis was evaluated by the evaluation score determined by the percentage of low Apgar score lower than 7, <span class="html-italic">i.e.</span>, it was four points when low Apgar appeared in 100% of that FHR change, three points if low Apgar was 70%, two points for 40% and one point for 20% (<a href="#algorithms-08-00395-t001" class="html-table">Table 1</a>). A statistician allowed the evaluation as a goodness score. The sum of evaluation scores in 5 min was the FHR score.</p> Full article ">Figure 3
<p>The algorithm to automatically define fetal behavioral states into active and resting states. Undeterminable state was intermediate fetal state [<a href="#B22-algorithms-08-00395" class="html-bibr">22</a>].</p> Full article ">Figure 4
<p>Fetal behavioral states obtained by computer analysis at four pregnancy periods using the algorithm of <a href="#algorithms-08-00395-f003" class="html-fig">Figure 3</a>. Fetal behavioral development would be complete in 37 weeks of pregnancy [<a href="#B22-algorithms-08-00395" class="html-bibr">22</a>].</p> Full article ">
898 KiB  
Article
Improving CLOPE’s Profit Value and Stability with an Optimized Agglomerative Approach
by Yefeng Li, Jiajin Le and Mei Wang
Algorithms 2015, 8(3), 380-394; https://doi.org/10.3390/a8030380 - 26 Jun 2015
Cited by 4 | Viewed by 5575
Abstract
CLOPE (Clustering with sLOPE) is a simple and fast histogram-based clustering algorithm for categorical data. However, given the same data set with the same input parameter, the clustering results by this algorithm would possibly be different if the transactions are input in a [...] Read more.
CLOPE (Clustering with sLOPE) is a simple and fast histogram-based clustering algorithm for categorical data. However, given the same data set with the same input parameter, the clustering results by this algorithm would possibly be different if the transactions are input in a different sequence. In this paper, a hierarchical clustering framework is proposed as an extension of CLOPE to generate stable and satisfactory clustering results based on an optimized agglomerative merge process. The new clustering profit is defined as the merge criteria and the cluster graph structure is proposed to optimize the merge iteration process. The experiments conducted on two datasets both demonstrate that the agglomerative approach achieves stable clustering results with a better profit value, but costs much more time due to the worse complexity. Full article
(This article belongs to the Special Issue Clustering Algorithms)
►▼ Show Figures

Figure 1

Figure 1
<p>Histograms of the two clustering.</p> Full article ">Figure 2
<p><b>(a)</b> Initial state of <span class="html-italic">G</span> with each transaction in a cluster; <b>(b)</b> clusters meeting with Global Maximum (<span class="html-italic">GM</span>) value are linked; <b>(c)</b> Linked clusters are merged; <b>(d)</b> The remaining clusters are linked; <b>(e)</b> The final result contains only one cluster.</p> Full article ">Figure 3
<p>Comparison of stability with different input sequence produced by three algorithms on the mushroom dataset.</p> Full article ">Figure 4
<p>Comparison of execution time with different repulsion produced by three algorithms on the mushroom dataset.</p> Full article ">Figure 5
<p>Comparison of purity with different repulsion produced by three algorithms on the mushroom dataset.</p> Full article ">Figure 6
<p>Comparison of cluster number with different repulsion produced by three algorithms on the mushroom dataset.</p> Full article ">Figure 7
<p>Comparison of stability with different input sequence produced by three algorithms on the splice-junction gene sequence dataset.</p> Full article ">Figure 8
<p>Comparison of execution time with different repulsion produced by three algorithms on the splice-junction gene sequence dataset.</p> Full article ">Figure 9
<p>Comparison of cluster number with different repulsion produced by three algorithms on the splice-juction gene sequence dataset.</p> Full article ">Figure 10
<p>Comparison of purity with different repulsion produced by three algorithms on the splice-juction gene sequence dataset.</p> Full article ">
283 KiB  
Article
Identification of Dual-Rate Sampled Hammerstein Systems with a Piecewise-Linear Nonlinearity Using the Key Variable Separation Technique
by Ying-Ying Wang, Xiang-Dong Wang and Dong-Qing Wang
Algorithms 2015, 8(3), 366-379; https://doi.org/10.3390/a8030366 - 24 Jun 2015
Cited by 4 | Viewed by 4733
Abstract
The identification difficulties for a dual-rate Hammerstein system lie in two aspects. First, the identification model of the system contains the products of the parameters of the nonlinear block and the linear block, and a standard least squares method cannot be directly applied [...] Read more.
The identification difficulties for a dual-rate Hammerstein system lie in two aspects. First, the identification model of the system contains the products of the parameters of the nonlinear block and the linear block, and a standard least squares method cannot be directly applied to the model; second, the traditional single-rate discrete-time Hammerstein model cannot be used as the identification model for the dual-rate sampled system. In order to solve these problems, by combining the polynomial transformation technique with the key variable separation technique, this paper converts the Hammerstein system into a dual-rate linear regression model about all parameters (linear-in-parameter model) and proposes a recursive least squares algorithm to estimate the parameters of the dual-rate system. The simulation results verify the effectiveness of the proposed algorithm. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>The dual-rate Hammerstein system.</p> Full article ">Figure 2
<p>The discrete-time Hammerstein system.</p> Full article ">Figure 3
<p>The flowchart for computing the estimates <math display="inline"> <mrow> <mover accent="true"> <mo>Θ</mo> <mo stretchy="false">^</mo> </mover> <mrow> <mo>(</mo> <mi>k</mi> <mi>q</mi> <mo>)</mo> </mrow> </mrow> </math> and <math display="inline"> <mrow> <mover accent="true"> <mi>θ</mi> <mo stretchy="false">^</mo> </mover> <mrow> <mo>(</mo> <mi>k</mi> <mi>q</mi> <mo>)</mo> </mrow> </mrow> </math>.</p> Full article ">
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-30
Previous Issue
Next Issue
Back to TopTop