Maximizing bichromatic reverse nearest neighbor for <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-norm in two- and three-dimensional spaces

Bichromatic reverse nearest neighbor (BRNN) has been extensively studied in spatial database literature. In this paper, we study a related problem called MaxBRNN: find an optimal region that maximizes the size of BRNNs for L _p -norm in two- and three- dimensional spaces. Such a problem has many real-life applications, including the problem of finding a new server point that attracts as many customers as possible by proximity. A straightforward approach is to determine the BRNNs for all possible points that are not feasible since there are a large (or infinite) number of possible points. To the best of our knowledge, there are no existing algorithms which solve MaxBRNN for any L _p -norm space of two- and three-dimensionality. Based on some interesting properties of the problem, we come up with an efficient algorithm called MaxOverlap for to solve this problem. Extensive experiments are conducted to show that our algorithm is efficient.     

<Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-Optimal Nonparametric Frontier Estimation via Linear Programming

A frontier estimation method for a set of points on a plane is proposed, being optimal in L₁-norm on a given class of β-Holder boundary functions under β ∈ (0, 1]. The estimator is defined as sufficiently regular linear combination of kernel functions centered in the sample points, which covers all these points and whose associated support is of minimal surface. The linear combination weights are calculated via solution of the related linear programming problem. The L₁-norm of the estimation error is demonstrated to be convergent to zero with probability one, with the optimal rate of convergence.     

Sparse Support Vector Machine with <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> Penalty for Feature Selection

We study the strategies in feature selection with sparse support vector machine (SVM). Recently, the socalled L _p -SVM (0 < p < 1) has attracted much attention because it can encourage better sparsity than the widely used L ₁-SVM. However, L _p -SVM is a non-convex and non-Lipschitz optimization problem. Solving this problem numerically is challenging. In this paper, we reformulate the L _p -SVM into an optimization model with linear objective function and smooth constraints (LOSC-SVM) so that it can be solved by numerical methods for smooth constrained optimization. Our numerical experiments on artificial datasets show that LOSC-SVM (0 < p < 1) can improve the classification performance in both feature selection and classification by choosing a suitable parameter p. We also apply it to some real-life datasets and experimental results show that it is superior to L ₁-SVM.     

H<Subscript>2</Subscript>-optimal tuning algorithms for fixed structure controllers

An H₂-method of optimal tuning is proposed for a fixed order controller. The SISO plant model is considered in state space. The H₂-method of tuning parameter design is based on the minimization of a transient process closeness criterion for appropriate open-loop and closed-loop control systems and their reference models. The controller tuning algorithms use the plant parameter estimations obtained during the plant parameter identification. The analytical expressions are obtained for the square of H₂-norm of a stable dynamic system. The following theorem is proven: the minimum necessary conditions for the functionals of transfer function H₂-norm of open-loop and closed-loop systems are the same as the minimum necessary conditions for the Frobenius norm of the controller parameter tuning polynomial.     

An Augmented Lagrangian Method for <Emphasis Type="Italic">TV</Emphasis><Subscript><Emphasis Type="Italic">g</Emphasis></Subscript>+<Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-norm Minimization

In this paper, the minimization of a weighted total variation regularization term (denoted TV _g ) with L ¹ norm as the data fidelity term is addressed using the Uzawa block relaxation method. The unconstrained minimization problem is transformed into a saddle-point problem by introducing a suitable auxiliary unknown. Applying a Uzawa block relaxation method to the corresponding augmented Lagrangian functional, we obtain a new numerical algorithm in which the main unknown is computed using Chambolle projection algorithm. The auxiliary unknown is computed explicitly. Numerical experiments show the availability of our algorithm for salt and pepper noise removal or shape retrieval and also its robustness against the choice of the penalty parameter. This last property is useful to attain the convergence in a reduced number of iterations leading to efficient numerical schemes. The specific role of the function g in TV _g is also investigated and we highlight the fact that an appropriate choice leads to a significant improvement of the denoising results. Using this property, we propose a whole algorithm for salt and pepper noise removal (denoted UBR-EDGE) that is able to handle high noise levels at a low computational cost. Shape retrieval and geometric filtering are also investigated by taking into account the geometric properties of the model.     

<Emphasis Type="BoldItalic">H</Emphasis><Subscript>2</Subscript>-Control and the Separation Principle for Discrete-Time Markovian Jump Linear Systems

In this paper we consider the H₂-control problem of discrete-time Markovian jump linear systems. We assume that only an output and the jump parameters are available to the controller. It is desired to design a dynamic Markovian jump controller such that the closed-loop system is mean square stable and minimizes the H₂-norm of the system. As in the case with no jumps, we show that an optimal controller can be obtained from two sets of coupled algebraic Riccati equations, one associated with the optimal control problem when the state variable is available, and the other associated with the optimal filtering problem. This is the principle of separation for discrete-time Markovian jump linear systems. When there is only one mode of operation our results coincide with the traditional separation principle for the H₂-control of discrete-time linear systems. Date received: June 1, 2001. Date revised: October 13, 2003.     

