11.1 子集搜索與評(píng)價(jià)

我們將屬性稱為特征
相關(guān)特征：對(duì)當(dāng)前學(xué)習(xí)任務(wù)有用的屬性骆捧。
無(wú)關(guān)特征：對(duì)當(dāng)前學(xué)習(xí)任務(wù)無(wú)用的屬性。
特征選擇：從給遠(yuǎn)的特征集合中選擇出相關(guān)特征子集的過(guò)程顿膨。

特征選擇是顯示機(jī)器學(xué)習(xí)任務(wù)中重要的"數(shù)據(jù)預(yù)處理"過(guò)程锅锨。
有兩個(gè)意義：
① 減少無(wú)關(guān)屬性，減輕維數(shù)災(zāi)難恋沃。
② 留下關(guān)鍵屬性必搞，降低學(xué)習(xí)任務(wù)的難度。

特征選擇的過(guò)程中要保證不丟失重要特征芽唇，否則將降低學(xué)習(xí)器性能。假設(shè)初始的特征集包含了所有重要特征。

欲從初始的特征集合中選取一個(gè)包含了所有重要信息的特征子集匆笤，可行的做法是產(chǎn)生一個(gè)"候選子集"研侣，評(píng)價(jià)出它的好壞，基于評(píng)價(jià)結(jié)果產(chǎn)生下一個(gè)候選子集炮捧，再對(duì)其進(jìn)行評(píng)價(jià)……這個(gè)過(guò)程持續(xù)進(jìn)行下去庶诡，直至無(wú)法找到更好的候選子集為止。

上述過(guò)程涉及兩個(gè)關(guān)鍵環(huán)節(jié):
如何根據(jù)評(píng)價(jià)結(jié)果獲取下一個(gè)候選特征子集?
如何評(píng)價(jià)候選特征子集的好壞?

給定特征集合{a₁,a₂,……,a_d}咆课，可以將每個(gè)特征看作一個(gè)候選子集末誓。

• 環(huán)節(jié)1：子集搜索問(wèn)題(如何根據(jù)評(píng)價(jià)結(jié)果獲取下一個(gè)候選特征子集?)
  1）前向搜索
  對(duì)d個(gè)候選子集進(jìn)行評(píng)價(jià)，假設(shè){a₂}最優(yōu)书蚪，于是將{a₂}作為第一輪的選定集喇澡；
  然后，在選定集中加上一個(gè)特征殊校，構(gòu)成兩個(gè)特征的候選子集晴玖，即{a₂,a_i}(i≠2)，假定在這d-1個(gè)候選子集中为流，{a₂,a₄}最優(yōu)呕屎，且優(yōu)于{a₂}，則作為選定集敬察，
  重復(fù)這樣的過(guò)程秀睛，直到第k+1輪，最優(yōu)的候選子集{a₂,a₄,……,a_i}不如第k輪的選定集時(shí)莲祸，則停止生成候選子集蹂安，并將第k輪的選定集作為特征選擇結(jié)果。

  2）后向搜索
  從完整的特征集開(kāi)始虫给，每次嘗試去掉一個(gè)無(wú)關(guān)特征藤抡，逐漸減少特征。

  3）雙向搜索
  將前向與后向搜索結(jié)合起來(lái)抹估，每一輪逐漸增加選定相關(guān)特征(這些特征在后續(xù)輪中將確定不會(huì)被去除)缠黍，同時(shí)減少無(wú)關(guān)特征。

• 環(huán)節(jié)2：子集評(píng)價(jià)問(wèn)題(如何評(píng)價(jià)候選特征子集的好壞?)
  假定樣本屬性均為離散型的药蜻。給定數(shù)據(jù)集D瓷式，D中第i類(lèi)樣本所占的比例為p_i(i=1,2,3,……,|Y|)。對(duì)屬性子集A语泽，假定根據(jù)其取值將 分成了V個(gè)子集{D¹, D² ,...,D^V}贸典，每個(gè)子集中的樣本在A上取值相同(4.2有相應(yīng)詳細(xì)解釋)，可得屬性子集A的信息增益

  信息增益Gain(A)越大踱卵，意味著特征子集A包含的重要信息越多廊驼。于是据过，將信息增益作為評(píng)價(jià)準(zhǔn)則。

