信號(hào)稀疏表示算法研究畢業(yè)論文

1、信號(hào)稀疏表示算法研究-畢業(yè)論文 學(xué)校代號(hào) 10524 學(xué) 號(hào)12009384分 類 號(hào)密 級(jí) 碩士學(xué)位論文信號(hào)稀 疏表示算 法研究學(xué)位申請(qǐng)人姓名 張政培 養(yǎng) 單 位 電子信 息工程學(xué)院導(dǎo)師姓名及職稱 朱翠濤 教授 學(xué) 科 專 業(yè) 通信與 信息系統(tǒng) 研 究 方 向 信號(hào)稀 疏表示 論文提交日 期 2012 年 月 日 學(xué)校代號(hào):10524 學(xué) 號(hào):12009384 密 級(jí): 中南民族大學(xué)碩士學(xué)位論文信號(hào)稀疏表示算法研究學(xué)位申請(qǐng)人姓名: 張政 導(dǎo)師姓名及職稱: 朱翠濤 教授培養(yǎng)單 位: 電子信息工程學(xué)院 專業(yè)名 稱: 通信與信息系統(tǒng)論文提交日 期 : 2012 年 月日論文答辯日 期 : 2012

2、 年 月 日答辯委員會(huì)主席: RESEARCH ON SIGNAL SPARSE REPRESENTATIONby Zhang ZhengB.E. South-Central University for Nationalities2009 A thesis submitted in partial satisfaction of theRequirements for the degree of Master of Engineering inCommunication and Information System in theGraduate School of South-Central

3、 University for NationalitiesSupervisorProfessor Zhu Cuitao May, 2012 中 南民族 大學(xué) 學(xué) 位論文 原創(chuàng)性 聲明 本人鄭重 聲明: 所 呈交的論 文是本人 在導(dǎo)師的 指導(dǎo)下獨(dú) 立進(jìn)行研 究所取得的研究 成果。 除 了文中特 別加以標(biāo) 注引用的 內(nèi)容外 , 本論文不 包含任何 其他個(gè)人或 集體已經(jīng) 發(fā)表或撰 寫(xiě)的成果 作品 。 對(duì)本 文的研究 做出重要 貢獻(xiàn)的 個(gè)人和集體 , 均已 在 文中以明 確方式標(biāo) 明。 本 人 完全意識(shí) 到本聲明 的法律后 果由本人承 擔(dān)。作者簽名 :日期:年 月 日學(xué) 位論文 版權(quán)使 用授權(quán) 書(shū) 本

4、學(xué)位論 文作者完 全了解學(xué) 校有關(guān)保 留、 使用 學(xué)位論文 的規(guī)定, 同意學(xué)校保留并 向國(guó)家有 關(guān)部門(mén)或 機(jī)構(gòu)送交 論文的復(fù) 印件和電 子版 , 允 許 論文被 查閱和借閱 。 本人授權(quán) 中南民族 大學(xué)可以 將本學(xué)位 論文的全 部或部分 內(nèi)容編 入有關(guān)數(shù)據(jù) 庫(kù)進(jìn)行檢 索, 可 以 采用影印 、 縮印 或 掃描等復(fù) 制手段保 存和匯編 本學(xué)位論文 。 本學(xué)位論 文屬于 1 、保 密 ,在_ 年解 密后 適用本授 權(quán)書(shū)。 2 、不 保密 。 (請(qǐng)?jiān)谝?上相應(yīng)方 框內(nèi)打“ ” )作者簽名 : 日期:年 月 日 導(dǎo)師簽名 : 日期:年 月 日 目 錄 摘 要I ABSTRACT. II 第 1 章 緒

5、 論 1 1.1 研究背景 和意義. 1 1.2 國(guó)內(nèi)外研 究現(xiàn)狀 1 1.3 論文主要 工作. 6 1.4 論文組織 結(jié)構(gòu). 7 第2 章 基于快速互相關(guān)運(yùn)算的信號(hào)稀疏表示算法8 2.1 問(wèn)題描述8 2.2 算法描述. 13 2.3 仿真及分 析 16 2.4 本章小結(jié). 23 第 3 章 基于稀疏框架的信號(hào)稀疏表示24 3.1 問(wèn)題描述. 24 3.2 稀疏框架 的構(gòu)造25 3.3 基于稀疏 框架的信號(hào)稀疏表示29 3.4 仿真及分 析 31 3.5 本章小結(jié) 33 第 4 章 總結(jié)與展望. 34 參考文獻(xiàn). 36 致 謝40 附錄 攻讀碩士學(xué)位期間所發(fā)表的學(xué)術(shù)論文 41 中南民族大學(xué)碩士

6、學(xué)位論文 摘 要 隨著 信 息 技 術(shù) 的 不 斷 發(fā) 展 , 人 們 對(duì) 信 息 量 的 需 求 就 變 得 越 來(lái) 越 大 , 傳 統(tǒng) 信 號(hào)的 分 解 過(guò) 程 中 產(chǎn) 生 大 量 高 復(fù) 雜 度 的 計(jì) 算 問(wèn) 題 就 顯 得 尤 為 突 出 , 制 約 了 信 號(hào) 的 后 繼處 理 和 傳 輸 。 所 以 人 們 一 直 在 尋 求 一 種 簡(jiǎn) 潔 、 高 效 的 信 號(hào) 表 示 方 法 , 信 號(hào) 的 稀 疏表 示 算 法 就 是 其 中 常 用 的 一 種 方 法 。 因 此 , 本 文 對(duì) 信 號(hào) 稀 疏 表 示 問(wèn) 題 中 的 內(nèi) 積 運(yùn)算和分解向量?jī)蓚€(gè)問(wèn)題展開(kāi)了研究。 針對(duì)

