Tensor Decomposition With Generalized Lasso Penalties

We present an approach for penalized tensor decomposition (PTD) that estimates smoothly varying latent factors in multiway data. This generalizes existing work on sparse tensor decomposition and penalized matrix decompositions, in a manner parallel to the generalized lasso for regression and smoothing problems. Our approach presents many nontrivial challenges at the intersection of modeling and computation, which are studied in detail. An efficient coordinate-wise optimization algorithm for PTD is presented, and its convergence properties are characterized. The method is applied both to simulated data and real data on flu hospitalizations in Texas and motion-capture data from video cameras. These results show that our penalized tensor decomposition can offer major improvements on existing methods for analyzing multiway data that exhibit smooth spatial or temporal features.     

An Augmented ADMM Algorithm With Application to the Generalized Lasso Problem

In this article, we present a fast and stable algorithm for solving a class of optimization problems that arise in many statistical estimation procedures, such as sparse fused lasso over a graph, convex clustering, and trend filtering, among others. We propose a so-called augmented alternating direction methods of multipliers (ADMM) algorithm to solve this class of problems. Compared to a standard ADMM algorithm, our proposal significantly reduces the computational cost at each iteration while maintaining roughly the same overall convergence speed. We also consider a new varying penalty scheme for the ADMM algorithm, which could further accelerate the convergence, especially when solving a sequence of problems with tuning parameters of different scales. Extensive numerical experiments on the sparse fused lasso problem show that the proposed algorithm is more efficient than the standard ADMM and two other existing state-of-the-art specialized algorithms. Finally, we discuss a possible extension and some interesting connections to two well-known algorithms. Supplementary materials for the article are available online.     

监督式分组套索法在急性白血病分型中的应用

急性白血病可分为急性淋巴细胞白血病(ALL)和急性髓系白血病(AML)两大亚型,准确诊断是治疗急性白血病的前提和关键。本文基于急性白血病的基因芯片数据,结合两样本T检验、Wilconxon秩和检验、系统聚类法以及变量选择方法监督式分组套索法(supervised group lasso,SGLasso)筛选出对急性白血病分型(AML、ALL)有显著意义的基因,根据训练组数据建立关于急性白血病分型的逻辑回归模型,并对训练组和检验组中患者的病型作拟合和预测,验证该模型的预测精度。     

A Path Algorithm for the Fused Lasso Signal Approximator

The Lasso is a very well-known penalized regression model, which adds an L₁ penalty with parameter λ₁ on the coefficients to the squared error loss function. The Fused Lasso extends this model by also putting an L₁ penalty with parameter λ₂ on the difference of neighboring coefficients, assuming there is a natural ordering. In this article, we develop a path algorithm for solving the Fused Lasso Signal Approximator that computes the solutions for all values of λ₁ and λ₂. We also present an approximate algorithm that has considerable speed advantages for a moderate trade-off in accuracy. In the Online Supplement for this article, we provide proofs and further details for the methods developed in the article.     

四元数正则矩阵束广义特征值反问题

对于任意给定的X∈Qn×m,∧=diag(λ1,…,λm)∈Rm×m,利用奇异值分解、谱分解及QR分解分别给出了满足AX=BX∧,及XHBX=Im,AX=BX∧,的正则矩阵束(A,B)的通解表达式.     

Implementations of the Monte Carlo EM Algorithm

The Monte Carlo EM (MCEM) algorithm is a modification of the EM algorithm where the expectation in the E-step is computed numerically through Monte Carlo simulations. The most exible and generally applicable approach to obtaining a Monte Carlo sample in each iteration of an MCEM algorithm is through Markov chain Monte Carlo (MCMC) routines such as the Gibbs and Metropolis–Hastings samplers. Although MCMC estimation presents a tractable solution to problems where the E-step is not available in closed form, two issues arise when implementing this MCEM routine: (1) how do we minimize the computational cost in obtaining an MCMC sample? and (2) how do we choose the Monte Carlo sample size? We address the first question through an application of importance sampling whereby samples drawn during previous EM iterations are recycled rather than running an MCMC sampler each MCEM iteration. The second question is addressed through an application of regenerative simulation. We obtain approximate independent and identical samples by subsampling the generated MCMC sample during different renewal periods. Standard central limit theorems may thus be used to gauge Monte Carlo error. In particular, we apply an automated rule for increasing the Monte Carlo sample size when the Monte Carlo error overwhelms the EM estimate at any given iteration. We illustrate our MCEM algorithm through analyses of two datasets fit by generalized linear mixed models. As a part of these applications, we demonstrate the improvement in computational cost and efficiency of our routine over alternative MCEM strategies.     

