Dimensionality Reduction with Subgaussian Matrices: A Unified Theory

We present a theory for Euclidean dimensionality reduction with subgaussian matrices which unifies several restricted isometry property and Johnson–Lindenstrauss-type results obtained earlier for specific datasets. In particular, we recover and, in several cases, improve results for sets of sparse and structured sparse vectors, low-rank matrices and tensors, and smooth manifolds. In addition, we establish a new Johnson–Lindenstrauss embedding for datasets taking the form of an infinite union of subspaces of a Hilbert space.     

Computer-assisted Modelling and Analysis of Linear Programming Problems: Towards a Unified Framework

A framework for model formulation and analysis to support operationsand management of large-scale linear programs is developed fromthe combined capabilities of CAMPS and ANALYZE. Both the systemsare reviewed briefly and the interface which integrates thetwo systems is then described. The model formulation, matrixgeneration, and model management capability of CAMPS and thecomplementary model and solution analysis capability of ANALYZEare presented within a unified framework. Relevant generic functionsare highlighted, and an example is presented in detail to illustratethe level of integration achieved in the current prototype system.Some new results on discourse models and model management supportare given in a framework designed to move toward an ‘intelligent’system for linear programming modelling and analysis.     

A Geometric Programming Framework for Univariate Cubic L 1 Smoothing Splines

Univariate cubic L ₁ smoothing splines are capable of providing shape-preserving C ¹-smooth approximation of multi-scale data. The minimization principle for univariate cubic L ₁ smoothing splines results in a nondifferentiable convex optimization problem that, for theoretical treatment and algorithm design, can be formulated as a generalized geometric program. In this framework, a geometric dual with a linear objective function over a convex feasible domain is derived, and a linear system for dual to primal conversion is established. Numerical examples are given to illustrate this approach. Sensitivity analysis for data with uncertainty is presented. This work is supported by research grant #DAAG55-98-D-0003 of the Army Research Office, USA.     

稀疏数据非线性降维的CN-Isomap算法

针对经典的流形学习算法Isomap在非线性数据稀疏时降维效果下降甚至失效的问题,提出改进的切近邻等距特征映射算法(Cut-Neighbors Isometric feature mapping,CN-Isomap).该算法在数据稀疏的情况下首先通过有效识别样本点的"流形邻居"来剔除近邻图上的"短路"边,然后再通过最短路径算法拟合测地线距离,使得拟合的测地线距离不会偏离流形区域,从而低维嵌入映射能够正确地反映高维输入空间样本点间的内在拓扑特征,很好地发现蕴含在高维空间里的低维流形,有效地对非线性稀疏数据进行降维.通过对Benchmark数据集的实验表明了算法的有效性.CN-Isomap算法是Isomap算法的推广,不仅能有效地对非线性稀疏数据进行降维,同样也适用于数据非稀疏的情况.     

A Unified Monotonic Approach to Generalized Linear Fractional Programming

We present an efficient unified method for solving a wide class of generalized linear fractional programming problems. This class includes such problems as: optimizing (minimizing or maximizing) a pointwise maximum or pointwise minimum of a finite number of ratios of linear functions, optimizing a sum or product of such ratios, etc. – over a polytope. Our approach is based on the recently developed theory of monotonic optimization.     

Unified Framework of Extragradient-Type Methods for Pseudomonotone Variational Inequalities

In this paper, we propose a unified framework of extragradient-type methods for solving pseudomonotone variational inequalities, which allows one to take different stepsize rules and requires the computation of only two projections at each iteration. It is shown that the modified extragradient method of Ref. 1 falls within this framework with a short stepsize and so does the method of Ref. 2 with a long stepsize. It is further demonstrated that the algorithmic framework is globally convergent under mild assumptions and is sublinearly convergent if in addition a projection-type error bound holds locally. Preliminary numerical experiments are reported.     

Nondifferentiability Detection and Dimensionality Reduction in Minisum Multifacility Location Problems

The minisum multifacility location problem is regarded as hard to solve, due to nondifferentiabilities whenever two or more facilities coincide. Recently, several authors have published conditions for the coincidence of facilities. In the present paper, these conditions are extended to more general location problems and improved with respect to new sufficient coincidence conditions for location problems with mixed asymmetric gauges. Some of these conditions are formulated only in terms of the given weights and certain values from a preprocessing step.     

An Algorithm for Linear L1 Approximation of Continuous Functions

The problem of solving linear continuous L₁ approximation problemsis considered. An algorithm is given for approximation on aninterval of the real line, which is globally convergent, usuallyat a second-order rate. The method is illustrated by numericalexamples.     

Adaptive Unified Biased Estimators of Parameters in Linear Model

