H2 optimal model order reduction on the Stiefel manifold for the MIMO discrete system by the cross Gramian

ABSTRACT

In this paper, the H₂ optimal model order reduction method for the large-scale multiple-input multiple-output (MIMO) discrete system is investigated. First, the MIMO discrete system is resolved into a number of single-input single-output (SISO) subsystems, and the H₂ norm of the original MIMO discrete system is expressed by the cross Gramian of each subsystem. Then, the retraction and the vector transport on the Stiefel manifold are introduced, and the geometric conjugate gradient model order reduction method is proposed. The reduced system of the original MIMO discrete system is generated by using the proposed method. Finally, two numerical examples show the efficiency of the proposed method.     

Cutting Plane Algorithms for Nonlinear Semi-Definite Programming Problems with Applications

We will propose an outer-approximation (cutting plane) method for minimizing a function f X subject to semi-definite constraints on the variables XR ⁿ. A number of efficient algorithms have been proposed when the objective function is linear. However, there are very few practical algorithms when the objective function is nonlinear. An algorithm to be proposed here is a kind of outer-approximation(cutting plane) method, which has been successfully applied to several low rank global optimization problems including generalized convex multiplicative programming problems and generalized linear fractional programming problems, etc. We will show that this algorithm works well when f is convex and n is relatively small. Also, we will provide the proof of its convergence under various technical assumptions.     

A fast matrix–vector multiplication method for solving the radiosity equation

A “fast matrix–vector multiplication method” is proposed for iteratively solving discretizations of the radiosity equation (I — К)u = E. The method is illustrated by applying it to a discretization based on the centroid collocation method. A convergence analysis is given for this discretization, yielding a discretized linear system (I — K _n )u _n = E _n. The main contribution of the paper is the presentation of a fast method for evaluating multiplications K_n v, avoiding the need to evaluate K_n explicitly and using fewer than O(n ²) operations. A detailed numerical example concludes the paper, and it illustrates that there is a large speedup when compared to a direct approach to discretization and solution of the radiosity equation. The paper is restricted to the surface S being unoccluded, a restriction to be removed in a later paper. This revised version was published online in June 2006 with corrections to the Cover Date.     

Difference of two sets and estimation of clarke generalized Jacobian via quasidifferential

The notion of difference for two convex compact sets inR ⁿ , proposed by Rubinovet al, is generalized toR ^m×n . A formula of the difference for the two sets, which are convex hulls of a finite number of points, is developed. In the light of this difference, the relation between Clarke generalized Jacobian and quasidifferential, in the sense of Demyanov and Rubinov, for a nonsnooth function, is established. Based on the relation, the method of estimating Clarke generalized Jacobian via quasidifferential for a certain class of functions, is presented.     

Approximating conditional density functions using dimension reduction

We propose to approximate the conditional density function of a random variable Y given a dependent random d-vector X by that of Y given θ^τX, where the unit vector θ is selected such that the average Kullback-Leibler discrepancy distance between the two conditional density functions obtains the minimum. Our approach is nonparametric as far as the estimation of the conditional density functions is concerned. We have shown that this nonparametric estimator is asymptotically adaptive to the unknown index θ in the sense that the first order asymptotic mean squared error of the estimator is the same as that when θ was known. The proposed method is illustrated using both simulated and real-data examples.     

Approximate multiplication of tensor matrices based on the individual filtering of factors

Algorithms are proposed for the approximate calculation of the matrix product $ \tilde C $ \tilde C ≈ C = A · B, where the matrices A and B are given by their tensor decompositions in either canonical or Tucker format of rank r. The matrix C is not calculated as a full array; instead, it is first represented by a similar decomposition with a redundant rank and is then reapproximated (compressed) within the prescribed accuracy to reduce the rank. The available reapproximation algorithms as applied to the above problem require that an array containing r ^2d elements be stored, where d is the dimension of the corresponding space. Due to the memory and speed limitations, these algorithms are inapplicable even for the typical values d = 3 and r ∼ 30. In this paper, methods are proposed that approximate the mode factors of C using individually chosen accuracy criteria. As an application, the three-dimensional Coulomb potential is calculated. It is shown that the proposed methods are efficient if r can be as large as several hundreds and the reapproximation (compression) of C has low complexity compared to the preliminary calculation of the factors in the tensor decomposition of C with a redundant rank.     

A continuous method for computing bounds in integer quadratic optimization problems

In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x ^T Q x where Q is an n × n real symmetric matrix with x an n-dimensional vector constrained to be an element of {–1, 1} ⁿ . We had proposed a technique for obtaining upper bounds on solutions to the problem using a continuous approach in [4]. In this paper, we extend this method by using techniques of differential geometry.     

