An Algorithm for Clustering Using L1‐Norm Based on Hyperbolic Smoothing Technique

Cluster analysis deals with the problem of organization of a collection of objects into clusters based on a similarity measure, which can be defined using various distance functions. The use of different similarity measures allows one to find different cluster structures in a data set. In this article, an algorithm is developed to solve clustering problems where the similarity measure is defined using the L₁‐norm. The algorithm is designed using the nonsmooth optimization approach to the clustering problem. Smoothing techniques are applied to smooth both the clustering function and the L₁‐norm. The algorithm computes clusters sequentially and finds global or near global solutions to the clustering problem. Results of numerical experiments using 12 real‐world data sets are reported, and the proposed algorithm is compared with two other clustering algorithms.     

Multiple Lyapunov Functions with Blending for Induced L2‐norm Control of Switched LPV Systems and its Application to an F‐16 Aircraft Model

This paper studies the induced L₂‐norm problem for switched linear parameter varying (LPV) systems using a blending method. For a switched LPV system where the parameters are grouped into slow‐varying and fast‐varying parameters, the blending method is used to construct blended Lyapunov functions based on the multiple Lyapunov functions conditions in terms of linear matrix inequalities (LMIs). The proposed method is applied to an F‐16 aircraft longitudinal model and the simulation results demonstrate the effectiveness of the approach.     

Output‐Feedback Control for Continuous‐time Interval Positive Systems under L1 Performance

This paper is concerned with the design of an L₁‐induced output‐feedback controller for continuous‐time positive systems with interval uncertainties. A necessary and sufficient condition for stability and an L₁‐induced performance of interval positive linear systems is proposed in terms of linear inequalities. Based on this, conditions for the existence of robust static output‐feedback controllers are established and an iterative convex optimization approach is developed to solve the conditions. For special single‐input‐multiple‐output (SIMO) positive systems, the problem of controller synthesis is completely solved with the help of an analytical formula for the L₁‐induced norm. An illustrative example is provided to show the effectiveness and applicability of the theoretical results.     

Robust non‐fragile H ∞ ∕ L2 − L ∞ control of uncertain linear system with time‐delay and application to vehicle active suspension

This paper presents an approach to design robust non‐fragile H _∞ ∕ L₂ ? L _∞ static output feedback controller, considering actuator time‐delay and the controller gain variations, and it is applied to design vehicle active suspension. According to suspension design requirements, the H _∞ and L₂ ? L _∞ norms are used, respectively, to reflect ride comfort and time‐domain hard constraints. By employing a delay‐dependent Lyapunov function, existence conditions of delay‐dependent robust non‐fragile static output feedback H _∞ controller and L₂ ? L _∞ controller are derived, respectively, in terms of the feasibility of bilinear matrix inequalities. Then, a new procedure based on LMI optimization and a hybrid algorithm of the particle swarm optimization and differential evolution is used to solve an optimization problem with bilinear matrix inequality constraints. Simulation results show that the designed active suspension system still can guarantee their own performance in spite of the existence of the model uncertainties, the actuator time‐delay and the controller gain variations. Copyright © 2014 John Wiley & Sons, Ltd.     

AN ITERATIVE LMI APPROACH TO RFDF FOR LINEAR SYSTEM WITH TIME‐VARYING DELAYS

This paper deals with robust fault detection filter (RFDF) problem for a class of linear uncertain systems with time‐varying delays and model uncertainties. The RFDF design problem is formulated as an optimization problem by using L₂‐induced norm to represent the robustness of residual to unknown inputs and modelling errors, and the sensitivity to faults. A sufficient condition to the solvability of formulated problem is established in terms of certain matrix inequalities, which can be solved with the aid of an iterative linear matrix inequality (ILMI) algorithm. Finally, a numerical example is given to illustrate the effectiveness of the proposed method.     

Lp范数压缩感知图像重建优化算法