To tackle multi collinearity or ill-conditioned design matrices in linear models,adaptive biasedestimators such as the time-honored Stein estimator,the ridge and the principal component estimators havebeen studied intensively.To study when a biased estimator uniformly outperforms the least squares estimator,some sufficient conditions are proposed in the literature.In this paper,we propose a unified framework toformulate a class of adaptive biased estimators.This class includes all existing biased estimators and some newones.A sufficient condition for outperforming the least squares estimator is proposed.In terms of selectingparameters in the condition,we can obtain all double-type conditions in the literature.     

Random Linear Combinations of Functions from L 1

In this paper, properties of random polynomials with respect to a general system of functions are studied. Some lower bounds for the mathematical expectation of the uniform norm and the recently introduced integral-uniform norm of random polynomials are established.     

An Unified Computational Framework for Parameter Identification of Material Models in Finite Inelasticity

Parameter identification processes concern the determination of parameters in a material model in order to fit experimental data. We provide a distinct, unified algorithmic setting of a generic class of material models and discuss the associated gradient–based optimization problem. Gradient–based optimization algorithms need derivatives of the objective function with respect to the material parameter vector κ . In order to obtain the necessary derivatives, an analytical sensitivity analysis is pointed out for the unified class of algorithmic material models. The quality of the parameter identification is demonstrated for a representative example.     

Study on the Splitting Methods for Separable Convex Optimization in a Unified Algorithmic Framework

It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality. Recently, we have proposed a unified algorithmic framework which can guide us to construct the solution methods for solving these monotone variational inequalities. In this work, we revisit two full Jacobian decomposition of the augmented Lagrangian methods for separable convex programming which we have studied a few years ago. In particular, exploiting this framework, we are able to give a very clear and elementary proof of the convergence of these solution methods.     

稀疏降维的近似凸壳覆盖一类分类器构造

针对高维数据集常常存在冗余和维数灾难,在其上直接构造覆盖模型难以充分反映数据分布信息的问题,提出一种基于稀疏降维近似凸壳覆盖模型.首先采用同伦算法求解稀疏表示中l_1优化问题,通过稀疏约束自动获取合理近邻数并构建图,再通过LPP(Locality Preserving Projections)来进行局部保持投影,进而实现对高维空间快速有效地降维,最后在低维空间通过构造近似凸壳覆盖实现一类分类.在UCI数据库,MNIST手写体数据库和MIT-CBCL人脸识别数据库上的实验结果证实了方法的有效性,与现有的一类分类算法相比,提出的覆盖模型具有更高的分类正确率.     

Foundations of a Multi-way Spectral Clustering Framework for Hybrid Linear Modeling

The problem of Hybrid Linear Modeling (HLM) is to model and segment data using a mixture of affine subspaces. Different strategies have been proposed to solve this problem, however, rigorous analysis justifying their performance is missing. This paper suggests the Theoretical Spectral Curvature Clustering (TSCC) algorithm for solving the HLM problem and provides careful analysis to justify it. The TSCC algorithm is practically a combination of Govindu’s multi-way spectral clustering framework (CVPR 2005) and Ng et al.’s spectral clustering algorithm (NIPS 2001). The main result of this paper states that if the given data is sampled from a mixture of distributions concentrated around affine subspaces, then with high sampling probability the TSCC algorithm segments well the different underlying clusters. The goodness of clustering depends on the within-cluster errors, the between-clusters interaction, and a tuning parameter applied by TSCC. The proof also provides new insights for the analysis of Ng et al. (NIPS 2001). This work was supported by NSF grant #0612608.     

Linear,Integer, Separable and Fuzzy Programming Problems: A Unified Approach towards Reformulation

For mathematical programming (MP) to have greater impact as a decision tool, MP software systems must offer suitable support in terms of model communication and modelling techniques. In this paper, modelling techniques that allow logical restrictions to be modelled in integer programming terms are described, and their implications discussed. In addition, it is illustrated that many classes of non-linearities which are not variable separable may be, after suitable algebraic manipulation, put in a variable separable form. The methods of reformulating the fuzzy linear programming problem as a max-min problem is also introduced. It is shown that analysis of bounds plays a key role in the following four important contexts: model reduction, reformulation of logical restrictions as 0-1 mixed integer programmes, reformulation of non-linear programmes as variable separable programmes and reformulation of fuzzy linear programmes. It is observed that, as well as incorporating an interface between the modeller and the optimizer, there is a need to make available to the modeller software facilities which support the model reformulation techniques described here.     

提前监考安排的0-1线性规划模型

提前考试的监考安排工作因诸多因素而显得比较繁琐,因此自动排考有相当的实际意义.基于监考安排的公平性和人本原则,根据监考时间和上课时间搭配的紧密程度,给监考时间设定相应的权值,从而建立了0-1线性规划模型.最后编制模型的AMPL程序,并以某高校数学系的教务数据为例进行计算,其求解速度和结果表明了所建模型的合理性.