Approximate Message Passing For L_1/2 Regularization

Feature extraction and variable selection are two most important research problems in machine learning and statistics. The regularization approaches arc recently proposed to extract information from massive data which are effective and efficient for feature extraction and variable selection. L1/2 regularization is a kind of important rcgularization methods. It has a wider application in vari-ous fields, such as variable selection, sparse signal reconstruction and biological signal. However, it is well known that the nonconvex regularization methods arc difficult to be solved. Therefore, study on the algorithms for solving L1/2 regularization method is of great importance.In this thesis, we study the algorithm for L1/2 regularization. The main works include the following, we study approximate message passing(AMP) for L1/2 regularization method. We propose an improved half iterative thresholding algorithm based on AMP. The new iterative thresholding algorithm is inspired by belief propagation in graphical models. Further, we study the convergence of new algorithm, and through extensive simulations to show several important nonconvex iterative thresholding algorithms based on AMP which have strong reconstruction capabilities and high phase transition.