7、信 號(hào) 稀 疏 分 解 過(guò) 程 中 存 在 的 大 量 的 內(nèi) 積 計(jì) 算 問(wèn)題, 本文 在 對(duì) 匹 配 追 蹤 算法 基 礎(chǔ) 上 進(jìn) 行 改 進(jìn) 得到 一種 基 于 快 速 互 相 關(guān) 運(yùn) 算 的 信 號(hào) 稀 疏 表 示 算法 。 該 算 法 的主要 思想 是 : 在 迭 代 進(jìn) 行 的 每 一 步 將 信 號(hào) 稀 疏 分 解 過(guò) 程 中 耗 費(fèi) 大 量 計(jì)算 時(shí) 間 和 存儲(chǔ) 空 間 的 內(nèi) 積 計(jì) 算 看 作 一 次 互 相 關(guān) 運(yùn) 算 , 然后 用一種 間 隔 取 點(diǎn) 跳 躍 計(jì) 算 的 快 速 算法 求 出 互 相 關(guān) 運(yùn) 算 的 最 大 值 來(lái) 尋 求 每 一 步 的 最 佳 原

8、子 。 通 過(guò) 軟 件 實(shí) 驗(yàn) 的 仿 真 , 改進(jìn)后的算法能夠較好地重構(gòu)出原始信號(hào)。 將改進(jìn)后的算法與 匹配追蹤算法相比較,改進(jìn) 后的 算法 的 運(yùn) 算 量 有 著 顯 著 的 降 低 , 計(jì) 算 速 度 有 了 較 大 的 提 高 , 并 具 有 良 好的收斂性 。 針 對(duì) 過(guò) 完 備 原 子 庫(kù) 形 成 過(guò) 程 中 需 要 進(jìn) 行 的 大 量 運(yùn) 算 和 存 儲(chǔ) 問(wèn) 題 , 本 文 在 引 入框架理論的基礎(chǔ)上將STF 算法應(yīng)用到框架的形成中, 得到一種稀疏框架,并用稀 疏框 架 代 替 過(guò) 完 備 原 子 庫(kù) 進(jìn) 行 信 號(hào) 的 稀 疏 表 示 。 軟 件 仿 真 結(jié) 果 表 明 , 信

9、 號(hào) 在 稀 疏 框架上 進(jìn)行 稀 疏 分 解 后 重 構(gòu) 出 的 信 號(hào) 能 夠 在 一 定 程 度 上 較 好 地 表 示 原 始 信 號(hào) 的 主 要特點(diǎn) 。 將 信 號(hào) 在 稀 疏 框 架 上 進(jìn) 行 信 號(hào) 的 稀 疏 表 示 與 信 號(hào) 在 過(guò) 完 備 原 子 庫(kù) 上 進(jìn) 行 信號(hào) 的 稀 疏 表示 相 比 較 , 構(gòu) 成 稀 疏 框 架 的 原 子 數(shù) 目 要 遠(yuǎn) 小 于 形 成 過(guò) 完 備 原 子 庫(kù) 的 原子 數(shù) 目 , 極 大 地 簡(jiǎn) 化 了 原 子 庫(kù) 形 成 中 大 量 的 計(jì) 算 和 存 儲(chǔ) , 減 少 了 計(jì) 算 時(shí) 間 , 提 高了計(jì)算效率。 關(guān)鍵 詞: 稀疏表 示

10、 ;快速互 相關(guān)運(yùn)算 ; 內(nèi)積運(yùn)算; 稀疏框架I 信號(hào)稀疏表示算法研究 ABSTRACT With the continuou development of information technology recentlly, the demand on the information becomes much bigger.There is a problem that a large amount of high complexity calculating produced in the traditional signal decomposition process appears ve

11、ry prominent,and restricting signal processing and transmission. The resrarchers have been looking for a simple, efficient method of signal representation, signal sparse representation algorithm is one of the methods which is commonly used. Therefore, this thesis does some reach about problems of th

12、e inner product and vector decomposition in sparse signal representationAiming at the large number of inner product problem in sparse decomposition, a fast computation method for sparse decomposition based on the cross-correlation calculation is proposed in this thesis. The main idea of the algorith

13、m is as fellow:It uses a fast jump point computation method instead of a large number of inner product operation at each step of iterative operation to find out the best atomic. Simulation results show that the improved algorithm can be used to reconstruct the orginal signal well. Compared with the

14、matching pursuit algorithm, the computation of the improved algorithm is significantly reduced, the calculation speed is improved, and has a better convergenceConsidering the issue of a large number of computing and storge in the process of formating Over-complete dictionary,in this paper,STF algori

15、thm is applied to the formation of the framework based on the introduction of the theory of frame to obtain a sparse frame,and the sparerepresentation of signal is processed by sparse frame instead of over-complete dictionary.The results of simulation by software shows that the reconstructed signal

16、which is decomposition by sparse frame can represent the main features of original signal well to some extentpared with the sparerepresentation of signal by over-complete dictionary,the number of atoms of constituting a spare frame is much smaller,and this approach greatly simplifies computing and s

17、torage during the formation of the atom library, and reduces the computational time and improves computing efficiency Keywords: sparse representation; fast cross-correlation calculation; inner product; sparse frameII 中南民族大學(xué)碩士學(xué)位論文 第 1 章 緒 論 1.1 研 究背景 和意義 近年來(lái) , 人 們 對(duì) 信 息 的 獲 取 、 加工 、 傳遞 、 處 理 以 及 應(yīng) 用

18、等 要 求 隨 著 社 會(huì) 的發(fā) 展 和 信 息 技 術(shù) 的 更 新 而 變 得 越 來(lái) 越 高 , 很 多 領(lǐng) 域 也 就 日 益 面 臨 著 對(duì) 各 種 諸 如 音頻 數(shù) 據(jù) , 視 頻 數(shù) 據(jù) , 天 文 數(shù) 據(jù) 等 大 量 數(shù) 據(jù) 的 處 理 和 存 儲(chǔ) 等 問(wèn) 題 。 然 而 用 什 么 方 法實(shí)現(xiàn) 對(duì) 這 些 數(shù) 據(jù) 的 表 達(dá) 更 加地 簡(jiǎn) 單和 靈 活 已 經(jīng) 成 為 一 個(gè) 研 究 熱 點(diǎn) 而 倍受 研 究 者 們的關(guān)注,其中 對(duì)信號(hào)進(jìn)行稀疏表示就是一個(gè)很有效的方法 。 在 對(duì) 信 號(hào) 進(jìn) 行 研 究 和 處 理 時(shí) 首 先 要 對(duì) 信 號(hào) 進(jìn) 行 分 解 或 者 變 換 到

