Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm

The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclear-norm minimization which requires computing singular value decompositions??a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale problems, we propose a low-rank factorization model and construct a nonlinear successive over-relaxation (SOR) algorithm that only requires solving a linear least squares problem per iteration. Extensive numerical experiments show that the algorithm can reliably solve a wide range of problems at a speed at least several times faster than many nuclear-norm minimization algorithms. In addition, convergence of this nonlinear SOR algorithm to a stationary point is analyzed.     

求解低秩矩阵恢复问题的非单调交替梯度方向法

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了...     

Low-rank tensor completion via smooth matrix factorization

Low-rank modeling has achieved great success in tensor completion. However, the low-rank prior is not sufficient for the recovery of the underlying tensor, especially when the sampling rate (SR) is extremely low. Fortunately, many real world data exhibit the piecewise smoothness prior along both the spatial and the third modes (e.g., the temporal mode in video data and the spectral mode in hyperspectral data). Motivated by this observation, we propose a novel low-rank tensor completion model using smooth matrix factorization (SMF-LRTC), which exploits the piecewise smoothness prior along all modes of the underlying tensor by introducing smoothness constraints on the factor matrices. An efficient block successive upper-bound minimization (BSUM)-based algorithm is developed to solve the proposed model. The developed algorithm converges to the set of the coordinate-wise minimizers under some mild conditions. Extensive experimental results demonstrate the superiority of the proposed method over the compared ones.     

低秩稀疏矩阵恢复的快速非单调交替极小化方法

针对低秩稀疏矩阵恢复问题的一个非凸优化模型,本文提出了一种快速非单调交替极小化方法.主要思想是对低秩矩阵部分采用交替极小化方法,对稀疏矩阵部分采用非单调线搜索技术来分别进行迭代更新.非单调线搜索技术是将单步下降放宽为多步下降,从而提高了计算效率.文中还给出了新算法的收敛性分析.最后,通过数值实验的比较表明,矩阵恢复的非单调交替极小化方法比原单调类方法更有效.     

Robust reduced rank regression in a distributed setting

This paper studies the reduced rank regression problem, which assumes a low-rank structure of the coefficient matrix, together with heavy-tailed noises. To address the heavy-tailed noise, we adopt the quantile loss function instead of commonly used squared loss. However, the non-smooth quantile loss brings new challenges to both the computation and development of statistical properties, especially when the data are large in size and distributed across different machines. To this end, we first transform the response variable and reformulate the problem into a trace-norm regularized least-square problem, which greatly facilitates the computation. Based on this formulation, we further develop a distributed algorithm. Theoretically, we establish the convergence rate of the obtained estimator and the theoretical guarantee for rank recovery. The simulation analysis is provided to demonstrate the effectiveness of our method.

     

Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations

Given a set of corrupted data drawn from a union of multiple subspace, the subspace recovery problem is to segment the data into their respective subspace and to correct the possible noise simultaneously. Recently, it is discovered that the task can be characterized, both theoretically and numerically, by solving a matrix nuclear-norm and a ?_2,1-mixed norm involved convex minimization problems. The minimization model actually has separable structure in both the objective function and constraint; it thus falls into the framework of the augmented Lagrangian alternating direction approach. In this paper, we propose and investigate an augmented Lagrangian algorithm. We split the augmented Lagrangian function and minimize the subproblems alternatively with one variable by fixing the other one. Moreover, we linearize the subproblem and add a proximal point term to easily derive the closed-form solutions. Global convergence of the proposed algorithm is established under some technical conditions. Extensive experiments on the simulated and the real data verify that the proposed method is very effective and faster than the sate-of-the-art algorithm LRR.     

Half thresholding eigenvalue algorithm for semidefinite matrix completion

The semidefinite matrix completion(SMC) problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, SMC problem and S1/2relaxation model share a unique solution. Then we prove that the global optimal solutions of S1/2regularization model are fixed points of a symmetric matrix half thresholding operator. We give an iterative scheme for solving S1/2regularization model and state convergence analysis of the iterative sequence.Through the optimal regularization parameter setting together with truncation techniques, we develop an HTE algorithm for S1/2regularization model, and numerical experiments confirm the efficiency and robustness of the proposed algorithm.     

A novel robust principal component analysis method for image and video processing

