Dissertation > Excellent graduate degree dissertation topics show

Nested Minimizing Algorithms for Subspace Recovery Problem

Author: ShenZuo
Tutor: XiaoYunHai
School: Henan University
Course: Operational Research and Cybernetics
Keywords: structure convex optimization matrix nuclear norm matrix mixed-norm variable inequality alternating direction method
CLC: O224
Type: Master's thesis
Year: 2013
Downloads: 11
Quote: 0
Read: Download Dissertation


The subspace recovery problem is to divide corrupted data into their respective sub-space and correct the possible noise as well. This task can be well illustrated, boththeoretically and numerically, by solving a matrix nuclear-norm and a2,1-norm involvedconvex minimization problem, i.e. low-rank representation (LRR). This thesis is aboutalternating direction method for LRR model. In particular, we propose nested minimizingalgorithms for three-variable separable minimization problem, establish the convergencetheorem, and do experiments to show their efectiveness. Moreover, we extend the nestedalgorithm to solve general three-variable separable minimization problem and give theconvergence result at the same time.In the frst chapter, we introduce the two-variable and three-variable separable convexminimization problems, give the equivalent transformation of the three-variable model,and recall the alternating direction method for its solution. We list the LRR model forsubspace recovery problem and review the LRR method and other recent solvers. To endthis chapter, the main contribution of this thesis, some important notations and symbolsused in the context are also included.In the second chapter, we provide three nested minimization methods to solve theproblem of subspace recovery. We transform LRR model to an equivalent formulationwith three separable variables by introducing an auxiliary variable. Firstly, by fxing twovariables, we minimize the corresponding augmented Lagrangian function to produce thetemporary value of one variable. Secondly, by fxing the variable with its latest value,we produce the value of the other two variables by classic alternating direction method.Finally, we update the Lagrangian multipliers with the latest value of these three variables.We show that the proposed method reduce to the well-known LRR method when theinner loop goes only once. This illustrates the reason why LRR doesn’t converge globally.Taking advantage of the special structure of the LRR model, we change minimizing orderof the variables to get the second nested minimizing algorithm. The third version ofnested algorithm is diferent from the mentioned two. More precisely, we add an auxiliaryvariable into the subproblem, and use alternating minimizing technique. We establish theglobal convergence of each method. Numerical experiments show that all the proposed methods perform well and are competitive with the recent solver SLAL.In the third chapter, the proposed method is extended to solve the general three-variable structure convex optimization problem, and the convergence result is establishedmeanwhile. We also give the reason why the classical alternating direction method doesn’tconverge globally when each variable is minimized in a parallel way.In the last chapter, we conclude this thesis, and list some further research topics.

Related Dissertations

  1. A Alternating Direction Method for Quadratic Semidefinite Programming,O221.2
  2. 2-D Water Quality Simulation for Mainstream of Huaihe River(from Lu Taizi to Tianjiaan),X824
  3. Numerical Method of Combining Orthogonal Spline Collocation Method and Alternating Direction Implicit Method for Two-dimensional Parabolic Problems on Rectangles,O241.82
  4. Alternating Direction Method for Solving a Class of Monotone Variational Inequalities,O241
  5. Solving a Class of Monotone Variational Inequalities by a Alternating Direction Method,O178
  6. The Galerkin Alternating-Direction Method for Hyperbolic Equations,O241.82
  7. Alternating Direction Method for Matrix Nuclear Norm Minimization,O241.6
  8. A Series of Projection and Contraction Alternating Direction Methods for Solving Separable Variational Inequality Problems,O178
  9. Alternating Direction Methods for Nuclear Norm Minimization,O221.2
  10. Some First-order Algorithms for Structured Optimizations,O241
  11. Proximal Alternating Direction Methods for Convex Optimization,O224
  12. On the Numerical Methods of Image Restoration,TP391.41
  13. Analysis of the Impact of the Population Aging on Economic Growth and Regional Disparities in Korea and China,F224
  14. Penalty framework for solving the generalized Nash equilibrium problem,O225
  15. An Alternating Direction Method with Gaussian Back Substitution for a Type of Inverse Quadratic Programming Problems,O221.2
  16. Video Background Modeling Based on Optimization Algorithms of Robust PCA,TP391.41
  17. Solve the Quasi-separable MDO Problems by the MPCPM Method,O224
  18. Double Algorithms for L1-Regularized Optimiation Problems,O224
  19. Research on Image Restoration Based on Coordinate Descent Method,TP391.41
  20. Application Research of Alternating Direction Method and TGV Regularization for Image Processing,TP391.41

CLC: > Mathematical sciences and chemical > Mathematics > Operations Research > Optimization of the mathematical theory
© 2012 www.DissertationTopic.Net  Mobile