[發明專利]一種基于指數化核范數與混合奇異值截斷的張量恢復方法

有效

• 申請號: 201410321348.0
• 申請日: 2014-07-07
• 公開（公告）號: CN104063852A
• 公開（公告）日: 2014-09-24
• 發明（設計）人: 張笑欽;王迪
• 申請（專利權）人: 溫州大學
• 主分類號: G06T5/00
• 分類號: G06T5/00
• 代理公司: 北京中北知識產權代理有限公司 11253
• 代理人: 段秋玲

技術領域

本發明涉及計算機模式識別技術領域，具體涉及一種基于指數化核范數與混合奇異值截斷的張量恢復方法。

背景技術

張量恢復(tensor completion)，即高維矩陣的恢復問題，對于一個部分元素缺失的高維矩陣，通過觀察其已有位置的元素，從而恢復出缺失部分元素的一般性問題，是計算機模式識別領域中的研究熱點之一，被廣泛應用于圖像去噪、圖像恢復、信息推薦系統等眾多領域。總的來說，大多數現有的張量恢復方法是基于低秩結構假設，即要求恢復的缺失元素使得整個張量的秩盡可能的小。目前有兩種傳統的定義張量秩的方法：基于張量的CP(CANDECOMP/PARAFAC)分解方法(CP秩)和Tucker分解方法(Tucker秩)。具體來說，CP秩可以定義為：用秩一張量(rank-one tensor)之和來表示給定張量需要的秩一張量的最小個數。Tucker秩可以定義為：不同模態下展開矩陣的秩的線性加權。無論是CP秩還是Tucker秩，最小化該張量秩的優化問題被證明是一個NP難問題。

為了解決上述問題，Gandy等人采用不同模態下展開矩陣秩的和來表示張量的秩，在計算過程中，將展開矩陣的秩用矩陣的核范數來近似代替。Signoretto等人提出一種Shatten-p范數來代替展開矩陣的核范數，并由此定義了張量的秩，最后討論了該方法與核范數之間的關系。隨后，Liu等人采用不同模態下展開矩陣核范數的線性加權來近似代替Tucker秩，并將該方法應用于圖像恢復和醫學圖像去噪。最后，Tomioka等人對張量恢復方法進行了總結，認為有兩種方式可以實現張量恢復：(1)將張量按某一個模態展開成二階矩陣，可以將張量恢復問題轉化為了二階矩陣的恢復問題；(2)采用不同模態下展開矩陣核范數的線性加權來近似代替Tucker秩。

可以看出，上述方法的目的都是尋找張量Tucker秩的近似。然而Tucker秩定義的幾何意義不清晰，并且張量不同模態下的權重難以選擇，如果某個模態下展開矩陣的秩很大，而其對應的權重很小，那么上述定義將無法正確地描述張量的秩結構，從而導致張量低秩恢復效果不夠理想。張量的CP秩是對矩陣秩的一個推廣，它的幾何意義比Tucker秩更為明確，然而直接優化CP秩是一個非常困難的問題，甚至連局部最優都難以獲得。

發明內容

針對現有技術存在的不足，本發明的目的在于提供一種基于指數化核范數與混合奇異值截斷的張量恢復方法，基于CP秩的思想，提出一種新的張量秩定義方式，該張量秩是CP秩的下界，并且能夠有效地逼近CP秩，使得張量恢復過程對噪聲更為魯棒。此外，該定義沒有任何權重參數需要設置，可以有效的消除參數影響。為了優化問題的可解性，我們用張量不同模態下展開矩陣核范數的指數和的對數來近似張量秩，并提出了一種混合奇異值截斷算法來獲得優化問題的解析解，從而實現快速有效的張量恢復。

為實現上述目的，本發明提供了如下技術方案：一種基于指數化核范數與混合奇異值截斷的張量恢復方法，其特征在于：包括以下三個步驟:

(1)提出一種新的張量秩定義：張量不同模態下展開矩陣秩的最大值；該定義是張量CP秩的下界，能夠有效的逼近CP秩，并消除了權重參數的影響，采用核范數指數和的對數來逼近該張量秩定義，將其轉化為凸函數；

(2)為了消除張量不同模態下展開的矩陣的相關性，引入一系列輔助變量來代替展開矩陣，并將約束條件利用拉格朗日乘子法轉化為增廣拉格朗日函數；

(3)采用交替方向法對增廣拉格朗日函數中各類變量進行迭代優化，直到收斂；其中，對于核范數的指數和中的優化變量，采用混合奇異值截斷算法來獲得解析解。

本發明進一步設置，所述的步驟(1)具體包括以下子步驟：

首先，根據張量CP秩和Tucker秩的優缺點，提出一種新的張量秩定義：張量展開矩陣秩的最大值；

其次，將展開矩陣的秩松弛為展開矩陣的核范數，并且利用核范數的指數和的對數來逼近最大值函數，從而將上述張量的秩定義轉化為凸函數。

本發明還進一步設置，所述的步驟(2)具體包括以下子步驟：

首先，由于張量在不同模態下的展開矩陣具有相關性，引入一系列輔助矩陣變量來替換不同模態下的展開矩陣，并增加對應的約束條件；

其次，采用拉格朗日乘子法將所有約束條件加入到目標函數中，獲得增廣拉格朗日函數。

本發明還進一步設置，所述的步驟(3)具體包括以下子步驟：

首先，為了對增廣拉格朗日函數中的不同變量進行分別優化，采用交替方向法對增廣拉格朗日函數中的各類變量進行迭代優化；