Research On The Block Coordinate Descent Methods For Sparse Subspace Clustering Problems

Block coordinate descent methods?BCD?circularly use the different block coordinate directions to find the optimal solutions.Because of its simple iteration,lower memory requirement and easy implementations,BCD is widely used for large-scale numerical optimization.Given a set of data approximately drawn from a union of multiple subspaces,the goal of the subspace clustering problem is to group the data into their underlying subspaces and correct the possible noise simultaneously.Subspace clustering is an effective approach in high-dimensional data clustering,and it was recently shown that,the clustering task can be characterized as a nonsmooth nonconvex optimization problem with block diagonal regularization.The purpose of this thesis is to study the BCD method for sparse subspace clustering,analyze its convergence,test its numerical effectiveness,and do performance comparatione with a famous algorithm.In Chapter one,we firstly review some basic concepts in optimization,and briefly recall the proximal block coordinate descent?PBCD?method and the alternating direction method of multipliers?ADMM?.Then,we introduce some optimization models for subspace clustering problem,and list some related research results.Finally,we state the main contributions of thesis,and list some symbols used in the subsequent developments.In Chapter two,we use the PBCD to improve the efficiency of the block diagonal representation?BDR?method,in which an intelligent symmetric Gauss-Seidel?s GS?technique to make the subproblems easy to implement is employed.Under some certain conditions,we analyze the convergence property of the PBCD algorithm,we also employ the Nesterov's acceleration technique?named APBCD₁?and give the iteration complexity.In spite of this,the problem tackled in this chapter is only a penalty model but not the original problem itself.In Chapter three,we propose two different types of algorithms to the original model:the first one is a variant of the PBCD,and the second one is a coupled ADMM?CADMM?to an equivalent problem.In addition,for PBCD proposed in Chapter three,we also employ the Nesterov's acceleration technique?named APBCD₂?to further improve their numerical performance.In Chapter four,we present numerical experiments on Hopkins 155 real datasets and do performance comparisons with the BDR.The numerical results demonstrate that APBCD₁ is about 1.7 times faster than BDR,and APBCD₂ is about 2 times faster than C-ADMM.In Chapter five,we conclude the thesis by listing some remarks and giving some further research topics.