19、 相 應(yīng) 的 域 , 傳統(tǒng) 意 義 上 對(duì) 信號(hào) 進(jìn)行 分解 或者 變換 一般 是 將 信 號(hào) 在 一 組 正 交 基 上 進(jìn)行 分解 , 而 這個(gè) 正 交 基 必 須 是 完 備 的 。 目 前 一 些 比 較 成 熟 的 分 解 方 法 有 傅 立 葉 變 換 、 短 時(shí) 傅 里葉變換、 小波變換、Gabor 變換等。 但是, 這 些 分解方法的不足之處 是對(duì)信號(hào)的表示形式只能 是唯一的, 不可變的。 如果待分解信號(hào)的特征 與正交基不是完全相同,那么信號(hào)分解后 就不能稀疏地表示原信號(hào)。 假設(shè) 一個(gè)長(zhǎng)為N 的待分解的信號(hào) f , 若將這個(gè)信號(hào)在一組正交基上 進(jìn)行正交分解, 那么構(gòu)成這組基的

20、向量數(shù)目應(yīng)為N,而由 于 基 的 正 交 性 , 所 構(gòu) 成 的 信 號(hào) 表 示 不 是 稀 疏 的 。 而 信 號(hào) 的 稀 疏 表 示 則 是 將 信 號(hào)分 解 在 一 組 過(guò) 完 備 非 正 交 基 , 這 樣 做 的 目 的 是 使 表 示 原 信 號(hào) 的 系 數(shù) 向 量 盡 量 含 有較 少 的 非 零 值 , 從而 讓 信 號(hào) 的 表 示 形 式 最 為 簡(jiǎn) 潔 。 為 了 得 到 信 號(hào) 的 稀 疏 表 示 , 則必 須 使 用 非 正 交 基 , 從 而 可 從 實(shí) 質(zhì) 上 降 低 信 號(hào) 處 理 的 復(fù) 雜 度 , 提 高 信 號(hào) 分 解 的 效率。因此 ,尋求新的信號(hào)稀疏表示

21、方法將會(huì)給信號(hào)的處理 帶來(lái)深刻的變革和發(fā)展。 信 號(hào) 的 稀 疏 表 示 是 指 以 有 限 的 非 零 系 數(shù) 來(lái) 線 性 地 表達(dá)原 信號(hào) 的特點(diǎn) , 這 些 非零 的 系 數(shù) 就 構(gòu) 成 了 信 號(hào) 的 稀 疏 表 示 。 稀 疏 表 示 在 信 號(hào) 的 重 構(gòu) 中 引 入 了 誤 差 , 在 保證 非 零 系 數(shù) 的 個(gè) 數(shù) 比 原 始 信 號(hào) 的 采 樣 點(diǎn) 少 的 情 況 下 來(lái) 最 小 化 地 逼 近 誤 差 。 因 為 信號(hào)稀疏表示 表現(xiàn)出的優(yōu)良特性, 文獻(xiàn)1-5 指 出, 信號(hào)的稀疏表示已經(jīng)被應(yīng)用到信號(hào) 分 解 和 處理 等 多 個(gè) 領(lǐng) 域 , 比 如 信 號(hào) 去 噪 、 壓

22、 縮 感 知 、 信 號(hào) 編 碼 、 信 號(hào) 識(shí) 別 、 微弱信號(hào)提取 、時(shí)頻分布等。 目 前 , 由 于 信 號(hào) 稀 疏 表 示 分 解 中 的 計(jì) 算 量 十 分 巨 大 , 難 以 在 實(shí) 際 中 得 到 應(yīng) 用和 推 廣 , 若 信 號(hào) 的 長(zhǎng) 度 較 長(zhǎng) , 在 現(xiàn) 有 的 條 件 下 , 信 號(hào) 稀 疏 表 示 的 計(jì) 算 時(shí) 間 會(huì) 讓 人難以忍受。參考文獻(xiàn)6指出,當(dāng)信號(hào)長(zhǎng)度超過(guò) 1024 的 時(shí)候,信號(hào)稀疏表示的計(jì)算 量 將 相 當(dāng) 巨 大 。 因 此 , 對(duì) 信 號(hào) 稀 疏 表 示 算 法 進(jìn) 行 研 究 , 有 著 極 其 重 要 的 理 論 意義和非常廣泛的應(yīng)用價(jià)值。 1

23、.2 國(guó)內(nèi)外研 究現(xiàn)狀1 信號(hào)稀疏表示算法研究 7對(duì)信號(hào)稀疏表示算法 進(jìn)行研究最早可以回溯到 1982 年,當(dāng)時(shí) Huber 在對(duì)統(tǒng)計(jì) 回 歸 領(lǐng) 域 進(jìn) 行 研 究 時(shí) 首先 提 出 了 一 種 投 影 追 蹤 法 。 發(fā) 展 更 新 到 現(xiàn) 在 , 信 號(hào) 的 稀8疏表示已經(jīng)形成了許多新的 不同的算法。其中最有代表性的是 Mallat 和 Zhang于 1993 年 在對(duì)小波理論進(jìn)行分析的基礎(chǔ)上,提出了一種新的信號(hào) 分解思想:即將信號(hào)分解在 過(guò)完備原子庫(kù)上來(lái)代替信號(hào)在正交基上的分解, 這種分解 思想的提出,對(duì)信號(hào)的稀疏表示有著極其重要的意義 。國(guó)內(nèi)外 對(duì) 信 號(hào) 稀 疏 表 示 的 研 究