將上述的子集搜索機(jī)制和子集評(píng)價(jià)機(jī)制結(jié)合妒挎，就是特征選擇方法绳锅。
常見(jiàn)的特征選擇方法大致可分為三類(lèi):
過(guò)濾式、包裹式和嵌入式

11.2 過(guò)濾式選擇

過(guò)濾式方法先對(duì)數(shù)據(jù)集進(jìn)行特征選擇酝掩，然后再訓(xùn)練學(xué)習(xí)器鳞芙，即先用特征選擇過(guò)程對(duì)初始特征進(jìn)行"過(guò)濾"，再用過(guò)濾后的特征來(lái)訓(xùn)練模型期虾。其中常用的過(guò)濾式特征選擇方法是Relief原朝。

• Relief過(guò)濾式特征選擇方法
  Relief是為二分類(lèi)問(wèn)題設(shè)計(jì)的。該方法利用"相關(guān)統(tǒng)計(jì)量"來(lái)度量特征的重要性镶苞。該統(tǒng)計(jì)量是一個(gè)向量喳坠，每個(gè)分量分別對(duì)應(yīng)于一個(gè)初始特征。
  特征子集的重要性則是由子集中每個(gè)特征所對(duì)應(yīng)的相關(guān)統(tǒng)計(jì)量分量之和來(lái)決定宾尚。
  最終只需指定一個(gè)閾值丙笋，然后選擇比閾值大的相關(guān)統(tǒng)計(jì)量的分量所對(duì)應(yīng)的特征即可』吞或者指定選取k特征個(gè)數(shù)御板，然后選擇前k大相關(guān)統(tǒng)計(jì)量即可。

  由上面可以知道牛郑，Relief關(guān)鍵在于如何確定統(tǒng)計(jì)量怠肋。

  給定數(shù)據(jù)集{(x₁,y₁),(x₁,y₁),……,(x_m,y_m)}，在Relief中淹朋，對(duì)每個(gè)樣本x_i有：
  "猜中近鄰"(near-hit)：同類(lèi)樣本中笙各，與x_i最近鄰的樣本x_i,nh。
  "猜錯(cuò)近鄰"(near-miss)：異類(lèi)樣本中础芍，與x_i最近鄰的樣本x_i,nm杈抢。

  對(duì)于每個(gè)屬性j的相關(guān)統(tǒng)計(jì)量的分量為

  其中，x_a^j表示樣本x_a在屬性j上的取值仑性；
  對(duì)diff(x_a^j,x_b^j)有：
  若屬性j為離散型惶楼，則x_a^j=x_b^j時(shí)，diff(x_a^j,x_b^j)=0诊杆，否則為1歼捐；
  若屬性j為連續(xù)型，則diff(x_a^j,x_b^j)=|x_a^j-x_b^j|晨汹。(x_a^j,x_b^j∈[0,1])
  從上式中可以看出：
  1）若x_i與其猜中近鄰樣本x_j,nh在屬性j上的距離小于x_i與其猜錯(cuò)近鄰樣本x_j,nj在屬性j上的距離豹储，則說(shuō)明屬性j對(duì)區(qū)分同類(lèi)與異類(lèi)樣本是有益的，故增大屬性j所對(duì)應(yīng)的統(tǒng)計(jì)量分量淘这。
  2）反之剥扣，若大于的話巩剖，則說(shuō)明屬性j對(duì)于分類(lèi)起負(fù)作用，故減小屬性j所對(duì)應(yīng)的統(tǒng)計(jì)量分量钠怯。
  3）最后球及，基于每個(gè)樣本x_i在屬性j上的估計(jì)結(jié)果進(jìn)行平均，就得到屬性j的統(tǒng)計(jì)量分量呻疹，分量值越大，則對(duì)應(yīng)屬性的分類(lèi)能力就越強(qiáng)筹陵。

• Relief-F是用于多分類(lèi)的刽锤。
  假定數(shù)據(jù)集D中的樣本來(lái)自Y個(gè)類(lèi)別。對(duì)樣本x_i朦佩，若它屬第k類(lèi)(k∈{1,2,,…,Y})并思，
  則Relief-F先在第k類(lèi)的樣本中尋找x_i的最近鄰樣本x_i,nh并將其作為猜中近鄰，
  然后在第k類(lèi)之外的每個(gè)類(lèi)中找到一個(gè)x_i的最近鄰樣本作為猜錯(cuò)近鄰语稠，記為x_i,l,nm (l=1,2,…,Y;且l≠k)宋彼。
  且記p_l記為第l類(lèi)樣本在數(shù)據(jù)集D中的占比。

  于是仙畦，相關(guān)統(tǒng)計(jì)量對(duì)應(yīng)于屬性j的分量為

