In this paper, the problem of one-bit compressed sensing (OBCS) is formulated as a problem in probably approximately correct (PAC) learning. It is shown that the Vapnik-Chervonenkis (VC-) dimension of the set of half-spaces in $\R^n$ generated by $k$-sparse vectors is bounded below by $k ( \lfloor\lg (n/k) \rfloor +1 )$ and above by $\lfloor 2k \lg (en) \rfloor $. By coupling this estimate with well-established results in PAC learning theory, we show that a consistent algorithm can recover a $k$-sparse vector with $O(k \lg n)$ measurements, given only the signs of the measurement vector. This result holds for \textit{all} probability measures on $\R^n$. The theory is also applicable to the case of noisy labels, where the signs of the measurements are flipped with some unknown probability.

In this paper we introduce a new optimization formulation for sparse regression and compressed sensing, called CLOT (Combined L-One and Two), wherein the regularizer is a convex combination of the $\ell_1$- and $\ell_2$-norms. This formulation differs from the Elastic Net (EN) formulation, in which the regularizer is a convex combination of the $\ell_1$- and $\ell_2$-norm squared. It is shown that, in the context of compressed sensing, the EN formulation does not achieve robust recovery of sparse vectors, whereas the new CLOT formulation achieves robust recovery. Also, like EN but unlike LASSO, the CLOT formulation achieves the grouping effect, wherein coefficients of highly correlated columns of the measurement (or design) matrix are assigned roughly comparable values. It is already known LASSO does not have the grouping effect. Therefore the CLOT formulation combines the best features of both LASSO (robust sparse recovery) and EN (grouping effect). The CLOT formulation is a special case of another one called SGL (Sparse Group LASSO) which was introduced into the literature previously, but without any analysis of either the grouping effect or robust sparse recovery. It is shown here that SGL achieves robust sparse recovery, and also achieves a version of the grouping effect in that coefficients of highly correlated columns belonging to the same group of the measurement (or design) matrix are assigned roughly comparable values.

Inferring gene regulatory networks (GRNs) from high-throughput gene-expression data is an important and challenging problem in systems biology. Several existing algorithms formulate GRN inference as a regression problem. The available regression based algorithms are based on the assumption that all regulatory interactions are linear. However, nonlinear transcription regulation mechanisms are common in biology. In this work, we propose a new regression based method named bLARS that permits a variety of regulatory interactions from a predefined but otherwise arbitrary family of functions. On three DREAM benchmark datasets, namely gene expression data from E. coli, Yeast, and a synthetic data set, bLARS outperforms state-of-the-art algorithms in the terms of the overall score. On the individual networks, bLARS offers the best performance among currently available similar algorithms, namely algorithms that do not use perturbation information and are not meta-algorithms. Moreover, the presented approach can also be utilized for general feature selection problems in domains other than biology, provided they are of a similar structure.

Classification tasks involving high dimensional vectors are affected by the curse of dimensionality requiring large amount of training data. This is because a high-dimensional space with a modest number of samples is mostly empty. To overcome this we employ the principle of Projection Pursuit. The principle is motivated by the aim to search for clusters in high-dimensional space. Data points are projected onto an appropriate projection direction. Search for clusters is in this single dimensional projection space. As a result inherent sparsity of the high-dimensional space is avoided. Classical discriminant analysis methods also seek clusters but require class labels to be specified. One such technique, the Fisher's Linear Discriminant (FLD) method, has been used to arrive at an unsupervised algorithm that seeks bimodal projection directions.

In this paper, a new notion of learnability is introduced, referred to as learnability with prior information (w.p.i.). This notion is weaker than the standard notion of PAC (probably approximately correct) learnability which has been much studied during recent years. A property called "dispersability" is introduced, and it is shown that dispersability plays a key role in the study of learnability w.p.i. Specifically, dispersability of a function class is always a sufficient condition for the function class to be learnable; moreover, in the case of concept classes, dispersability is also a necessary condition for learnability w.p.i. Thus in the case of learnability w.p.i., the dispersability property plays a role similar to the finite metric entropy condition in the case of PAC learnability with a fixed distribution. It is further shown in the paper that, if a function class consists of measurable functions mapping a separable metric space into a compact subset of R, then such a function class is automatically learnable w.p.i. In particular, any collection of measurable subsets of R/sup n/, for any integer n, is automatically learnable w.p.i. Next, the notion of learnability w.p.i. Is extended to the distribution-free situation, and it is shown that a property called d.f. dispersability (introduced here) is always a sufficient condition for d.f. learnability w.p.i., and is also a necessary condition for d.f. learnability in the case of concept classes.

