Two Related Problems of Redundancy Reduction in Data Representation by Means of Convex Polyhedra

Two problems of data representation by means of convex polyhedra are considered. In the first problem, it is required to exclude from a finite set of points X the points that are not vertices of the convex hull of X. An algorithm based on solving a series of linear programming problems is developed. Its computational complexity is asymptotically lower than the complexity of a convex hull constructing, and it requires much less additional memory than for constructing a convex hull. The second problem consists in finding the minimal subset of inequalities in a system of linear inequalities whose solution set coincides with the solution set of the initial system. It is shown that this problem can be solved similarly to the first one, and the solution algorithm can be extended to the case of nonlinear inequalities. Randomized improved versions of both algorithms are proposed.     

Improved conditioning of finite element matrices using new high-order interpolatory bases

The condition number of finite element matrices constructed from interpolatory bases will grow as the polynomial degree of the basis functions is increased. The worst case scenario for this growth rate is exponential and in this paper we demonstrate through computational example that the traditional set of uniformly distributed interpolation points yields this behavior. We propose a set of nonuniform interpolation points which yield a much improved polynomial growth rate of condition number. These points can be used to construct several types of popular hexahedral basis functions including the 0-form (standard Lagrangian), 1-form (Curl conforming), and 2-form (Divergence conforming) varieties. We demonstrate through computational example the benefits of using these new interpolatory bases in finite element solutions to Maxwell's equations in both the frequency and time domain.     

Exact linear modeling with polynomial coefficients

Given a finite set of polynomial, multivariate, and vector-valued functions, we show that their span can be written as the solution set of a linear system of partial differential equations (PDE) with polynomial coefficients. We present two different but equivalent ways to construct a PDE system whose solution set is precisely the span of the given trajectories. One is based on commutative algebra and the other one works directly in the Weyl algebra, thus requiring the use of tools from non-commutative computer algebra. In behavioral systems theory, the resulting model for the data is known as the most powerful unfalsified model (MPUM) within the class of linear systems with kernel representations over the Weyl algebra, i.e., the ring of differential operators with polynomial coefficients.     

A generalized mass lumping technique for vector finite-element solutions of the time-dependent Maxwell equations

Time-domain finite-element solutions of Maxwell's equations require the solution of a sparse linear system involving the mass matrix at every time step. This process represents the bulk of the computational effort in time-dependent simulations. As such, mass lumping techniques in which the mass matrix is reduced to a diagonal or block-diagonal matrix are very desirable. In this paper, we present a special set of high order 1-form (also known as curl-conforming) basis functions and reduced order integration rules that, together, allow for a dramatic reduction in the number of nonzero entries in a vector finite element mass matrix. The method is derived from the Nedelec curl-conforming polynomial spaces and is valid for arbitrary order hexahedral basis functions for finite-element solutions to the second-order wave equation for the electric (or magnetic) field intensity. We present a numerical eigenvalue convergence analysis of the method and quantify its accuracy and performance via a series of computational experiments.     

Fixed-order robust H/sub /spl infin// filter design for Markovian jump systems with uncertain switching probabilities

This paper discusses the fixed-order robust H/sub /spl infin// filtering problem for a class of Markovian jump linear systems with uncertain switching probabilities. The uncertainties under consideration are assumed to be norm-bounded in the system matrices and to be elementwise bounded in the mode transition rate matrix, respectively. First, a criterion based on linear matrix inequalities is provided for testing the H/sub /spl infin// filtering level of a filter over all the admissible uncertainties. Then, a sufficient condition for the existence of the fixed-order robust H/sub /spl infin// filters is established in terms of the solvability of a set of linear matrix inequalities with equality constraints. To determine the filter, a globally convergent algorithm involving convex optimization is suggested. Finally, a numerical example is used to illustrate that the developed theory is more effective than the existing results.     

Distributed stabilisation of spatially invariant systems: positive polynomial approach

The paper gives a computationally feasible characterisation of spatially distributed controllers stabilising a linear spatially invariant system, that is, a system described by linear partial differential equations with coefficients independent on time and location. With one spatial and one temporal variable such a system can be modelled by a 2-D transfer function. Stabilising distributed feedback controllers are then parametrised as a solution to the Diophantine equation ax + by = c for a given stable bi-variate polynomial c. The paper is built on the relationship between stability of a 2-D polynomial and positiveness of a related polynomial matrix on the unit circle. Such matrices are usually bilinear in the coefficients of the original polynomials. For low-order discrete-time systems it is shown that a linearising factorisation of the polynomial Schur-Cohn matrix exists. For higher order plants and/or controllers such factorisation is not possible as the solution set is non-convex and one has to resort to some relaxation. For continuous-time systems, an analogue factorisation of the polynomial Hermite-Fujiwara matrix is not known. However, for low-order systems and/or controller, positivity conditions on the closed-loop polynomial coefficients can be invoked. Then the computational framework of linear matrix inequalities can be used to describe the stability regions in the parameter space using a convex constraint.     

