一類高維多響應(yīng)變量誤差模型的極小極大下界

李欣, 吳東亞

(1. 西北大學(xué)數(shù)學(xué)學(xué)院, 陜西 西安 710127;2. 西北大學(xué)信息科學(xué)與技術(shù)學(xué)院, 陜西 西安 710127)

1 引言

近幾十年來, 高維統(tǒng)計(jì)學(xué)在理論和應(yīng)用上都取得了豐碩的成果[1-2]; 為了應(yīng)對維度災(zāi)難, 研究者們提出了不同的具有低維結(jié)構(gòu)的統(tǒng)計(jì)模型, 如稀疏線性回歸, 低秩矩陣回歸, 以及近幾年的高階張量回歸等等. 例如, 文獻(xiàn)[3-4] 研究了低秩矩陣回歸, 提出了核范數(shù)正則化估計(jì)量, 在一定的正規(guī)條件下證明了估計(jì)量的統(tǒng)計(jì)一致性. Chen 等人考慮了多變量廣義線性模型, 通過塊稀疏回歸技巧建立了特征選擇一致性和參數(shù)估計(jì)的最優(yōu)性[5]. 文獻(xiàn)[6-9] 采用凸或非凸優(yōu)化方法研究了高維多響應(yīng)張量回歸. 在合適的低維結(jié)構(gòu)化假設(shè)下, 研究者們給出了關(guān)于統(tǒng)計(jì)和計(jì)算層面的理論保證. 具體地, 文獻(xiàn)[7] 提出了一般的凸優(yōu)化方法并在協(xié)變量相依的情況下得到了估計(jì)量的統(tǒng)計(jì)誤差上界. 文獻(xiàn)[8] 進(jìn)一步考慮了計(jì)算效率, 提出的非凸估計(jì)方法取得了較凸方法更優(yōu)的收斂速率, 并應(yīng)用近端梯度算法實(shí)現(xiàn)了問題的求解. 文獻(xiàn)[9] 采用極大似然估計(jì)方法, 得到了參數(shù)的估計(jì)和預(yù)測誤差以及漸進(jìn)性質(zhì). 文獻(xiàn)[6] 考慮了非凸估計(jì)方法, 建立了統(tǒng)計(jì)誤差界和近端梯度算法的線性收斂速率, 并證明了非凸估計(jì)量的極小極大最優(yōu)性.

特別地, 多響應(yīng)回歸模型作為矩陣回歸的一個(gè)重要實(shí)例, 在理論層面得到了深入研究[3,10], 并被廣泛應(yīng)用于實(shí)際問題,如神經(jīng)影像分析等[11-12]. 考慮如下多響應(yīng)回歸模型

其中Θ?∈Rd1×d2是未知的參數(shù)矩陣,Y∈Rn×d2是響應(yīng)矩陣,X∈Rn×d1是協(xié)變量矩陣,?∈Rn×d2是噪音矩陣. 為了獲得相合的估計(jì), 參數(shù)矩陣Θ?通常被賦予某些結(jié)構(gòu)約束如低秩性.

高維統(tǒng)計(jì)學(xué)通常分為兩個(gè)研究方向. 一方面, 研究者們致力于構(gòu)造具有快速收斂率的估計(jì)量. 另一方面, 探索估計(jì)量的本質(zhì)或信息理論極限進(jìn)而評價(jià)其性能也具有十分重要的意義. 前一目標(biāo)可以通過一些統(tǒng)計(jì)技巧如集中不等式等建立估計(jì)誤差的上界實(shí)現(xiàn),而后者通常需要借助信息理論工具以推導(dǎo)基于某些定量標(biāo)準(zhǔn)的下界.

給定真實(shí)未知參數(shù)的一個(gè)任意估計(jì)量, 存在很多標(biāo)準(zhǔn)可以用于評價(jià)估計(jì)的質(zhì)量. 從決策理論的框架而言, 通常是引入一個(gè)損失函數(shù)用以表示估計(jì)過程所帶來的損失. 然后根據(jù)極小極大法則, 構(gòu)造一個(gè)最壞情況損失函數(shù)并極小化之, 以刻畫最優(yōu)收斂率. 在推導(dǎo)最壞情況損失函數(shù)下界的過程中, 經(jīng)常需要用到假設(shè)檢驗(yàn)不等式和Fano 不等式以及估計(jì)一些信息理論參量, 如互信息, Kullback-Leibler(KL) 散度以及全變差距離等; 詳細(xì)的討論見文獻(xiàn)[13-14].