The research on the robust principal component analysis has been attracting much attention recently. Generally, the model assumes sparse noise and characterizes the error term by the λ₁-norm. However, the sparse noise has clustering effect in practice so using a certain λ_p-norm simply is not appropriate for modeling. In this paper, we propose a novel method based on sparse Bayesian learning principles and Markov random fields. The method is proved to be very effective for low-rank matrix recovery and contiguous outliers detection, by enforcing the low-rank constraint in a matrix factorization formulation and incorporating the contiguity prior as a sparsity constraint. The experiments on both synthetic data and some practical computer vision applications show that the novel method proposed in this paper is competitive when compared with other state-of-the-art methods.     

Sparse trace norm regularization

We study the problem of estimating multiple predictive functions from a dictionary of basis functions in the nonparametric regression setting. Our estimation scheme assumes that each predictive function can be estimated in the form of a linear combination of the basis functions. By assuming that the coefficient matrix admits a sparse low-rank structure, we formulate the function estimation problem as a convex program regularized by the trace norm and the \(\ell _1\) -norm simultaneously. We propose to solve the convex program using the accelerated gradient (AG) method; we also develop efficient algorithms to solve the key components in AG. In addition, we conduct theoretical analysis on the proposed function estimation scheme: we derive a key property of the optimal solution to the convex program; based on an assumption on the basis functions, we establish a performance bound of the proposed function estimation scheme (via the composite regularization). Simulation studies demonstrate the effectiveness and efficiency of the proposed algorithms.     

Projected Landweber iteration for matrix completion

Recovering an unknown low-rank or approximately low-rank matrix from a sampling set of its entries is known as the matrix completion problem. In this paper, a nonlinear constrained quadratic program problem concerning the matrix completion is obtained. A new algorithm named the projected Landweber iteration (PLW) is proposed, and the convergence is proved strictly. Numerical results show that the proposed algorithm can be fast and efficient under suitable prior conditions of the unknown low-rank matrix.     

Quantile regression for right-censored and length-biased data

Length-biased data arise in many important fields, including epidemiological cohort studies, cancer screening trials and labor economics. Analysis of such data has attracted much attention in the literature. In this paper we propose a quantile regression approach for analyzing right-censored and length-biased data. We derive an inverse probability weighted estimating equation corresponding to the quantile regression to correct the bias due to length-bias sampling and informative censoring. This method can easily handle informative censoring induced by length-biased sampling. This is an appealing feature of our proposed method since it is generally difficult to obtain unbiased estimates of risk factors in the presence of length-bias and informative censoring. We establish the consistency and asymptotic distribution of the proposed estimator using empirical process techniques. A resampling method is adopted to estimate the variance of the estimator. We conduct simulation studies to evaluate its finite sample performance and use a real data set to illustrate the application of the proposed method.     

Regularization Using QR Factorization and the Estimation of the Optimal Parameter

In this paper we propose a direct regularization method using QR factorization for solving linear discrete ill-posed problems. The decomposition of the coefficient matrix requires less computational cost than the singular value decomposition which is usually used for Tikhonov regularization. This method requires a parameter which is similar to the regularization parameter of Tikhonov's method. In order to estimate the optimal parameter, we apply three well-known parameter choice methods for Tikhonov regularization.This revised version was published online in October 2005 with corrections to the Cover Date.     

�������ݾ�ֵ��Э����������Ч�Ƚ�����

In this article, we develop efficient robust method for estimation of mean and covariance simultaneously for longitudinal data in regression model. Based on Cholesky decomposition for the covariance matrix and rewriting the regression model, we propose a weighted least square estimator, in which the weights are estimated under generalized empirical likelihood framework. The proposed estimator obtains high efficiency from the close connection to empirical likelihood method, and achieves robustness by bounding the weighted sum of squared residuals. Simulation study shows that, compared to existing robust estimation methods for longitudinal data, the proposed estimator has relatively high efficiency and comparable robustness. In the end, the proposed method is used to analyse a real data set.     

An alternating direction algorithm for matrix completion with nonnegative factors

This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M are given, and (ii) low-rank matrix completion where nonnegativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on the classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.     

Low-rank and sparse matrix recovery from noisy observations via 3-block ADMM algorithm