24、 至 今 已經(jīng)有 相 當(dāng) 一 部 分 研 究 成 果 。 常 用 的 一 些9信 號(hào) 稀 疏 表 示 算 法 比如 基 追 蹤 算 法 (basis pursuit,BP ) , 匹 配 追 蹤 算 法10(matching pursuit ,MP)以及 MOF 算法method of frames 等等。如何實(shí)現(xiàn)算 法 的 快 速 計(jì) 算 , 降 低 算 法 的 復(fù) 雜 度 , 提 高 運(yùn) 算 效 率 ; 如 何 選 擇 原 子 或 者 向 量 集合 和 選擇 怎 么 樣 的 原 子 構(gòu) 造 合 適 的 過(guò)完備 原 子 庫(kù) 或者 級(jí) 聯(lián) 字 典 ; 怎樣 快速地 去 構(gòu)造 分 解 向 量 和

25、 過(guò) 完 備 原 子 庫(kù) ; 或 者 確定 哪 一 類 信 號(hào) 適 合 用 于 哪 一 類 原 子 庫(kù) 可以 獲得 比 較 好 的 稀 疏 表 示 的 效 果 , 這 些 問(wèn) 題 一 直 是 信號(hào) 稀疏 表示 領(lǐng)域 的 研 究 熱 點(diǎn) 。 總的來(lái)講, 對(duì)信號(hào)稀疏表示的研究主要從以下兩個(gè)方面展開(kāi): (1)信號(hào)稀疏表示的分解算法的研究 11Chen 于 1995 年首先提出了基追蹤算法(basis pursuit,BP ) ,該算法的基本思想是將最小化l 范數(shù)的問(wèn)題轉(zhuǎn)變?yōu)樽钚』痩 范數(shù)的線性規(guī)劃問(wèn)題進(jìn)行求解, 從0 1而 使 得 問(wèn) 題 的 求 解 變 成 了 一 個(gè) 在 沒(méi) 有 約 束 的 的

26、情 況 下 的 優(yōu) 化 問(wèn) 題 。 但 是 基 追 蹤 算法 存 在 一 個(gè) 不 足 之 處 就 在 于 它 具 有 高 復(fù) 雜 度 的 計(jì) 算 , 尤 其 是 在 對(duì) 信 號(hào) 進(jìn) 行 重 構(gòu) 的時(shí)候。 于是, 在小波分析的基礎(chǔ)上,Mallat 和 Zhang 利用平方可積空間中基本函數(shù)的 平 移 、 調(diào) 制 和 尺 度 等 參 數(shù) 的 變 換 構(gòu) 造 出 具 有 時(shí) 頻 特 性 的 過(guò) 完 備 原 子 庫(kù) , 并 且 提12-13出 了 匹 配 追 蹤 方 法matching pursuit,MP 。 匹 配 追 蹤 算 法 的 基 本 思 想 是 從一 個(gè) 給 定 的 過(guò) 完 備 原 子

27、庫(kù) 中 選 擇 最 匹配 原子, 然后 從 信 號(hào) 殘 余 中 減 去 其 在 該 最 匹配 原 子 上 的 投 影 , 獲 得 新 的 信 號(hào) 殘 余, 這 個(gè) 過(guò) 程 不 斷 地 迭 代 進(jìn) 行, 直 到 殘 余 信 號(hào) 的能量小于 設(shè)定的閾值或滿足其他設(shè)定的停止條件為止。Mallat 和 Zhang 提出的算 法 一 般 被 稱 作 基 本 的 匹 配 追 蹤 方 法 。 而 這 種 基 本 的 匹 配 追 蹤 算 法 也 存 在 一 個(gè) 不足之處,就是所選的最佳原子可能是己經(jīng)被選擇的原子。 14 15Pati 及 Davis 等人在對(duì)匹配追蹤算法進(jìn)行分析研究的基礎(chǔ)上提出用 Gram16

28、-17?Schmidt 正 交 化 過(guò) 程 將 投 影 方 向 正 交 化 來(lái) 改 進(jìn) 匹 配 追 蹤 算 法 的 逼 近 效 果 。這 種 正 交 匹 配 追 蹤 算 法 只 需 要 進(jìn) 行 有 限 次 的 迭 代 就 可 以 形 成 收 斂 , 這 與 非 正 交 追蹤 相 比 收 斂 速 度 有 了 一 定 的 提 高 。 在 進(jìn) 行 迭 代 計(jì) 算 的 前 幾 次 , 基 本 的 匹 配 追 蹤 算法在尋求最佳原子時(shí)往往是挑選近似正交的向量, 因此 Gram-Schmidt 正交化幾乎是不必要的, 因?yàn)檫@個(gè) 時(shí)候正交匹配追蹤和非正交匹配追蹤的迭代逼近差異不大。2 中南民族大學(xué)碩士學(xué)位論

29、文 但 隨 著 迭 代 進(jìn) 行 到 一 定 的 次 數(shù) 時(shí) , 正 交 匹 配 追 蹤 算 法 得 到 的 殘 余 信 號(hào) 能 量 將 比 基本的匹配追蹤算法下降得更快。 Natarajan 等 人 在 對(duì) 正 交 匹 配 追 蹤 算 法 進(jìn) 行 研 究 的 基 礎(chǔ) 上 進(jìn) 一 步 進(jìn) 行 改 進(jìn) 提18-20出了順序遞歸匹配追蹤算法 Order Recursive Matching Pursuit ,ORMP 。它相對(duì)于OMP 算法改進(jìn)的地方是ORMP 算法是在每一步進(jìn)行迭代找到內(nèi)積的最大值前進(jìn)行調(diào)整里選擇最佳原子。 21為了進(jìn)一步提高計(jì)算速度,Cotter 等人 通過(guò)對(duì) 匹配追蹤算法、 正

