快速低秩矩陣與張量恢復(fù)的算法研究

1、快速低秩矩陣與張量恢復(fù)的算法研究作者簡介劉園園，吉林長春人。2 0 0 2年本科畢業(yè)于吉林工程技術(shù)師范學(xué)院。2 0 0 7年畢業(yè)于東北大學(xué)獲碩士學(xué)位。2 0 13年6月獲西安電子科技大獲工學(xué)博士學(xué)位。導(dǎo)師：焦李成主要研究方向:機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識別和計yuanyuanl算機(jī)視覺等。u , wa s bo rn i nchangchun,j i 1 inprovince,china,ceivedherb. a.tersoftwarechersuteofengng & techno 1 ogy,chanchinat h e m. s . degreei n f rompauemre

2、c ogn i t ionandlntel 1heasternunivgentsystemf r o m n o r t e r s i t y , shenyang, china, i n 2 0 0 7 , andt h e p h d . degreeinpaaernrecogni t ion an din t e11 igents yste m f ro m x1d ia nuni ver s ity，x i 'an ，chi na ,i n jun e20 1herresearchinterests i n c 1 u d e m achinelearning, datami

3、ning, p a r e r n r ecogni t ion, andcomputervi s io n.西安電子科技大學(xué)學(xué)位論文獨(dú)創(chuàng)性（或創(chuàng)新性）聲明秉承學(xué)校嚴(yán)謹(jǐn)?shù)膶W(xué)風(fēng)和優(yōu)良的科學(xué)道德，本人聲明所呈交的論文是我 個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了文 中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外，論文中不包含其他人已經(jīng)發(fā) 表或撰寫過的研究成果；也不包含為獲得西安電子科技大學(xué)或其它教育機(jī) 構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任 何貢獻(xiàn)均己在論文屮做了明確的說明并表示了謝意。申請學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切的法律責(zé)任。本人簽名：西安電

4、子科技大學(xué)關(guān)于論文使用授權(quán)的說明本人完全了解西安電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即: 研究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬西安電子科技大學(xué)。 學(xué)校有權(quán)保留送交論文的復(fù)印件，允許查閱和借閱論文；學(xué)校可以公布論 文的全部或部分內(nèi)容，可以允許采用影印、縮卬或其它復(fù)制手段保存論文。 同時本人保證，畢業(yè)后結(jié)合學(xué)位論文研究課題再撰寫的文章一律署名單位 為西安電子科技大學(xué)。（保密的論文在解密后遵守此規(guī)定）本學(xué)位論文屬于保密，在一一年解密后適用本授權(quán)書。本人簽名:導(dǎo)師簽名：矗uu期：3 d吸7、工摘要摘要隨著現(xiàn)代傳感器、多媒體技術(shù)、計算機(jī)通信及網(wǎng)絡(luò)技術(shù)的飛速發(fā)展與 廣泛應(yīng)用，人們經(jīng)常需要存

5、儲、處理與分析規(guī)模更大、高維更高、結(jié)構(gòu)更 復(fù)雜的數(shù)據(jù)，如人臉圖像、監(jiān)控視頻、生物信息數(shù)據(jù)等。如何從被噪聲或 奇異點(diǎn)污染或部分丟失的觀測數(shù)據(jù)中恢復(fù)原始數(shù)據(jù)，已成為機(jī)器學(xué)習(xí)、數(shù) 據(jù)挖掘、模式識別及計算機(jī)視覺等領(lǐng)域的熱點(diǎn)研究問題。最近幾年，低秩矩陣與張量恢復(fù)及補(bǔ)全的核范數(shù)最小化方法取得了廣 泛的應(yīng)用。然而，它們的算法往往都需要迭代求解，而每次迭代又要進(jìn)行 一次或多次較大規(guī)模矩陣的奇異值分解（svd）或特征值分解計算，其 時間復(fù)雜度非常高。此外，矩陣或張量分解也是低秩矩陣與張量恢復(fù)及補(bǔ) 全常用的類方法，然而這類方法對噪聲及給定秩不夠魯棒。為了克服上 述的困難，本文圍繞快速低秩矩陣與低秩張量恢復(fù)及補(bǔ)全問

6、題中模型的建 立、算法的設(shè)計及算法的分析等方面進(jìn)行了系統(tǒng)的研究。從二階矩陣到高階張量，所取得的主要研究成果有：1為了避免每次迭代過程中較大矩陣的svd求解，提出了一種基 于矩陣三分解的快速核范數(shù)最小化框架。該框架可推廣應(yīng)用到三類問題: 低秩矩陣填充、低秩與稀疏矩陣分解和低秩表示。受啟發(fā)于svd與非負(fù) 矩陣分解，把矩陣的三分解思想引入到核范數(shù)最小化問題中。然后又分別 化模型。最后，還給出了相應(yīng)的交替迭代的求解算法。大量的實(shí)驗結(jié)果表 明了該章提出的快速矩陣分解的核范數(shù)正則最小化方法無論在性能與效 率上還是魯棒性上都超過了相關(guān)的核范數(shù)最小化算法。2 針對引入過多輔助變量從而導(dǎo)致迭代速度變慢的問題，提

