Journal of Zhejiang University SCIENCE C

Principal component analysis (PCA) is fundamental in many pattern recognition applications. Much research has been performed to minimize the reconstruction error in L1-norm based reconstruction error minimization (L1-PCA-REM) since conventional L2-norm based PCA (L2-PCA) is sensitive to outliers. Recently, the variance maximization formulation of PCA with L1-norm (L1-PCA-VM) has been proposed, where new greedy and nongreedy solutions are developed. Armed with the gradient ascent perspective for optimization, we show that the L1-PCA-VM formulation is problematic in learning principal components and that only a greedy solution can achieve robustness motivation, which are verified by experiments on synthetic and real-world datasets.

To facilitate the application of support vector machines (SVMs) in embedded systems, we propose and test a parallel and scalable digital architecture based on the sequential minimal optimization (SMO) algorithm for training SVMs. By taking advantage of the mature and popular SMO algorithm, the numerical instability issues that may exist in traditional numerical algorithms are avoided. The error cache updating task, which dominates the computation time of the algorithm, is mapped into multiple processing units working in parallel. Experiment results show that using the proposed architecture, SVM training problems can be solved effectively with inexpensive fixed-point arithmetic and good scalability can be achieved. This architecture overcomes the drawbacks of the previously proposed SVM hardware that lacks the necessary flexibility for embedded applications, and thus is more suitable for embedded use, where scalability is an important concern.

We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson’s. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.

In this paper, we determine the delay-dependent conditions of global asymptotic stability for a class of multi-dimensional nonlinear time-delay systems with application to computer communication networks. A nonlinear delayed model is considered for a rate-based congestion control system of a heterogeneous network with arbitrary topology and time-varying delays. We propose a Lyapunov-based method to obtain a sufficient condition under which global asymptotic stability of the equilibrium is guaranteed. The main contribution of the paper lies in considering time variations of delays in a heterogeneous network which may be applicable in actual networks. Moreover, we obtain conditions for Internet-style networks with multi-source multi-link topology. We first prove the stability for a class of nonlinear time-delay systems. Then, we apply the results to a Kelly’s rate-based approximation of the congestion control system.

We design a task mapper TPCM for assigning tasks to virtual machines, and an application-aware virtual machine scheduler TPCS oriented for parallel computing to achieve a high performance in virtual computing systems. To solve the problem of mapping tasks to virtual machines, a virtual machine mapping algorithm (VMMA) in TPCM is presented to achieve load balance in a cluster. Based on such mapping results, TPCS is constructed including three components: a middleware supporting an application-driven scheduling, a device driver in the guest OS kernel, and a virtual machine scheduling algorithm. These components are implemented in the user space, guest OS, and the CPU virtualization subsystem of the Xen hypervisor, respectively. In TPCS, the progress statuses of tasks are transmitted to the underlying kernel from the user space, thus enabling virtual machine scheduling policy to schedule based on the progress of tasks. This policy aims to exchange completion time of tasks for resource utilization. Experimental results show that TPCM can mine the parallelism among tasks to implement the mapping from tasks to virtual machines based on the relations among subtasks. The TPCS scheduler can complete the tasks in a shorter time than can Credit and other schedulers, because it uses task progress to ensure that the tasks in virtual machines complete simultaneously, thereby reducing the time spent in pending, synchronization, communication, and switching. Therefore, parallel tasks can collaborate with each other to achieve higher resource utilization and lower overheads. We conclude that the TPCS scheduler can overcome the shortcomings of present algorithms in perceiving the progress of tasks, making it better than schedulers currently used in parallel computing.

The pivot language approach for statistical machine translation (SMT) is a good method to break the resource bottleneck for certain language pairs. However, in the implementation of conventional approaches, pivot-side context information is far from fully utilized, resulting in erroneous estimations of translation probabilities. In this study, we propose two topic-aware pivot language approaches to use different levels of pivot-side context. The first method takes advantage of document-level context by assuming that the bridged phrase pairs should be similar in the document-level topic distributions. The second method focuses on the effect of local context. Central to this approach are that the phrase sense can be reflected by local context in the form of probabilistic topics, and that bridged phrase pairs should be compatible in the latent sense distributions. Then, we build an interpolated model bringing the above methods together to further enhance the system performance. Experimental results on French-Spanish and French-German translations using English as the pivot language demonstrate the effectiveness of topic-based context in pivot-based SMT.

Based on our recent study on probability distributions for evolution in extremal optimization (EO), we propose a modified framework called EOSAT to approximate ground states of the hard maximum satisfiability (MAXSAT) problem, a generalized version of the satisfiability (SAT) problem. The basic idea behind EOSAT is to generalize the evolutionary probability distribution in the Bose-Einstein-EO (BE-EO) algorithm, competing with other popular algorithms such as simulated annealing and WALKSAT. Experimental results on the hard MAXSAT instances from SATLIB show that the modified algorithms are superior to the original BE-EO algorithm.

This paper presents a method to detect the quantization index modulation (QIM) steganography in G.723.1 bit stream. We show that the distribution of each quantization index (codeword) in the quantization index sequence has unbalanced and correlated characteristics. We present the designs of statistical models to extract the quantitative feature vectors of these characteristics. Combining the extracted vectors with the support vector machine, we build the classifier for detecting the QIM steganography in G.723.1 bit stream. The experiment shows that the method has far better performance than the existing blind detection method which extracts the feature vector in an uncompressed domain. The recall and precision of our method are all more than 90% even for a compressed bit stream duration as low as 3.6 s.

This paper presents a new approach for solving a class of infinite horizon nonlinear optimal control problems (OCPs). In this approach, a nonlinear two-point boundary value problem (TPBVP), derived from Pontryagin’s maximum principle, is transformed into a sequence of linear time-invariant TPBVPs. Solving the latter problems in a recursive manner provides the optimal control law and the optimal trajectory in the form of uniformly convergent series. Hence, to obtain the optimal solution, only the techniques for solving linear ordinary differential equations are employed. An efficient algorithm is also presented, which has low computational complexity and a fast convergence rate. Just a few iterations are required to find an accurate enough suboptimal trajectory-control pair for the nonlinear OCP. The results not only demonstrate the efficiency, simplicity, and high accuracy of the suggested approach, but also indicate its effectiveness in practical use.