目的 压缩感知理论中的重构算法作为关键技术之一,在科学研究方面起到了关键的作用。常用的重构算法包括L₀范数的非凸优化算法和L₁范数的凸优化算法,但它们的缺点是重构精度不高,运算时间很长。为了克服这一缺陷,提高现有基于L_p范数的压缩感知图像重构算法的重建精度和算法效率,本文提出改进算法。方法 针对拉格朗日函数序列二次规划（SQP）方法中海瑟（Hesse）矩阵不正定导致计算量很大的问题,引入价值函数,修正Hesse矩阵的序列二次规划方法并结合图像分块压缩感知技术,提出了一种基于L_P范数压缩感知图像重构算法。结果 在采样率同为40%情况下,本文算法下的信噪比为34.28 dB,高于BOMP（block orthogonal matching pursuit）算法信噪比2%,高于当罚函数作为修正方法时的13.2%。本文算法计算时间为190.55 s,快于BOMP算法13.4%,快于当罚函数作为修正方法时的67.5%。采样率同为50%的情况下,本文算法下的信噪比为35.42 dB,高BOMP算法信噪比2.4%,高于当罚函数作为修正方法时信噪比12.8%。本文算法的计算时间是196.67 s,快于BOMP算法68.2%,快于81.7%。在采样率同为60%的情况下,本文算法的信噪比为36.33 dB,高于BOMP算法信噪比3.2%,高于当罚函数作为修正方法时信噪比8.2%。本文算法计算时间为201.72 s,快于BOMP算法82.3%,快于当罚函数作为修正方法时86.6%。在采样率为70%的情况下,本文算法信噪比38.62 dB,高于BOMP算法信噪比2.5%,高于当罚函数作为修正方法时信噪比9.8%。本文算法计算时间为214.68 s,快于BOMP算法88.12%,快于当罚函数作为修正方法时的91.1%。实验结果显示在相同的采样率的情况下,本文改进算法在重构精度和算法时间上均优于BOMP算法等其他算法。并且采样率越高,重构图像精度越来越高,重构算法时间越来越短。结论 通过实验对本文算法、BOMP重构算法等其他算法在信噪比和算法计算时间进行对比,在不同采样率下,本文算法都明显优于其他两种算法,而且在采样率仅为20.5%时,信噪比高达85.154 3 dB,重构图像比较清晰。本文算法的最大优点在于采用了分块压缩感知技术,提高图像重构效率,降低了重构时间,缺点是在图像采样率比较低的情况下,存在图像干扰块效应。接下来研究方向是如何在采样率低的情况下,高精度地还原图片,消除图像干扰块效应。     

Using a sparse promoting method in linear programming approximations to schedule parallel jobs

In this paper, we tackle the well‐known problem of scheduling a collection of parallel jobs on a set of processors either in a cluster or in a multiprocessor computer. For the makespan objective, that is, the completion time of the last job, this problem has been shown to be NP‐hard, and several heuristics have already been proposed to minimize the execution time. In this paper, we consider both rigid and moldable jobs. Our main contribution is the introduction of a new approach to the scheduling problem, based on the recent discoveries in the field of compressed sensing. In the proposed approach, all possible positions and shapes of the jobs are encoded into a matrix, and the scheduling is performed by selecting the best columns under natural constraints. Thus, the solution to the new scheduling formulation is naturally sparse, and we may use appropriate relaxations to achieve the optimization task in the quickest possible way. Among many possible relaxation strategies, we choose to minimize the ℓ_p‐quasi‐norm for p∈(0,1). Minimization of the ℓ_p‐quasi‐norm is implemented via a successive linear programming approximation heuristic. We propose several new algorithms based on this approach, and we assess their efficiency through simulations. The experiments show that the scheme outperforms the classic Largest Task First list based algorithm for scheduling small to medium instances but needs improvements to compete on larger numbers of jobs. Copyright © 2014 John Wiley & Sons, Ltd.     

L∞ Observer for Uncertain Linear Systems

In this paper, an L_∞ observer design method is proposed for linear system subject to parameter uncertainty and bounded disturbance. The proposed L_∞ observer, which satisfies a peak‐to‐peak disturbances attenuation performance, is designed to overbound the estimation error. Moreover, sufficient conditions for the design of L_∞ observer are derived and expressed in terms of linear matrix inequalities (LMIs). The novelty of the proposed method is that we develop an L_∞ observer that not only can attenuate bounded disturbance but also provides an upper bound of estimation error norm. Simulation results are presented to illustrate the effectiveness of the proposed method.     

L1 synthesis of a static output controller for positive systems by LMI iteration

An approach to find a static output feedback gain that makes the feedback system positive and minimizes the L₁ gain is proposed. The problem of finding a static output feedback gain has 3 aspects: stabilizing the system, making the system positive, and then minimizing the L₁ gain. Each subproblem is described by bilinear matrix inequality with respect to the feedback gain and the Lyapunov matrix or vector. Linear matrix inequality (LMI) that is sufficient to satisfy bilinear matrix inequality is derived using a convex‐concave decomposition, and the feedback gain sequence is calculated by an iterative solution of LMI. The sequence of the upper bounds on the design parameter is guaranteed to be monotonically nonincreasing for each algorithm. Similarly, 2 other LMIs are derived for each subproblem using another convex‐concave decomposition and PK iteration. The effectiveness of these algorithms is illustrated via several numerical examples.     

