Research On L1-norm-based Two-Dimensional Non-Greedy Weighted Maximum Margin Criterion

Nowadays,with the rapid development of computers,people are able to get more and more information from life by using computers.For example,in the field of computer vision,with the development of computer hardware,software,and the popularization of digital products,the number and dimensions of images increase exponentially each year.The higher the image's dimensions,the more information it contains.However,not all the information is useful.There is still a large amount of redundant information in high-dimensional image data.In the procedure of image processing,these useless information often brings many problems.Therefore,we often need to perform dimension reduction operations before processing images.There are classic one-dimensional linear dimension reduction methods,such as PCA and LDA,and two-dimensional methods,such as 2DPCA and 2DLDA.L1-norm are often adopted as a measure in these methods,such as PCA-L1,MMC-L1 and so on.They have worked well in many scenarios.However,traditional LDA is weak in multi-class classification due to its over-emphasis on the class far from the center,which leads to the easy separation for the center-away class while confuses the separation for the center-close classes.Furthermore,it is difficult to solve the objective function directly because L1-norm has absolute sign based on L1-norm.Many methods which take L1-norm as a metric adopt the greedy strategy to solve each projection direction one by one.The optimal solution obtained from this method is tend to fall into local optimum.Aiming at the deficiency of these methods,some weight-based dimensionality reduction methods such as ILDA are proposed.The main idea is to redefine the objective function and weaken the class that is farther from the sample population center and emphasize the influence of the class that is closer to the sample population center on the final projection direction and it will avoid the alienation of the class near the sample population center after dimensionality reduction.At the same time,some methods based on non-greedy dimensionality reduction methods such as NPCA-L1 are proposed.The advantages of these methods lie in that the whole projection matrix can be optimized simultaneously.In addition,some dimension reduction methods based on the max-min idea have been applied to many scenes and have achieved good results.Such as CLMLDA,RMMLDA and so on.Through the study of the above methods and their shortcomings,we propose the following three improved methods:(1)Aiming at the problem that the matrix of image needs to be vectorized before the dimension reduction of MMC-L1,which leads to the destruction of the spatial structure information of images,the poor robustness to the noises and the weakness in the multi-class classification of the 2DMMC,a two-dimensional weighted maximum margin criterion based on L1-norm(2DWMMC-L1)is proposed.The method has three advantages:First,L1-norm is used as a metric to enhance the anti-noise ability of the algorithm.The second is that in order to avoid the input sample into a vector form,projection on the sample matrix will be carried out directly in order not to undermine the sample matrix spatial structure information.The third is to redefine the objective function and weaken the classes which are far from the center,and to emphasize the classes which are close to center.This avoids mixing those classes which are close to center.Finally,the method of solving the objective function and the proof of monotonicity are given.(2)Traditionally,since there are absolute value operation in the dimension reduction method which is based on L1-norm,it is not easy to solve the optimal solution of the objective function directly.Therefore,many L1-norm-based dimensionality reduction methods adopt greedy strategies to solve each projection direction one by one.The optimal solution obtained by this method is tend to fall into local optimum.Therefore,we propose a two-dimensional non-greedy weighted maximum margin criterion based on L1-norm(2DNWMMC-L1).Compared with the traditional 2DWMMC-L1 method,the highlight of this method is that it can optimize all the projection vectors at the same time and seek a better projection matrix.(3)By introducing the idea of max-min into MMC-L1,a method of maximum minimum non-greedy maximum margin criterion based on L1-norm(NMLM-L1)and a two-dimensional extended version based on L1-nonn is proposed.This method makes full use of the idea of max-min,the advantages of MMC-L1,and uses non-greedy optimization algorithm to solve the objective function.