Efficient strategies for deriving the subset VAR models

Algorithms for computing the subset Vector Autoregressive (VAR) models are proposed. These algorithms can be used to choose a subset of the most statistically-significant variables of a VAR model. In such cases, the selection criteria are based on the residual sum of squares or the estimated residual covariance matrix. The VAR model with zero coefficient restrictions is formulated as a Seemingly Unrelated Regressions (SUR) model. Furthermore, the SUR model is transformed into one of smaller size, where the exogenous matrices comprise columns of a triangular matrix. Efficient algorithms which exploit the common columns of the exogenous matrices, sparse structure of the variance-covariance of the disturbances and special properties of the SUR models are investigated. The main computational tool of the selection strategies is the generalized QR decomposition and its modification. This work is in part supported by the Swiss National Foundation for Research Grants 101312-100757/1, 200020-10016/1 and 101412-105978. Correspondence to: Cristian Gatu, Institut d'informatique, Université de Neuchatel, Emile-Argand 11, Case Postale 2, CH-2007 Neuchatel, Switzerland. e-mail: erricos@ucy.ac.cy     

On the Convergence of Stewart's QLP Algorithm for Approximating the SVD

The pivoted QLP decomposition, introduced by Stewart [20], represents the first two steps in an algorithm which approximates the SVD. The matrix A₀ is first factored as A₀=QR, and then the matrix R ^T₁ is factored as R ^T₁=PL ^T, resulting in A=Q₁ LP ^T₀ ^T, with Q and P orthogonal, L lower-triangular, and ₀ and ₁ permutation matrices. Stewart noted that the diagonal elements of L approximate the singular values of A with surprising accuracy. In this paper, we provide mathematical justification for this phenomenon. If there is a gap between _k and _k+1, partition the matrix L into diagonal blocks L ₁₁ and L ₂₂ and off-diagonal block L ₂₁, where L ₁₁ is k-by-k. We show that the convergence of ( _j (L ₁₁)^–1– _j ^–1)/ _j ^–1 for j=1,. . .,k, and of ( _j (L ₂₂)– _k+j )/ _k+j , for j=1,. . .,n–k, are all quadratic in the gap ratio _k+1/ _k . The worst case is therefore at the gap, where the absolute errors L ₁₁ ^–1– _k ^–1 and L ₂₂– _k+1 are thus cubic in _k ^–1 and _k+1, respectively. One order of convergence is due to the rank-revealing pivoting in the first step; then, because of the pivoting in the first step, two more orders are achieved in the second step. Our analysis assumes that ₁=I, that is, that pivoting is done only on the first step. Although our results explain some of the properties of the pivoted QLP decomposition, they hypothesize a gap in the singular values. However, a simple example shows that the decomposition can perform well even in the absence of a gap. Thus there is more to explain, and we hope that our paper encourages others to tackle the problem. The QLP algorithm can be continued beyond the first two steps, and we make some observations concerning the asymptotic convergence. For example, we point out that repeated singular values can accelerate convergence of individual elements. This, in addition to the relative convergence to all of the singular values being quadratic in the gap ratio, further indicates that the QLP decomposition can be powerful even when the ratios between neighboring singular values are close to one.     

个人信用评分的Adaptive Lasso-Logistic回归分析

以个人信用风险为研究对象,分析影响个人信用评分的因素.利用某商业银行个人信用数据,并采用.Adaptive Lasso-Logistic回归模型对影响顾客的个人信用风险的因素进行分析,并与传统Logistic回归模型以及Lasso-Logistic回归模型进行比较.以对顾客"好"与"坏"的二分类结果的正确比例为主要衡量标准,实证发现以.Adaptive Lassi-Logistic回归方法建立的个人信用评分模型,在变量选择和解释上,以及预测的准确性上,均优于传统的Logistic和Lasso-Logistic方法.     

The Algorithm of Sequential KKT Equations by Nonmonotone Search for Arbitrary Initial Point

In this paper, a new algorithm for arbitrary initial point is proposed. The feature of the algorithm is that only KKT equations are solved in each iteration which greatly decreases the amount of computation. Under some proper assumptions, the algorithm is globally and superlinearly convergent.     

Lower Semicontinuity of the Set of Efficient Solutions for Generalized Systems