Low-rank matrix decomposition in L1-norm by dynamic systems

Low-rank matrix approximation is used in many applications of computer vision, and is frequently implemented by singular value decomposition under L₂-norm sense. To resist outliers and handle matrix with missing entries, a few methods have been proposed for low-rank matrix approximation in L₁ norm. However, the methods suffer from computational efficiency or optimization capability. Thus, in this paper we propose a solution using dynamic system to perform low-rank approximation under L₁-norm sense. From the state vector of the system, two low-rank matrices are distilled, and the product of the two low-rank matrices approximates to the given measurement matrix with missing entries, in L₁ norm. With the evolution of the system, the approximation accuracy improves step by step. The system involves a parameter, whose influences on the computational time and the final optimized two low-rank matrices are theoretically studied and experimentally valuated. The efficiency and approximation accuracy of the proposed algorithm are demonstrated by a large number of numerical tests on synthetic data and by two real datasets. Compared with state-of-the-art algorithms, the newly proposed one is competitive.     

Discriminative low-rank representation with Schatten-p norm for image recognition

Low-rank representation (LRR) has attracted much attention recently due to its efficacy in a rich variety of real world applications. Recently, the non-convex regularization has become widely used in the rank minimization problem. In this paper, we propose a discriminative low-rank representation with Schatten-p norm (DLRR-SPN) to learn a robust and discriminative affinity matrix for image recognition. To this end, we first impose the Schatten-p norm regularization on the representation matrix to learn the global structure of data. Moreover, the adaptive distance penalty is used to preserve the local neighbor relationship of data. The objective function is formulated as a Schatten-p norm minimization problem, which can be solved via alternating direction method of multipliers (ADMM). To enhance the separation ability of the discriminative affinity matrix for semi-supervised recognition problem, the angular information of the principal directions of the low-rank representation is further exploited. Finally, an effective semi-supervised classifier is utilized on the learned affinity matrix for final prediction. Extensive experimental results on image recognition demonstrate the effectiveness of the proposed method and its superiority in performance over the related state-of-the-art methods.

     

Switching linear parameter‐varying control with improved local performance and optimized switching surfaces

This paper presents a novel approach to designing switching linear parameter‐varying (SLPV) controllers with improved local performance and an algorithm for optimizing switching surfaces to further improve the performance of the SLPV controllers. The design approach utilizes the weighted average of the local L₂‐gain bounds (representing the local performance) as the cost function to be minimized, whereas the maximum of the local L₂‐gain bounds (representing the worst‐case performance over all subsets) is bounded with a tuning parameter. The tuning parameter is useful for taking the trade‐off between the local performance and the worst‐case performance. An algorithm based on the particle swarm optimization is introduced to optimize the switching surfaces of an SLPV controller. The efficacy of the proposed SLPV controller design approach and switching surface optimization algorithm is demonstrated on both a numerical example and a physical example of air‐fuel ratio control of an automotive engine.     

Reliable Location and Regression Estimates with Application to Range Image Segmentation

Range images provide important sources of information in many three-dimensional robot vision problems such as navigation and object recognition. Many physical factors, however, introduce noise to the discrete measurements in range images, identifying the need to reassess the error distribution in samples taken from real range images. This paper suggests the use of the L _p norms to yield reliable estimates of location and regression coefficients. This particular approach is compared against two commonly used approaches: Equally Weighted Least Squares, which minimizes the L₂ norm; and the Chebychev approximation, which minimizes the L ₁ norm. The problem is a weighted least squares case where the weights are derived from the chosen parameter, p, and its ability to yield a variety of location estimates spanning from the sample mean to the sample median. These two estimates have a wide application in image processing that includes noise removal. This paper will show the problems associated with these two techniques, and suggest experimental solutions to minimize them. A specific operating range is determined in which the L _p norms perform well and a regression module is used in conjunction with a region-growing segmentation algorithm to provide a reliable partition of range images.     

A comment on ‘ self-tuning pole/zero assignment regulators’

The generalized H ₂ optimal control problem for a linear time-invariant system is one in which the conventional H ₂ norm is replaced by an operator norm. The closed-loop system is described in terms of a mapping between the space of time-domain input disturbances in L ₂ and the space of time-domain regulated outputs in L _∞. A minimum of this norm is then sought over all stabilizing controllers. It is shown that optimal controllers for such problems have the structure of a Kalman filter with estimated state feedback, where the feedback gains are obtained from the solution to a weighted LQR problem. A computational algorithm is presented to determine the weights in this LQR problem, and examples are given which demonstrate various problems which may arise in obtaining the optimal weights. In particular, it is shown that the generalized H ₂ problem may involve the solution to a singular LQR problem.     