30、交匹配追蹤 算 法 、 順 序 遞 歸 匹 配 追 蹤 算 法 等 三 種 前 向 的 納 入 型 算 法 的 計(jì) 算 復(fù) 雜 性 進(jìn) 行 了 較22為詳細(xì)的比較和分析,在此基礎(chǔ)上提出了一種新的改進(jìn)算法 ?反向刪除算法 。反 向 刪 除 算 法 與 匹 配 追 蹤 算 法 的 不 同 之 處 是 最 初 始 入 選 原 子 從 整 個(gè) 過(guò) 完 備 原 子 庫(kù)開(kāi)始,選擇需要?jiǎng)h掉的原子是利用1 范數(shù)最小準(zhǔn)則來(lái)確定的。 pJaggi 在 文 獻(xiàn)23 中 在 對(duì) 匹 配 追 蹤 的 一 步 優(yōu) 化 這 一 準(zhǔn) 則 進(jìn) 行 分 析 的 基 礎(chǔ) 上 結(jié)合局部相似性 , 一致性和匹配性的概念提出了HRP 算

31、法。HRP 算法的主要思想是要求 形 成 過(guò) 完 備 原 子 庫(kù) 的 原 子 具 有 多 分 辨 的 特 性 , 并 且 在 每 一 步 的 迭 代 過(guò) 程 中 定 義當(dāng) 前 殘 余 信 號(hào) 與 當(dāng) 前 尺 度 原 子 的 相 似 性 需 要 原 子 的 尺 度 更 加 精 細(xì), 因 此 具 有 較 高的分辨率,并且獲得的信號(hào)內(nèi)部結(jié)構(gòu)就會(huì)更加精準(zhǔn), 但這 種算法要求原子庫(kù)具有特殊的結(jié)構(gòu) ,所以也就同時(shí)提高了計(jì)算的復(fù)雜性。 文獻(xiàn)24中 Coifman 等人將余弦包和小波包等幾類原子庫(kù) 進(jìn)行結(jié)合,提出了“ 最 優(yōu) 正 交 基 ” 的 概 念 。 其 主要 思 想 是 從 原 子 庫(kù) 中 的 原 子

32、 所 構(gòu) 成 的 所 有 正 交 基 中選 擇 嫡 最 小 的 正 交 基 來(lái) 進(jìn) 行 信 號(hào) 表 示 , 但 是 在 一 些 特 定 的 情 況 下 , 由 于 其 合 成 觀測(cè)信號(hào)的原子并不能組成正交基,因而這種算法也存在一定的局限性。 文獻(xiàn)25介紹了一種FOCUSS 算法, 這種算法是Rao 和Borodnitshy 等人在對(duì)生 物 醫(yī) 學(xué)成像 的 角 度 求解 時(shí) 利 用 最小l 范數(shù) 的求解 為 基 礎(chǔ)提出 的 。FOCUSS 算法與2帶限信號(hào)重構(gòu)中的迭代濾波思想有非常多的相似之處。 26在內(nèi)積快速運(yùn)算方面,B.Jeon 和S.Oh 經(jīng)過(guò)研究 分析得出在原子搜索過(guò)程中 , 并 不 要

33、 計(jì) 算 全 部 內(nèi) 積 , 可 以 利 用 向 量 的 范 數(shù) 比 較 來(lái) 降 低 運(yùn) 算 的 復(fù) 雜 度 , 實(shí) 驗(yàn)表 明 該 方 法 可 以 減 少 一 部 分 內(nèi) 積 運(yùn) 算 。 但 是 內(nèi) 積 的 優(yōu) 化 通 常 很 難 保 證 算 法 的 收 斂速 度 和 算 法 的 性 能 和 精 度 同 時(shí) 提 高 , 往 往 是 提 高 收 斂 速 度 就 會(huì) 影 響 算 法 的 重 構(gòu) 精度,所以在實(shí)際情況中往往需要根據(jù)不同的應(yīng)用從而選取不同的方法。 為了實(shí)現(xiàn)算法的收斂速度和性能精度兩者之間的折中。E.Cottcr 和D.Rao 等2728提 出 樹(shù) 狀 搜 索 策 略 , 樹(shù) 狀 搜 索

34、 方 法 的 核 心 理 論 是 并 從 次 優(yōu) 原 子 庫(kù) 中 選 擇 原 子來(lái) 代 替 從 一 個(gè) 最 優(yōu) 原 子 庫(kù) 中 選 擇 原 子 , 通 過(guò) 這 一 方 式 來(lái) 平 衡 算 法 的 復(fù) 雜 度 和 重 構(gòu)精度。 文獻(xiàn)29介紹了一種在Schwarz 不等式的基礎(chǔ)上,用簡(jiǎn)單的距離比較來(lái)搜索最3 信號(hào)稀疏表示算法研究 佳原子的方法,這種方法是由 S.Jun 和 B.Jeon 共同設(shè)計(jì)提出的,該算法執(zhí)行的速度快慢取決于獲得內(nèi)積最大值的快慢。而該算法的主要優(yōu)點(diǎn)是能 賈云得在文獻(xiàn)30 中提出在 信息 編碼 中 對(duì)能量?jī)?yōu)先的原子搜索策略進(jìn)行 分 析的 基 礎(chǔ) 上 , 提 出 了 一 種 改 進(jìn)

35、 的 全 面 搜索 算法 和 加 權(quán) 能 量 優(yōu) 先 搜 索 算法 , 這 種 方 法在一定的情況下也可以適當(dāng)?shù)靥岣咚褜ぷ罴言拥乃俣取?最近幾年,Starck 等人經(jīng)過(guò)研究分析提出了另外一種新的用于信號(hào)稀疏表示的分離方法 ? 形態(tài)成分分析法Morpho-logical Component Analysis ,MCA3132。 這 種 方 法 的 基 本 思 想 表 述 如 下 : 假 設(shè) 對(duì) 于 存 在 于 混 合 信 號(hào) 中 任 意 的 一 個(gè) 單獨(dú) 的 源 信 號(hào) , 都 存 在 著 唯 一 的 能 夠 對(duì) 這 個(gè) 單 一 的 信 號(hào) 源 稀 疏 表 示 的 原 子 庫(kù) , 并 且這 個(gè)