7、出了一 種矩陣雙分解核范數(shù)正則的線性化框架。在此框架下，首先給出了一種矩 陣雙分解的線性化低秩表示模型，并推導(dǎo)了其交替迭代線性化算法。作為 上述模型的拓展，乂提出了一種矩陣雙分解的線性化低秩矩陣填充模型， 并提供了其交替迭代線性化算法。最后還理論分析了算法的收斂性。3.矩陣分解核范數(shù)止則框架的推廣與應(yīng)用。該章內(nèi)容不但推廣了第 二章的方法，提出一種半正定約束的低秩表示模型，而且還推廣了第三章 的方法，提出一種低，2.秩張量補(bǔ)全模型。然后又分別給出了上述兩個 模型相應(yīng)的有效迭代求解算法。通過大量的人工數(shù)據(jù)及實(shí)際數(shù)據(jù)的實(shí)驗， 驗證了本章提出的兩種算法的可行性與有效性。4針對矩陣分解的不唯一性導(dǎo)致求解

8、過程易陷入局部極小的問題， 將黎曼流形的思想引入非光滑優(yōu)化問題中，提岀了一種歐式空間梯度與黎 曼梯度混合的交西安電子科技大學(xué)智能感知與圖像理解教育部重點(diǎn)實(shí)驗 室替迭代框架用來求解核范數(shù)最小二乘問題。不但避免了大規(guī)模矩陣的 svd計算，還能確保迭代算法的解收斂到原始核范數(shù)模型的最優(yōu)解。首 先，對線性化近似的冃標(biāo)函數(shù)進(jìn)行矩陣分解將其轉(zhuǎn)化為g rassman n流形上的優(yōu)化問題；然后在g rassman n流形上推導(dǎo)其黎曼梯度,求解。最后還給出了算法的收斂性分析。5針對現(xiàn)有張量補(bǔ)全方法每次迭代需計算多重較大規(guī)模矩陣的s v d,從而導(dǎo)致復(fù)雜度非常高的問題，提出一種核心張量核范數(shù)最小化的框 架。受經(jīng)典

9、的張量tu c k e f分解的啟發(fā)，該章首先定義了一種核心張 量核范數(shù)，并分析了定義的核心張量核范數(shù)與張量核范數(shù)的關(guān)系。然后又 給出了核心張量核范數(shù)的張量補(bǔ)全模型，將大規(guī)模矩陣的svd計算轉(zhuǎn)換 成小規(guī)模矩陣的s v d計算問題，從而使得提出的模型具有很低的計算復(fù) 雜度。最后，還給出了一種基于交替方向乘子法的迭代求解算法。6為了克服低刀一秩張量核范數(shù)最小化問題計算復(fù)雜度高的問題, 并根據(jù)經(jīng)典的parafac (cp)分解的定義及性質(zhì)，提出了一種新 的因子矩陣秩最小化方法，并將提出的該框架應(yīng)用于張量補(bǔ)全問題。為了 區(qū)別已有的低行.秩模型，木文將提出的方法稱為廣義張量秩的張量填充 方法。通過使用凸

10、松弛技術(shù)，給出了相應(yīng)廣義張量核范數(shù)的張量補(bǔ)全模型, 并推導(dǎo)了一種基于交替方向乘子法的迭代求解算法。最后通過大量的人工 數(shù)據(jù)和實(shí)際數(shù)據(jù)驗證了提出的算法的有效性與高效性。關(guān)鍵詞：低秩矩陣恢復(fù)低秩矩陣補(bǔ)全核范數(shù)，1或f 2.范數(shù)低秩表 示魯棒主成分分析低秩張量補(bǔ)全西安電子科技大學(xué)博士論文abstract i i ia b s t rac tw i ththe rap i ddeve 1 opmentof thesensortechnology, m u 1 t imediatechnologr n e two rkandcommun i dimecompncevideos f romthep rem

11、orcorrupts . thenrankandcompuearning,hot top i c i n m a c h i n er n o r mm itensandcompcomeitercompcompchiton. theretheycoven r a n k t o m i t i g a tc 1 a s s o f approaches fori o w r a n kbussear mmmodr mm i n i m ii o n (f t f) b ai sproposed, andi susedintothreecf 1 ow r a nkma t r i x r e c

12、 o n s t r uoblemssuchi o n (mc ),1 ow rankandspa rsvdandnonne(l r s d ), and(lrr). motivatedthei n t r o d u c e d i n t o t h enuciearnormmiels. thenthreesma 1 e a r n o r mm i n i m i z af o r l r r, l r s d, andmca repingdirectionmethod(adm) b a s e d irat i v e a 1 g o rpedenteeproposmodandedftfapprate o f t h2 anoalgortion(mbf)nuclearzationframewo rizedoptimizationm e w o r k , r