Recovering low-rank and sparse matrix from a given matrix arises in many applications, such as image processing, video background substraction, and so on. The 3-block alternating direction method of multipliers (ADMM) has been applied successfully to solve convex problems with 3-block variables. However, the existing sufficient conditions to guarantee the convergence of the 3-block ADMM usually require the penalty parameter $\gamma$ to satisfy a certain bound, which may affect the performance of solving the large scale problem in practice. In this paper, we propose the 3-block ADMM to recover low-rank and sparse matrix from noisy observations. In theory, we prove that the 3-block ADMM is convergent when the penalty parameters satisfy a certain condition and the objective function value sequences generated by 3-block ADMM converge to the optimal value. Numerical experiments verify that proposed method can achieve higher performance than existing methods in terms of both efficiency and accuracy.     

An Information-theoretic Approach to the Effective Usage of Auxiliary Information from Survey Data

In this paper, we propose an information-theoretic approach to the effective usage of auxiliary information from survey data, which is suitable for both simple and complex survey data. Our estimator under simple random sampling without replacement will be consistent and asymptotically normal. We show that the resulting estimates have smaller asymptotic variances than the usual estimates which do not use auxiliary information. For more complex survey designs, the resulting estimator is in essence asymptotically equivalent to a pseudo empirical likelihood estimator. Results of a limited simulation study show that the proposed estimators perform well among a number of competitors.     

High dimensional covariance matrix estimation using multi-factor models from incomplete information

Covariance matrix plays an important role in risk management, asset pricing, and portfolio allocation. Covariance matrix estimation becomes challenging when the dimensionality is comparable or much larger than the sample size. A widely used approach for reducing dimensionality is based on multi-factor models. Although it has been well studied and quite successful in many applications, the quality of the estimated covariance matrix is often degraded due to a nontrivial amount of missing data in the factor matrix for both technical and cost reasons. Since the factor matrix is only approximately low rank or even has full rank, existing matrix completion algorithms are not applicable. We consider a new matrix completion paradigm using the factor models directly and apply the alternating direction method of multipliers for the recovery. Numerical experiments show that the nuclear-norm matrix completion approaches are not suitable but our proposed models and algorithms are promising.     

Adaptive Penalized Weighted Least Absolute Deviations Estimation for the Accelerated Failure Time Model

The accelerated failure time model always offers a valuable complement to the traditional Cox proportional hazards model due to its direct and meaningful interpretation. We propose a variable selection method in the context of the accelerated failure time model for survival data, which can simultaneously complete variable selection and parameter estimation. Meanwhile, the proposed method can deal with the potential outliers in survival times as well as heteroscedastic model errors, which are frequently encountered in practice. Specifically, utilizing the general nonconvex penalty, we propose the adaptive penalized weighted least absolute deviation estimator for the accelerated failure time model. Under some regularity conditions, we show that the proposed method yields consistent estimator and possesses the oracle property. In addition, we propose a new algorithm to compute the estimate in the high dimensional settings, and evaluate the practical utility of the proposed method through extensive simulation studies and two real examples.     

右删失长度偏差数据分位数差的非参数估计

利用长度偏差数据所特有的辅助信息,对带右删失的长度偏差数据的分位数差提出了一种新的非参数估计.该方法提高了估计的有效性,所得的估计量形式简洁,便于计算.同时,本文用经验过程理论建立了该分位数差估计的相合性及渐近正态性,并给出方差估计的重抽样方法.本文还通过数值模拟考察了该估计量在有限样本下的表现,并将其应用到一个关于老年痴呆的实际数据中.     

Methods for improvement in estimation of a normal mean matrix

This paper is concerned with the problem of estimating a matrix of means in multivariate normal distributions with an unknown covariance matrix under invariant quadratic loss. It is first shown that the modified Efron-Morris estimator is characterized as a certain empirical Bayes estimator. This estimator modifies the crude Efron-Morris estimator by adding a scalar shrinkage term. It is next shown that the idea of this modification provides a general method for improvement of estimators, which results in the further improvement on several minimax estimators. As a new method for improvement, an adaptive combination of the modified Stein and the James-Stein estimators is also proposed and is shown to be minimax. Through Monte Carlo studies of the risk behaviors, it is numerically shown that the proposed, combined estimator inherits the nice risk properties of both individual estimators and thus it has a very favorable risk behavior in a small sample case. Finally, the application to a two-way layout MANOVA model with interactions is discussed.