注意在模型(1) 中, 當(dāng)d2= 1 且未知參數(shù)Θ?被賦予向量稀疏性約束時(shí), 模型(1)退化為稀疏線性回歸, 并得到了大量關(guān)于極小極大估計(jì)的研究. 例如, 文獻(xiàn)[15-16] 采用標(biāo)準(zhǔn)的信息理論技巧, 給出了估計(jì)的極小極大收斂率. 文獻(xiàn)[17] 提出一種聚合策略, 借此建立了極小極大最優(yōu)收斂率, 進(jìn)一步構(gòu)造了一個(gè)自適應(yīng)的最優(yōu)估計(jì)量. 轉(zhuǎn)到低秩估計(jì)問題, 研究者們主要關(guān)注矩陣補(bǔ)全問題進(jìn)而建立極小極大最優(yōu)收斂率[18-20]; 文獻(xiàn)[21]則考慮了一類一般的低秩矩陣恢復(fù)問題, 利用有限維Schatten 空間中某些恒等映射的Gelfand 寬度, 給出了最壞情況誤差界的估計(jì).

上述提到的工作都基于協(xié)變量是干凈數(shù)據(jù)的假設(shè), 這在理論分析中是很標(biāo)準(zhǔn)的. 然而, 實(shí)際問題中由于實(shí)驗(yàn)儀器的限制或觀測的不完全, 這一假設(shè)總是會被違背. 也就是說, 收集得到的協(xié)變量數(shù)據(jù)通常帶有一定的測量誤差. 那么如果忽略測量誤差, 直接應(yīng)用針對干凈協(xié)變量數(shù)據(jù)建立的方法呢? 答案令人沮喪, 因?yàn)橐呀?jīng)有文獻(xiàn)[22] 通過模擬指出這一操作只會帶來錯誤的結(jié)果. 因此, 在協(xié)變量數(shù)據(jù)帶有誤差擾動的情形下, 研究統(tǒng)計(jì)模型并建立方法更加必要且具有現(xiàn)實(shí)意義.

近年來, 研究者們開始致力于變量誤差回歸模型, 大部分結(jié)果建立在線性或廣義線性模型上[23-26]; 在信息理論層面, 文獻(xiàn)[27-28] 考慮了線性誤差模型, 分別估計(jì)了不同向量集合的KL 散度, 建立了稀疏向量估計(jì)的極小極大下界.

然而迄今為止, 研究者們對帶有測量誤差的多響應(yīng)回歸模型(1) 的關(guān)注相對較少.盡管一個(gè)自然而簡單的想法是將協(xié)變量矩陣和響應(yīng)變量矩陣同時(shí)向量化, 這時(shí)原始的多響應(yīng)模型退化為單響應(yīng)變量情形, 進(jìn)而可以直接應(yīng)用上述關(guān)于單響應(yīng)變量，亦即線性回歸的結(jié)果. 但是由于更為復(fù)雜的流形結(jié)構(gòu), 矩陣的低秩性與向量的稀疏性截然不同[4].更進(jìn)一步, 響應(yīng)變量的多元性使得人們可以建立更為復(fù)雜的模型用于現(xiàn)代大規(guī)模關(guān)聯(lián)分析, 如fMRI 影像分析等[12], 因而相比于單響應(yīng)變量模型具有更為廣泛的應(yīng)用.