36、 原 子 庫(kù) 對(duì) 于 混 合 信 號(hào) 中 的 其 他 源 信 號(hào) 卻 不 能 進(jìn) 行 稀 疏 表 示 , 然 后 再 利 用 追 蹤算 法 來(lái) 搜 尋 最 佳 原 子 , 就 可 以 產(chǎn) 生 一 個(gè) 比 較 理 想 的 信 號(hào) 分 離 效 果 。 在 信 號(hào) 和 圖 像的 稀 疏 表 示 領(lǐng) 域 中 , 形 態(tài) 成 分 分 析 法 是 一 種 比 較 新 的 稀 疏 表 示 方 法 , 由 于 他 對(duì) 混合 信 號(hào) 進(jìn) 行 稀 疏 表 示 有 一 定 的 效 果 , 它 的 提 出 便 得 到 了 很 多 這 一 領(lǐng) 域 研 究 者 的 關(guān)注 , 它 的 應(yīng) 用 范 圍 也 在 不 斷 的 擴(kuò)

37、 展 , 它 的 不 足 之 處 是 由 于 它 的 理 論 面 貌 比 較 新 ,同 時(shí) 在 實(shí) 際 應(yīng) 用 中 有 一 定 的 局 限 性 , 這 種 形 態(tài) 成 分 分 析 的 方 法 還 存 在 著 各 種 問(wèn) 題值得研究者們進(jìn)行進(jìn)一步的分析研究。在形態(tài)成分分析算法的基礎(chǔ)上,Boin 等人將其擴(kuò)展到多通道數(shù)據(jù)的情況中,提 出 了 兩 種 新 的 算 法 ?MMCA MultichannelMorpholgical Component 33-35Analysis 和GMCA Generalized MCA方法 。MMCA 方法實(shí)際上是對(duì)MCA 方法的 一 種 改 進(jìn) , 這 種 改 進(jìn)

38、是 建 立 在 在 多 通 道 數(shù) 據(jù) 的 基 礎(chǔ) 上 。 研 究 者 們 的 實(shí) 驗(yàn) 結(jié) 果 表明 , 較 多 的 數(shù) 據(jù) 能 夠 更 好 地 提 高 信 號(hào) 的 分 離 能 力 , 并 且 對(duì) 算 法 的 性 能 有 一 定 的 改善。 上 面 的 方 法 都 是 在 給 定 的 待 分 解 信 號(hào) 是 確 定 信 號(hào) 的 情 況 下 , 而 在 實(shí) 際 的 應(yīng) 用和 測(cè) 試 的 時(shí) 候 , 待 分 解 信 號(hào) 有 時(shí) 候 并 不 是 確 定 的 信 號(hào) 而 是 隨 機(jī) 信 號(hào) 。 對(duì) 隨 機(jī) 信 號(hào)進(jìn) 行 稀 疏 表 示 采 用 的 基 本 算 法 與 上 面 介 紹 的 對(duì) 于 確 定

39、 信 號(hào) 的 稀 疏 表 示 算 法 基 本 是相 同 的 , 但 是 不 同 之 處 在 于 觀 測(cè) 模 型 發(fā) 生 了 變 化 , 因 此 對(duì) 隨 機(jī) 信 號(hào) 進(jìn) 行 稀 疏 表 示也 就 有 些 不 同 之 處 。 上 面 所 提 到 的 匹 配 追 蹤 算 法 等 一 些 吐 故 納 新 類 型 的 算 法 , 一般采用的是信號(hào)的殘余能量控制 準(zhǔn)則。 (2)原子和過(guò)完備原子庫(kù)的構(gòu)造 信 號(hào) 稀 疏 表 示 算 法 的 另 一 個(gè) 熱 點(diǎn) 領(lǐng) 域 就 是 原 子 和 過(guò) 完 備 原 子 庫(kù) 的 構(gòu) 造 。 研 究者們常用的原子庫(kù)有: 由時(shí)移參數(shù)、頻移參數(shù)確定的雙參數(shù)原子庫(kù), 由時(shí)移參數(shù)、

40、頻 移 和 參 數(shù) 尺 度 因 子 確 定 的 三 參 數(shù) 原 子 庫(kù), 以 及 由 時(shí) 移 參 數(shù) 、 頻 移 參 數(shù) 、 尺 度 因子和調(diào)頻率確定的四參數(shù)原子庫(kù)。這些原子庫(kù)的形成分別對(duì)應(yīng) Gabor 變換、傅里葉變換和 Chirplet 變換。 在原子庫(kù)的設(shè)計(jì)和構(gòu)造方面, 由于信號(hào)稀疏表示算法的性 能 是 由 原 子 庫(kù) 中 的 原 子 與 待 分 解 信 號(hào) 的 相 關(guān) 程 度 來(lái) 決 定 的 , 因 此 , 如 果 設(shè) 計(jì) 出4 中南民族大學(xué)碩士學(xué)位論文 的 過(guò) 完 備 原 子 庫(kù) 與 待 分 解 信 號(hào) 的 相 關(guān) 程 度 越 高 , 便 可 以 用 越 少 的 向 量 來(lái) 逼 近

41、原 信號(hào) , 也 就 是 說(shuō) 就 有 更 快 的 收 斂 速 度 , 這 樣 一 來(lái) 就 能 夠 得 到 較 高 的 表 示 精 度 或 是 付出 較 少 的 計(jì) 算 代 價(jià) 。 因 此 如 何 構(gòu) 建 這 樣 的 過(guò) 完 備 原 子 庫(kù) 或 者 快 速 地 形 成 原 子 , 便成為信號(hào)稀疏表示算法研究的另一個(gè)重要問(wèn)題 研究者們?cè)谶M(jìn)行信號(hào)稀疏表示的研究時(shí)最為常用的就是 Gabor 原子庫(kù)。文獻(xiàn)36介紹了 Gabor 函數(shù)最早是由 R.Neff 等在 1997 年提出將其作為信號(hào)分解的原子庫(kù), 并且在 2002 年對(duì)原子庫(kù)進(jìn)行了改進(jìn), 構(gòu)造二維可分的 Gabor 函數(shù)作為原子庫(kù),明顯地提高了計(jì)