The <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>-Optimality of the IIPG Method for Odd Degrees of Polynomial Approximation in 1D

The paper deals with a numerical analysis of the incomplete interior penalty Galerkin (IIPG) method applied to one dimensional Poisson problem. Based on a particular choice of the interior penalty parameter σ (order of O(h ⁻¹)), we derive the optimal error estimate in the L ²-norm for odd degrees of polynomial approximation for locally quasi-uniform meshes. Moreover, we show that only the mentioned choice of the penalty parameter leads to optimal orders of convergence. Finally, presented numerical experiments verify the theoretical results.     

<Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> disturbance attenuation control for input saturated spacecraft attitude stabilization without angular velocity measurements

This work explores a novel efficient and low-cost control scheme for rigid spacecraft attitude stabilization problem, in which the unavailability of angular velocity measurements is considered. The resulting controller is independent on spacecraft inertia parameters, and explicit accounts for control input saturation with angular velocity measurements eliminated. Moreover, the proposed control law allows L ₂ gain of the closed-loop attitude system to be chosen arbitrarily small so as to achieve any level of L ₂ disturbance attenuation. Numerical simulation results are also presented to highlight those highly desirable features.     

Particle swarm optimization-based fixed-structure <Emphasis Type="Italic">ℋ</Emphasis><Subscript>∞</Subscript> control design

In this paper, a new robust fixed-structure ℋ _∞ controller design based on the Particle Swarm Optimization (PSO) technique is proposed. The optimization-based structured synthesis problem is formulated and solved by a constrained PSO algorithm. In the proposed approach, the ℋ _∞ controller’s structure is selectable. PI and PID controller structures are especially adopted. The case study of an electrical DC drive benchmark is adopted to illustrate the efficiency and viability of the proposed control approach. A comparison to another similar evolutionary algorithm, such as Genetic Algorithm Optimization (GAO), shows the superiority of the PSO-based method to solve the formulated optimization problem. Simulations and experimental results show the advantages of simple structure, lower order and robustness of the proposed controller.     

<Emphasis Type="Italic">H</Emphasis><Subscript>2</Subscript>-optimization of time-delayed sampled-data systems on the basis of the parametric transfer matrix method

A solution to the H ₂-optimization problem for multi-input-multi-output sampled-data system with delay is presented on the basis of the parametric transfer matrix concept. A procedure is developed for design of the optimal controller by means of factorization and separation of real rational matrices. Some qualitative properties of the H ₂-optimal system are established, which are useful for applications. In particular, it is proved that there is a set of fixing poles of continuous-time elements of the system, and performance of the optimal system is limited because of them. A constructive algorithm is given for determination of the set of fixing poles.     

Positive <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-gain filter design for positive continuous-time Markovian jump systems with partly known transition rates

The paper is concerned with the problem of positive L ₁-gain filter design for positive continuous-time Markovian jump systems with partly known transition rates. Our aim is to design a positive full-order filter such that the corresponding filtering error system is positive and stochastically stable with L ₁-gain performance. By applying a linear co-positive Lyapunov function and free-connection weighting vectors, the desired positive L ₁-gain filter is provided. The obtained theoretical results are demonstrated by numerical examples.     

Pareto optimal generalized <Emphasis Type="Italic">H</Emphasis><Subscript>2</Subscript>-control and vibroprotection problems

We consider a novel multi-objective control problem where the criteria are generalized H ₂-norms of transfer matrices of individual channels from the disturbance input to various objective outputs. We obtain necessary conditions for Pareto optimality. We show that synthesis of Pareto optimal controls can be done in terms of linear matrix inequalities based on optimizing Germeier’s convolution, which also turns out to be the generalized H ₂-norm of the closed-loop system with output composed of the objective outputs multiplied by scalars. As applications we consider multi-objective problems of vibration isolation and oscillation suppression with new types of criteria.     

A fast and adaptive method for complex-valued SAR image denoising based on <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">k</Emphasis></Subscript> norm regularization

This paper developed a fast and adaptive method for SAR complex image denoising based on l _k norm regularization, as viewed from parameters estimation. We firstly establish the relationship between denoising model and ill-posed inverse problem via convex half-quadratic regularization, and compare the difference between the estimator variance obtained from the iterative formula and biased Cramer-Rao bound, which proves the theoretic flaw of the existent methods of parameter selection. Then, the analytic expression of the model solution as the function with respect to the regularization parameter is obtained. On this basis, we study the method for selecting the regularization parameter through minimizing mean-square error of estimators and obtain the final analytic expression, which resulted in the direct calculation, high processing speed, and adaptability. Finally, the effect of regularization parameter selection on the resolution of point targets is analyzed. The experiment results of simulation and real complex-valued SAR images illustrate the validity of the proposed method. Supported by the National Natural Science Foundation of China (Grant No. 60572136), the Fundamental Research Fund of NUDT (Grant No. JC0702005)     

二阶收敛的光滑正则化压缩感知信号重构方法