本文研究了多響應(yīng)變量誤差模型的信息理論極限. 首先將對下界的估計(jì)轉(zhuǎn)換為一個(gè)多重假設(shè)檢驗(yàn)問題, 然后應(yīng)用Fano 不等式[14]估計(jì)錯誤概率的下界. 本文的主要貢獻(xiàn)如下. 首先借助隨機(jī)矩陣乘法的集中不等式, 得到互信息中涉及的KL 散度的估計(jì). 然后對一類低秩矩陣, 以平方Frobenius 范數(shù)的形式建立了極小極大損失函數(shù)的下界. 更進(jìn)一步, 這一下界達(dá)到了文獻(xiàn)[18,20-21] 在干凈協(xié)變量假設(shè)下的收斂率, 表明即使在更具實(shí)際意義的變量誤差模型中, 仍然不需要更多的樣本以獲得收斂率最優(yōu)的估計(jì).

本文的結(jié)構(gòu)安排如下. 在第2 節(jié), 給出關(guān)于多響應(yīng)變量誤差模型和極小極大估計(jì)問題的背景知識. 在第3 節(jié), 建立了關(guān)于極小極大下界的主要結(jié)果. 結(jié)論和未來工作在第4 節(jié)討論.

在此, 先介紹一些符號以供接下來參考. 所有向量都是遵從經(jīng)典數(shù)學(xué)慣例的列向量.對d≥1, 令I(lǐng)d表示d×d維恒等矩陣. 對矩陣X∈Rn×d, 令Xij(i= 1,··· ,n,j=1,2,··· ,d) 表示其第ij個(gè)元素,Xi·(i=1,··· ,n) 表示其第i行,X·j(j=1,2,··· ,d)表示其第j列. 當(dāng)X是方陣, 即n=d時(shí), 用diag(X) 表示一個(gè)對角矩陣, 其對角元分別等于X11,X22,··· ,Xdd. 用λmin(X) 和λmax(X) 分別表示矩陣X的最小和最大特征值. 對矩陣Θ ∈Rd1×d2, 定義d= min{d1,d2}, 并將其按降序排列的奇異值記為σ1(Θ) ≥σ2(Θ) ≥···σd(Θ) ≥0. 用|||·||| 表示基于奇異值的不同矩陣范數(shù), 包括核范數(shù)|||Θ|||?= ∑dj=1σj(Θ), 譜或算子范數(shù)|||Θ|||op=σ1(Θ), 以及Frobenius 范數(shù)

2 問題建立

本節(jié)將給出多響應(yīng)回歸變量誤差模型的詳細(xì)描述并介紹極小極大估計(jì)問題.

考慮如下高維多響應(yīng)回歸模型, 表達(dá)了響應(yīng)向量Yi·∈Rd2與協(xié)變量向量Xi·∈Rd1之間的關(guān)系

其中Θ?∈Rd1×d2是未知的參數(shù)矩陣,?i·∈Rd2是響應(yīng)向量的觀測誤差, 且?i,j,?i·與Xj·獨(dú)立. 模型(1) 可以更緊湊的矩陣形式表達(dá). 具體而言, 定義多響應(yīng)矩陣Y=(Y1·,Y2·,··· ,Yn·)?∈Rn×d2, 類似的, 以向量的形式分別定義協(xié)變量矩陣X∈Rn×d1和噪音矩陣?∈Rn×d2. 那么模型(2) 可重新寫作

本文主要研究高維情形, 其中協(xié)變量或響應(yīng)變量的數(shù)量(即d1或d2) 可能超過樣本數(shù)量n. 眾所周知, 在這一情形下, 除非參數(shù)空間被賦予額外的低維結(jié)構(gòu)(如矩陣估計(jì)問題中的低秩性) , 否則無法實(shí)現(xiàn)估計(jì)的相合性. 特別地, 假設(shè)R0?min{d1,d2}, 在本文中將考慮如下的低秩矩陣集合

在下面定理3.1 的證明中, 將看到關(guān)于Stiefel 流形的結(jié)果將被用于分析目標(biāo)低秩矩陣集合