Algebraic methods for image processing and computer vision

Many important problems in image processing and computer vision can be formulated as the solution of a system of simultaneous polynomial equations. Crucial issues include the uniqueness of solution and the number of solutions (if not unique), and how to find numerically all the solutions. The goal of this paper is to introduce to engineers and scientists some mathematical tools from algebraic geometry which are very useful in resolving these issues. Three-dimensional motion/structure estimation is used as the context. However, these tools should also be helpful in other areas including surface intersection in computer-aided design, and inverse position problems in kinematics/robotics. The tools to be described are Bezout numbers, Grobner bases, homotopy methods, and a powerful theorem which states that under rather general conditions one can draw general conclusions on the number of solutions of a polynomial system from a single numerical example.     

Distributed power control algorithms for wireless networks

Power control has been shown to be an effective way to increase capacity in wireless systems. In previous work on power control, it has been assumed that power levels can be assigned from a continuous range. In practice, however, power levels are assigned from a discrete set. In this work, we consider the minimization of the total power transmitted over given discrete sets of available power levels subject to maintaining an acceptable signal quality for each mobile. We have developed distributed iterative algorithms for solving a more general version of this integer programming problem, which is of independent interest, and have shown that they find the optimal solution in a finite number of iterations which is polynomial in the number of power levels and the number of mobiles     

Robust Dichotomy Analysis and Synthesis With Application to an Extended Chua's Circuit

Dichotomy, or monostability, is one of the most important properties of nonlinear dynamic systems. For a dichotomous system, the solution of the system is either unbounded or convergent to a certain equilibrium, thus periodic or chaotic states cannot exist in the system. In this paper, a new methodology for the analysis of dichotomy of a class of nonlinear systems is proposed, and a linear matrix inequality (LMI)-based criterion is derived. The results are then extended to uncertain systems with real convex polytopic uncertainties in the linear part, and the LMI representation for robust dichotomy allows the use of parameter-dependent Lyapunov function. Based on the results, a dynamic output feedback controller guaranteeing robust dichotomy is designed, and the controller parameters are explicitly expressed by a set of feasible solutions of corresponding linear matrix inequalities. An extended Chua's circuit with two nonlinear resistors is given at the end of the paper to demonstrate the validity and applicability of the proposed approach. It is shown that by investigating the convergence of the bounded oscillating solutions of the system, our results suggests a viable and effective way for chaos control in nonlinear circuits.     

高阶非线性非自治系统分析研究

为了更有效的解决高阶非线性非自治系统的求解问题,提出基于等效小参数法的高阶非线性非自治系统的求解方法,应用分解法原理,通过引入谐波平衡和同阶小量相等,建立一类非线性动态系统周期解的逆算符表达的递推算法,将高阶非线性非自治系统转化成一个通用方程,然后利用Matlab开发出相应的软件系统,实现计算机自动求解。对包含sin（t）或cos（t）的非线性非自治GENESIO系统和非线性非自治COULLET系统使用等效小参数法进行详细推导,分别求解非自治GENESIO系统和非自治COULLET系统的周期解,该算法具有较高的计算精度和较大的普适性,是求解一类非线性非自治系统周期解的有效方法。     

On a Non-homogeneous Singular Linear Discrete Time System with a Singular Matrix Pencil

In this article, we study the initial value problem of a non-homogeneous singular linear discrete time system whose coefficients are either non-square constant matrices or square with an identically zero matrix pencil. By taking into consideration that the relevant pencil is singular, we provide necessary and sufficient conditions for existence and uniqueness of solutions. More analytically we study the conditions under which the system has unique, infinite and no solutions. Furthermore, we provide a formula for the case of the unique solution. Finally we provide some numerical examples based on a singular discrete time real dynamical system to justify our theory.     

Optimal linear codes from matrix groups

New linear codes (sometimes optimal) over the finite field with q elements are constructed. In order to do this, an equivalence between the existence of a linear code with a prescribed minimum distance and the existence of a solution of a certain system of Diophantine linear equations is used. To reduce the size of the system of equations, the search for solutions is restricted to solutions with special symmetry given by matrix groups. This allows to find more than 400 new codes for the case q=2,3,4,5,7,9.     

Robust FIR equalization for time-varying communication channels with intermittent observations via an LMI approach