11.3 包裹式選擇

包裹式特征選擇直接把最終將要使用的學(xué)習(xí)器性能作為特征子集的評(píng)價(jià)準(zhǔn)則输涕。包裹式特征選擇的目的就是為給定學(xué)習(xí)器選擇最有利于其性能、 "量身定做"的特征子集慨畸。

LVW是常用的包裹時(shí)特征選擇方法莱坎。
LVW基于拉斯維加斯框架下使用隨機(jī)策略來(lái)進(jìn)行子集搜索，并以最終分類(lèi)器的誤差作為特征子集評(píng)價(jià)標(biāo)準(zhǔn)寸士。

拉斯維加斯方法

11.4 嵌入式選擇與L1正則化

嵌入式特征選擇是將特征選擇過(guò)程與學(xué)習(xí)器訓(xùn)練過(guò)程融為一體弱卡，兩者在同一個(gè)優(yōu)化過(guò)程中完成乃正，即在學(xué)習(xí)器訓(xùn)練過(guò)程中自動(dòng)地進(jìn)行了特征選擇。

給定數(shù)據(jù)集D={(x₁,y₁),(x₂,y₂),……,(x_m,y_m)}婶博，以線性回歸模型為學(xué)習(xí)模型瓮具，以平方誤差為損失函數(shù)，則優(yōu)化目標(biāo)為

• 若引入L₂范數(shù)正則化，則優(yōu)化目標(biāo)稱為"嶺回歸"忠荞，很夠顯著降低過(guò)擬合風(fēng)險(xiǎn)蒋歌。

• 但我們可以引入更好的L₁范數(shù)正則化帅掘，則有

  其中，λ>0堂油，稱為LASSO(最小絕對(duì)收縮選擇算子)修档。L₁不僅可以降低過(guò)擬合風(fēng)險(xiǎn)，還可以更容易求得"稀疏解"府框，即LASSO求得的w會(huì)有更少的非零分量吱窝。
  通過(guò)一個(gè)直觀的例子來(lái)理解：假設(shè)x僅有兩個(gè)屬性，于是有w₁,w₂迫靖，將他們作為坐標(biāo)軸院峡；
  然后畫(huà)出，上式中 第一項(xiàng)的"等值線"系宜，即Σ_i=1^m(y_i-w^Tx_i)2的等值線照激，即在(w₁,w₂)空間中平方誤差項(xiàng)取值相同的點(diǎn)的連線；
  接著分別畫(huà)出盹牧，L₁范數(shù)和L₂范數(shù)的等值線俩垃。在(w₁,w₂)空間中L₁范數(shù)取值相同的點(diǎn)的連線，以及L₂范數(shù)取值相同的點(diǎn)的連線汰寓。
  可以看出口柳，采用L₁范數(shù)時(shí)，平方誤差項(xiàng)等值線與L₁范數(shù)等值線的交點(diǎn)常出現(xiàn)在坐標(biāo)軸上有滑，即w₁或w₂取值為0啄清；
  而采用L₂范數(shù)時(shí)，兩者的交點(diǎn)常出現(xiàn)在某個(gè)象限中俺孙，即w₁或w₂均不為0辣卒；也就是說(shuō)，采用L₁范數(shù)比L₂范數(shù)更易于得到稀疏解睛榄。

基于L₁正則化的學(xué)習(xí)方法就是一種嵌入式特征選擇方法荣茫，其特征選擇過(guò)程與學(xué)習(xí)器訓(xùn)練過(guò)程融為一體， 同時(shí)完成场靴。