在標(biāo)準(zhǔn)多響應(yīng)回歸模型(3) 中, 通常假設(shè)協(xié)變量矩陣X是準(zhǔn)確獲得的. 然而在實(shí)際應(yīng)用中, 協(xié)變量經(jīng)常受到噪音的干擾. 在這一更為現(xiàn)實(shí)的情形下, 人們只能觀測到帶有擾動的協(xié)變量矩陣Z而不是真實(shí)協(xié)變量矩陣X, 這也將是本文關(guān)注的情形. 詳細(xì)而言, 本文考慮如下的帶有加性噪音的變量誤差模型：對每個(gè)i= 1,2,··· ,n, 觀測到Zi·=Xi·+Wi·, 其中Wi·∈Rd1是一個(gè)與Xi·獨(dú)立的隨機(jī)噪音向量, 均值為0, 協(xié)方差矩陣已知為Σw. 當(dāng)噪音協(xié)方差矩陣Σw未知時(shí), 可嘗試以統(tǒng)計(jì)方法從觀測數(shù)據(jù)中進(jìn)行估計(jì), 見文獻(xiàn)[29]. 舉例而言, 一個(gè)簡單的方法是從空白控制觀測組中估計(jì)Σw. 具體來說, 假設(shè)矩陣W0∈Rn×d1是空白觀測組中的數(shù)據(jù), 由n個(gè)獨(dú)立同分布的測量誤差向量組成, 那么矩陣可被用于Σw的估計(jì)量. 基于此方法的更加復(fù)雜的方法見文獻(xiàn)[29].

本文對加性變量誤差模型施加如下的Gaussian 隨機(jī)假設(shè).

假設(shè)2.1對i=1,2,··· ,n, 向量Xi·,Wi·和?i·是獨(dú)立同分布的Gaussian 隨機(jī)向量, 均值為0, 協(xié)方差矩陣分別為

注2.1上述Gaussian 隨機(jī)假設(shè)在研究者可以根據(jù)目標(biāo)設(shè)計(jì)實(shí)驗(yàn)的領(lǐng)域, 如信號處理和壓縮感知中, 具有特殊的重要意義而被廣泛使用[30]. 其中零均值假設(shè)很容易通過列歸一化得到滿足. 但值得注意的是, 在某些統(tǒng)計(jì)領(lǐng)域, 這一獨(dú)立Gaussian 假設(shè)仍然有一定局限性. 進(jìn)一步的研究將推廣當(dāng)前結(jié)果至更一般的協(xié)變量數(shù)據(jù), 如具有非對角協(xié)方差矩陣的次- Gaussian 分布.

因?yàn)閷γ總€(gè)i=1,2,··· ,n,Zi·=Xi·+Wi·,所以擾動協(xié)變量向量Zi也是Gaussian的, 均值為0, 協(xié)方差矩陣為(σ2x+σ2w)Id1. 為了簡單起見, 令σ2z=σ2x+σ2w, 并將Zi的協(xié)方差矩陣記為Σz=σ2zId1.

從統(tǒng)計(jì)學(xué)的角度, 為了估計(jì)未知參數(shù)Θ?, 研究者們試圖構(gòu)造一個(gè)估計(jì)量:Rn×d1×Rn×d2→Rd1×d2, 它是觀測數(shù)據(jù)(Z,Y) 的可測函數(shù). 而信息理論的任務(wù)是評估估計(jì)量的性能. 標(biāo)準(zhǔn)做法是引入一個(gè)損失函數(shù)L(,Θ?), 其表達(dá)了當(dāng)真實(shí)參數(shù)屬于某個(gè)特定集合(即本文中的Θ?∈) 時(shí), 由估計(jì)量所引入的損失. 在極小極大法則中, 本文目標(biāo)是找到下述以平方Frobenius 范數(shù)形式給出的最壞情況損失函數(shù)的下界

其中下確界inf 取遍觀測數(shù)據(jù)(Z,Y) 的所有可測函數(shù). 由于對噪音W和?的依賴,M() 是隨機(jī)的. 因此, 所要得到的下界應(yīng)該以期望或概率的形式給出.

3 主要結(jié)果

本節(jié)中將以很高的概率建立極小極大下界. 為清晰起見, 下面給出一些有用的定義.

定義3.1(次- Gaussian 矩陣) 隨機(jī)矩陣Γ ∈Rn×d1稱為是參數(shù)為(Σγ,σ2γ) 的次- Gaussian 矩陣, 如果它滿足如下條件:

(i) 每一行Γi·都是獨(dú)立同分布的隨機(jī)向量, 均值為0, 協(xié)方差矩陣為Σγ;