The optimal design of finite impulse response (FIR) filters for equalization/deconvolution is investigated in this paper. Two practical yet challenging constraints are incorporated into the modeling of the equalization system: (1) The parameters of the communication channel model are arbitrarily time-varying within a polytope with finite known vertices; (2) at the received end, the received signal is usually intermittent due to network-induced packet dropouts which are modeled by a stochastic Bernoulli distribution. Under the stochastic theory framework, a robust design method for the FIR equalizer is proposed such that the equalization system can achieve the prescribed energy-to-peak performance even it is subject to uncertainties, external noise, and data missing. Sufficient conditions for the existence of the equalizer are derived by a set of linear matrix inequalities (LMIs). An illustrative design example demonstrates the design procedure and the effectiveness of the proposed method.     

Every discrete 2D autonomous system admits a finite union of parallel lines as a characteristic set

In this paper, we show that every discrete 2D autonomous system, that is described by a set of linear partial difference equations with constant real coefficients, admits a finite union of parallel lines as a characteristic set. In order to prove our claim, we first look at a special class of scalar discrete 2D systems and provide such characteristic sets for systems in this class. This special class has the property that systems in this class have their quotient rings to be finitely generated modules over a one-variable Laurent polynomial subring of the original two-variable Laurent polynomial ring in the shift operators. We show that such systems always admit a finite collection of horizontal lines for a characteristic set. We then extend this result to non-scalar discrete 2D autonomous systems. We achieve this in two steps: first, we show that every scalar discrete 2D system can be converted into a system in the above-mentioned class by a coordinate transformation on the independent variables set, \(\mathbb {Z}^2\). Using this we then show that characteristic sets for the original system can be found by applying the inverse coordinate transformation on characteristic sets of the transformed system. Since the transformed system, by virtue of being in the special class, admits a finite union of horizontal lines as a characteristic set, the original system is guaranteed to admit a characteristic set that is a coordinate transformation applied to a finite union of horizontal lines. The coordinate transformation maps this union of horizontal lines to a union of parallel, but possibly tilted, lines. In the next step, we generalize the scalar case to the general vector case: that is, systems with more than one dependent variables. The main motivation for studying characteristic sets that are unions of finitely many parallel lines is that, arguably, such sets can be called “thin” in \(\mathbb {Z}^2\) in comparison to the prevalent notions of convex cones and half-spaces as characteristic sets (see “Appendix 1”).     

基于观测概率有效下界估计的二维激光雷达和摄像机标定方法

针对2D激光雷达和摄像机最小解标定方法的多解问题,该文提出一种基于观测概率有效下界估计的标定方法。首先,提出一种最小解集合的分级聚类方法,将每类最优解替换原来的解集合,从而减少解集合样本个数。然后,提出一种基于激光误差的联合观测概率度量,对解集合元素的优劣进行度量。最后,利用聚类结果和观测概率度量结果,该文提出基于观测概率有效下界估计的有效解选取策略,将优化初始值从最优解转化为有效解候选集合,提高了标定结果的准确性。仿真实验结果表明,在真解命中率性能上相比于Francisco方法,该文方法在不同棋盘格个数情况下提升真解命中率16%～20%,在不同噪声水平下提升真解命中率6%～20%,有效提高真解比例。     

The inequalities of quantum information theory

Let /spl rho/ denote the density matrix of a quantum state having n parts 1, ..., n. For I/spl sube/N={1, ..., n}, let /spl rho//sub I/=Tr/sub N/spl bsol/I/(/spl rho/) denote the density matrix of the state comprising those parts i such that i/spl isin/I, and let S(/spl rho//sub I/) denote the von Neumann (1927) entropy of the state /spl rho//sub I/. The collection of /spl nu/=2/sup n/ numbers {S(/spl rho//sub I/)}/sub I/spl sube/N/ may be regarded as a point, called the allocation of entropy for /spl rho/, in the vector space R/sup /spl nu//. Let A/sub n/ denote the set of points in R/sup /spl nu// that are allocations of entropy for n-part quantum states. We show that A~/sub n/~ (the topological closure of A/sub n/) is a closed convex cone in R/sup /spl nu//. This implies that the approximate achievability of a point as an allocation of entropy is determined by the linear inequalities that it satisfies. Lieb and Ruskai (1973) have established a number of inequalities for multipartite quantum states (strong subadditivity and weak monotonicity). We give a finite set of instances of these inequalities that is complete (in the sense that any valid linear inequality for allocations of entropy can be deduced from them by taking positive linear combinations) and independent (in the sense that none of them can be deduced from the others by taking positive linear combinations). Let B/sub n/ denote the polyhedral cone in R/sup /spl nu// determined by these inequalities. We show that A~/sub n/~=B/sub n/ for n/spl les/3. The status of this equality is open for n/spl ges/4. We also consider a symmetric version of this situation, in which S(/spl rho//sub I/) depends on I only through the number i=/spl ne/I of indexes in I and can thus be denoted S(/spl rho//sub i/). In this case, we give for each n a finite complete and independent set of inequalities governing the symmetric allocations of entropy {S(/spl rho//sub i/)}/sub 0/spl les/i/spl les/n/ in R/sup n+1/.     

