關于秩函數近似方法綜述

山東科技大學數學與系統科學學院 常彩霞

關于秩函數近似方法綜述

山東科技大學數學與系統科學學院 常彩霞

主要介紹了秩函數的近似方法，包括凸近似法和非凸近似法，討論了各自的優點和不足。最后，指出了非凸近似法的研究趨勢及其應用前景。

秩函數；凸近似；非凸近似

一、引言

問題在機械學習、計算機視覺、控制、信號處理、系統識別等領域普遍存在。因為秩函數的非連續性和非凸性，矩陣秩最小化問題為NP難問題。為了高效解決該問題，需要對秩函數進行松弛，即尋找一個連續的函數來近似秩函數，作為低秩正則化項。秩函數近似方法主要分為兩類：凸近似和非凸近似。凸近似中，近似秩函數最常用的方法為核范數，求解核范數最小化問題的優點有很多，如求解比較容易，可以設計多種有效的優化算法等。但是，核范數近似是有一定缺陷的，如核范數最小化，就是同時將矩陣X 所有奇異值的和最小化，也就是對奇異值的懲罰力度是一樣的。眾所周知，矩陣的主要性質，通常是由矩陣的那些大的奇異值來起決定性作用，但核范數對矩陣所有奇異值的懲罰力度相同，實際上對大的奇異值是不公平的。相比于凸近似方法，非凸近似可以對實際問題有著更好的近似，能夠更好地刻畫實際問題的本質屬性。然而非凸優化問題具有很高的復雜性，設計快速高效的優化算法求解非凸優化問題是一項巨大的挑戰。

二、秩函數的凸近似方法

三、秩函數的非凸近似方法

為解決（2），提出TNNR-ADMM，TNNR-APGL和TNNRADMMAP三種有效算法。

2015年，Zhong X等[2]考慮一個解決低秩矩陣最小化問題的一般性框架，使用加權核范數作為正則化項：

問題（6）可利用ALM算法解決。

四、總結與展望

本文綜合介紹了現有的秩函數的近似方法，包括凸近似和非凸近似發展及研究現狀。在實際的問題中，非凸近似比凸近似方法有著更好的低秩矩陣恢復效果。但是核范數具有嚴格的理論保證，非凸松弛方法只有直觀的解釋，缺乏嚴格的理論論證。因此，下一步的研究重點是，對非凸松弛方法進行嚴格的理論分析，使用非凸近似方法，才能完美地恢復原來的矩陣秩函數，因此，秩函數近似的研究仍將是未來的一個研究熱點。

[1]Hu Y,Zhang D,Ye J,et al.Fast and accurate matrix completion via truncated nuclear norm regularization[J].IEEE.2013,35(9):2117-2130.

[2]Zhong X,Xu L,Li Y,et al.A Nonconvex Relaxation Approach for Rank Minimization Problems[C]. AAAI.2015:1980-1987.

[3]Kang Z,Peng C,Cheng Q.Robust subspace clustering via tighter rank approximation[C].2015:393-401.