(ii) 對任意單位向量u∈Rd1, 隨機(jī)變量u?Γi·是次- Gaussian 的, 參數(shù)最大為σγ.

注3.1回憶本文施加在加性噪音模型上的假設(shè)2.1. 由定義3.1 易見矩陣X,W和?都是次- Gaussian 矩陣, 參數(shù)分別為(Σx,σ2x), (Σw,σ2w) 和(Σ?,σ2?). 又因?yàn)閆=X+W,Z也是次- Gaussian 矩陣, 參數(shù)為(Σz,σ2z).

定義3.2(KL 散度) 對兩個(gè)分布P 和Q, 其概率密度關(guān)于某個(gè)基礎(chǔ)測度μ分別是dP 和dQ, 這兩個(gè)分布之間的KL散度定義為

定義3.3(互信息) 對兩個(gè)隨機(jī)變量B和B′, 其分布函數(shù)分別是PB和PB′, 這兩個(gè)隨機(jī)變量之間的互信息定義為I(B;B′)=EB′[D(PB|B′||PB)], 其中PB|B′是B關(guān)于B′的條件分布.

定義3.4(?- packing 集合) 令(V,ρ) 是一個(gè)賦范線性空間, 范數(shù)為ρ:V×V→R+,S?V. {Θ1,Θ2,··· ,ΘN} 稱為是S的一個(gè)?- packing 集合, 如果滿足對任意i≠j, 都有ρ(Θi,Θj)>?. ?稱為S的這個(gè)packing 集合的半徑.

在給出定理3.1 之前, 需要如下三個(gè)引理. 引理3.1 來自文獻(xiàn)[25] 的補(bǔ)充材料的引理14, 給出了一般的次- Gaussian 隨機(jī)矩陣與固定向量乘法的偏離界. 引理3.2 同樣是統(tǒng)計(jì)意義上的, 反映了一般的次- Gaussian 隨機(jī)矩陣與固定矩陣乘法的集中不等式. 引理3.3 是信息理論層面的, 利用了引理3.2 的結(jié)果, 并且專門針對本文考慮的Gaussian隨機(jī)模型(見假設(shè)2.1). 引理3.3 估計(jì)了由不同參數(shù)Θ,Θ′∈所導(dǎo)出的響應(yīng)變量Y的兩個(gè)分布之間的KL 散度. 令PΘ表示多響應(yīng)加性變量誤差模型中, 當(dāng)給定參數(shù)矩陣Θ和觀測協(xié)變量矩陣Z時(shí), 響應(yīng)變量Y的分布.

引理3.2令t> 0 是任意常數(shù), Γ ∈Rn×d1是一個(gè)零均值的次- Gaussian 矩陣,參數(shù)為(Σγ,σ2γ). 那么對任意固定矩陣Θ ∈Rd1×d2, 存在一個(gè)普適正常數(shù)c0使得

證明根據(jù)矩陣Frobenius 范數(shù)的定義, 有

然后根據(jù)基本概率理論得到

另一方面, 由題設(shè)Γ 是參數(shù)為(Σγ,σ2γ) 的次- Gaussian 矩陣, 應(yīng)用引理3.1 可得, 存在一個(gè)普適正常數(shù)c0使得

引理3.3在加性變量誤差模型中, 令假設(shè)2.1 成立. 那么存在一個(gè)普適正常數(shù)c0, 使得至少以概率1-2 exp(-c0n+logd2) 保證如下結(jié)果成立, 其表示不同參數(shù)所導(dǎo)出Y的兩個(gè)分布的KL 散度的上界

證明對每個(gè)固定的i= 1,2,··· ,n, 根據(jù)模型設(shè)置, (Yi·,Zi·) 服從均值為0 的聯(lián)合Gaussian 分布. 通過計(jì)算協(xié)方差矩陣可以得到

然后由關(guān)于Gaussian 隨機(jī)向量條件分布的標(biāo)準(zhǔn)結(jié)果可得

假設(shè)σ?和σw不同時(shí)為0, 因?yàn)榉駝t的話, 結(jié)論自然成立. 對不同參數(shù)定義采用類似的方式定義. 回憶假設(shè)2.1中并注意到Σz=σ2zId1, 有