In this paper we examine a technique by which fault tolerance can be embedded into a feedforward network leading to a network tolerant to the loss of a node and its associated weights. The fault tolerance problem for a feedforward network is formulated as a constrained minimax optimization problem. Two different methods are used to solve it. In the first method, the constrained minimax optimization problem is converted to a sequence of unconstrained least-squares optimization problems, whose solutions converge to the solution of the original minimax problem. An efficient gradient-based minimization technique, specially tailored for nonlinear least-squares optimization, is then applied to perform the unconstrained minimization at each step of the sequence. Several modifications are made to the basic algorithm to improve its speed of convergence. In the second method a different approach is used to convert the problem to a single unconstrained minimization problem whose solution very nearly equals that of the original minimax problem. Networks synthesized using these methods, though not always fault tolerant, exhibit an acceptable degree of partial fault tolerance.

In this paper, uniformly consistent estimation (learnability) of decision rules for pattern classification under a family of probability measures is investigated. In particular, it is shown that uniform boundedness of the metric entropy of the class of decision rules is both necessary and sufficient for learnability under each of two conditions: (i) the family of probability measures is totally bounded, with respect to the total variation metric, and (ii) the family of probability measures contains an interior point, when equipped with the same metric. In particular, this shows that insofar as uniform consistency is concerned, when the family of distributions contains a total variation neighborhood, nothing is gained by this knowledge about the distribution. Then two sufficient conditions for learnability are presented. Specifically, it is shown that learnability with respect to each of a finite collection of families of probability measures implies learnability with respect to their union; also, learnability with respect to each of a finite number of measures implies learnability with respect to the convex hull of the corresponding families of uniformly absolutely continuous probability measures.

The author analyzes the number, location, and stability behavior of the equilibria of arbitrary nonlinear neural networks without resorting to energy arguments based on assumptions of symmetric interactions or no self-interactions. The class of networks studied consists of very general continuous-time continuous-state (CTCS) networks that contain the standard Hopfield network as a special case. The emphasis is on the case where the slopes of the sigmoidal nonlinearities become larger and larger.

All articulated robots suffer from the adverse effects of gravity loading, namely, increased actuator size and degraded performance. It is pointed out that parallelogram linkage manipulators are uniquely suited for counterbalancing technique due to the decoupled nature of gravity terms in their dynamic equations. The authors present a novel parallelogram linkage configuration where the two actuated degrees-of-freedom in the vertical plane are gravity compensated using torsional springs. They show that the robot design is thus improved in two ways: the peak torques required to be output by the actuators are reduced, thereby allowing smaller motors to be selected; and by ensuring that the equilibrium position for all robot joints assumes a safe configuration on power-off, i.e. a position where the robot links do not collide with one another or with other objects, the need for fail-safe brakes is eliminated. A three-degree-of-freedom direct drive robot using the proposed configuration is under development at the Centre for Artificial Intelligence and Robotics to demonstrate the feasibility of these concepts.>

Dynamic equations are derived for a class of multilink manipulators with the last link flexible. The manipulators have three degrees of freedom and are moved by three actuators. This class includes the elbow manipulator and the five-bar-linkage manipulator. Some reasonable assumptions that simplify the dynamic equations for control purposes are described, and the simplified dynamic equations are then presented. It is shown that, for pick-and-place operations, a rigid-body robot controller and a single flexible link controller may be combined to control the manipulator in a straightforward manner.>

A nonlinear control strategy for a large class of multilink manipulators with one flexible link is proposed. The design is based on a transformation which almost linearizes the system. A nonlinear observer is proposed, and it is shown that combining this observer with the proposed nonlinear controller results in a system which is input/output stable in a local sense. >