• PGD求解L1正則化問(wèn)題
  可以使用近端梯度下降去求解L1正則化問(wèn)題啡莉。
  1）優(yōu)化目標(biāo)
  令▽表示微分算子，對(duì)優(yōu)化目標(biāo)：
  若f(x)可導(dǎo)旨剥，且▽f 滿足L-Lipschitz（利普希茨連續(xù)條件）咧欣，即存在常數(shù)L＞0使得：
  2）泰勒展開(kāi)
  則在x_k處我們可以泰勒展開(kāi)：
  上式是嚴(yán)格相等，由L-Lipschitz條件我們可以看到：
  這里給出了一個(gè)L的下界轨帜，且下界的形式與二階導(dǎo)函數(shù)形式類(lèi)似魄咕，從而泰勒展開(kāi)式的二階導(dǎo)便通過(guò)L替代，從而嚴(yán)格不等也變成了近似：
  3）簡(jiǎn)化泰勒展開(kāi)式
  化簡(jiǎn)上式：
  其中φ(x_k)是與x無(wú)關(guān)的const常數(shù).
  4）簡(jiǎn)化優(yōu)化問(wèn)題
  這里若通過(guò)梯度下降法對(duì)f(x)進(jìn)行最小化蚌父，則每一步下降迭代實(shí)際上等價(jià)于最小化二次函數(shù)f(x)哮兰，從而推廣到我們最上面的優(yōu)化目標(biāo)毛萌，類(lèi)似的可以得到每一步的迭代公式:
  令
  則我們可以先計(jì)算z，再求解優(yōu)化問(wèn)題：
  5）求解上式
  

參考鏈接：
https://blog.csdn.net/kabuto_hui/article/details/88534460

11.5 稀疏表示與字典學(xué)習(xí)

• 稀疏表示
  數(shù)據(jù)集D以矩陣表示喝滞，每一行為一個(gè)樣本阁将，每一列為一個(gè)屬性。特征選擇所考慮的問(wèn)題是特征具有“稀疏性”右遭，即矩陣中的許多列與當(dāng)前學(xué)習(xí)任務(wù)無(wú)關(guān)做盅，我們需要通過(guò)特征選擇去除這些列。

  考慮另一種稀疏性：在數(shù)據(jù)集 D 所對(duì)應(yīng)的矩陣中存在很多零元素窘哈，但這些零元素并不是以整列言蛇、整行形式存在的。當(dāng)樣本具有這樣的稀疏表示時(shí)宵距，對(duì)學(xué)習(xí)任務(wù)有不少好處，比如稀疏表示的數(shù)據(jù)更容易線性可分吨拗。同時(shí)满哪，稀疏表示的數(shù)據(jù)在存儲(chǔ)上的負(fù)擔(dān)不大。

  我們可以通過(guò)將數(shù)據(jù)轉(zhuǎn)換為“恰當(dāng)稀疏”的形式劝篷，獲得稀疏表示的好處哨鸭，簡(jiǎn)化學(xué)習(xí)任務(wù)。這種為普通稠密表達(dá)的樣本找到合適的字典娇妓，將樣本轉(zhuǎn)化為稀疏表示形式像鸡，從而使學(xué)習(xí)任務(wù)得以簡(jiǎn)化，模型復(fù)雜度得以降低哈恰，通常稱為“字典學(xué)習(xí)”只估，亦稱“稀疏編碼”。

• 字典學(xué)習(xí)
  給定數(shù)據(jù)集{x₁,x₂,…,x_m}着绷，字典學(xué)習(xí)最簡(jiǎn)單的形式為

  其中B∈R^dxk為字典矩陣蛔钙；k稱為字典的詞匯量，通常由用戶指定荠医；
  α_i∈R^k則是樣本x_i∈R^d的稀疏表示吁脱。上式中，第一項(xiàng)希望由α重構(gòu)x_i彬向，第二項(xiàng)則是希望α盡量稀疏兼贡。

  我們采用變量交替優(yōu)化的策略來(lái)求解上式。
  第一步：固定字典矩陣B娃胆，更新上式中的分量遍希，我們可以用LASSO的解法(上一節(jié)中有講過(guò))來(lái)求解，從而為每個(gè)樣本x_i找到相應(yīng)的α_i里烦。

  分量
  第二步：固定α_i孵班，更新字典B涉兽，原式寫(xiě)為
  求解該式的策略有基于逐列更新的K-SVD。令b_i表示字典矩陣B的第i列篙程，α_i表示稀疏矩陣A的第i行枷畏，上式可以寫(xiě)為
  在更新字典的第i列時(shí)，其他列是固定的虱饿，因此E_i是固定的拥诡，只需要對(duì)上式進(jìn)行奇異值分解得到最大奇異值所對(duì)應(yīng)的正交向量即可。
  但是氮发，這樣做會(huì)破壞第一步得到的稀疏性渴肉，因此K-SVD在奇異值分解之前，對(duì)E_i和α_i做專(zhuān)門(mén)處理：αⁱ只保留非零元素爽冕，E_i只保留b_i與αⁱ的非零元素的乘積項(xiàng)仇祭；然后再進(jìn)行奇異值分解。

  反復(fù)迭代上述兩步颈畸，最終即可求得字典B和樣本x_i的稀疏表示 α_i乌奇。

