The article describes recent adaptive estimation algorithms over distributed networks. The algorithms rely on local collaborations and exploit the space-time structure of the data. Each node is allowed to communicate with its neighbors in order to exploit the spatial dimension, while it also evolves locally to account for the time dimension. Algorithms of the least-mean-squares and least-squares types are described. Both incremental and diffusion strategies are considered.

An audio-based shot classification method for audiovisual indexing is proposed in this paper. The proposed method mainly consists of two parts, an audio analysis part and a shot classification part. In the audio analysis part, the proposed method utilizes both principal component analysis (PCA) and Mahalanobis generalized distance (MGD). The effective features for the analysis can be automatically obtained by using PCA, and these features are analyzed based on MGD, which can take into account the correlations of the data set. Thus, accurate analysis results can be obtained by the combined use of PCA and MGD. In the shot classification part, the proposed method utilizes a fuzzy algorithm. By using the fuzzy algorithm, the mixing rate of the multiple audio sources can be roughly measured, and thereby accurate shot classification can be attained. Results of experiments performed by applying the proposed method to actual audiovisual materials are shown to verify the effectiveness of the proposed method.

This paper proposes a new computational optimization method modified from the dynamic encoding algorithm for searches (DEAS). Despite the successful optimization performance of DEAS for both benchmark functions and parameter identification, the problem of exponential computation time becomes serious as problem dimension increases. The proposed optimization method named univariate DEAS (uDEAS) is especially implemented to reduce the computation time using a univariate local search scheme. To verify the algorithmic feasibility for global optimization, several test functions are optimized as benchmark. Despite the simpler structure and shorter code length, function optimization performance show that uDEAS is capable of fast and reliable global search for even high dimensional problems.

In this paper, we propose the introduction of a frequency domain variable perturbation control and a leaky algorithm to the frequency domain time difference simultaneous perturbation (FDTDSP) method in order to improve the cancellation performance and the stability of the active noise control (ANC) system using the perturbation method. Since the ANC system using the perturbation method does not need the secondary path model, it has an advantage of being able to track the secondary path changes. However, the conventional perturbation method has the problem that the cancellation performance deteriorates over the entire frequency band when the frequency response of the secondary path has dips because the magnitude of the perturbation is controlled in the time domain. Moreover, the stability of this method also deteriorates in consequence of the dips. On the other hand, the proposed method can improve the cancellation performance by providing the appropriate magnitude of the perturbation over the entire frequency band and stabilizing the system operation. The effectiveness of the proposed method is demonstrated through simulation and experimental results.

SAL is a toolkit for analyzing transition systems, providing several different tools. Among the tools are a BDD-based symbolic model checker (SMC) and an SMT-based infinite bounded model checker (infBMC). The unique functionality provided by SAL is k-induction, which is supported by infBMC. Given appropriate lemmas, infBMC can prove automatically by k-induction that an infinite-state transition system satisfies invariant properties. Maude is a specification language and system based on membership equational logic and rewriting logic. Maude is equipped with an on-the-fly explicit state model checker. The unique functionality provided by the Maude model checker supports inductive data types. We make a comparison of SAL (especially SMC and infBMC) and the Maude model checker by conducting case studies in which the Suzuki-Kasami distributed mutual exclusion algorithm is analyzed. The purpose of the comparison is to clarify some of the two tools' functionalities, especially the unique ones, through the case studies.

With the rapid adoption of mobile devices and location based services (LBS), applications provide with nearby information like recommending sightseeing resort are becoming more and more popular. In the mean time, traffic congestion in cities led to the development of mobile public transportation systems. In such applications, mobile devices need to communicate with servers via wireless communications and servers should process queries from tons of devices. However, because users can not neglect the payment for the wireless communications and server capacities are limited, decreasing the communications made between central servers and devices and reducing the burden on servers are quite demanding. Therefore, in this paper, we propose a cost-effective intelligent public transportation system, ACE-INPUTS, which utilizes a mobile device to retrieve the bus routes to reach a destination from the current location at the lowest wireless communication cost. To accomplish this task, ACE-INPUTS maintains a small amount of information on bus stops and bus routes in a mobile device and runs a heuristic routing algorithm based on such information. Only when a user asks more accurate route information or calls for a "leave later query", ACE-INPUTS entrusts the task to a server into which real-time traffic and bus location information is being collected. By separating the roles into mobile devices and servers, ACE-INPUTS is able to provide bus routes at the lowest wireless communication cost and reduces burden on servers. Experimental results have revealed that ACE-INPUTS is effective and scalable in most experimental settings.