Homogenization of integrals with pointwise gradient constraints via the periodic unfolding method

Abstract The pointwise gradient constrained homogenization process, for Neumann and Dirichlet type problems, is analyzed by means of the periodic unfolding method recently introduced in [21]. Classically, the proof of the homogenization formula in presence of pointwise gradient constraints relies on elaborated measure theoretic arguments. The one proposed here is elementary: it is based on weak convergence arguments in L^p spaces, coupled with suitable regularization techniques. Keywords: Homogenization, Gradient constrained problems, Periodic unfolding method Mathematics Subject Classification (2000): 49J45, 35B27, 74Q05     

An alternating iterative method and its application in statistical inference

This paper studies non-convex programming problems. It is known that, in statistical inference, many constrained estimation problems may be expressed as convex programming problems. However, in many practical problems, the objective functions are not convex. In this paper, we give a definition of a semi-convex objective function and discuss the corresponding non-convex programming problems. A two-step iterative algorithm called the alternating iterative method is proposed for finding solutions for such problems. The method is illustrated by three examples in constrained estimation problems given in Sasabuchi et al. （Biometrika, 72, 465472 （1983））, Shi N. Z. （J. Multivariate Anal., 50, 282-293 （1994）） and El Barmi H. and Dykstra R. （Ann. Statist., 26, 1878 1893 （1998））.     

Toward the Calculation of Higher-Dimensional Stable Manifolds and Stable Sets for Noninvertible and Piecewise-Smooth Maps

This paper presents a new numerical method for computing global stable manifolds and global stable sets of nonlinear discrete dynamical systems. For a given map f:ℝ ^d →ℝ ^d , the proposed method is capable of yielding large parts of stable manifolds and sets within a certain compact region M⊂ℝ ^d . The algorithm divides the region M in sets and uses an adaptive subdivision technique to approximate an outer covering of the manifolds. In contrast to similar approaches, the method requires neither the system’s inverse nor its Jacobian. Hence, it can also be applied to noninvertible and piecewise-smooth maps. The successful application of the method is illustrated by computation of one- and two-dimensional stable manifolds and global stable sets.     

Estimation in Linear Models with Random Effects and Errors-in-Variables

The independent variables of linear mixed models are subject to measurement errors in practice. In this paper, we present a unified method for the estimation in linear mixed models with errors-in-variables, based upon the corrected score function of Nakamura (1990, Biometrika, 77, 127–137). Asymptotic normality properties of the estimators are obtained. The estimators are shown to be consistent and convergent at the order of n ^–1/2. The performance of the proposed method is studied via simulation and the analysis of a data set on hedonic housing prices.     

Band plus algebra preconditioners for two-level Toeplitz systems

In this paper we are interested in the fast and efficient solution of nm×nm symmetric positive definite ill-conditioned Block Toeplitz with Toeplitz Blocks (BTTB) systems of the form T _nm (f)x=b, where the generating function f is a priori known. The preconditioner that we propose and analyze is an extension of the one proposed in (D. Noutsos and P. Vassalos, Comput. Math. Appl., 56 (2008), pp. 1255–1270) and it arises as a product of a Block band Toeplitz matrix and matrices that may belong to any trigonometric matrix algebra. The underlying idea of the proposed scheme is to embody the well known advantages characterizing each component of the product when used alone. As a result we obtain spectral equivalence and a weak clustering of the eigenvalues of the preconditioned matrix around unity, ensuring the convergence of the Preconditioned Conjugate Gradient (PCG) method with a number of iterations independent of the partial dimensions. Finally, we compare our method with techniques already employed in the literature. A wide range of numerical experiments confirms the effectiveness of the proposed procedure and the adherence to the theoretical analysis.     

Fast Wavelet Transform for Toeplitz Matrices and Property Analysis

Fast wavelet transform algorithms for Toeplitz matrices are proposed in this paper. Distinctive from the well known discrete trigonometric transforms, such as the discrete cosine transform （DCT） and the discrete Fourier transform （DFT） for Toeplitz matrices, the new algorithms are achieved by compactly supported wavelet that preserve the character of a Toeplitz matrix after transform, which is quite useful in many applications involving a Toeplitz matrix. Results of numerical experiments show that the proposed method has good compression performance similar to using wavelet in the digital image coding. Since the proposed algorithms turn a dense Toeplitz matrix into a band-limited form, the arithmetic operations required by the new algorithms are O（N） that are reduced greatly compared with O（N log N） by the classical trigonometric transforms.     

Nonlinear Periodic Optimal Control: A Pseudospectral Fourier Approach

Abstract