稀疏表示的具體的過(guò)程簡(jiǎn)單描述如下：
1）確定映射字典的詞匯量k，并初始化字典B眯娱，d*k礁苗，其中d為樣本屬性數(shù)
2）固定住字典B，用LASSO求得樣本集 X 通過(guò)字典映射后的稀疏表示a_i
3）固定住α_i來(lái)更新字典B徙缴，K-SVD進(jìn)行求解试伙。
4）反復(fù)第2、3步于样，最終可得合適的字典B和樣本X的稀疏表示a_i疏叨。

• 代碼實(shí)現(xiàn)

  1）載入數(shù)據(jù)，可以隨便找一個(gè)張圖片

import numpy as np
import pandas as pd
from scipy.io import loadmat
 
train_data_mat = loadmat("../data/train_data2.mat")
 
train_data = train_data_mat["Data"]
train_label = train_data_mat["Label"]
 
print(train_data.shape, train_label.shape)

2）初始化字典

u, s, v = np.linalg.svd(train_data)
n_comp = 50
dict_data = u[:, :n_comp]

3）字典更新

def dict_update(y, d, x, n_components):
    """
    使用KSVD更新字典的過(guò)程
    """
    for i in range(n_components):
        index = np.nonzero(x[i, :])[0]
        if len(index) == 0:
            continue
        # 更新第i列
        d[:, i] = 0
        # 計(jì)算誤差矩陣
        r = (y - np.dot(d, x))[:, index]
        # 利用svd的方法穿剖，來(lái)求解更新字典和稀疏系數(shù)矩陣
        u, s, v = np.linalg.svd(r, full_matrices=False)
        # 使用左奇異矩陣的第0列更新字典
        d[:, i] = u[:, 0]
        # 使用第0個(gè)奇異值和右奇異矩陣的第0行的乘積更新稀疏系數(shù)矩陣
        for j,k in enumerate(index):
            x[i, k] = s[0] * v[0, j]
    return d, x

4）迭代更新求解
可以指定迭代更新的次數(shù)考廉，或者指定收斂的誤差。

from sklearn import linear_model
 
max_iter = 10
dictionary = dict_data
 
y = train_data
tolerance = 1e-6
 
for i in range(max_iter):
    # 稀疏編碼
    x = linear_model.orthogonal_mp(dictionary, y)
    e = np.linalg.norm(y - np.dot(dictionary, x))
    if e < tolerance:
        break
    dict_update(y, dictionary, x, n_comp)
 
sparsecode = linear_model.orthogonal_mp(dictionary, y)
 
train_restruct = dictionary.dot(sparsecode)

字典學(xué)習(xí)以及稀疏特征詳細(xì)理解：
https://www.cnblogs.com/hdu-zsk/p/5954658.html

字典學(xué)習(xí)過(guò)程詳解：
https://www.cnblogs.com/endlesscoding/p/10090866.html#_label0

奇異值分解：
https://www.cnblogs.com/endlesscoding/p/10033527.html
https://blog.csdn.net/weixin_42462804/article/details/83905320

11.6 壓縮感知

在現(xiàn)實(shí)任務(wù)中携御，我們希望可以通過(guò)部分信息來(lái)恢復(fù)全部信息昌粤。因?yàn)樵趯?shí)際中為了便于數(shù)據(jù)的傳輸存儲(chǔ)，人們通常會(huì)將數(shù)據(jù)進(jìn)行壓縮啄刹，這有可能會(huì)損失一部分信息涮坐，而傳輸?shù)倪^(guò)程中又可能會(huì)丟失一部分信息。這時(shí)候擁有根據(jù)接收到的受損的數(shù)據(jù)來(lái)恢復(fù)全部數(shù)據(jù)的能力就很重要了誓军。壓縮感知為解決此類(lèi)問(wèn)題提供了靈感袱讹。

