數(shù)據(jù)恢復(fù)的相關(guān)技術(shù)的研究現(xiàn)狀綜述目錄TOC\o"1-3"\h\u1904數(shù)據(jù)恢復(fù)的相關(guān)技術(shù)的研究現(xiàn)狀綜述 1175861.1數(shù)據(jù)恢復(fù)的關(guān)鍵技術(shù) 1283331.2數(shù)據(jù)恢復(fù)的相關(guān)應(yīng)用 2313991.3矩陣填充技術(shù)的研究現(xiàn)狀 3274971.4張量填充技術(shù)的研究現(xiàn)狀 51.1數(shù)據(jù)恢復(fù)的關(guān)鍵技術(shù)5g時(shí)代，對(duì)海量數(shù)據(jù)分析和挖掘的需求越來越大。物聯(lián)網(wǎng)無線傳感器設(shè)備受限于硬件性能，不同地域網(wǎng)絡(luò)覆蓋差異大，信號(hào)不穩(wěn)定，數(shù)據(jù)丟包現(xiàn)象屢見不鮮，且多數(shù)設(shè)備缺少人機(jī)交互界面，一旦出現(xiàn)設(shè)備離線，消息丟失，往往會(huì)給用戶造成不可估量的損失。由于各種原因（如采樣成本或設(shè)備故障)，有時(shí)人們只能對(duì)部分?jǐn)?shù)據(jù)進(jìn)行采樣，而其他信息則丟失或空缺。確保提供物聯(lián)網(wǎng)服務(wù)的連續(xù)性和可用性并避免任何潛在的操作故障和中斷是如今無線傳感器領(lǐng)域一個(gè)非常重要的挑戰(zhàn)。當(dāng)收集到的數(shù)據(jù)不完整時(shí)，數(shù)據(jù)的后續(xù)使用就不能達(dá)到預(yù)期的效果，因此需要數(shù)據(jù)恢復(fù)技術(shù)。有三種流行的方法可以從一部分已知數(shù)據(jù)中恢復(fù)完整的數(shù)據(jù)：壓縮采樣技術(shù)、矩陣填充技術(shù)和張量填充技術(shù)[5]。壓縮采樣是一種準(zhǔn)確重建稀疏采樣子集的技術(shù)，允許數(shù)據(jù)的采樣方式遠(yuǎn)低于香農(nóng)-奈奎斯特采樣定理標(biāo)準(zhǔn)，用隨機(jī)采樣獲取信號(hào)的離散樣本，然后通過非線性重建算法完美重建信號(hào)。其基本思想是：只要信號(hào)是可壓縮的或在某個(gè)變換域是稀疏的，那么就可以用一個(gè)與變換基不相關(guān)的觀測(cè)矩陣將變換所得高維信號(hào)投影到一個(gè)低維空間上，然后通過求解一個(gè)最優(yōu)化問題就可以從這些少量的投影(或稱測(cè)量值)中以高概率重構(gòu)出原信號(hào)。然而，壓縮感應(yīng)主要用于處理向量數(shù)據(jù)，這限制了它的應(yīng)用范圍。緊接著壓縮感知，矩陣填充出現(xiàn)了。對(duì)比基于向量的恢復(fù)方法，作為矩陣可以捕獲更多的信息，基于矩陣的方法可以得到更精確地恢復(fù)性能。矩陣填充為在各種相關(guān)的應(yīng)用中充分利用低秩性帶來了新的機(jī)遇。目前，主流的矩陣填充算法主要包括四種類型：小規(guī)模矩陣完形算法、核參數(shù)化算法、格拉斯曼算法、最小化算法、格拉斯曼尼流形最小化算法和其他新算法[2]。不足的樣本數(shù)會(huì)使重建算法的計(jì)算時(shí)間過長(zhǎng)，恢復(fù)的數(shù)據(jù)不準(zhǔn)確，甚至算法不能收斂[1,8]。此外，盡管在數(shù)據(jù)缺失比例較低時(shí)，矩陣完成呈現(xiàn)出良好的性能，但當(dāng)缺失率較高時(shí)，性能將受到較大影響。因此，在低采樣率下準(zhǔn)確的數(shù)據(jù)恢復(fù)一直是很多研究的主題。當(dāng)人們需要處理規(guī)模更大、維度更高、結(jié)構(gòu)更復(fù)雜的數(shù)據(jù)而矩陣不能捕捉到數(shù)據(jù)的所有特征時(shí)，張量模型是一個(gè)更好的選擇。張量是一種類似于矢量但比矢量應(yīng)用范圍更廣的數(shù)據(jù)結(jié)構(gòu)，并可用于廣泛的應(yīng)用，如圖像、監(jiān)視和蜂群智能，在降低成本的同時(shí)提高效果。在傳統(tǒng)的數(shù)據(jù)分析方法中，數(shù)據(jù)通常被表示為向量形式，然而，這種處理方式會(huì)破壞數(shù)據(jù)的時(shí)空結(jié)構(gòu)，導(dǎo)致維度災(zāi)難和小樣本情況[12]。而張量表示則可以在一定程度上避免這些缺點(diǎn)。張量作為向量和矩陣的高階擴(kuò)展，而向量和矩陣可以分別被看作是一階和二階張量。由于張量元素的數(shù)量隨著維數(shù)的增加而呈指數(shù)級(jí)增長(zhǎng)，計(jì)算和存儲(chǔ)需求迅速增加，這成為實(shí)際應(yīng)用張量分解的一個(gè)主要挑戰(zhàn)。因此，設(shè)計(jì)高效準(zhǔn)確的數(shù)據(jù)張量恢復(fù)算法以減少計(jì)算開銷和加快張量完成過程是至關(guān)重要的。張量完成過程。1.2數(shù)據(jù)恢復(fù)的相關(guān)應(yīng)用壓縮感知方法被應(yīng)用到了多跳網(wǎng)絡(luò)和無線傳感器網(wǎng)絡(luò)中具有稀疏性或可壓縮性網(wǎng)絡(luò)數(shù)據(jù)的重構(gòu)上面。壓縮感知采樣的普遍性和分散式編碼的特征有可能使其成為一種新的網(wǎng)絡(luò)數(shù)據(jù)分析范例．更重要的是，借助偽隨機(jī)寬帶調(diào)制器，低通濾波器和采樣器，壓縮感知方法可以以較低采樣率實(shí)現(xiàn)對(duì)模擬信號(hào)到離散信號(hào)的直接采集。[17]矩陣填充在協(xié)同過濾、系統(tǒng)識(shí)別、信號(hào)處理、機(jī)器學(xué)習(xí)、計(jì)算機(jī)視覺、數(shù)據(jù)挖掘和模式識(shí)別、在線推薦系統(tǒng)等很多實(shí)際問題中都有非常重要的應(yīng)用。在圖像處理分析方面，壓縮感知方法也被廣泛應(yīng)用．此外，矩陣填充還被廣泛引入到計(jì)算機(jī)視覺、機(jī)器學(xué)習(xí)和圖像處理[13]。張量填充目前用在很多的網(wǎng)絡(luò)工程任務(wù)中，例如容量規(guī)劃，負(fù)載平衡，路徑建立，網(wǎng)絡(luò)供應(yīng)，異常檢測(cè)和故障恢復(fù)等，逐漸成為研究和應(yīng)用的熱點(diǎn)。因張量模型所具備的多維特性、多模式相關(guān)性和低秩特性高度吻合了交通流數(shù)據(jù)特征，因此多位學(xué)者在交通領(lǐng)域中引入張量理論與模型，研究?jī)?nèi)容包含交通流數(shù)據(jù)處理與修復(fù)、交通數(shù)據(jù)融合、短時(shí)交通流預(yù)測(cè)、交通事故探測(cè)、實(shí)時(shí)交通預(yù)警等多個(gè)方面。HadiFnaee．T與JoaoGama構(gòu)建了張量模型下的OD矩陣，結(jié)合Tucker分解提出了一種創(chuàng)新的交通事故探測(cè)算法，并在模擬環(huán)境和實(shí)際環(huán)境下進(jìn)行了實(shí)驗(yàn)驗(yàn)證；柯文前等人基于交通流網(wǎng)絡(luò)的時(shí)空特征，從張量分解的視角出發(fā)，對(duì)交通網(wǎng)絡(luò)時(shí)空特性進(jìn)行了解析、提取與挖掘，從局部至整體提取出不同的交通流時(shí)變規(guī)律；譚華春等人創(chuàng)新性地將張量理論運(yùn)用至交通領(lǐng)域，進(jìn)行了交通數(shù)據(jù)處理與修復(fù)、短時(shí)交通流預(yù)測(cè)與多元數(shù)據(jù)融合等多方面應(yīng)用研究，并在此基礎(chǔ)上提出了多種新型張量分解算法與張量填充算法。1.3矩陣填充技術(shù)的研究現(xiàn)狀矩陣填充的主要工作是研究如何從矩陣中的已知數(shù)據(jù)去恢復(fù)其未知數(shù)據(jù)的過程，即在僅僅采集到未知矩陣小部分?jǐn)?shù)據(jù)下恢復(fù)數(shù)據(jù)的問題。在沒有任何限制條件的情況下，矩陣填充問題的解是無窮多的，是不可解的，但在實(shí)際問題中，很多時(shí)候?qū)嶋H需要處理的數(shù)據(jù)矩陣都屬于低秩矩陣或者近似低秩矩陣，已有研究者證明了未知矩陣的低秩性是問題存在唯一解的前提。矩陣填充問題主要集中在恢復(fù)矩陣所需條件以及矩陣填充算法兩方面，其中設(shè)計(jì)出精確的低秩矩陣的重構(gòu)算法受到極大的關(guān)注，并已經(jīng)有了大量的研究成果。目前主流的矩陣填充算法主要包括小規(guī)模矩陣填充算法、核范數(shù)最小化求解類算法、格拉斯曼流形最小化求解類算法、其它新型算法四類[1]。小規(guī)模矩陣填充算法代表算法有內(nèi)點(diǎn)法[2]、投影次梯度法[3]和低秩參數(shù)化法[4]。核范數(shù)最小化求解類的代表算法有奇異值閾值算法、近似值的奇異值不動(dòng)點(diǎn)連續(xù)法等。格拉斯曼流形最小化求解類算法代表的有OptSpace算法[5]、SET算法[6]等。其他新型算法類中包括低秩矩陣擬合算法、截?cái)嗍胶朔稊?shù)類算法[7]等。這些算法使用觀察到的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)來獲得所需的參數(shù)，有助于更好的捕捉矩陣數(shù)據(jù)的全局特征，恢復(fù)丟失的數(shù)據(jù)。由于本文實(shí)驗(yàn)的需要，這里重點(diǎn)介紹OptSpace算法和SVT算法。OptSpace算法是一個(gè)從隨機(jī)采樣中恢復(fù)低秩矩陣的高效算法，主要使用了譜方法，它是在格拉斯曼流形上進(jìn)行目標(biāo)函數(shù)優(yōu)化。該算法對(duì)觀測(cè)矩陣進(jìn)行修剪，能夠顯著地提高數(shù)據(jù)恢復(fù)性能。在清理殘差時(shí)運(yùn)用格拉斯曼流形中的梯度下降法最小化目標(biāo)函數(shù)。OptSpace算法的目標(biāo)函數(shù)為矩陣填充的誤差，即在低秩性的約束下，使得填充得到的矩陣的元素值盡可能接近真實(shí)值。Cai等人在[？？]中指出核范數(shù)最小化方法受到最低秩矩陣條件約束，存在恢復(fù)結(jié)果不理想的情況。受線性化Bregman迭代方法在壓縮感知領(lǐng)域中用于求解L1范數(shù)極小化問題的啟發(fā)，Cai等人提出了一種簡(jiǎn)單的適用于較大規(guī)模的矩陣填充方法：奇異值閾值（SingularValueThresholding）算法。SVT算法是最早的一種解決矩陣填充問題的典型的Lagrange乘子算法，該算法使用軟閾值算子簡(jiǎn)化對(duì)迭代矩陣進(jìn)行的SVD分解，且迭代步驟較簡(jiǎn)潔，對(duì)于高維低秩矩陣的恢復(fù)非常有效。近年來矩陣填充理論取得了較大發(fā)展。Candés等人[8]證明了在采樣數(shù)目充分的條件下，規(guī)模為且秩為r的低秩矩陣可以通過求解一個(gè)簡(jiǎn)單的凸優(yōu)化問題恢復(fù)。并且證明了采樣率需要滿足的條件是。這里C是一個(gè)常數(shù)，。因此證明了精確恢復(fù)矩陣的數(shù)據(jù)所需的采樣數(shù)目下限不僅與矩陣秩r有關(guān)，還與矩陣的尺寸有關(guān)。如果采樣數(shù)目不充分，將使得重建算法需要長(zhǎng)時(shí)間的計(jì)算，恢復(fù)數(shù)據(jù)不準(zhǔn)確，甚至算法不收斂。此外，盡管數(shù)據(jù)缺失的比例較低時(shí)，矩陣填充呈現(xiàn)良好的性能，但當(dāng)缺失率高時(shí)，性能將會(huì)受到較大影響。因此在采樣率低的條件下精確恢復(fù)數(shù)據(jù)成為很多學(xué)者研究的課題。數(shù)據(jù)之間的關(guān)聯(lián)性是不同數(shù)據(jù)之間的關(guān)系，數(shù)據(jù)之間的關(guān)系對(duì)了解整個(gè)系統(tǒng)的運(yùn)行有著最直接的影響，數(shù)據(jù)之間的正確關(guān)系的梳理是系統(tǒng)有效運(yùn)行，產(chǎn)生價(jià)值的基石。因?yàn)閿?shù)據(jù)內(nèi)部的相關(guān)特性導(dǎo)致數(shù)據(jù)具有稀疏性，稀疏性使得通過采集部分推斷其余部分成為一種可行性方式。QuL[9]等人提出概率主成分分析方法解決數(shù)據(jù)丟失問題對(duì)流量分析的影響，并證明了相似性是影響數(shù)據(jù)恢復(fù)性能的一個(gè)因素。王樂樂等人[10]基于大量空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)的分析，揭露了空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)潛在的時(shí)間穩(wěn)定性，空間相關(guān)性等特性，同時(shí)證明了矩陣重構(gòu)降低了矩陣恢復(fù)所需的采樣數(shù)目下限，進(jìn)而可以獲得更好的恢復(fù)性能。并且充分利用空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)的潛在結(jié)構(gòu)，提出了矩陣重排原則，基于該原則提出了基于矩陣重排的矩陣填充算法來精確恢復(fù)不完整的矩陣。對(duì)于矩陣填充來說低秩性是數(shù)據(jù)能精確恢復(fù)的一個(gè)必要條件，而且矩陣的秩直接反映了對(duì)已知數(shù)據(jù)數(shù)量的要求。但是，除了低秩性，實(shí)際應(yīng)用中產(chǎn)生的數(shù)據(jù)往往還隱含著很多其他相關(guān)性例如，以氣象數(shù)據(jù)為例，根據(jù)經(jīng)驗(yàn)我們很容易能得出結(jié)論：氣象數(shù)據(jù)在不同地區(qū)、不同季節(jié)有著明顯的規(guī)律性，因此氣象數(shù)據(jù)應(yīng)該隱含著位置相關(guān)性、周期性等等相關(guān)特性。因?yàn)閿?shù)據(jù)內(nèi)部的相關(guān)特性會(huì)導(dǎo)致數(shù)據(jù)具有稀疏性，這是影響數(shù)據(jù)恢復(fù)性能的一個(gè)重要因素。因此，如果能盡量充分地利用數(shù)據(jù)內(nèi)部隱含的相關(guān)性，那么算法的性能有望得到很大提升。然而，現(xiàn)有的矩陣填充算法往往忽視了這些相關(guān)性，在數(shù)據(jù)缺失率很高的情況下，矩陣填充算法的性能大打折扣。如何在數(shù)據(jù)缺失率很高的情況下充分利用數(shù)據(jù)內(nèi)部隱含的相似性對(duì)缺失數(shù)據(jù)進(jìn)行填充是目前的一大挑戰(zhàn)，如果能夠解決這一問題，那么數(shù)據(jù)恢復(fù)的性能將得到極大提高。同時(shí)，由于只使用很少一部分?jǐn)?shù)據(jù)就能精確地恢復(fù)全部數(shù)據(jù)，可以減少采樣過程中的能量損耗以及傳輸成本，使采樣間隔更長(zhǎng)或者對(duì)設(shè)備的要求降低，這對(duì)于氣象數(shù)據(jù)監(jiān)控、群智感知、網(wǎng)絡(luò)監(jiān)控等等領(lǐng)域都有著重大意義。1.4張量填充技術(shù)的研究現(xiàn)狀張量填充是一個(gè)可以從有限的測(cè)量來恢復(fù)低秩張量的理論，已經(jīng)應(yīng)用于推薦系統(tǒng)[15]，多分類學(xué)習(xí)[16]，圖像壓縮[17]，數(shù)據(jù)挖掘[18]等領(lǐng)域。張量填充可以從有限的測(cè)量來恢復(fù)低秩張量，基于張量的缺失數(shù)據(jù)恢復(fù)方法可以充分利用數(shù)據(jù)的多重相關(guān)特性，克服基于矩陣方法的不足，對(duì)于多維數(shù)據(jù)已經(jīng)被證明是一個(gè)很好的分析手段。因?yàn)閿?shù)據(jù)內(nèi)部的相關(guān)特性導(dǎo)致了數(shù)據(jù)的稀疏性，稀疏性使得從收集的張量完成關(guān)鍵依賴于張量分解，它有兩種主要形式：CANDECOMP/PARAFAC(CP)分解[19]與Tucker分解[20]。CP分解是擴(kuò)展矩陣分解到多維數(shù)據(jù)最成功的，如REF_Ref97038706\h圖2，CP分解將一個(gè)高維的張量分解成多個(gè)向量外積的和，通過這樣的分解，可以降低參數(shù)的維度。然而，CP方法仍有不足。至今沒有直接的算法來計(jì)算給定張量的秩，這被證明是一個(gè)NP難問題。對(duì)于實(shí)際問題，事先確定一個(gè)張量的CP秩或者最低的CP秩近似常常計(jì)算復(fù)雜度非常高。圖SEQ圖\*ARABIC2三維張量CP分解示意圖Tucker分解可以看作是矩陣奇異值分解與主成分分析的高維范化，如REF_Ref97038757\h圖3所示，主要思路是將張量分解為一個(gè)核張量與每一維度上對(duì)應(yīng)矩陣的乘積。然而，不同于矩陣PCA中最佳降維可以通過截?cái)嗟腟VD獲得，Tucker分解的降維沒有多線性的求解方法。此外，由于張量元素隨著維度的數(shù)目增加而指數(shù)級(jí)增長(zhǎng)，計(jì)算與存儲(chǔ)需求急速增加，這成為實(shí)際中應(yīng)用張量分解的主要挑戰(zhàn)。因此，設(shè)計(jì)有效的精確的數(shù)據(jù)張量恢復(fù)算法用以減少計(jì)算開銷并加速?gòu)埩刻畛溥M(jìn)程至關(guān)重要。圖SEQ圖\*ARABIC3三維張量Tucker分解示意圖基于這兩種分解方法，PrateekJain等人給出了基于CP分解的張量完成方案[18]，JiLiu等人給出了基于Tucker分解的張量完成方案[19]，這些方案已經(jīng)被應(yīng)用到許多領(lǐng)域，如推薦系統(tǒng)和計(jì)算機(jī)視覺。AcarE等人開發(fā)了一種名為CP-WOPT的算法，該算法使用一階優(yōu)化方法來解決加權(quán)最小二乘問題[?]