針對魯棒矩陣補全的加權冪分解方法

涂劍凱 李春光

（浙江大學信息與電子工程學院，浙江杭州 310027）

1 引言

矩陣補全旨在通過部分觀測的數據點來恢復一個完整的矩陣。由于大量的實際數據天然都是以矩陣形式進行組織的，矩陣補全在許多研究領域都引起了廣泛的關注，包括圖像修復［1-3］，推薦系統［4-7］與視頻靜態背景提取［8-10］。相較于基于數據學習的方式［11］，矩陣補全僅針對單個樣本即可完成上述任務，不需要額外的訓練數據。但在沒有額外信息的情況下，完整恢復部分觀測的矩陣幾乎是不可能的。在許多場景中，需要恢復的矩陣存在低秩的特性。核范數啟發式理論的提出證明了在矩陣存在低秩特性時，可以以較高的概率完整重構出這一矩陣［12-13］。具體而言，可以將矩陣的秩轉換為矩陣的核范數，矩陣補全問題因此可以建模成一個半正定的凸優化問題。但隨著大數據時代的到來以及高分辨率數字圖像的廣泛使用，矩陣補全問題的規模不斷擴大，傳統的半正定規劃算法［14］因其沒有很好地利用矩陣的低秩特性，面臨著巨大的效率問題。

近年來，許多方法被提出來高效地解決矩陣補全問題，同時利用矩陣低秩特性來進一步增強補全的性能。許多基于完整的（full）或者截斷的（truncated）奇異值分解（SVD）的方法被提出來以最小化矩陣的核范數，如奇異值閾值約束（SVT）方法［15］，定點連續化方法（FPC）［16］，硬閾值歸一化迭代方法（NIHT）［17］。但這一類算法在每個迭代環節中需要進行奇異值分解，這給每個迭代的計算過程帶來了較高的計算復雜度。……