目的压缩感知信号重构过程是求解不定线性系统稀疏解的过程。针对不定线性系统稀疏解3种求解方法不够鲁棒的问题:最小化l₀-范数属于NP问题,最小化l₁-范数的无解情况以及最小化l_p-范数的非凸问题,提出一种基于光滑正则凸优化的方法进行求解。方法为了获得全局最优解并保证算法的鲁棒性,首先,设计了全空间信号l₀-范数凸拟合函数作为优化的目标函数;其次,将n元函数优化问题转变为n个一元函数优化问题;最后,求解过程中利用快速收缩算法进行求解,使收敛速度达到二阶收敛。结果该算法无论在仿真数据集还是在真实数据集上,都取得了优于其他3种类型算法的效果。在仿真实验中,当信号维数大于150维时,该方法重构时间为其他算法的50%左右,具有快速性;在真实数据实验中,该方法重构出的信号与原始信号差的F-范数为其他算法的70%,具有良好的鲁棒性。结论本文算法为二阶收敛的凸优化算法,可确保快速收敛到全局最优解,适合处理大型数据,在信息检索、字典学习和图像压缩等领域具有较大的潜在应用价值。     

Algorithms for P<Subscript>4</Subscript>-Comparability Graph Recognition and Acyclic P<Subscript>4</Subscript>-Transitive Orientation

We consider two problems pertaining to P₄-comparability graphs, namely, the problem of recognizing whether a simple undirected graph is a P₄-comparability graph and the problem of producing an acyclic P₄-transitive orientation of a P₄-comparability graph. These problems have been considered by Hoàng and Reed who described O(n⁴)- and O(n⁵)-time algorithms for their solution, respectively, where n is the number of vertices of the input graph. Faster algorithms have recently been presented by Raschle and Simon, and by Nikolopoulos and Palios; the time complexity of these algorithms for either problem is O(n + m²), where m is the number of edges of the graph. In this paper we describe O(n m)-time and O(n + m)-space algorithms for the recognition and the acyclic P₄-transitive orientation problems on P₄-comparability graphs. The algorithms rely on properties of the P₄-components of a graph, which we establish, and on the efficient construction of the P₄-components by means of the BFS-trees of the complement of the graph rooted at each of its vertices, without however explicitly computing the complement. Both algorithms are simple and use simple data structures.     

States on <Emphasis Type="Italic">R</Emphasis><Subscript>0</Subscript> algebras

The aim of this paper is to introduce the notion of states on R ₀ algebras and investigate some of their properties. We prove that every R ₀ algebra possesses at least one state. Moreover, we investigate states on weak R ₀ algebras and give some examples to show that, in contrast to R ₀ algebras, there exist weak R ₀ algebras which have no states. We also derive the condition under which finite linearly ordered weak R ₀ algebras have a state. This work is supported by NSFC (No.60605017).     

Inertial motion tracking using sensor saturation compensation with <Emphasis Type="Italic">l</Emphasis><Subscript>1</Subscript> norm regularization

A smoother is proposed for inertial sensor-based motion tracking, where the sensor saturation is compensated. The sensor saturation estimation term is added using l ₁ norm regularization techniques to the standard smoothing problem. The proposed algorithm is in the form of a quadratic optimization problem. Three slightly different methods are proposed, where the geometric models on sensor saturation are slightly different. Through simulation and experiments, it is shown that the proposed method effectively compensates the sensor saturation.     

Multiscale enrichment of a finite volume element method for the stationary Navier–Stokes problem

In this paper, we introduce a finite volume element method for the Navier–Stokes problem. This method is based on the multiscale enrichment and uses the lowest finite element pair P ₁/P ₀. The stability and convergence of the optimal order in H ¹-norm for velocity and L ²-norm for pressure are obtained. Using a dual problem for the Navier–Stokes problem, we establish the convergence of the optimal order in L ²-norm for the velocity.     

Nonparametric Frontier Estimation by Linear Programming

A new method for estimating the frontier of a set of points (or a support, in other words) is proposed. The estimates are defined as kernel functions covering all the points and whose associated support is of smallest surface. They are written as linear combinations of kernel functions applied to the points of the sample. The weights of the linear combination are then computed by solving a linear programming problem. In the general case, the solution of the optimization problem is sparse, that is, only a few coefficients are non zero. The corresponding points play the role of support vectors in the statistical learning theory. The L ₁-norm for the error of estimation is shown to be almost surely converging to zero, and the rate of convergence is provided.     

Intuitionistic (<Emphasis Type="Italic">S</Emphasis>, <Emphasis Type="Italic">T</Emphasis>)-fuzzy hyperquasigroups

The concept of intuitionistic fuzzy subhyperquasigroups in a hyperquasigroup with respect to an s-norm and a t-norm on intuitionistic fuzzy sets is introduced and their properties of such hyperquasigroups are studied. Intuitionistic (S, T)-fuzzy relations on a hyperquasigroup G are discussed. In particular, we investigate connections hyperquasigroups with binary quasigroups.