In orthogonal frequency-division multiplex access (OFDMA) uplink, the carrier-frequency offsets (CFOs) between the multiple transmitters and the receiver introduce inter-carrier interference (ICI) and severely degrade the performance. In this paper, based on the perfect estimation of each user's CFO, we propose two low-complexity iterative algorithms to cancel ICI due to CFOs, which are denoted as the basic algorithm and the improved algorithm with decision-feedback equalization (DFE), respectively. For the basic one, two theorems are proposed that yield a sufficient condition for the convergence of iterations. Moreover, the interference-power-evolution (IPE) charts are proposed to evaluate the convergence behavior of this interference cancellation algorithm. Motivated by the IPE chart, the procedure of DFE is introduced into the iterations, which is the basic idea of the improved algorithm. For this improved algorithm, the error-propagation effect are analyzed and suppressed by an efficient stopping criterion. From IPE charts and simulation results, it can be easily observed that the basic algorithm has the same capability of ICI cancellation as the linear optimal minimum mean square error (MMSE) method, but offers lower complexity, while the improved algorithm with DFE outperforms the MMSE method in terms of the bit-error rate (BER) performance.

The subspace algorithm can be utilized for the blind detection of space-time block codes (STBC) without knowledge of channel state information (CSI) both at the transmitter and receiver. However, its performance degrades when the channels are correlated. In this letter, we analyze the impact of channel correlation from the orthogonality loss between the transmit signal subspace (TSS) and the statistical noise subspace (SNS). Based on the decoding property of the subspace algorithm, we propose a revised detection in favor of the channel correlation matrix (CCM) only known to the receiver. Then, a joint transmit-receive preprocessing scheme is derived to obtain a further performance improvement when the CCM is available both at the transmitter and receiver. Analysis and simulation results indicate that the proposed methods can significantly improve the blind detection performance of STBC over the correlated channels.

We propose a new genetic fuzzy discretization method with feature selection for the pattern classification problems. Traditional discretization methods categorize a continuous attribute into a number of bins. Because they are made on crisp discretization, there exists considerable information loss. Fuzzy discretization allows overlapping intervals and reflects linguistic classification. However, the number of intervals, the boundaries of intervals, and the degrees of overlapping are intractable to get optimized and a discretization process increases the total amount of data being transformed. We use a genetic algorithm with feature selection not only to optimize these parameters but also to reduce the amount of transformed data by filtering the unconcerned attributes. Experimental results showed considerable improvement on the classification accuracy over a crisp discretization and a typical fuzzy discretization with feature selection.

The performance of the blind multiuser detector for a DS-CDMA system with linearly constrained constant modulus (LCCM) criterion is known to highly depend on the exact knowledge of the desired user amplitude; it is usually not available at receiver end. In this paper, we propose a novel LC adaptive CM RLS (LC-ACM-RLS) algorithm to adaptively implement the optimal solution of the LCCM receiver, and to track the desired user's amplitude, simultaneously. From computer simulations, we verify the superiority of the new proposed algorithm over the conventional LCCM-RLS algorithm for multiple access interference (MAI) suppression. Also, for time-varying channel during the adaptation processes, if the amplitude of desired user is not available and varies with time, such as hand-off and Rayleigh fading environments, we show that the proposed LC-ACM-RLS algorithm has better tracking capability compared with the conventional approaches.

This paper presents an automated design of linear and non-linear differential analog circuits accelerated by reuse of genetic operations. The system first synthesizes circuits using pairs of simplified MOSFET model. During the evolutionary process, genetic operations that improve circuit characteristics are stored in a database and reused to effectively obtain a better circuit. Simplified elements in a generated circuit are replaced by MOSFETs and optimization of the transistor size is performed using an optimizer available in market if necessary. The capability of this method is demonstrated through experiments of synthesis of a differential voltage amplifier, a circuit having cube-law characteristic in differential mode and square-law characteristic in common-mode, and a dB-linear VGA (Variable Gain Amplifier). The results show the reuse of genetic operations accelerates the synthesis and success rate becomes 100%.

In recent years, network analysis has revealed that some real networks have the properties of small-world and/or scale-free networks. In this study, a simple Genetic Algorithm (GA) is regarded as a network where each node and each edge respectively represent a population and the possibility of the transition between two nodes. The characteristic path length (CPL), which is one of the most popular criteria in small-world networks, is derived analytically and shows how much the crossover operation affects the path length between two populations. As a result, the crossover operation is not so useful for shortening the CPL.

List decoding is a process by which a list of decoded words is output instead of one. This works for a larger noise threshold than the traditional algorithms. Under some circumstances it becomes useful to be able to find out the actual message from the list. List decoding is assumed to be successful, meaning, the sent message features in the decoded list. This problem has been considered by Guruswami. In Guruswami's work, this disambiguation is done by sending supplementary information through a costly, error-free channel. The model is meaningful only if the number of bits of side information required is much less than the message size. But using deterministic schemes one has to essentially send the entire message through the error free channel. Randomized strategies for both sender and receiver reduces the required number of bits of side information drastically. In Guruswami's work, a Reed-Solomon code based hash family is used to construct such randomized schemes. The scheme with probability utmost ε reports failure and returns the whole list. The scheme doesn't output a wrong message. Also, in Guruswami's work some theoretical bounds have been proved which lower bound the bits of side information required. Here we examine whether the gap between the theoretical bounds and existing schemes may be narrowed. Particularly, we use the same scheme as in Guruswami's work, but use hash families based on Hermitian curve and function fields of Garcia-Stichtenoth tower and analyze the number of bits of side information required for the scheme.

