Studies On Models,Algorithms And Application For Matrix Completion

Recently, there have been extensive research on matrix completion, a process ofrecovering the unknown or missing elements of a matrix. Matrix completion can beappliedinmanyfelds, suchaseconomics, imageandvedioprocessing, wherematriceswith low rank are used in the model construction. Without any additional assumption,missing elements can be set to be any values, the solution of matrix completion is notuniqueinthissituation. Undercertainassumptionsonthematrix, e.g. lowrankorevenapproximately low rank, the incomplete matrix can be reconstructed very well.This thesis aims at studying models, algorithms and application of matrix com-pletion. It consists of six parts. In the frst chapter, we introduce the modeling, someclassic algorithms, research background, signifcance and the recent situations of ma-trix completion and summarize the main results of the paper.In chapter2, we propose a novel robust linear optimization framework based onmatrix completion when there are missing elements in the coefcient matrix of lin-ear programming and known elements have uncertainty. Linear programming modelshave been widely used in input-output analysis for analyzing the interdependence ofindustries in economics and in environmental science. In these applications, someof the entries of the coefcient matrix cannot be measured physically or there existssampling errors. On the other hand, the coefcient matrix can often be low-rank. Wecharacterizetherobustcounterpartofthesetypesoflinearprogrammingproblemswithuncertainty set described by the nuclear norm. We design a fast algorithm based on thealternating direction method of multipliers. Simulations for the input-output analysisshow that the new paradigm can be helpful.In chapter3, two non-convex models and the corresponding algorithms of matrix completion are given, they are designed for high-dimensional covariance matrix esti-mationfromincompleteinformation. Covariancematrixestimationplaysanimportantrole in risk management, asset pricing, and portfolio allocation. This task becomeschallenging when the dimensionality is comparable or much larger than the samplesize. A widely used approach for reducing dimensionality is based on multi-factormodels. 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 nontrivialamount of missing data in the factor matrix for both technical and cost reasons. Sincethe factor matrix is only approximately low rank or even has full rank, existing matrixcompletionalgorithmsarenotapplicable. Inthispaper,weconsideranewmatrixcom-pletion paradigm using the factor models directly and apply the alternating directionmethod of multipliers for the recovery. Numerical experiments show that the nuclear-norm matrix completion approaches are not suitable for this problem but our proposedmodels and algorithms are promising.In chapter4, we propose two models and the corresponding algorithms for non-negative matrix completion. Life-cycle assessment (LCA) and input-output analysis(IOA) are two data-intensive approaches whose reliability and applicability are depen-dent on the quality of the data. The difculty is that not all data is available due totechnical or cost reasons. However, the processes producing similar commodities havesimilar data structures in LCA, while the sectors of the historical surveyed years inIOA have similar input structures as the sectors of the objective year. These featuresimply that the data usually has low-rank or approximately low-rank structures whichenables us to apply the emerging techniques of low-rank matrix completion to recoverthe missing data. Since the data should be nonnegative in LCA and IOA if we ignorethe minor by-product issue, we propose two models for nonnegative matrix completionto recover the missing information of LCA and IOA. The alternating direction methodof multipliers is then applied to solve them. The applicability and efciency of ourmethods are demonstrated in an application to the widely used database “Ecoinvent”for the life-cycle assessment. Recovering results show that our approaches are helpful.In chapter5, we develop three new fast algorithms for the nuclear norm regular-ized linear least squares model with nonnegative constraints, the model is proposed inchapter4. Nonnegative matrix completion aims to fnd nonnegative low-rank matrices from a subset of entries of a matrix. It is widely applicable in many felds, such asimage processing, recommendation systems, and national economy. This task can beconductedbysolvingthenuclearnormregularizedlinearleastsquaresmodelwithnon-negative constraints. We use alternating direction method of multipliers to solve themodel and get three novel algorithms for nonnegative matrix completion.On one hand,we give two exact ADMM-based algorithms, whose subproblems are solved exactly.On other hand, we also derive an inexact ADMM-based algorithm, of which one sub-problem is approximatively solved by the Forward-backward splitting method. We testthreenewADMM-basedalgorithmsontwokindsofproblems: randommatrixcomple-tion problems and random low-rank approximation problems. Numerical experimentsshow that all our proposed algorithms output satisfactory results.