Scrambler blind recognition method based on soft information

Two scrambler blind recognition methods based on soft information were proposed for received signal in non-cooperative ways.The first method established a cost function of the scrambler coefficients by using the soft information,and adopted the optimization theory of real number field for positive solution.So it didn’t need to traverse the closed set of test polynomial any more.The second method built conformity degree concept with the soft information,and used the size of conformity of each test scrambler polynomial as the discriminant criteria.So it made more full use of the received information compared to the hard sentence recognition algorithm.Simulation results show that the first method can shorten the recognition time of a synchronous scrambler polynomial from 5 min 18 s to 8 s compared with the traversal method put forward by Cluzeau,and the second method has 2 dB SNR gain when to achieve the relatively high accuracy compared with the hard sentence recognition algorithm.     

Signal processing in adaptive arrays using power basis

The development of the theory of adaptive arrays (AAs) is proposed based on the representation of the inverse covariance matrix (CM) of a noise in the AA channels as a finite power series expansion using the direct CM and by representation of a weight vector of the AA as a finite series expansion of the power vectors. The dimension of the power CM basis is equal to the power of the minimum polynomial of the CM. In the case when the number of external interference sources is less than the number of AA channels, such polynomials have the same fundamental role as the characteristic polynomial of the CM in an opposite case. Proofs for the existence of the above mentioned polynomials of the CM are given. A new method for the calculation of the polynomial coefficients is presented, and the physical properties of the power vector basis are studied. It is shown that the power vectors are correlated and that there are two stages of AA signal processing.     

On the theory of the synthesis of single and dual offset shaped reflector antennas

Since Kinber (Radio Technika and Engineering-1963) and Galindo (IEEE Trans. Antennas Propagat.-1963/1964) developed the solution to the circular symmetric dual shaped synthesis problem, the question of existence (and of uniqueness) for offset dual (or single) shaped synthesis has been a point of controversy. Many researchers thought that the exact offset solutions may not exist. Later, Galindo-Israel and Mittra (IEEE Trans. Antennas Propagat.-1979) and others formulated the problem exactly and obtained excellent and numerically efficient but approximate solutions. Using a technique similar to that first developed by Schruben for the single reflector problem (Journal of the Optical Society-1973), Brickell and Westcott (Proc. Institute of Electrical Engineering-1981) developed a Monge-Ampere (MA) second-order nonlinear partial differential equation for the dual reflector problem. They solved an elliptic form of this equation by a technique introduced by Rall (1979) which iterates, by a Newton method, a finite difference linearized MA equation. The elliptic character requires a set of finite difference equations to be developed and solved iteratively. Existence still remained in question. Although the second-order MA equation developed by Schruben is elliptic, the first-order equations from which the MA equation is derived can be integrated progressively (e.g., as for an initial condition problem such as for hyperbolic equations) a noniterative and usually more rapid type solution. In this paper, we have solved, numerically, the first-order equations. Exact solutions are thus obtained by progressive integration. Furthermore, we have concluded that not only does an exact solution exist, but an infinite set of such solutions exists. These conclusions are inferred, in part, from numerical results.     

Dynamical Analysis of Full-Range Cellular Neural Networks by Exploiting Differential Variational Inequalities

The paper considers the full-range (FR) model of cellular neural networks (CNNs) in the case where the neuron nonlinearities are ideal hard-comparator functions with two vertical straight segments. The dynamics of FR-CNNs, which is described by a differential inclusion, is rigorously analyzed by means of theoretical tools from set-valued analysis and differential inclusions. The fundamental property proved in the paper is that FR-CNNs are equivalent to a special class of differential inclusions termed differential variational inequalities. A sound foundation to the dynamics of FR-CNNs is then given by establishing the existence and uniqueness of the solution starting at a given point, and the existence of equilibrium points. Moreover, a fundamental result on trajectory convergence towards equilibrium points (complete stability) for reciprocal standard CNNs is extended to reciprocal FR-CNNs by using a generalized Lyapunov approach. As a consequence, it is shown that the study of the ideal case with vertical straight segments in the neuron nonlinearities is able to give a clear picture and analytic characterization of the salient features of motion, such as the sliding modes along the boundary of the hypercube defined by the hard-comparator nonlinearities. Finally, it is proved that the solutions of the ideal FR model are the uniform limit as the slope tends to infinity of the solutions of a model where the vertical segments in the nonlinearities are approximated by segments with finite slope.