We discuss the lower semicontinuity of the set of efficient solutions for parametric generalized systems with monotone bifunctions in real locally convex Hausdorff topological vector spaces. This research was partially supported by the National Natural Science Foundation of China (10561007), the Natural Science Foundation of Jiangxi Province, China, and a grant from the National Science Council of ROC.     

A Piecewise Linear Dual Phase-1 Algorithm for the Simplex Method

A dual phase-1 algorithm for the simplex method that handles all types of variables is presented. In each iteration it maximizes a piecewise linear function of dual infeasibilities in order to make the largest possible step towards dual feasibility with a selected outgoing variable. The algorithm can be viewed as a generalization of traditional phase-1 procedures. It is based on the multiple use of the expensively computed pivot row. By small amount of extra work per iteration, the progress it can make is equivalent to many iterations of the traditional method. While this is its most important feature, it possesses some additional favorable properties, namely, it can be efficient in coping with degeneracy and numerical difficulties. Both theoretical and computational issues are addressed. Some computational experience is also reported which shows that the potentials of the method can materialize on real world problems.     

Connectedness of the Set of Efficient Solutions for Generalized Systems

We introduce the concept of positive proper efficient solutions to the generalized system in this paper. We show that, under some suitable conditions, the set of positive proper efficient solutions is dense in the set of efficient solutions to the generalized system. We discuss also the connectedness of the set of efficient solutions for the generalized system with monotone bifunctions in real locally convex Hausdorff topological vector spaces. This research was partially supported by the National Natural Science Foundation of China (10561007), the Natural Science Foundation of Jiangxi Province, China, and a grant from the National Science Council of ROC.     

On the Convergence of the Generalized Linear Least Squares Algorithm

This paper considers the issue of parameter estimation for biomedical applications using nonuniformly sampled data. The generalized linear least squares (GLLS) algorithm, first introduced by Feng and Ho (1993), is used in the medical imaging community for removal of bias when the data defining the model are correlated. GLLS provides an efficient iterative linear algorithm for the solution of the non linear parameter estimation problem. This paper presents a theoretical discussion of GLLS and introduces use of both Gauss Newton and an alternating Gauss Newton for solution of the parameter estimation problem in nonlinear form. Numerical examples are presented to contrast the algorithms and emphasize aspects of the theoretical discussion. AMS subject classification (2000) 65F10.R. A. Renaut: This work was partially supported by the Arizona Center for Alzheimer’s Disease Research, by NIH grant EB 2553301 and for the second author by NSF CMG-02223.Received December 2003. Revised November 2004. Communicated by Lars Eldén.     

关于使用最大改进规则的对偶单纯形算法

本举例证明了[3]的定理10-1是错误的。     

广义投影型的超线性收敛算法

该文利用矩阵分解与广义投影等技巧，给出了求解线性约束的非线性规划的一个广义投影型的超线性收敛算法，不需要δ－主动约束与每一步反复计算投影矩阵，避免了计算的数值不稳定性，利用矩阵求逆的递推公式，计算简便，由于采用了非精确搜索，算法实用可行，文中证明了算法具有收敛性及超线性的收敛速度．     

一类广义指派问题的有效解法

提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.     

二阶广义系统的极点配置问题(英文)

以Ｈｉｌｂｅｒｔ空间算子理论为工具讨论二阶广义分布参数系统的极点配置问题,应用算子的广义逆给出了所讨论问题的解及解的构造性表达式．     

任意Banach空间中线性算子的Moore-Penrose度量广义逆

在无空间严格凸的几何假定下,利用Banach空间几何方法给出了任意Banach空间中线性算子T的Moore-Penrose度量广义逆T~+的存在性、唯一性、极小性和线性性的充要条件,同时还讨论了T~+的一些性质,这些本质地将文献[8]的最近结果从严格凸Banach空间拓广至任意Banach空间．     

On the Discrete Spectrum of Generalized Quantum Tubes

The spectrum (of the Dirichlet Laplacian) of non-compact, non-complete Riemannian manifolds is much less understood than their compact counterparts. In particular it is often not even known whether such a manifold has any discrete spectra. In this article, we will prove that a certain type of non-compact, non-complete manifold called the quantum tube has non-empty discrete spectrum. The quantum tube is a tubular neighborhood built about an immersed complete manifold in Euclidean space. The terminology of “quantum” implies that the geometry of the underlying complete manifold can induce discrete spectra – hence quantization. We will show how the Weyl tube invariants appear in determining the existence of discrete spectra. This is an extension and generalization, on the geometric side, of the previous work of the author on the “quantum layer.”