42、算效率。在此基礎(chǔ)上,Chen 和 Qian 通過(guò)研究信號(hào)的 Wigner分布,于 1994 年利用高斯函數(shù)的平移、 調(diào)制和尺度變換構(gòu)造 出相應(yīng)的時(shí)頻詞典原37子庫(kù) ,增加了原子庫(kù)的過(guò)完備性。 Gabor 函數(shù)構(gòu)成的過(guò)完備原子庫(kù)存在一個(gè)不足之處是當(dāng)信號(hào)重構(gòu)時(shí)可能會(huì) 引起震蕩, 于 是 Chou 等引入了量化學(xué)習(xí)法通過(guò)學(xué)習(xí)新的原子庫(kù)來(lái)解決這種重構(gòu)中的震蕩問(wèn)題。 在此基礎(chǔ)上, 文獻(xiàn)38介紹了B.Maeq 和C.Vleeschouwer 于1998 年提出了一種與 Gabor 原子庫(kù)性能相當(dāng)?shù)脑訋?kù)即子帶字典,在一定情況下用這種原子庫(kù)進(jìn)行信號(hào)的稀疏表示有著更小的運(yùn)算量。 文獻(xiàn)39介紹了針對(duì)過(guò)完備原子庫(kù)

43、原子數(shù)目過(guò)大的問(wèn)題,Qiao W 等人提出在逼 近 誤 差 給 出 的 情 況 下 , 可 以 將 稀 疏 分 解 過(guò) 程 中 的 比 特 數(shù) 進(jìn)行 最 小 化 處理 從 而 簡(jiǎn)化原子庫(kù)的大小。 40P.Vandergheynst 等人 對(duì) Gabor 函數(shù)進(jìn)行改進(jìn),加入它的導(dǎo)數(shù)得到新的 原41子庫(kù), 在對(duì)圖像處理時(shí)有較好的效果。 而 L.Granai 等人 則在此基礎(chǔ)上融入高斯函數(shù)得到新的原子庫(kù),在分解運(yùn)算中有著更好的收斂效果。 近年來(lái),隨著信號(hào)的稀疏表示在信號(hào)處理等方面的研究和應(yīng)用不斷擴(kuò)展,國(guó)際 信 號(hào) 處 理 方 面 的 研 究 學(xué) 者 們 對(duì) 這 個(gè) 領(lǐng) 域 也 十 分 關(guān) 注 , 比

44、 如 近 年 來(lái) 國(guó) 際 圖 像 處 理年會(huì)等一些會(huì)議(IEEE ICIP)都對(duì)信號(hào)的稀疏表示方面的研究開(kāi)展了專項(xiàng)討論,一 些 著 名 的 通 信 類 期 刊 也 以 專 對(duì) 此 進(jìn) 行 了 專 題 報(bào) 道 。 而在 國(guó)內(nèi) , 由 于 對(duì) 信 號(hào) 的 稀疏表示研究起步比較晚,研究進(jìn)展 比較有限。2005 年國(guó)家自然科學(xué)基金對(duì)信號(hào)的稀 疏 表 示 這 一 研 究 熱 點(diǎn) 進(jìn) 行 了 兩 項(xiàng) 專 項(xiàng) 資 助, 使 得 研 究 者 們 在 這 方 面 的 研 究 力 度開(kāi) 始 增 加 。 在 自 然 圖 像 的 稀 疏 編 碼 以 及 雷 達(dá) 成 像 處 理 等 方 面 國(guó) 防 科 技 大 學(xué) 等

45、高 校取 得 了 一 定 的 成 果 ; 將 信 號(hào) 的 稀 疏 表 示 用 在 圖 像 壓 縮 和 圖 像 的 去 噪 等 方 面 西 南 交通 大 學(xué) 等 高 校 也 取 得 了 一定 的 進(jìn) 展 ; 在 盲 信 號(hào) 處 理 方 面 廣 州 大 學(xué) 等 高 校 也 有 一 定的 進(jìn) 步 等 等 。 比 較 有 代 表 性 的 應(yīng)用 比 如 王 成 梅 等 人 提 出 的 改 進(jìn) 的 雷 克 子 波 原 子 庫(kù)在 對(duì) 地 震 信 號(hào) 進(jìn) 行 稀 疏 分 解 的 時(shí) 候 有 著 非 常 好 的 效 果 , 但 其 應(yīng) 用 范 圍 有 一 定 的 局限性。 綜 上 所 述 , 由 于 信 號(hào) 的

46、 稀 疏 表 示 具有 能 夠 在 一 定 程 度 上 比 較 好 地 表 達(dá) 原 始 信號(hào) 的 基 本 特 征 , 從 而 對(duì) 信 號(hào) 的 稀 疏 表 示 的 研 究 和 應(yīng) 用 也 就 日 益 廣 泛 。 信 號(hào) 的 稀 疏5 信號(hào)稀疏表示算法研究 表 示 理 論 目前 仍 處 于 發(fā) 展 的 初期 , 對(duì)于 原子 過(guò) 完 備 原 子 庫(kù) 的 快速 形 成 、 提高 分解算法的 效率 等 方 面 還 有 很 多 工 作 要 做 。 信 號(hào) 的 稀 疏 表 示 發(fā) 展 至 今 已 有 一 些 不 同 的算法, 綜 合 考 慮 算 法 在 計(jì) 算 復(fù) 雜 度 和 逼 近 效 果 方 面 的 兩

47、 個(gè) 重 要 因 素 , 以 貪 婪 算 法為 核 心 的 匹 配 追 蹤 算法 相比 其 他 的 算法 有 著 明 顯 的 優(yōu) 越 性 , 也 是 目 前 研 究 者 最 常采用的算法。 采 用匹配追蹤算法 來(lái)對(duì) 信號(hào) 進(jìn)行 稀疏表示, 在一定程度上 能夠得到比較好的應(yīng) 用 。 但 這 種 方 法 也 存 在 一 些 缺 點(diǎn): 最 主 要 的 問(wèn) 題 是 計(jì) 算 量 過(guò) 于 龐 大 。 在 對(duì) 信 號(hào)的 每 一 步 分 解 尋 求 最 佳 原 子 的 過(guò) 程 中 , 都 需 要 進(jìn) 行 大 量 的 內(nèi) 積 運(yùn) 算 , 從 而 決 定 應(yīng)該 選 出 原 子 庫(kù) 的 哪 一 個(gè) 向 量 來(lái) 做

48、分 解 , 分 解 的 每 一 步 都 要 計(jì) 算 殘 余 信 號(hào) 在 過(guò) 完 備原 子 庫(kù) 中 每 一 個(gè) 原 子 上 的 投 影 ; 在 過(guò) 完 備 原 子 庫(kù) 的 形 成 過(guò) 程 中 , 由 于 過(guò) 完 備 原 子庫(kù) 的 原 子 數(shù) 目 相 當(dāng) 巨 大 , 這 就 造 成 了 其 分 解 過(guò) 程 中 的 計(jì) 算 量 十 分 巨 大 , 高 復(fù) 雜 度的計(jì)算 代價(jià) 成 為 了 信 號(hào) 的 稀 疏 表示 在 實(shí) 際 的 研 究 應(yīng) 用 中 難 以 展 開(kāi) 的 瓶 頸 。 因 此 ,本文 針 對(duì) 如 何 簡(jiǎn) 化 信 號(hào) 稀 疏 表 示 中 的 內(nèi) 積 運(yùn) 算 , 尋 求 更 佳 的 向 量 組

49、 合 來(lái) 代 替 過(guò) 完備原子庫(kù) 這兩個(gè)方面的問(wèn)題進(jìn)行研究。 1.3 論文主要 工作本 文 主 要 對(duì) 壓 縮 感 知 理 論 中 的 信 號(hào) 稀 疏 表 示 算 法 進(jìn) 行 了 探 討 與 研 究 , 對(duì)目前信 號(hào) 稀 疏 表 示 算 法 及 常 用 的 過(guò) 完 備 原 子 庫(kù) 進(jìn) 行 了 系 統(tǒng) 的 分 析 、 歸 納 和 總 結(jié) 。 在 對(duì)信 號(hào) 匹 配 追 蹤 算 法 進(jìn) 行 深 入 研 究 的 基 礎(chǔ) 上 , 針 對(duì) 現(xiàn) 有 匹 配 追 蹤 算 法 中 存 在 的 高 復(fù)雜 度 計(jì) 算 的 問(wèn) 題 , 提 出 了 一 種 基 于 快 速 互 相 關(guān) 運(yùn) 算 的 信 號(hào) 稀 疏 表 示

50、 算 法 ; 針 對(duì) 原子 和 過(guò) 完 備 原 子 庫(kù) 形 成 的 問(wèn) 題 , 提 出 了 用 稀 疏 框 架 代 替 過(guò) 完 備 原 子 庫(kù) 作 為 分 解 函數(shù)進(jìn)行信 號(hào)的稀疏分解。主要的研究?jī)?nèi)容如下: (1 ) 對(duì)信號(hào)的匹配追蹤算法進(jìn)行了深入分析與研究, 仿真分析了信號(hào)稀疏表示與重構(gòu)。 (2 ) 針對(duì)匹配追蹤算法的計(jì)算量過(guò)于龐大問(wèn)題, 提出了一種 基于快速互相關(guān)運(yùn) 算 的 匹 配 追 蹤 算 法 。 該 算 法 的 主 要 思 想 是 : 將 稀 疏 表 示 過(guò) 程 中 最 消 耗 時(shí) 間 的 N次 內(nèi) 積 運(yùn) 算 轉(zhuǎn) 化 成 一 次 互 相 關(guān) 運(yùn) 算 , 由 于 互 相 關(guān) 的 結(jié)

51、果 存 在 峰 值 特 性 , 對(duì) 互 相 關(guān)結(jié)果 進(jìn) 行 多 個(gè) 點(diǎn) 的 跳 躍 計(jì) 算 , 首先 找 出 最 大 值 存 在 的 一 個(gè) 比 較 小 的 區(qū) 間 , 然 后 再比較 小 區(qū) 間 內(nèi) 各 點(diǎn) 的 互 相 關(guān) 運(yùn) 算 結(jié) 果 , 找 出 最 大 值 點(diǎn) 位 置 和 最 大 值 , 這 樣 一 來(lái) ,就極大地 減少了計(jì)算的點(diǎn)數(shù),加快了計(jì)算的速度。 (3 ) 針對(duì)原子和過(guò)完備原子庫(kù)形成這一問(wèn)題, 并結(jié)合 不同的信號(hào)特點(diǎn)在不同的原子庫(kù)上進(jìn)行信號(hào)的稀疏分解并比較仿真結(jié)果,引入框架理論,通過(guò) STF 方法形 成 一 種 稀 疏 框 架 , 并 用 其 代 替 過(guò) 完 備 原 子 庫(kù) 進(jìn)

52、行 信 號(hào) 的 稀 疏 分 解 , 由 于 框 架 的稀 疏 性 , 極 大 地 降 低 了 計(jì) 算 復(fù) 雜 度 。 實(shí) 驗(yàn) 證 明 , 在 一 定 情 況 下 選 取 稀 疏 框 架 代 替過(guò)完備原子庫(kù),能夠在保證算法精度的情況下降低運(yùn)算量提高計(jì)算速度。6 中南民族大學(xué)碩士學(xué)位論文 1.4 論文 組織 結(jié)構(gòu) 本論文總共分為四章,組織結(jié)構(gòu)如下: 第 1 章 介紹論文的研究背景、 國(guó)內(nèi)外研究現(xiàn)狀、 闡述課題的研究目的和意義。對(duì)信號(hào)稀疏表示算法進(jìn)行了詳細(xì)的研究現(xiàn) 狀分析。 并介紹了本 論 文的主要工作及組織結(jié)構(gòu)。第 2 章 描述信號(hào)稀疏表示算法,并在其基礎(chǔ)上,針對(duì)信號(hào)稀疏分解過(guò)程中存在的大量的內(nèi)積運(yùn)算問(wèn)題,提