A pseudospectral method for generating optimal trajectories of the class of periodic optimal control problems is proposed. The method consists of representing the solution of the periodic optimal control problem by an mth degree trigonometric interpolating polynomial, using Fourier nodes as grid points, and then discretizing the problem using the trapezoidal rule as the quadrature formula for smoothly differentiable periodic functions. The periodic optimal control problem is thereby transformed into an algebraic nonlinear programming problem. Due to its dynamic nature, the pseudospectral Fourier approach avoids many of the numerical difficulties typically encountered in solving standard periodic optimal control problems. An illustrative example is provided to demonstrate the applicability of the proposed method.     

Modified High-order Upwing Method for Convection Diffusion Equation

Abstract   In this paper, we study the high-order upwind finite difference method for steady convection-diffusion problems. Based on the conservative convection-diffusion equation, a high-order upwind finite difference scheme on nonuniform rectangular partition for convection-diffusion equation is proposed. The proposed scheme is in conversation form, satisfies maximum value principle and has second-order error estimates in discrete H ¹ norm. To illustrate our conclusion, several numerical examples are given. Supported by the Research Fund for Doctoral Program of High Education of China State Education Commission.     

The limiting normality of the test statistic for the two-sample problem induced by a convex sum distance

Critchlow (1992, J. Statist. Plann. Inference, 32, 325–346) proposed a method of a unified construction of a class of rank tests. In this paper, we introduce a convex sum distance and prove the limiting normality of the test statistics for the two-sample problem derived by his method.     

Importance Link Function Estimation for Markov Chain Monte Carlo Methods

Abstract

This article focuses on improving estimation for Markov chain Monte Carlo simulation. The proposed methodology is based upon the use of importance link functions. With the help of appropriate importance sampling weights, effective estimates of functionals are developed. The method is most easily applied to irreducible Markov chains, where application is typically immediate. An important conceptual point is the applicability of the method to reducible Markov chains through the use of many-to-many importance link functions. Applications discussed include estimation of marginal genotypic probabilities for pedigree data, estimation for models with and without influential observations, and importance sampling for a target distribution with thick tails.     

Weighted Kaplan-Meier Tests for Umbrella Alternatives

The problem of testing for umbrella alternatives in a one-way layout with right-censored survival data is considered. Testing procedures based on the two-sample weighted Kaplan-Meier statistics suggested by Pepe and Fleming (1989, Biometrics, 45, 497–507; 1991, J. Roy. Statist. Soc. Ser. B, 53, 341–352) are suggested for both cases when the peak of the umbrella is known or unknown. The asymptotic relative efficiency of the weighted Kaplan-Meier test and the weighted logrank test proposed by Chen and Wolfe (2000, Statist. Sinica, 10, 595–612) is computed for the umbrella peak-known setting where the piecewise exponential survival distributions have the proportional or crossing hazards, or the related hazards differ at early or late times. Moreover, the results of a Monte Carlo study are presented to investigate the level and power performances of the umbrella tests. Finally, application of the proposed procedures to an appropriated data set is illustrated.     

On Nearest Neighbor Classification Using Adaptive Choice of k

Nearest neighbor classification is one of the simplest and popular methods for statistical pattern recognition. It classifies an observation x to the class, which is the most frequent in the neighborhood of x. The size of this neighborhood is usually determined by a predefined parameter k. Normally, one uses cross-validation techniques to estimate the optimum value of this parameter, and that estimated value is used for classifying all observations. However, in classification problems, in addition to depending on the training sample, a good choice of k depends on the specific observation to be classified. Therefore, instead of using a fixed value of k over the entire measurement space, a spatially adaptive choice of k may be more useful in practice. This article presents one such adaptive nearest neighbor classification technique, where the value of k is selected depending on the distribution of competing classes in the vicinity of the observation to be classified. The utility of the proposed method has been illustrated using some simulated examples and well-known benchmark datasets. Asymptotic optimality of its misclassification rate has been derived under appropriate regularity conditions.     

CHESS—Changing Horizon Efficient Set Search: A Simple Principle for Multiobjective Optimization

This paper presents a new concept for generating approximations to the non-dominated set in multiobjective optimization problems. The approximation set A is constructed by solving several single-objective minimization problems in which a particular function D(A, z) is minimized. A new algorithm to calculate D(A, z) is proposed.No general approach is available to solve the one-dimensional optimization problems, but metaheuristics based on local search procedures are used instead. Tests with multiobjective combinatorial problems whose non-dominated sets are known confirm that CHESS can be used to approximate the non-dominated set. Straightforward parallelization of the CHESS approach is illustrated with examples.The algorithm to calculate D(A, z) can be used in any other applications that need to determine Tchebycheff distances between a point and a dominant-free set.