根據(jù)制粒原料不同的力學(xué)特性，考慮到物料在喂料過程中的規(guī)律性和?？捉Y(jié)構(gòu)的軸對稱性，可以將?？字械奈锪蟿澐譃闄M觀各向同性材料和各向同性材料。分別如圖2和圖3所示。

由(9) 式可知ΣΘ= ΣΘ′, 因此(10) 式中的前兩項(xiàng)均等于0. 再根據(jù)(9) 式得到也是對角矩陣, 其前R0個(gè)對角元等于, 后d2-R0個(gè)對角元等于由于, 將這些討論與(10) 式聯(lián)合, 得到

現(xiàn)在只需應(yīng)用引理3.2 估計(jì)(11) 式中|||Z(Θ-Θ′)|||2F的界. 由假設(shè)2.1 可知, 矩陣Z是由服從N(0,σ2zId1) 的獨(dú)立同分布的行組成的. 根據(jù)定義3.1 可得矩陣Z是參數(shù)為(σ2zId1,σ2z) 的次- Gaussian 矩陣. 那么在引理3.2 中用(11) 式的矩陣Z替換矩陣Γ, 并令t=d2σ2z, 可得存在一個(gè)普適正常數(shù)c0使得

這表明

將上式帶入(11) 式, 得到存在一個(gè)普適正常數(shù)c0, 使得下式至少以概率1 -2 exp(-c0n+logd2) 成立

定理3.1在加性變量誤差模型中, 令2 ≤R0≤d1-R0以及假設(shè)2.1 成立. 那么存在普適正常數(shù)(c0,c1) 使得, 至少以概率1/2(1-2 exp(-c0n+logd2)) 成立如下極小極大下界

這一下界的證明遵循信息理論分析的標(biāo)準(zhǔn)步驟. 從全局角度而言, 證明基本分為以下三步. 首先, 對極小極大下界的估計(jì)轉(zhuǎn)化為一個(gè)合適的packing 集合上的多重假設(shè)檢驗(yàn)問題. 這個(gè)packing 集合在目前被當(dāng)做已知, 其具體形式將在最后一步確定. 然后, 應(yīng)用Fano 不等式[14]來估計(jì)錯誤概率的下界, 即(14) 式的右端(見(15) 式). 在這一步, 需要估計(jì)(15) 式中涉及到的互信息的上界, 這將通過其與KL 散度的聯(lián)系實(shí)現(xiàn)(見定義3.3 和(16) 式). 最后, 找到前述packing 集合. 為此需要確定三個(gè)與這一特定packing 集合相關(guān)的參數(shù), 分別為(14) 式中的packing 半徑?, (14) 式中的基數(shù)N,以及(17) 式中任意兩個(gè)不同元素間距離的上界(即, 對所有j≠k). 此外, 選擇的packing 集合還必須確保(15) 式的概率嚴(yán)格大于0. 將通過選取合適的常數(shù), 借助Stiefel 流形Vd1,R0(見(5) 式) 的packing 集合來構(gòu)造目標(biāo)集合(見(4)式) 的packing 集合.

證明對正數(shù)?> 0, 令{Θ1,Θ2,··· ,ΘNF(?)} 表示按Frobenius 范數(shù)意義的最大?- packing 集合, 其中NF(?) 表示這一packing 集合的基數(shù). 后續(xù)用N作為NF(?) 的簡寫. 直接由文獻(xiàn)[14] 中的標(biāo)準(zhǔn)技巧將對下界的估計(jì)轉(zhuǎn)化為如下多重假設(shè)檢驗(yàn)問題

其中?> 0 是packing 集合{Θ1,Θ2,··· ,ΘN} 的半徑,B∈Rd1×d2是一個(gè)均勻分布于這一packing 集合的矩陣隨機(jī)變量,是取值于這一packing 集合的B的估計(jì)量.由(14) 式可見需要估計(jì)概率P(≠B) 的下界. 根據(jù)Fano 不等式, 有