• 假設(shè)有長(zhǎng)度為m的離散信號(hào)x，以一個(gè)采樣率進(jìn)行采樣，得到長(zhǎng)度為n的采樣后信號(hào)y(y也稱"測(cè)量值")捷雕，其中n遠(yuǎn)小于m椒丧，有

  其中，Φ∈R^nxm是對(duì)信號(hào)x的測(cè)量矩陣救巷，它確定了以某個(gè)頻率進(jìn)行采樣以及如何將采樣樣本組成采樣后的信號(hào)壶熏。
  若已知Φ和x，很容易求出y浦译；但由于上式是一個(gè)欠定方程(方程的個(gè)數(shù)少于未知函數(shù)的個(gè)數(shù))棒假，即使將y和Φ傳輸給對(duì)方，也難以還原原來(lái)的x精盅。(假定x本身不是稀疏的)

  若有個(gè)線性變化Ψ∈R^mxm帽哑，使得x=Ψs，且s具有稀疏性叹俏，y可以表示為

  s具有稀疏性妻枕，就可以很好解決欠定方程的問(wèn)題，因?yàn)橄∈栊允沟梦粗蛩卮蟠鬁p少粘驰。Ψ稱為稀疏基屡谐，而A=ΦΨ的作用類(lèi)似于字典，能將信號(hào)轉(zhuǎn)化為稀疏表示晴氨。于是，若能根據(jù)y恢復(fù)s碉输，就可以通過(guò)x=Ψs求出原來(lái)信號(hào)x籽前。
  s可以通過(guò)處理后會(huì)轉(zhuǎn)化稀疏信號(hào)。如敷钾，傅里葉轉(zhuǎn)換等枝哄。

• 壓縮感知關(guān)注的是如何利用信號(hào)本身所具有的稀疏性，從部分觀測(cè)樣本中恢復(fù)原信號(hào)阻荒。
  它可以分為兩個(gè)階段：
  1）感知測(cè)量
  對(duì)原始信號(hào)進(jìn)行處理以獲得稀疏樣本表示挠锥，涉及傅里葉變換、小波變換侨赡、字典學(xué)習(xí)蓖租、稀疏編碼等、
  2）重構(gòu)恢復(fù)
  基于稀疏性從少量觀測(cè)中復(fù)原信號(hào)羊壹，是壓縮感知的精髓蓖宦。

• 壓縮感知的重要理論："限定等距性"(RIP)
  對(duì)一個(gè)nxm(n遠(yuǎn)小于m)矩陣A，若有常數(shù)ε∈(0,1)使得任意向量s和任意A的子矩陣A_k∈R^nxk遵循下式油猫，則稱A滿足k限定等距性

  A滿足k限定等距性
  這時(shí)稠茂，可以通過(guò)下面的優(yōu)化問(wèn)題從y中恢復(fù)稀疏信號(hào)s，再恢復(fù)得到x情妖。
  壓縮感知問(wèn)題就可通過(guò)L₁范數(shù)最小化問(wèn)題求解睬关，例如上式可轉(zhuǎn)為LASSO的等價(jià)形式再通過(guò)PGD求解诱担。

• 壓縮感知有很多應(yīng)用。
  如矩陣補(bǔ)全技術(shù)电爹。該問(wèn)題的形式為：

  其中X為需要恢復(fù)的稀疏信號(hào)蔫仙，rank(X)表示矩陣的秩。 A是已觀測(cè)信號(hào)藐不，Ω是已知元素的下標(biāo)(i,j)的集合匀哄。
  注意到，rank(X)在集合X∈R^m×n:||X||2_F≤1}上的凸包是X的核范數(shù):
  核范數(shù)
  其中σ_j(X)表示X的奇異值雏蛮，即矩陣的核范數(shù)為矩陣的奇異值之和涎嚼。
  我們可以將優(yōu)化目標(biāo)轉(zhuǎn)化為，通過(guò)最小化矩陣核范數(shù)來(lái)求解挑秉，有
  上式是一個(gè)凸優(yōu)化問(wèn)題法梯，可以通過(guò)半正定規(guī)劃SDP求解。
  理論上犀概，當(dāng)滿足一定條件立哑，A的秩為r, n?m，則只需要觀察到O(mrlog2m)個(gè)元素就可以完美恢復(fù)出A。