In this paper, a novel independent component analysis (ICA) approach is proposed, which is robust against the interference of impulse noise. To implement ICA in a noisy environment is a difficult problem, in which traditional ICA may lead to poor results. We propose a method that consists of noise detection and image signal recovery. The proposed approach includes two procedures. In the first procedure, we introduce a self-organizing map (SOM) network to determine if the observed image pixels are corrupted by noise. We will mark each pixel to distinguish normal and corrupted ones. In the second procedure, we use one of two traditional ICA algorithms (fixed-point algorithm and Gaussian moments-based fixed-point algorithm) to separate the images. The fixed-point algorithm is proposed for general ICA model in which there is no noise interference. The Gaussian moments-based fixed-point algorithm is robust to noise interference. Therefore, according to the mark of image pixel, we choose the fixed-point or the Gaussian moments-based fixed-point algorithm to update the separation matrix. The proposed approach has the capacity not only to recover the mixed images, but also to reduce noise from observed images. The simulation results and analysis show that the proposed approach is suitable for practical unsupervised separation problem.

Recently, the superimposed pilot channel estimation has attracted attention for wireless communications, where the pilot symbol sequence is superimposed on a data symbol sequence and transmitted together, and thus there is no drop in information rate. In the superimposed pilot channel estimation, the receiver correlates the received symbol sequence with the pilot symbol sequence, and obtains the channel estimate. However, the correlation between the pilot symbol sequence and the data symbol sequence deteriorates the channel estimation accuracy. In particular, the channel estimation accuracy of the superimposed pilot channel estimation scheme is significantly deteriorated in MIMO systems, because the pilot symbol power of each transmit antenna to the total transmit power of all transmit antennas becomes smaller as the number of transmit antennas increases. On the other hand, it has been well known that the SAGE algorithm is an effective method for channel estimation and data detection. This algorithm is particularly effective in MIMO systems, because the operation of this algorithm can cancel the interference from other transmit antennas. In this paper, we evaluate the performance of the SAGE algorithm for channel estimation and data detection using superimposed pilot channel estimation in MIMO systems. From the results of computer simulations, we show that the system using the SAGE algorithm with superimposed training can achieve the good BER performances by using the SAGE algorithm with iteration.

We present a computationally efficient sequential detection scheme using a modified Fano algorithm (MFA) for V-BLAST systems. The proposed algorithm consists of the following three steps: initialization, tree searching, and optimal selection. In the first step, the proposed detection scheme chooses several candidate symbols at the tree level of one. Based on these symbols, the MFA then finds the remaining transmitted symbols from the second tree level in the original tree structure. Finally, an optimal symbol sequence is decided among the most likely candidate sequences searched in the previous step. Computer simulation shows that the proposed scheme yields significant saving in complexity with very small performance degradation compared with that of sphere detection (SD).

Data detection based on self organizing maps is presented for hematopoietic tumor patients. Learning data for the maps are generated from the screening data of examinees. The incomplete screening data without some item values is then supplemented by substituting averaged non-missing item values. In addition, redundant items, which are common to all the data and tend to have an unfavorable influence on data detection, are eliminated by a genetic algorithm and/or an immune algorithm. It is basically judged, by observing the label of a winner neuron in the map, whether the data presented to the map belongs to the class of hematopoietic tumors. Some experimental results are provided to show that the proposed methods achieve the high probability of correctly identifying examinees as hematopoietic tumor patients.

This paper proposes a suboptimal algorithm for the maximum likelihood detection (MLD) in multiple-input multiple-output (MIMO) communications. The proposed algorithm regards transmitted signals as continuous variables in the same way as a common method for the discrete optimization problem, and then searches for candidates of the transmitted signals in the direction of a modified gradient vector of the metric. The vector is almost proportional to the direction of the noise enhancement, from which zero-forcing (ZF) or minimum mean square error (MMSE) algorithms suffer. This method sets the initial guess to the solution by ZF or MMSE algorithms, which can be recursively calculated. Also, the proposed algorithm has the same complexity order as that of conventional suboptimal algorithms. Computer simulations demonstrate that it is much superior in BER performance to the conventional ones.

In this paper we give a simple algorithm to generate all partitions of a positive integer n. The problem is one of the basic problems in combinatorics, and has been extensively studied for a long time. Our algorithm generates each partition of a given integer in constant time for each without repetition, while best known algorithm generates each partition in constant time on "average." Also, we propose some algorithms to generate all partitions of an integer with some additional property in constant time.

It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n3) time by using simple dynamic programming procedures. For this problem, an O(n3(log log n)1/2/(log n)1/2) time exact algorithm and an O(n2.776+(1/ε)O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n5) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.