其中I(Y;B) 表示隨機(jī)分布參數(shù)矩陣B∈Rd1×d2與觀測響應(yīng)矩陣Y∈Rn×d2的互信息. 由(15) 式可知需要估計(jì)互信息I(Y;B) 的上界. 令PΘj表示當(dāng)給定B= Θj和噪音協(xié)變量矩陣Z時(shí),Y的分布. 由于B均勻分布在packing 集合上,Y具有混合分布, 進(jìn)而可得

其中最后一個(gè)不等式由KL 散度的凸性得到. 將這一不等式與引理3.3 聯(lián)立可得, 存在一個(gè)普適正常數(shù)c0, 使得至少以概率1-2 exp(-c0n+logd2), (16) 式具有如下上界

定義隨機(jī)事件A={(17) 成立}. 那么有P(A)≥1-2 exp(-c0n+logd2). 接下來, 將找到的一個(gè)合適的packing 集合, 并據(jù)此估計(jì)(17) 式中|||Θ-Θ′|||2F的上界, 以及確保(15) 式嚴(yán)格大于0. 根據(jù)假設(shè)2 ≤R0≤d1-R0以及文獻(xiàn)[31] 中的引理A.6 與公式(A.16) 可得對正數(shù)δ>0, 存在集合使得對任意j≠k,都有并且logN≥R0(d1-R0)log(c2/δ), 其中c2是一個(gè)普適正常數(shù). 也就是說是Vd1,R0的一個(gè)δ- packing 集合. 接下來對所有j=1,··· ,N, 令

其中0 表示d1×(d2-R0) 維零子矩陣. 容易驗(yàn)證{Θ1,Θ2,··· ,ΘN} ?并且是的一個(gè)這是因?yàn)閷θ我鈐≠k都有進(jìn)一步可得那么由(18) 式定義的集合{Θ1,Θ2,··· ,ΘN} 正是要尋找的的?-packing 集合. ?的具體值稍后給出. 將不等式帶入(17) 式, 得到在事件上A成立

將(19) 式和(15) 式聯(lián)立并注意到logN≥R0(d1-R0)log(c2/δ), 可得

對普適正常數(shù)c3, 令因此那么只需選取合適的常數(shù), (20) 式一定嚴(yán)格大于0, 并且可以1/2 為下界. 具體而言, 容易驗(yàn)證只要選擇常數(shù)c2,c3滿足

那么(20) 式以1/2 為下界. 事實(shí)上, 由2 ≤R0≤d1-R0可得R0(d1-R0) ≥4.因此只要一定有(21) 式成立. 并且如果選取合適常數(shù)c2,c3滿足(22) 式也成立. 將P(≠B|A) ≥1/2 和P(A) ≥1-2 exp(-c0n+logd2) 帶入(14) 式, 最終得到存在普適正常數(shù)(c0,c1)(其中c1=c23) 使得

注3.2(i) 注意到Fano 不等式在定理3.1 的證明中至關(guān)重要. Fano 不等式在文獻(xiàn)[32] 中首先被提出, 最初是為了反映多重假設(shè)檢驗(yàn)的平均誤差概率與隨機(jī)樣本和相應(yīng)參數(shù)的聯(lián)合分布之間的關(guān)系. 隨后這一不等式被用于統(tǒng)計(jì)學(xué)研究, 用來估計(jì)的信息理論極小極大收斂率[33-34]. 為了應(yīng)用這一技巧, 需要控制互信息并構(gòu)造合適的packing集合. 這也是本文的工作之一.

(ii) 定理3.1 證明在加性變量誤差情形下, 以很高的概率, 用任何方法都大約需要max{d1,d2}R0個(gè)樣本以實(shí)現(xiàn)對秩為R0的d1×d2維矩陣相合的估計(jì). 以往的研究也涉及到矩陣補(bǔ)全問題的信息理論極限[18,20]. 具體而言, 對一個(gè)秩為R0的d×d維方陣, 文獻(xiàn)[18] 表明大約需要R0dlogd個(gè)樣本去恢復(fù), 而在文獻(xiàn)[20] 中, 樣本數(shù)的階降為R0d, 這是因?yàn)槭┘恿祟~外的“spikiness” 性質(zhì), 這是對低秩矩陣奇異值向量的特定條件. 文獻(xiàn)[21] 利用有限維Schattenp- 空間之間恒等映射的Gelfand 寬度, 并證明對低秩矩陣恢復(fù)問題, 其最壞情況函數(shù)下界的階為R0d/n. 本文的結(jié)果適用于更一般的多響應(yīng)回歸模型且不需要求未知參數(shù)矩陣是方陣, 在協(xié)變量帶有測量誤差的情形下, 建立的極小極大下界仍然達(dá)到了上述針對干凈數(shù)據(jù)的階. 這一結(jié)果進(jìn)一步表明即使在加性變量誤差模型中, 依然不需要更多的樣本以實(shí)現(xiàn)收斂率最優(yōu)的估計(jì).