Refinements to nearest-neighbor searching ink-dimensional trees

This note presents a simplification and generalization of an algorithm for searchingk-dimensional trees for nearest neighbors reported by Friedmanet al [3]. If the distance between records is measured usingL ₂ , the Euclidean norm, the data structure used by the algorithm to determine the bounds of the search space can be simplified to a single number. Moreover, because distance measurements inL ₂ are rotationally invariant, the algorithm can be generalized to allow a partition plane to have an arbitrary orientation, rather than insisting that it be perpendicular to a coordinate axis, as in the original algorithm. When ak-dimensional tree is built, this plane can be found from the principal eigenvector of the covariance matrix of the records to be partitioned. These techniques and others yield variants ofk-dimensional trees customized for specific applications.It is wrong to assume thatk-dimensional trees guarantee that a nearest-neighbor query completes in logarithmic expected time. For smallk, logarithmic behavior is observed on all but tiny trees. However, for largerk, logarithmic behavior is achievable only with extremely large numbers of records. Fork = 16, a search of ak-dimensional tree of 76,000 records examines almost every record.     

Output feedback design for saturated linear plants using deadzone loops

In this paper, we present an LMI-based synthesis approach on output feedback design for input saturated linear systems by using deadzone loops. Algorithms are developed for minimizing the upper bound on the regional L₂ gain for exogenous inputs with L₂ norm bounded by a given value, and for minimizing this upper bound with a guaranteed reachable set or domain of attraction. The proposed synthesis approach will always lead to regionally stabilizing controllers if the plant is exponentially unstable, to semi-global results if the plant is non-exponentially unstable, and to global results if the plant is already exponentially stable, where the only requirement on the linear plant is detectability and stabilizability. The effectiveness of the proposed techniques is illustrated with one example.     

L2 − L∞ Consensus Control for High‐Order Multi‐Agent Systems with Nonuniform Time‐Varying Delays

This paper considers consensus problem for high‐order multi‐agent systems with dynamically changing topologies and nonuniform time‐varying delays. By means of the tree‐type transformation approach, the model transformation is conducted and the consensus problem is converted into an L₂ ? L_∞ control problem of equivalent reduced‐order systems. Furthermore, a Lyapunov‐Krasovkii function is constructed for stability analysis and sufficient conditions in terms of linear matrix inequalities are derived to ensure the consensus with the prescribed L₂ ? L_∞ performance. A numerical simulation is provided to verify the correctness of the theoretical results.     

Polygonal approximation of planar curves in the L 1 norm

An algorithm for obtaining a polygonal approximation in the L ₁, norm of a plane curve of arbitrary shape is presented. The L ₁ error norm in any segment is not to exceed a pre-assigned value. The given curve is first digitized and the algorithm is then applied to the discrete points. The algorithm uses linear programming techniques which makes it efficient and fast. Numerical results and comments are given.     

Piece wise linear least–squares approximation of planar curves

Two algorithms for solving the piecewise linear least–squares approximation problem of plane curves are presented. The first is for the case when the L ₂ residual (error) norm in any segment is not to exceed a pre–assigned value. The second algorithm is for the case when the number of segments is given and a (balanced) L ₂ residual norm solution is required. The given curve is first digitized and either algorithm is then applied to the discrete points. For each segment, we obtain the upper triangular matrix R in the QR factorization of the (augmented) coefficient matrix of the resulting system of linear equations. The least–squares solutions are calculated in terms of the R (and Q) matrices. The algorithms then work in an iterative manner by updating the least–squares solutions for the segments via up dating the R matrices. The calculation requires as little computational effort as possible. Numerical results and comments are given. This, in a way, is a tutorial paper.     

Robust H∞ control for uncertain singular systems with state delay

This paper addresses the problem of robust H_∞ control for uncertain continuous singular systems with state delay. The singular system under consideration involves state time delay and time‐invariant norm‐bounded uncertainty. Based on the linear matrix inequality (LMI) approach, we design a memoryless state feedback controller law, which guarantees that, for all admissible uncertainties, the resulting closed‐loop system is not only regular, impulse free and stable, but also meets an H_∞‐norm bound constraint on disturbance attenuation. A numerical example is provided to demonstrate the applicability of the proposed method. Copyright © 2003 John Wiley & Sons, Ltd.