A modified output consisting of the reflected tip position is analyzed. It is shown that, for an arbitrary beam, the transfer function from the base torque to the derivative of the modified output is passive when the hub inertia is very large compared to the beam inertia. In addition, it is shown that for a uniform beam, the same result also holds when the hub inertia is very small compared to the beam inertia. With the modified output, flexible beams can be easily controlled using quite simple control strategies such as PD control.>

The problem of generating a path between any two points for a point object in a 2D plane filled with unknown obstacles of arbitrary shapes is discussed. This problem is termed P1. The issue of worst-case path lengths is analysed in a general setting, independent of any particular algorithm. It is shown that there are two distinct approaches available to solve P1, dividing the set of all possible algorithms that solve P1 into two disjoint classes. The minimum worst-case path length possible in each class is determined and the universal lower bound on the worst case path length of any algorithm is found. The results are shown to be useful in developing algorithms and more general problem models.>

One method of controlling a flexible beam is H/sub 2/ optimal compensation, which minimizes the mean square tracking error for a particular reference input. However, for many flexible beams the H/sub 2/ optimal compensator requires plant input magnitudes that are unrealizable. To avoid this difficulty, constrained H/sub 2/ optimal compensation is used which requires that the plant input not exceed a certain value. An algorithm based on stable factorization and a Lagrangian multiplier has been developed to solve this problem. A further difficulty in controlling flexible beams is that the usual output definition of the beam does not have a well defined model. Previous work has shown that an alternative output definition does have a well defined model. Experimental results indicate that by applying the algorithm to either model an excellent controller can be obtained.>

It is demonstrated that, for an appropriately chosen output variable, the transfer function for some single flexible links can be considered to be passive. Therefore, by the passivity theorem, using any strictly passive controller with finite gain will result in an L/sub 2/-stable system. One approach to designing such a controller is outlined, and experimental results are presented. The implications of this work are examined and future research issues are discussed.>

A nonheuristic path planning for moving a point object, or mobile automation (MA), in a two-dimensional plane, amidst unknown obstacles, is considered. A path is to be generated, point by point, using only the local information, like the MA's current position and whether it is in contact with an obstacle. A path-planning algorithm to solve this problem is proposed. The algorithm is used to realize the smallest worst-case path length possible in its category. The procedure for the algorithm is presented with explanations. Its various characteristics, such as local cycle creation, worst-case path length, target reachability conditions, etc. are dealt with. Its performance is compared with that of the existing algorithms. Examples showing the operation of the algorithm are presented. >

The problem of designing a neural network which will give the correct binary representation of any given real number is studied. The proposed neural network almost always has a single, globally attractive, asymptotically stable equilibrium, regardless of the input current. Hence, irrespective of the initial conditions of the network, it will always yield a correct binary representation of the given input

The author analyzes the dynamic behavior of neural networks which consist of a set of sigmoid nonlinearities with linear interconnections, without assuming that the interconnections are symmetric or that there are no self-interactions. By eliminating these assumptions, the effects of imperfect implementation on the behavior of Hopfield networks can be studied. If one views the neural network as evolving on ann-dimensional hypercube, H=(0, 1)n. Thus, nearly complete solutions approach an equilibrium in a corner, irrespective of the initial condition. However, this might not be the correct equilibrium. As an illustration, the analog-to-digital converter proposed by Tank and Hopfield is analyzed using the methods developed

The authors examine some issues in the transfer function modeling of a single flexible link. Using the assumed-modes approach, it is possible to find the transfer function between the torque input and the net tip deflection. It is shown that when the number of modes is increased for more accurate modeling, the relative degree of the transfer function becomes ill-defined. This can greatly affect the performance of a controller designed using the model. In addition, any attempt to identify the transfer function is also affected. An alternative approach that uses the rigid body deformations minus the elastic deformations as the output is proposed. This solves the above problems and results in a transfer function with a well-defined relative degree of two. Even if three or four vibration modes are used, the leading coefficient in the numerator is much larger with the proposed new output.>

The optimal trajectory planning problem for planar n-link (n=2,3) revolute manipulators in the presence of obstacles is considered. A method for modeling the obstacles is proposed. Through the proposed method, closed-form approximations of obstacles in terms of the generalized coordinates of the manipulator are obtained. These expressions are then used to formulate the optimal trajectory planning problem as an optimal control problem in constrained state space. The resulting optimal control problem is then solved numerically.>

A single-link flexible beam is an infinite-dimensional system. A full-order model containing all the modes of the system within the bandwidth of the actuator and sensors is presented. Such a model would result in a high-order controller which may not be feasible to implement in practice. Hence, a low-order model for the system is obtained using Hankel norm minimization. A controller is designed for the beam on the basis of the reduced-order model thus obtained. Experimental results show that a controller designed for the reduced-order model guarantees effective vibration control of the flexible beam.>

A model of a five-bar-linkage root is examined where the top link is flexible. The modeling process is described and applied to the simpler problem of a single link beam. The model of the five-bar-linkage robot with the top link flexible is derived and then simplified using various assumptions which are discussed. It is shown that under these assumptions, it may be possible to control two joints using a typical rigid-body controller while using the third joint to control the vibrations. This greatly simplifies the control problem.>

The purpose of this paper is to present some qualitative results related to collision-free path planning in the joint space for a planar n-DOF linkage. It will be shown that if each of the joints of the linkage has full range, then the forbidden regions in the joint space due to obstacles which obstruct only the last link of the linkage are closed surfaces in the joint space. The consequences of limited joint ranges are also discussed. The connectedness of the collision-free joint space for this special case is also studied.

This paper studies the effectiveness of various controller design approaches on a flexible robot arm. The robot arm model used is that of Cannon-Schmitz flexible one-link robot. It is shown that the conventional PI controller cannot stabilize the closed-loop system. The idea of controller design using the stable factorization approach is explored. The controller design procedures, both with and without constraints on the actuator torque are discussed. The simulation results shows better system performance can be achieved by using these controllers instead of conventional LQG controller. The conclusion of this paper is that the stable factorizatlon approach has great potential in the area of flexible robot arm control.

The objective of this paper is to examine the end-point control of a flexible beam using the stable factorization approach. We begin with a description of the experimental setup at the University of Waterloo and discuss the derivation of the state space model of the beam using the method of modal expansions. The model is an eighth order nonminimum phase system with poles on the imaginary axis. The stable factorization approach is used to obtain the optimal step response of the system in the sense that the mean square tracking error is minimized over all the stabilizing controllers. Since the plant is strictly proper, the optimal step response is not realizable and only suboptimal controllers, whose responses approach the optimal step response, can be constructed. First, the one parameter compensator is studied. The results are discussed and the effect of weighting the error is analyzed. A two parameter compensator is also simulated and the result is compared to the one parameter compensator. The paper concludes with suggestions for future research.

The motion control of robotic manipulators is investigated using a recently developed approach to linear multivariable control known as the stable factorization approach. Given a nominal model of the manipulator dynamics, the control scheme consists of an approximate feedback linearizing control followed by a linear compensator design based on the stable factorization approach. Using a multiloop version of the small gain theorem, robust trajectory tracking is shown under the assumption that the deviation of the model from the true system satisfies certain norm inequalities. In turn, these norm inequalities lead to quantifiable bounds on the tracking error.

In this paper we survey some recent developments in nonlinear system theory. The paper is divided into three parts, namely Foundations, Large-Scale Systems, and Geometric Methods. The first provides adequate background to follow the paper, while the other two sections give an overview of two of the more prominent areas of development in nonlinear system theory. Several examples are given at appropriate places, and the references include several useful sources of additional information.

In this paper we investigate the application to the motion control of n-link robotic manipulators of the recently developed stable factorization approach to tracking and disturbance rejection. Given a nominal model of the manipulator dynamics, the control scheme consists of an approximate feedback linearizing control followed by a linear compensator design based on the stable factorization approach to achieve optimal tracking and disturbance rejection. Using a multi-loop version of the small gain theorem [17], the applicability of the linear design techniques and the stability of the closed loop system are rigorously demonstrated.

This work, which is part of the benchmark series in electrical engineering and computer science, is a compilation of the research papers representing the major advances in the area of nonlinear systems stability. It contains a total of 28 papers that pertain to both Lyapunov-like approach applied to ordinary differential equations and functional-analytic approach applied to feedback systems. The papers are categorized into eight parts, listed below.

Parts of this monograph appeared in the author's doctoral dissertation entitled 'Nonlinear harmonic analysis' ... 1968.