(iii)極小極大最優(yōu)性一般通過兩個(gè)方面進(jìn)行分析,也就是關(guān)于最壞情況函數(shù)(見(6)式) 的信息理論下界和統(tǒng)計(jì)誤差上界. 信息理論重點(diǎn)關(guān)注下界的理論性質(zhì), 定理3.1 建立的下界階為(見(13) 式). 在統(tǒng)計(jì)層面, 上界的推導(dǎo)通常依賴于對特定估計(jì)量的構(gòu)造性分析并進(jìn)行數(shù)值模擬驗(yàn)證. 對加性誤差模型而言, 已在另一篇文章中通過構(gòu)造一個(gè)形式為∈arg minΘ{L(Θ)+λ|||Θ|||?} 的糾偏估計(jì)量, 其中L(Θ) 表示模型擬合的糾偏損失函數(shù),λ> 0 表示施加低秩約束的正則化參數(shù), 從而得到了上界, 見文獻(xiàn)[36] 的定理1. 注意當(dāng)選擇正則化參數(shù)時(shí), 本文的下界(13)與文獻(xiàn)[36] 的定理1 的上界同階. 與此同時(shí), 文獻(xiàn)[36] 通過數(shù)值模擬驗(yàn)證了上界階的合理性, 這也從另一方面驗(yàn)證了本文關(guān)于下界的極小極大最優(yōu)收斂速率.

4 結(jié)論

本文關(guān)注了高維多響應(yīng)變量誤差模型中低秩估計(jì)問題的信息理論極限. 借助信息理論和統(tǒng)計(jì)學(xué)的技巧, 針對一類特殊的矩陣集合, 建立了以平方Frobenius 損失函數(shù)形式給出的極小極大下界. 結(jié)果表明在測量誤差情形下, 估計(jì)的難度并沒有增加, 仍然只需要與干凈數(shù)據(jù)情形時(shí)相當(dāng)?shù)臉颖炯纯蓪?shí)現(xiàn)相合估計(jì).

需要注意的是這一工作仍然存在一些局限性. 首先對模型施加的獨(dú)立同分布Gaussian 假設(shè)(見假設(shè)2.1 式). Gaussian 隨機(jī)矩陣在研究者們可以設(shè)計(jì)實(shí)驗(yàn)的領(lǐng)域,如信號處理和壓縮感知[30], 具有特殊的意義和廣泛的應(yīng)用. 然而, 獨(dú)立Gaussian 假設(shè)在其它統(tǒng)計(jì)領(lǐng)域中仍有一定的局限性, 盡管零均值假設(shè)很容易通過列歸一化被滿足. 下一步研究可以將現(xiàn)有結(jié)果推廣至更一般的協(xié)變量類中, 如帶有非對角元的次- Gaussian矩陣, 或者其它誤差模型, 如乘性或相關(guān)噪音. 此外, 本文只考慮了一類相對局限的目標(biāo)參數(shù)集(見(4) 式), 其與Stiefel 流形具有某種相似結(jié)構(gòu). 這一相似性在推導(dǎo)KL 散度以及構(gòu)造合適的packing 集合中至關(guān)重要. Stiefel 流形上packing 集合的豐富性極大促進(jìn)了定理3.1 的證明. 對其它矩陣類的分析將是未來一個(gè)很有前景的研究方向, 關(guān)鍵在于對KL 散度更精準(zhǔn)的估計(jì)和適當(dāng)packing 集合的構(gòu)尋找.