L1投影的解析计算方法

南京大学学报(自然科学版) ›› 2017, Vol. 53 ›› Issue (3): 476–.

L1投影的解析计算方法

杨绪兵1*，顾一凡1，陈松灿2，薛　晖3

出版日期:2017-05-30 发布日期:2017-05-30
作者简介: 1.南京林业大学信息科学技术学院，南京，210037；2.南京航空航天大学计算机科学技术学院，南京，210016；3．东南大学计算机科学与工程学院，南京，210096
基金资助:
基金项目：国家自然科学基金(31670554，61472186，60375057)，江苏省自然科学基金(BK20161527)，江苏高校品牌专业建设工程(PPZY2015A062)
收稿日期：2016－10－22
*通讯联系人，Email：xbyang@njfu.edu.cn

An analytic solution for L1 projection problem

Yang Xubing1*，Gu Yifan1，Chen Songcan2，Xue Hui3

Online:2017-05-30 Published:2017-05-30
About author: 1.College of Information Science and Technology，Nanjing Forestry University，Nanjing，210037，China；
2．School of Computer Science and Engineering，Nanjing University of Aeronautics & Astronautics，Nanjing，210016，China；
3．School of Computer Science and Engineering，Southeast University，Nanjing，210096，China

摘要/Abstract

摘要： 点到平面距离的解析表示对度量间隔、模式可分性起到决定性作用，该距离均可归结为范数最小化问题．除L2范数易于求解外，其他类型范数求解均困难．以L1范数为例，尽管L1范数问题是凸的，由于L1范数的不可导性，迄今尚无解析表示，所以目前的L1学习机并非从L1间隔导出．讨论了在L1赋范线性空间中，L1距离及在超平面上的投影解析计算问题，主要完成了：(1)导出了L1范数下的点到超平面距离以及点在平面上的投影的解析表达式；(2)证明了该投影与欧氏度量下的L2范数投影之间的关系，并给出了几何解释．最后通过模拟实验，验证解析解的正确性及计算效率．

Abstract: Analytic solutions of distances between scatter points and the decision hyperplane play conclusive roles in measuring margin and pattern separability.Theoretically，such distances can be induced into norm minimization problems.However，compare to L2 norm，nonL2 norms problems are more complex.As far as L1 norm is concerned，the stateoftheart L1 machines is NOT genuinely induced from L1 norm because of lacking of L1 closed solution.L1 minimization problem is convex，however，due to its nondifferentiability，the leading problem has to be computed by timeconsuming iteration methods.In this paper，we discuss how to analytically compute L1 distance and projection in linear space.Concretely，similar to L2 norm，we introduce two analytic formula for L1 distance and projection.Furthermore，we also prove relationship between L1 and L2 Euclidian distance，which can be described by a bilateral inequality.Finally，compared to linear programming methods，we show the effectiveness and efficiency of the proposal in some datasets.

杨绪兵1*，顾一凡1，陈松灿2，薛　晖3. L1投影的解析计算方法[J]. 南京大学学报(自然科学版), 2017, 53(3): 476–.

Yang Xubing1*，Gu Yifan1，Chen Songcan2，Xue Hui3. An analytic solution for L1 projection problem[J]. Journal of Nanjing University(Natural Sciences), 2017, 53(3): 476–.

参考文献

[1]　Suykens J A K，Vandewalle J．Least squares support vector machine classifiers.Neural Processing Letters，1999，9(3)：293－300.
[2] Mangasarian O L，Wild E W．Multisurface proximal support vector machine classification via generalized eigenvalues.IEEE Transaction Pattern Analysis and Machine Intelligence，2006，28(1)：69－74.
[3] Weinberger K Q，Saul L K．Distance metric learning for large margin nearest neighbor classification.Journal of Machine Learning Research，2009，10：207－244.
[4] Huang K，Yang H，King I，et al.Learning large margin classifiers locally and globally.In：Proceedings of the 21st International Conference on Machine Learning.Banff，Canada：ACM Press，2004，19：401－408.
[5] Yeung D S，Wang D，Ng W W Y，et al.Structured large margin machines：Sensitive to data distributions.Machine Learning，2007，68：171－200.
[6] Lanckriet G R G，Ghaoui L E，Bhattacharyya C，et al.A robust minimax approach to classification.Journal of Machine Learning Research，2002，3：555－582.
[7] Yang A Y，Ganesh A，Zhou Z，et al.Fast L1minimization algorithms and application in robust face recognition：A review.In：IEEE International Conference on Image Processing.Lake Buena Vista，USA：IEEE Press，2012：1849－1852.
[8] Figueiredo M，Nowak R，Wright S．Gradient projection for sparse reconstruction：application to compressed sensing and other inverse problems.IEEE Journal of Selected Topics in Signal Processing，2007，1：586－597.
[9] Weinberger K Q，Saul L K．Distance metric learning for large margin nearest neighbor classification.Journal of Machine Learning Research，2009，10：207－244.
[10] Malioutov D，Cetin M，Willsky A．Homotopy continuation for sparse signal representation.In：Proceedings of the IEEE International Conference on Acoustics，Speech，and Signal Processing(ICASSP)．Philadelphia，USA：IEEE Explore Press，2005，5：733－736.
[11] Yin W，Osher S，Goldfarb D，et al.Bregman iterative algorithms for l1minimization with applications to compressed sensing.SIAM Journal on Imaging Sciences，2008，1：143－168.
[12] Becker S，Bobin J，Candes E．NESTA：A fast and accurate firstorder method for sparse recovery.SIAM Journal of Imaging Science，2011 4：1－39.
[13] Lu G ，Zou J．Wang Y，et al.L1norm based principal component analysis with adaptive regularization.Pattern Recognition，2016，60：901－907.
[14] Mangasarian O L．Exact 1norm support vector machines via unconstrained convex differentiable minimization.Journal of Machine Learning Research，2006，7：1517－1530.
[15] Liu J，Ye J．Efficient euclidean projection in linear time.In：The 26th International Conference on Machine Learning(ICML)．Montreal，Canada：Omni Press，2009：657－664.
[16] Nesterov Y．Introduction Lectures on convex optimization：A basic course.Dordrecht，Netherlands：Kluwer Academic Publishers，2004，23－28.
[17] 杨绪兵，王一雄，陈　斌．马氏度量学习中的几个关键问题研究及几何解释．南京大学学报(自然科学)，2013，49(2)：133－141.(Yang X B，Wang Y X，Chen B．Research on several key problems of Mahalanobis metric learning and corresponding geometrical interpretations.Journal of Nanjing University(Natural Sciences)，2013，49(2)：133－141.)
[18] Zhu Q，Zhang D，Sun H，et al.Combining L1norm and L2norm based sparse representations for face recognition.International Journal for Light and Electron Optics，2015，126(7－8)：719－724.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed