Nested Minimizing Algorithms For Subspace Recovery Problem

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.